Application

Nous allons maintenant appliquer les algorithmes génétiques à la résolution du problème du voyageur de commerce.

Un algorithme génétique se caractérise par différents points :

• une instance du problème
• un espace de recherche
• le codage des points de l'espace de recherche (par un chromosome)
• les opérateurs génétiques classiques
  • sélection
  • hybridation
  • mutation
  • diversification

Nous allons préciser pour chaqu'un de ces points les options choisies pour l'implantation du problème du voyageur de commerce.

Une instance du problème

Une instance du PVC est un graphe complet de $n$ sommets dont les arêtes sont pondérées par un coût strictement positif. L'instance sera alors implantée comme une matrice $M$ $n\times n$ dont les coefficients sont strictements positifs sauf sur la première diagonale où ils sont tous nuls. $M$ est appelé matrice de coût. Ainsi la distance entre le sommet j et le sommet i est $M_{ij}$. On n'a pas forcemment $M_{ij}=M_{ji}$ et on n'a pas non plus l'inégalité triangulaire dans le cas général. Cependant, pour l'implantation de l'algorithme, nous avons choisi le cas d'une distance euclidienne sur $n$ points du plan, pour construire la matrice de coût.

L'espace de recherche

C'est l'ensemble $\mathcal{S}_n$ des permutations de $\{1,2, \cdots,n\}$. Un point de l'espace de recherche est une permutation.

Codage des points de l'espace de recherche

Chaque points de l'espace de recherche est une permutation de $\{1,2, \cdots,n\}$. Une première idée est de coder alors chaque permutation par une chaîne de bits. Par exemple, pour $n=8$ :

$$011\;111\;000\;100\;001\;010\;101\;110$$

représente la permutation :

$$3\;7\;0\;4\;1\;2\;5\;6.$$

Cependant après quelques hybridations, on risque d'avoir un chromosome qui ressemble à :

$$011\;111\;011\;100\;000\;000\;111$$

à savoir

$$3\;7\;3\;4\;0\;0\;7$$

ce qui ne représente plus une permutation. Il suffit alors de répartir les chromosomes comme une chaîne d'entiers et d'adapter les opérateurs génétiques à ce codage. Notons que les sommets sont répartis à partir de 0.

La fonction d'évaluation

C'est ici le coût total d'une permutation. A savoir pour une permutation $\sigma$ :

$$f(\sigma)=\sum_{i=0}^{n-2}M_{\sigma (i)\sigma (i+1)}+M_{\sigma (n)\sigma (0)}.$$

Le dernier terme de la somme permettant de revenir au sommet initial. C'est cette fonction là que nous cherchons à minimiser.

Opérateurs génétiques classiques

Sélection

Nous utilisons ici la méthode de sélection par roulette ($cf.$ 2.4.1). On calcule d'abord la valeur moyenne de la fonction d'évaluation dans la population :

$$\overline{f}=\frac{1}{m}\sum_{i=0}^{m-1}f(P_i),$$

où $P_i$ est l'individu i de la population et $m$ la taille de la population. La place d'un individu $P_i$ dans la roulette est proportionnel à $\frac{\overline{f}}{f(P_i)}$. On sélectionne alors $m/2$ individus pour la reproduction. Il y a aussi la possibilité d'avoir une politique d'«élitisme». C'est à dire qu'à chaque étape de sélection le meilleur chromosome est automatiquement sélectionné.

Hybridation

Une fois la population intermédiaire sélectionné, on complète la population avec les enfants de la population intermédiaire. Deux chromosomes se combinant donnent naissance à deux autres chromosomes de la façon suivante :

1. Un point d'hybridation est déterminé aléatoirement (entre 0 et la longueur du chromosome).
2. On copie dans le premier fils les indices du premier père jusqu'au point d'hybridation.
3. On complète ensuite par les indices du deuxième chromosome père ne se trouvant pas déjà dans le fils dans l'ordre donné par le deuxième parent.
4. On réitère 2) et 3) avec le même point d'hybridation, mais en inversant le rôle des deux parents.

Par exemple, pour $n=8$, on a les deux chromosomes suivants qui s'hybrident :

$$C1=(1\;0\;5\;3\;2\;7\;4\;6),$$

$$C2=(7\;1\;3\;5\;6\;2\;0\;4).$$

On hybride à partir du rang 5. On arrive alors aux deux nouveaux chromosomes :

$$C1=(1\;0\;5\;3\;2\;\bf {7\;6\;4}),$$

$$C2=(7\;1\;3\;5\;6\;\bf {0\;2\;4}).$$

Mutation

