Algorithme génétique [les méthodes de résolution du problème du voyageur de commerce]

Algorithme génétique

Les algorithmes génétiques s'inspirent de la théorie de l'évolution, initiée par Charles Darwin au XIXeme siècle.

Dans cette théorie, une population d'individus évolue grâce au mécanisme de la reproduction sexuée. Les individus les plus adaptés à leur milieu se reproduisent plus que les autres, favorisant les caractères les plus adaptés. Ainsi une girafe avec un cou plus long que les autres aura accès à plus de nourriture, et aura donc plus de chances de survivre et de se reproduire. Ses descendants auront un cou plus long, et en moyenne la population de girafe aura un cou plus long.

Au niveau de l'ADN, la recombinaison de l'ADN des deux parents (lors de la reproduction) permet de générer différentes combinaisons de gènes. Il y a des chances qu'en recombinant l'ADN de deux parents bien adaptés, l'individu généré soit encore mieux adapté.

Exemple :

Parent 1	Parent 2
Cou : long	Cou : court
Pattes : courtes	Pattes : longues
adaptation : moyenne	adaptation : moyenne

peut donner à la génération suivante :

Fils 1	Fils 2	Fils 3
Cou : court	Cou : court	Cou : long
Pattes : courtes	Pattes : longues	Pattes : longues
adaptation : mauvaise	adaptation : moyenne	adaptation : bonne

Adaptation à l'algorithmique et au PVC

L'idée a été proposée la premiere fois par John Holland au début des années 1970, qu'il a d'ailleurs utilisée pour le problème du voyageur de commerce.

Il s'agit de résoudre un problème d'optimisation d'une combinaison de paramètres dépendants les uns des autres. Ces paramètres peuvent prendre plusieurs valeurs prédéfinies, de la même manière que des gènes peuvent prendre plusieurs expressions (pattes longues ou pattes courtes, par exemple). Une solution particulière au problème (une solution approchée) est représentée par l'ensemble des valeurs prises pour chaque paramètre, qui constitue en quelque sorte l'ADN de cette solution.

Quant à l'adaptation à l'environnement, elle est représentée par une évaluation chiffrée indiquant la pertinence de la solution.
Par exemple pour le PVC : un individu est un trajet, son évaluation est la longueur totale de ce trajet, un gène est la ville où l'on passe à une certaine position dans le parcours, et l'ADN est la liste des villes dans l'ordre du parcours.

Parmi un ensemble de solutions approchées (la population), on sélectionne alors deux bonnes solutions et on les recombine pour en produire une nouvelle.
D'autre part, on élimine les solutions les moins adaptées.
En répétant ce processus, l'adaptation de la population augmente, et donc on converge vers la solution du problème.

Il s'agit bien sûr d'une adaptation informatique, il ne faut pas chercher une similitude plus poussée avec les "lois de la nature". Entre autres parce dans la nature, le cerveau joue un grand rôle, et que l'environnement est changeant. Donc une solution moyenne mais adaptable à plusieurs environnements est plus intéressante qu'une solution très adaptée à un environnement particulier.

De manière plus formelle, voici un algorithme génétique de base :

Pour chaque Individu dans Groupe
        Initialiser Individu
FinPour
Pour nombre_d'itérations
        Parent A = Sélection_d'un_Individu (Groupe)
        Parent B = Sélection_d'un_Individu (Groupe)
        Fils =  Recombinaison (Parent A, Parent B)
        Si hasard > pourcentage Alors
                Appliquer_une_mutation_à Fils
        FinSi
        Optimiser Fils  // Optionnel
        Evaluer Fils
        Si Fils est_accepté_dans Groupe Alors
                Réinsérer Fils dans Groupe
        FinSi
FinPour

Il existe énomément de variantes et de paramétrages qui affectent grandement les résultats.

Voyons maintenant plus en détail chaque phase :

Sélection :

Comment choisir les parents pour la reproduction ? Il existe plusieurs possibilités :

au hasard
préférer les individus avec une meilleur évaluation (stratégie élitiste)
toujours choisir le meilleur individu comme premier parent et un autre individu au hasard comme deuxième parent (variante de la stratégie élitiste)
sélectionner les deux parents selon un critère de proximité dans la liste des individus

Il semble qu'une stratégie élitiste soit plus efficace au démarrage de l'algorithme, puis au fur et à mesure que l'on se rapproche de l'optimum, chaque individu a à peu près autant de chances d'être précurseur d'une meilleure solution.

Pour tspgen 0.32 j'ai utilisé une stratégie élitiste inspirée de la "roulette wheel" : On considère la sélection d'un individu comme le lancement d'une bille sur une roulette. Chaque individu possède plusieurs cases dans la roulette. Les meilleurs individus possèdent plus de cases et sont donc sélectionnés plus souvent.

Pour cela les individus sont classés selon leur adaptation (premier individu = longueur de trajet la plus courte). Je crée un tableau d'entiers, qui comporte autant d'éléments que d'individus dans le groupe. Chaque entier du tableau prend une valeur croissante entre 1 et RAND_MAX. L'intervalle entre les chiffres du tableau est plus grand au début et plus petit à la fin. Comme la fonction rand () renvoie un entier au hasard entre 1 et RAND_MAX il suffit de tirer un chiffre au hasard et de le comparer au chiffre du tableau pour connaitre l'index de l'individu sélectionné.
Pour que chaque individu ait la même probabilité d'être séléctionné, il suffirait de positionner les chiffres du tableau à un intervalle de RAND_MAX / Nb_individus.
Voir le code source des fonctions Group::InitSelectionArray () et Group::GetRandSelectionArrayIndex ()

Recombinaison :

