Equipe ORCHIDS

ALGORITHMES GENETIQUES
Page principale
PRINCIPES DE BASE ET FONCTIONNEMENT

On utilise des algorithmes génétiques pour explorer un espace de solutions lorsqu'il n'est pas possible d'en extraire la meilleure solution par des algorithmes (exacts) ayant une durée raisonnable.

Un algorithme génétique manipule des populations de solutions dont il évalue la valeur et retient en permanence la meilleure solution trouvée (en jaune sur la figure).

Globalement, le fonctionnement est simple :

1) On génère une population initiale de solutions de manière aléatoire ou avec des méthodes heuristiques qui essaient de fabriquer de bonnes solutions.

2) On évalue les solutions de la population en cours et on retient la meilleure de toutes les solutions construites.

3) On passe de la population en cours à une nouvelle population en utilisant des opérateurs génétiques, généralement de "croisement" et/ou de "mutation". Certains individus étant conservés par simple recopie.

4) On retourne en 2) tant qu'un critère d'arrêt n'est pas vérifié, par exemple un nombre maximal de populations générées ou une durée maximale d'exécution.

Pour le mettre en application, il faut :

- choisir la manière de coder les individus de la population (par exemple des gènes à 0 ou à 1 indiquent la présence ou l'absence de certains éléments dans la solution ou, comme dans les applications considérées ici, la solution est décrite par une séquence de n objets et cette séquence est représentée par la liste des n numéros des objets dans l'ordre où on les classe, il s'agit de ce que l'on appelle une permutation, par exemple, l'ordre 1, 4, 10, 9, 8, 5, 6, 3, 2, 7

- définir des opérateurs génétiques qui à partir d'un ou plusieurs individus d'une population donnée fabrique de nouveaux individus, on distingue l'opérateur binaire de croisement qui marie les gènes de deux individus pour fabriquer deux enfants et l'opérateur unaire de mutation qui modifie légèrement un individu.

- choisir des paramètres qui précisent le fonctionnement de l'algorithme génétique tels que nombre maximal de populations à fabriquer, nombre d'individus dans chaque population, pourcentage de croisements et de mutations ...

Pour les problèmes dont les inconnues sont des permutations (ordre de visite d'une liste d'objets), vous trouverez des exemples de croisements et des exemples de mutations en cliquant sur les boutons suivants.