Algorithmes génétiques

Lecture conseillée au préalable : Théorie de l'évolution.

Les algorithmes génétiques appartiennent à une grande famille d'algorithme appellés métaheuristiques, ces méthodes sont adaptables à un grand nombre de problèmes jugés complexes et fournissent des solutions satisfaisantes mais non exactes.

Nous allons approcher ces algorithmes à travers la problématique du voyageur de commerce. Le problème du voyageur de commerce est très simple :

• Un voyageur de commerce part d'une ville ;
• Il doit effectuer sa tournée dans dix villes différentes en passant une fois dans chaque ville ;
• Le temps de trajet entre chaque ville est connue ;
• Ce voyageur cherche à trouver quel enchainement de ville est le plus court tout en revenant à la fin du parcours à sa ville de départ.

Petit exemple : tout le monde comprend que si l'on part et revient à Paris, le trajet Paris, Lille, Lyon, Marseille, Paris est plus court que Paris, Marseille, Lille, Lyon, Paris. Ce qui est évident pour quatre ville se complexifie très rapidement avec le nombre de villes. S'il y a n villes-étapes, le nombre de possibilités de trajets est n! . Sachant que la factorielle de 3 (noté 3!) est 3! = 3 * 2 * 1 = 6, je laisse calculer 10! ceux qui ont encore des doutes quand à son ordre de grandeur.

Les algorithmes génétiques se proposent de trouver une solution acceptable à un problème. Sur notre problème le terme solution fait simplement référence à un trajet possible répondant au problème mais n'étant pas forcément le meilleur.

Ainsi pour se rapprocher de Darwin, chaque solution est considérée comme un individu (on utilise juste ce terme pour faire le lien, mais il n'y a pas d'élément particulier à comprendre). Comme dans la théorie de l'évolution, une phase importante de l'algorithme est la sélection : on sélectionne les individus qui vont pouvoir se reproduire. L'important de cette phase est que statistiquement les individus sélectionnés répondent mieux au problème que la moyenne, un moyen simple (mais qui pose certains problèmes) est de prendre tout simplement les meilleurs.

Notons ici que l'évaluation de l'efficacité d'un individu est l'un des premiers problèmes rencontrés lors de l'utilisation d'algorithmes génétiques.

Ainsi donc considérons que notre voyageur parte de A et doive passer par cinq villes B, C, D, E et F. Le groupe de solution de départ (population) est simplement constituée de parcours aléatoires (une centaine pour l'exemple), par exemple :
A-D-E-B-C-F-A
A-D-F-C-B-E-A
A-B-C-D-E-F-A
A-F-E-B-C-D-A
...

La sélection des cinquante meilleurs chemins de la population de départ sera donc constituée d'individus similaires. Remarquons seulement ici qu'un chemin sera dit "meilleur" qu'un autre en fonction de sa longueur; en clair : il est meilleur s'il est plus court.

La seconde étape du processus sera la réutilisation des individus sélectionnés pour former une nouvelle génération. Traditionnellement on appelle ça la reproduction, mais c'est pas assez technique, on parlera donc de croisement.

C'est là le second problème des algorithmes génétiques : trouver une bidouille quelconque pour recombiner les individus. Dans le cas de trajets c'est facile, si on a sélectionné les deux trajets suivant :
A-F-E-B-C-D-A
A-E-D-C-B-F-A

On décide aléatoirement d'un point de coupure, disons le troisième élément :
A-F-E-B-C-D-A devient A-F-E et B-C-D-A
A-E-D-C-B-F-A devient A-E-D et C-B-F-A

On croise deux à deux les quatre bouts pour former deux nouveaux individus, on rectifie ensuite en rajoutant les villes manquantes là où il y a des villes redondantes :
A-F-E et C-B-F-A donneront A-F-E-C-B-D-A
A-E-D et B-C-D-A donneront A-E-D-B-C-F-A

Ici rien ne garantis que les deux individus soient meilleurs que leurs parents, mais c'est une hypothèse de la théorie de l'évolution. L'efficacité des algorithmes génétiques lui donne corps.

Ici on est bien capable de partir d'une "population" de solution et d'obtenir une "population fille" à partir des individus les plus performants. La pratique montre l'efficacité des algorithmes génétiques.

Je m'arrêterais là pour les explications, les plus intéressés doivent savoir que les deux éléments donnés ci-dessus suffisent. Mais l'esprit avisé envisagera de rajouter une phase de mutation pour parcourir un plus grand espace des possibles, et les problèmes de convergence trop rapide impliquent ainsi d'affiner un peu la méthode de sélection. Ne prendre que les meilleurs n'amène à rien de bon sur le long terme.

Illustration prise ici