C'est la fonction principale de l'algorithme génétique. La recombinaison (ou reproduction ou crossover) consiste à créer un individu à partir de deux individus parents.
Il existe presque autant d'algorithmes de recombinaison que d'implémentations d'algorithmes génétiques...

Un exemple de crossover réussi (à comparer avec l'exemple des girafes) :

Parent 1	Parent 2
Fils 1

Je vais décrire ici un des plus simples, le crossover à 1 point (c'est loin d'être le plus efficace mais il a le mérite d'être assez simple à coder).

Il s'agit de recopier dans le fils une partie du parent 1, jusqu'à une "cassure", puis ensuite la partie correspondante du parent 2. La difficulté réside dans le fait que les villes ne doivent pas être répétées. Si la ville a déjà été prise, on passe à la ville suivante dans l'ordre du parent 2.

Exemple :

Parent 1 :

1-2-3-4-5-6-7-8-9-10

Parent 2:

2-7-1-4-10-6-9-8-3-5

Fils :

1-2-3-4-10-6-9-8-5-7

On détermine aléatoirement la cassure : ici entre le 4^eme et le 5^eme élément.
Avant la cassure (pour les 4 premiers éléments du fils) : On recopie exactement chaque élément du premier parent dans le fils.
Après la cassure (pour les 6 derniers éléments du fils) : On recopie chaque éléments du deuxième parent dans le fils, sauf s'il s'y trouve déjà, dans ce cas on passe à l'élément suivant (c'est le cas de la ville 7)

Une variante de ce crossover est le crossover à 2 points (un peu plus efficace) : on introduit une deuxième cassure et le parent 2 n'est recopié qu'entre ces deux cassures.

Ces deux algorithmes ont un défaut pour le PVC, c'est qu'ils ne respectent pas toujours la règle suivante :
- si une arête (chemin entre 2 villes) se trouve dans les deux trajets parents, il faut qu'elle se trouve dans le trajet fils

Ce problème a été en partie résolu par le crossover OX (entres autres) [que je présenterai ici prochainement].

Les crossovers peuvent aussi utiliser des informations heuristiques, comme le crossover KFP dans tspgen 0.32 (qui utilise les villes les plus proches). Cet algo a été décrit par Karoly F. Pal dans un papier de 1993 (je n'en ai qu'un exemplaire papier, il n'est pas dispo sur le net à ma connaissance).

Dans les sources de tspgen voir les fonctions Individual::CrossoverKFP, Individual::CrossoverPMX, Individual::CrossoverOX, Individual::CrossoverCX, Individual::CrossoverAA

Mutation :

Il s'agit d'une modification (plus ou moins aléatoire) du code génétique d'un individu. Cela permet de sortir des minimums locaux, grâce à une perturbation, un peu à la manière du recuit simulé.

Exemples de mutations pour le PVC :

Echange de deux villes
Renversement de parcours entre deux villes (assez efficace en particulier s'il est appliqué parfois deux ou trois fois à la suite)
Remplacement d'une liaison entre deux villes par une liaison entre la première ville et la ville la plus proche
"Double bridge" ou 4-change non séquentiel : le parcours : 0 ... i i+1 ... j j+1 ... k k+1 ... l l+1 ... est modifié en : 0...i k+1 ... l j+1 ... k i+1 ... j l+1 ...
i et k ainsi que j et l peuvent être proche pour plus d'efficacité (assez efficace)

Dans les sources de tspgen voir la fonction Individual::Mutate et suivantes

Optimisation :

Cette phase est à mon avis très importante et pas assez mise en valeur dans les différentes docs sur les algos génétiques.
L'optimisation est l'utilisation d'une méthode de recherche locale (par exemple 2-opt ou 3-opt), appliquée à chaque individu lors de sa création. Chaque individu est un minimum local, on ne risque donc pas de passer à côté d'une bonne solution.

Il faut savoir que la plupart du temps de calcul est passée dans ces optimisations locales (au moins dans tspgen, mais je pense que c'est la même chose dans tous les algorithmes génétiques ou les autres métaheuristiques comme le recuit simulé ou la méthode de la colonie de fourmis). Sans cette optimisation, le résultat serait assez médiocre. Mais on ne peut pas dire que c'est l'optimisation qui fait tout le travail ! Le grand avantage des algorthmes génétiques est qu'ils fonctionnent quand même EN PLUS de l'optimisation locale. L'algorithme génétique est donc responsable de la partie la plus difficile du calcul.

Pour tspgen 0.32 j'utilise pour l'optimisation l'algo 2-opt.
Dans les sources voir les fonctions Individual::Optimize2ChangeCompl ()

Réinsertion :

Comment réinsérer le fils dans le groupe ? Les solutions sont :

Eliminer le moins bon du groupe
Eliminer l'individu qui ressemble le plus au nouvel individu
Remplacer un des deux parents
La nouvelle génération remplace l'ancienne génération (sauf le meilleur individu de l'ancienne génération)

Ce qui est certain est qu'il ne faut pas supprimer le meilleur individu du groupe, sous peine de voir l'adaptation globale diminuer !

Paramétrages divers :

Quelle est la taille d'un groupe (nombre d'individus) ?
Faut il utiliser une heuristique pour initialiser la population (exemple : meilleurs voisins + 2opt)
Le paramétrage doit il changer en fonction de la phase de calcul (par exemple, plus de mutations à la fin...)
Certaines fonctions sont elles plus efficaces avec un nombre de villes faibles ou élévé ?
Dans le crossover ou les optimisations, faut il préférer la rapidité (afin de faire plus d'itérations) ou des opérateurs plus ophistiqués mais plus longs ?

Les méthodes de résolution du problème du voyageur de commerce