CHAPITRE 2
du premier individu et les mélange avec des
gènes du deuxième individu de sorte à créer un tout
nouvel individu différent des deux autres. Cette opération est
répétée plusieurs fois jusqu'à ce que le nombre de
nouveaux individus créés (appelées enfants) soit
égal au nombre des individus déjà présent dans la
population (parents).
Bien que la taille de la population augmente après
l'exécution de cette opération, elle sera réduite à
sa taille originale lors de la prochaine itération après avoir
appliqué l'opéra-teur de sélection.
Il est important à noter que l'opérateur de
croisement n'est pas forcément appliqué systématiquement
à tous les individus. Un facteur de probabilité est
utilisé pour contrôler le taux de croisement dans la population.
Ce facteur est souvent choisi dans un intervalle entre 0.7 à 1.0.
Mutation
Cette opération apporte des changements mineurs aux
individus en modifiant aléatoirement la valeur de certains gènes.
Ceci permet à l'algorithme d'examiner une plus grande
variété de solutions potentielles et l'empêche de rester
coincé dans des optimums locaux. Cependant, il ne faut pas que cette
opération soit effectuée trop souvent pour éviter de
tomber dans une recherche aléatoire. Elle est donc appliquée avec
une probabilité relativement faible (souvent inférieure à
5%).
Le diagramme présenté dans la figure 2.11 montre
les étapes de l'algorithme génétique.
2.6.2 L'optimisation par Essaim de Particules (PSO)
Cette méthode a été publiée en
1995 [58]. Elle se base sur le comportement social des essaims observés
dans la nature.
Dans cet algorithme, une population de particules
représentant des solutions potentielles est générée
aléatoirement. Ces particules se déplacent dans l'espace de
recherche en modifiant leurs emplacements actuels en fonction de leurs
emplacements précédents et de ceux de leurs voisins.
L'équation qui gouverne le déplacement d'une
particule met à jour à chaque itération deux informations
: la vitesse de la particule et sa position (voir les équations 2.3 et
2.4). Ces deux informations sont calculées en fonction de 3
composants:
-- Composant social : attire la particule à se diriger
vers la position de la meilleure solution connue par la population
(dénotée g*).
-- Composant cognitif: attire la particule à se diriger
vers la position de la meilleure solution qu'elle a visité dans le
passé (dénotée x.*).
-- Composant inertiel : pousse la particule à garder sa
direction courante.
L'utilisateur attribue au début de l'algorithme un
facteur de pondération pour chaque composant pour contrôler le
degré d'influence de ces composants sur le mouvement des
67
particules. Plus le facteur du composant social est grand,
plus l'algorithme s'oriente vers la diversification de la population. Plus le
facteur du composant cognitif est grand, l'algo-rithme s'oriente vers une
stratégie d'intensification.
Vitesse : vt+1
i = wvt i +
c1r1(pt_best
i xt i) +
c2r2(gt_bestxt
i) (2.3)
Position: xt+1
i = xt i + vt+1
(2.4)
i
Où :
-- w est le poids d'inertie
-- r1 et r2 sont des vecteurs
aléatoires distribués uniformément dans l'interval
[0,1]
-- c1 et c2 sont des hyperparamètres
appelés facteurs d'accélération, ou facteur cognitif et
facteur social respectivement.
2.6.3 L'otimisation par Colonie de Fourmies
(ACO)
Cet algorithme a été introduit par Colorni et
Dorigo en 1991 [24]. Il simule la façon dont les fourmis naviguent pour
trouver la source de nourriture la plus proche de leur nid.
Étant donné que les fourmis dans le monde
réel dégagent des odeurs (ou phéromones) volatiles
lorsqu'elles trouvent une source de nourriture, et que les autres fourmis ont
tendance à suivre les chemins qui contiennent ces phéromones. Les
itinéraires les plus courts entre la source de nourriture et le nid
seront favorisés puisque la quantité de phéromones non
volatilisée sera plus grande en raison de la courte distance. Ces
chemins optimaux seront donc de plus en plus empruntés par les fourmis.
Ce qui résulte en un effet de renforcement.
De la même manière, les agents de l'ACO utilisent
des phéromones virtuelles pour marquer les meilleures solutions
trouvées. Au début de l'algorithme, les fourmis se
déplacent de manière aléatoire tout en mettant à
jour une matrice de phéromones. Cette matrice contient la
quantité de phéromones pour chaque solution trouvée, qui
est incrémentée avec une valeur proportionnelle à la
qualité de la solution.
Cette valeur décroit avec le temps suivant
l'équation 2.5 afin de simuler l'effet d'évapo-ration:
ôi ?- (1 - ñ)ôi
(2.5)
Où ñ est une constante
d'évaporation à définir par l'utilisateur et
ôi est la quantité de phéromones de la solution
i
| 
