4.3 Algorithme mémétique
Un algorithme génétique (Genetic Algorithm
ou GA) est une technique de recherche utilisée pour trouver des
solutions approchées à différents types de
problèmes d'optimisation (voir par exemple (Winter et al.,
1995; Vose, 1998; Man et al., 1999) pour plus de détails). Les
algorithmes génétiques font partie des métaheuristiques et
sont une classe particulière des algorithmes évolutionnaires, qui
utilisent des techniques inspirées de la biologie telles que la
mutation, les croisements ou la sélection naturelle. Les algorithmes
génétiques maintiennent un nombre important de solutions tout au
long de la résolution du problème. L'ensemble des solutions
mémorisées est appelé la population. Chaque
solution est appelé un individu ou un chromosome. Un
individu représente donc une version encodée d'une solution.
À chaque itération d'un algorithme génétique, une
nouvelle population est générée en utilisant un certain
nombre d'opérateurs : la reproduction, la sélection et la
mutation.
Les algorithmes génétiques couplés avec
des techniques de recherche locale sont classés comme des algorithmes
mémétiques, tels qu'ils ont été
présentés par Moscato et Norman (1992) et (Moscato et Cotta,
2005) (voir par exemple (Hart et al., 2005; Sörensen et Sevaux,
2006) pour plus de détails sur des les algorithmes
mémétiques). Dans cette section, nous présentons un
algorithme mémétique. Nous insistons en particulier sur
l'opérateur de croisement, qui est notre principale contribution. Afin
d'évaluer plus facilement l'impact de cet opérateur, nous avons
volontairement développé une implémentation standard pour
le reste de l'algorithme mémétique.
4.3.1 Composants basiques de l'algorithme Individus
Chaque individu (une solution du problème) est
représenté par une liste ordonnée de groupes, dans
laquelle le premier et le dernier groupe sont identiques. À partir de
cette liste, on peut déterminer un tour des villes optimal,
correspondant à cet ordre de visite des groupes. Le coût de
l'individu est le coût du tour des villes. Ce coût est obtenu en
utilisant l'algorithme ST (Shortest Tour) développé par
Renaud et Boctor (1998a).
Le principe de l'algorithme Shortest Tour est le suivant. Une
succession de groupes définit une séquence d'ensembles de villes,
dans laquelle les villes d'un groupe ne peuvent être atteintes que par
des villes appartenant à un groupe précédent. En
représentant les villes par des noeuds, nous obtenons un graphe
orienté acyclique. L'ensemble des chemins du graphe ainsi construit et
dont le sommet de départ est confondu avec le sommet d'arrivée,
correspond alors à l'ensemble des solutions respectant l'ordre
défini par la séquence de groupes. La meilleure de ces solutions
est le plus court chemin du graphe. Le calcul d'un plus court chemin dans un
graphe acyclique peut être effectué en un temps polynomial
à l'aide d'une simple récurrence. Dans le cas du GTSP, le plus
court chemin doit être calculé pour chaque ville du groupe de
départ en ajoutant la contrainte que le chemin commence et finit par la
ville considérée. Le tour des villes optimal est le meilleur tour
parmi ces solutions. Cette procédure n'est pas très
coûteuse en temps de calcul, ce qui nous permet de l'appeler
régulièrement (la complexité de cet algorithme est en
O(n3/m3), voir (Renaud et
Boctor, 1998a) pour plus de détails).
Population initiale
La population initiale contient N individus. Les
individus sont générés à l'aide de listes de
groupes construites aléatoirement. L'algorithme ST est appliqué
afin de déterminer le tour des villes optimal, ainsi que le coût
de chaque individu. Afin de limiter les symétries, le groupe de
départ (et d'arrivée) est fixé pour tous les individus.
Dans le but de réduire le temps de calcul requis par la procédure
ST, le groupe qui contient le moins de villes est choisi pour être le
premier et le dernier groupe de la liste pour chacun des individus.
Renouvellement de la population
À chaque génération, deux individus sont
choisis aléatoirement par sélection proportionnelle à
l'adaptation (Roulette Wheel selection) et appairés à
l'aide de l'opérateur de croisement. Ces deux parents donnent naissance
à deux enfants. Cette opération est répétée
k fois. Les 2 * k nouveaux individus sont alors
ajoutés à la population et seuls les N meilleurs
individus sont gardés. Ainsi, la taille de la population reste constante
dans le temps.
Mutation
Une procédure de mutation est appliquée afin de
diversifier la population. Chaque individu de la population a une
probabilité u d'être sélectionné pour la
procédure de mutation. Dans nos expérimentations, nous avons
fixé u = 0.05 (ce pourcentage arbitraire a été
choisi car il est utilisé dans plusieurs articles, par exemple dans
(Silberholz et Golden, 2007)). La mutation consiste à échanger la
place de deux groupes choisis aléatoirement puis d'appliquer
l'algorithme Shortest Tour pour calculer le tour optimal de villes, ainsi que
le nouveau coût de l'individu.
Critère d'arrêt
L'algorithme s'arrête lorsque N1
générations ont été calculées ou
lorsqu'aucune amélioration n'a eu lieu durant N2
générations.
Algorithme Mémétique
La figure 5 présente une vue synthétique de notre
algorithme.
Algorithme 5 : Algorithme de l'algorithme
mémétique
1 Initialisation: Construire
aléatoirement une population initiale de N individus;
2 tant que le nombre d'itérations est
plus petit que N1 et qu'il y a eu une amélioration depuis moins
de N2 itérations faire
3 pour chaque i = 0 à k
faire
4
5
6
7
8
9
Choisir deux individus aléatoirement;
Construire deux nouveaux individus par croisement;
Appliquer de la recherche locale sur les deux individus;
Ajouter les 2 * k nouveaux individus à la
population; Garder les N meilleurs individus dans la population;
Appliquer une mutation avec une probabilité u
à chaque individu de la population;
| 
