Optimisation à l'aide du réseau Hopfield
L'optimisation consiste à rendre quelque chose comme la conception, la situation, les ressources et le système aussi efficace que possible. En utilisant une ressemblance entre la fonction de coût et la fonction d'énergie, nous pouvons utiliser des neurones hautement interconnectés pour résoudre des problèmes d'optimisation. Un tel type de réseau de neurones est le réseau de Hopfield, qui consiste en une seule couche contenant un ou plusieurs neurones récurrents entièrement connectés. Cela peut être utilisé pour l'optimisation.
Points à retenir lors de l'utilisation du réseau Hopfield pour l'optimisation -
La fonction énergétique doit être au minimum du réseau.
Il trouvera une solution satisfaisante plutôt que de sélectionner un des modèles stockés.
La qualité de la solution trouvée par le réseau Hopfield dépend fortement de l'état initial du réseau.
Problème de vendeur itinérant
Trouver l'itinéraire le plus court parcouru par le vendeur est l'un des problèmes de calcul, qui peut être optimisé en utilisant le réseau neuronal de Hopfield.
Concept de base du TSP
Le problème du voyageur de commerce (TSP) est un problème d'optimisation classique dans lequel un vendeur doit voyager nvilles, qui sont connectées les unes aux autres, en gardant au minimum le coût ainsi que la distance parcourue. Par exemple, le vendeur doit parcourir un ensemble de 4 villes A, B, C, D et l’objectif est de trouver le circuit circulaire le plus court, ABC – D, afin de minimiser le coût, qui comprend également le coût du voyage depuis la dernière ville D jusqu'à la première ville A.
![](https://assets.edu.lat/artificial_neural_network/images/travelling_salesman_problem.jpg)
Représentation matricielle
En fait, chaque visite du TSP n-city peut être exprimée comme n × n matrice dont ith la ligne décrit le ithl'emplacement de la ville. Cette matrice,M, pour 4 villes A, B, C, D peuvent être exprimées comme suit -
$$ M = \ begin {bmatrix} A: & 1 & 0 & 0 & 0 \\ B: & 0 & 1 & 0 & 0 \\ C: & 0 & 0 & 1 & 0 \\ D: & 0 & 0 & 0 & 1 \ end {bmatrix} $$
Solution par Hopfield Network
En considérant la solution de ce TSP par le réseau Hopfield, chaque nœud du réseau correspond à un élément de la matrice.
Calcul de la fonction énergétique
Pour être la solution optimisée, la fonction énergétique doit être minimale. Sur la base des contraintes suivantes, nous pouvons calculer la fonction énergétique comme suit -
Contrainte-I
La première contrainte, sur la base de laquelle nous allons calculer la fonction énergétique, est qu'un élément doit être égal à 1 dans chaque ligne de matrice M et les autres éléments de chaque ligne doivent être égaux à 0parce que chaque ville ne peut apparaître qu'à une seule position dans la tournée TSP. Cette contrainte peut s'écrire mathématiquement comme suit -
$$ \ displaystyle \ sum \ limits_ {j = 1} ^ n M_ {x, j} \: = \: 1 \: for \: x \: \ in \: \ lbrace1, ..., n \ rbrace $ $
Maintenant, la fonction d'énergie à minimiser, basée sur la contrainte ci-dessus, contiendra un terme proportionnel à -
$$ \ displaystyle \ sum \ limits_ {x = 1} ^ n \ left (\ begin {array} {c} 1 \: - \: \ displaystyle \ sum \ limits_ {j = 1} ^ n M_ {x, j } \ end {array} \ right) ^ 2 $$
Contrainte-II
Comme nous le savons, dans TSP, une ville peut apparaître à n'importe quelle position de la tournée, donc dans chaque colonne de la matrice M, un élément doit être égal à 1 et les autres éléments doivent être égaux à 0. Cette contrainte peut s'écrire mathématiquement comme suit -
$$ \ displaystyle \ sum \ limits_ {x = 1} ^ n M_ {x, j} \: = \: 1 \: for \: j \: \ in \: \ lbrace1, ..., n \ rbrace $ $
Maintenant, la fonction d'énergie à minimiser, basée sur la contrainte ci-dessus, contiendra un terme proportionnel à -
$$ \ displaystyle \ sum \ limits_ {j = 1} ^ n \ left (\ begin {array} {c} 1 \: - \: \ displaystyle \ sum \ limits_ {x = 1} ^ n M_ {x, j } \ end {array} \ right) ^ 2 $$
Calcul de la fonction de coût
Supposons une matrice carrée de (n × n) désigné par C désigne la matrice de coût de TSP pour n villes où n > 0. Voici quelques paramètres lors du calcul de la fonction de coût -
Cx, y - L'élément de matrice de coût désigne le coût du voyage depuis la ville x à y.
La contiguïté des éléments de A et B peut être représentée par la relation suivante -
$$ M_ {x, i} \: = \: 1 \: \: et \: \: M_ {y, i \ pm 1} \: = \: 1 $$
Comme nous le savons, dans Matrix, la valeur de sortie de chaque nœud peut être 0 ou 1, donc pour chaque paire de villes A, B, nous pouvons ajouter les termes suivants à la fonction d'énergie -
$$ \ displaystyle \ sum \ limits_ {i = 1} ^ n C_ {x, y} M_ {x, i} (M_ {y, i + 1} \: + \: M_ {y, i-1}) $$
Sur la base de la fonction de coût et de la valeur de contrainte ci-dessus, la fonction d'énergie finale E peut être donné comme suit -
$$ E \: = \: \ frac {1} {2} \ displaystyle \ sum \ limits_ {i = 1} ^ n \ displaystyle \ sum \ limits_ {x} \ displaystyle \ sum \ limits_ {y \ neq x} C_ {x, y} M_ {x, i} (M_ {y, i + 1} \: + \: M_ {y, i-1}) \: + $$
$$ \: \ begin {bmatrix} \ gamma_ {1} \ displaystyle \ sum \ limits_ {x} \ left (\ begin {array} {c} 1 \: - \: \ displaystyle \ sum \ limits_ {i} M_ {x, i} \ end {array} \ right) ^ 2 \: + \: \ gamma_ {2} \ displaystyle \ sum \ limits_ {i} \ left (\ begin {array} {c} 1 \: - \ : \ displaystyle \ sum \ limits_ {x} M_ {x, i} \ end {array} \ right) ^ 2 \ end {bmatrix} $$
Ici, γ1 et γ2 sont deux constantes de pesée.