Une des méthodes les plus simples pour muter un chromosome est d'inverser les positions de deux villes. Par exemple :

$$C3=(0\;1\;\textbf{3}\;6\;4\;\textbf{7}\;5\;2)$$

devient

$$C3'=(0\;1\;\textbf{7}\;6\;4\;\textbf{3}\;5\;2).$$

Cependant, cette mutation change beaucoup la fonction d'adaptation. Si on veut inverser deux sommets non-contigües i et j, la fonction d'adaptation change :

$$\begin{array}{rccl} \delta_{f} &= & & d(i-1,j)-d(i-1,j)+d(... ... & &+ & d(j-1,i)-d(j-1,j)+d(i,j+1)-d(j,j+1).\\ \end{array}$$

Une solution qui perturbe moins l'individu consiste à inverser tous les sommets entre $i$ et $j$. Par exemple,

$$C4=(0\;1\;3\;6\;4\;7\;5\;2)$$

devient

$$C4'=(0\;1\;\textbf{7}\;\textbf{4}\;\textbf{6}\;\textbf{3}\;5\;2).$$

La différence de la fonction d'évaluation ne dépend plus que de quatre termes :

$$\delta_{f}=d(i-1,j)-d(i-1,i)+d(j+1,i)-d(j,j+1).$$

En fait, au lieu d'inverser deux sommets, cette méthode efface deux arêtes et les remplace par deux autres.

Diversification

La diversification consiste à mieux répartir les individus de la population dans l'espace de recherche. Ici, on fait un décalage vers la gauche de longueur aléatoire sur tout les individus nouvellement créés. Cela n'affecte pas leur valeur d'adaptation et cela permet une meilleur diversité génétique.

Autre implantation possible : séquences de Bean

Introduction

On a déjà vu que l'AGC utilisé pour le PVC fabrique des individus qui n'était pas des permutations. Le but des séquences de Bean et de conserver les méthodes de l'AGC en changeant le codage des individus pour résoudre le PVC.

Principes

Pour générer une séquence de Bean, on associe à chaque ville de l'instance du problème un nombre aléatoire. Par exemple, soit l'ensemble des villes $\{ A, B, C, D \}$ :

$$\begin{array}{lccccc} \mbox{s\'equence de villes} &: &A &B &C &D\\ \mbox{nb al\'eatoires} &: &3 &6 &2 &4.\\ \end{array}$$

On obtient ainsi une séquence de couples (nb aléatoire, ville). Ici, pour l'exemple :

$$(A,3) (B,6) (C,2) (D,4).$$

Cette séquence s'appelle séquence de Bean.

Pour obtenir l'ordre de séquencement des villes, il faut ensuite trier dans l'ordre croissant cette séquence de Bean par rapport au nombre associé à chaque ville.

$$(A,3) (B,6) (C,2) (D,4)$$

devient alors

$$(C,2) (A,3) (D,4) (B,6).$$

Elle code le chemin passant respectivement par $C, A, D, B$ pour revenir en C (cycle hamiltonien).

L'application des opérateurs d'hybridation est simple à réaliser, il suffira de procéder à une hybridation sur les nombres associés : soient les séquences de Bean

$$s1=(A,2)(B,6)(C,1)(D,4)$$

codant la séquence $(C,A,D,B)$ et

$$s2=(A,5)(B,7)(C,3)(D,0)$$

codant la séquence $(D,C,A,B)$, une hybridation à 1 point entre ces deux chromosomes donnerait :

$$\begin{array}{lcccccc} \mbox{chromosome 1} &: &2 &6 &\vert... ...\\ \mbox{chromosome 2} &: &5 &7 &\vert &3 &0\\ \end{array}$$

$$\begin{array}{lccccc} \mbox{fils 1} &: &2 &6 &3 &0\\ \mbox{fils 2} &: &5 &7 &1 &4.\\ \end{array}$$

Le fils 1 représente la séquence de Bean

$$s3=(A,2)(B,6)(C,3)(D,0).$$

Il code donc la séquence $(D,A,C,B)$.
Le fils 2 représente la séquence de Bean

$$s4=(A,5)(B,7)(C,1)(D,4).$$

Il code donc la séquence $(C,D,A,B)$.

Critiques de la méthode

Cette méthode de représentation d'une solution potentielle permet de lever l'ambiguité pour les opérateurs d'hybridation. Néanmoins, elle ne donne pas pour autant de meilleurs résultats (pas de gain d'itérations sur le nombre de générations par rapport à la méthode implantée). De plus, il est difficile de contrôler ses effets lors d'une hybridation, empéchant de ce fait une optimisation locale de l'algorithme.