Generational Genetic Algorithm.
Appelé aussi Simple Genetic Algorithm, il utilise une sélection stochastique pour sélectionner N parents (population p'). Certains parents peuvent donc être sélectionnés plusieurs fois et d'autres aucune fois en fonction de leur capacité de survie. Ces N parents générent ensuite N enfants (population p'') par application des opérateurs génétiques de croisement et de mutation. Enfin ces N enfants remplacent purement et simplement les N parents pour créer la génération suivante.
Steady-State Genetic Algorithm.
Cet algorithme utilise la technique du chevauchement (overlapping). A partir d'une population initiale p0 de taille N, une sélection stochastique est utilisée pour sélectionner M (M<N) individus (population p0'). Ces M parents générent ensuite M enfants par application des opérateurs génétiques de croisement et de mutation (population p0''). Nous obtenons ainsi une population de N+M individus (p0+ p0''). Pour passer à la génération suivante de taille N, une heuristique de remplacement est appliquée :
ALEATOIRE : les M individus de p0'' remplacent M parmi N de p0 aléatoirement.
LES_PLUS_MAUVAIS : les N meilleurs des N+M survivent.
TOURNOI_INVERSE : les M individus de p0'' remplacent M mauvais parmi N de p0 par tournoi inversé.
Remarque: Le taux de croisement n'a aucune importance dans cet algorithme. En effet le passage de la population p0' à p0'' s'effectue par croisement 2 à 2 des individus (si M est impair le dernier individus est créé par mutation).
Par contre le taux de mutation conserve toute son importance, après le croisement les enfants obtenus peuvent subir une mutation.
Algorithme incrémental
Cet algorithme consiste à remplacer au fur à mesure les parents par les enfants produits. Ainsi l'algorithme se déroule de la manière suivante :
- phase d'initialisation avec ou sans augment merge
- pendant un certain nombre d'itérations (correspondant à un certain nombre de croisements) faire :
1) population triée par ordre décroissant
2) sélectionner un parent par une méthode favorisant les meilleurs
3) sélectionner un autre parent de manière uniforme
4) réaliser le croisement des 2 parents et conserver un enfant au hasard
5) l'enfant a une chance de muter
6) si c'est un clone rien ne se passe
7)sinon l'enfant écrase un individu situé sous la médiane de la population au hasard
La sélection par rang trie d'abord la population par fitness. Ensuite, chaque chromosome se voit associé un rang en fonction de sa position. Ainsi le plus mauvais chromosome aura le rang 1 etc… jusqu'au meilleur de rang N. Ensuite le principe est le même que pour la roulette mais les proportions sont liées au rang. Contrairement à la roulette, tout les individus gardent une bonne chance d'être sélectionné (ce qui évite les convergences prématurées), en contre partie, la convergence est plus lente car les bons individus se distinguent moins bien du lot.
Le plus utilisé, la roulette consiste à donner une plus grande chance aux individus de bonnes fitness qu'aux individus peu adaptés. La part de la roulette de chaque individu est égale à sa fitness divisé par la fitness de toute la population. Un individu peut être choisi plusieurs fois.
La sélection par tournois consiste à choisir un individu parmi un sous ensemble de la population en les faisant participer à un tournoi. La probabilité de victoire augmente avec la fitness de l'individu. Le sous ensemble peut être de taille quelconque même si des petits tournois semblent " meilleurs " car sinon il y a un risque de sélectionner trop de fois le même parent.
Pour commencer et cela quelque soit l'algorithme, pour deux parents P1 et P2 de longueur t, on tire au sort deux position p et q avec p <= q. Pour construire l'enfant E1, la portion de P1 entre p et q inclus est copiées dans E1, aux mêmes positions. Ensuite P2 est balayé de 0 à t-1 et les éléments non déjà présents dans l'enfant E1 remplissent de gauche à droite les positions libres de l'enfant. La construction de l'enfant E2 est identique, en permutant les rôles de P1 et P2.
Dans OX, la seule différence avec LOX, est que le balayage de P2 et le rangement dans l'enfant s'effectuent de façon circulaire, en commençant à l'index q+1 (modulo t).
X1 peut être vu comme un cas particulier de LOX avec p = 1.
Swap tire au sort deux positions p et q entre 1 et t inclus, permute les gènes situés à ces positions, et inverse la voirie composant chacun d'eux avec une probabilité de 0.5 si celle-si sont des " petits axes ".
Move tire au sort deux positions p et q du chromosome, avec 0 <= p <= (t-1), -1 <= q <= (t-1), p != q et p != (q+1). Le gène g au rang p est déplacé après celui de rang q (q = -1 signifie une insertion en tête et q = t-1 une insertion en queue ). Puis, si la voirie qui compose le gène g est un " petit axe " (pour les grands axes la voirie et son inverse ne sont pas ramassables en une seule fois), on inverse avec une probabilité de 0.5 le sens de traitement.
RL est une recherche locale consistant à améliorer les enfants avant de les injecter dans la population.
Cette recherche locale opère sur l'ensemble des tournées d'une solution complète, sans modifier le découpage en tournées. Nous avons donc dût découper l'ensemble des gènes d'un chromosome en tournées spécifiquement pour cette méthode de mutation. Ainsi chaque itération teste les déplacements de voiries (dans la même tournée ou vers une autre tournée) et les permutations de deux voiries (de la même tournée ou de tournées différentes). Pour chaque voirie u déplacée ou permutée, on teste deux cas : la voirie est réinsérée en conservant son sens de collecte ou bien en inversant ce sens. La première transformation améliorante détectée est effectuée. Le processus est répété jusqu'à ce qu'on ne trouve plus d'amélioration où si le nombre d'améliorations autorisées est atteint.
Option permettant d'activer ou de désactiver le déplacement de gènes dans la recherche locale.
Option permettant d'activer ou de désactiver l'échange de gènes dans la recherche locale.
Nombre limite d'améliorations effectuées par la recherche locale.
L'élitisme consiste tout simplement à recopier tel quel dans la génération suivante un ou des individus qui sont les meilleurs de leur génération. C'est un bon moyen de conserver les meilleures solutions même s'il ne faut pas garder trop d'individus (sinon la convergence est trop rapide).
Cette option permet d'accepeter ou non la présence de clones dans la population. Un clone étant un individu illustrant la même solution qu'un individu déjà présent.
Le taux de mutation intervient au niveau de la population, il représente le pourcentage de chance de mutation d'un individu.
Le taux de croisement intervient aussi au niveau de la population, il représente le pourcentage de chance de croisement de deux individus.
La méthode de création par défaut d'un chromosome est simple. En partant de la liste des voiries à ramasser on choisit au hasard une voirie non encore traitée, ainsi que son sens si la voirie est un " petit axe ". On réitère ce processus jusqu'à que toutes les voiries soient traitées.
Les résultats obtenus par la création par défaut des chromosomes étant relativement mauvais, nous avons intégré la possibilité de choisir l'utilisation d'une autre heuristique plus adaptée à notre problème. Cette dernière est une version, remaniée pour notre solution, de la très bonne heuristique Augment-Merge (Golden et al., 1983). Cette heuristique n'est appliquée qu'à un seul individu de la population, ceci n'altère donc pas la diversité de la population mais nous assure que l'individu ainsi créé représente une solution plutôt bonne du problème.
Utilisable seulement avec l'algorithme SSGA, ce nombre indique le nombre d'individus peuvant etre remplacés dans la population initiale d'une itération à l'autre.
Définit le nombre d'individus de la population initiale.
Le nombre d'itérations est la seule condition d'arrêt, elle détermine le nombre de populations générées par l'algorithme pour se rapprocher de la solution optimale. Il est utile de noter que l'algorithme ne s'arrête que si le nombre d'itérations est atteint et ceci même si la meilleure solution est déjà trouvée.
Temps utilisé pour trouver la meilleure solution.
Numéro de l'itération courante.
Note de la meilleure solution.
Note moyenne de l'ensemble des individus.
Indication de la charge d'occupation du processeur par les différentes étapes de l'algorithme.