Comparaison de l'optimisation par essaim
particulaire avec d'autres
heuristiques évolutionnaires utilisant
des opérateurs implicites
Louis Gacogne
LIP6, Université Paris VI (case 169), Place Jussieu, 75252
Paris
et
CEA bureau B741, 8 rue du Capitaine Scott, 75015 Paris
Louis.Gacogne@lip6.fr
Nous présentons une comparaison
sur un certain nombre de fonctions tests, entre différentes
heuristiques évolutionnaires, qui ont en commun de ne pas
prendre aléatoirement des opérateurs
génétiques au hasard, mais d'appliquer des règles
de transition fixes entre générations
- le "particle swarm optimization", dont le
principe est que chaque individu soit animé d'une "vitesse" qui
va déterminer sa "position" suivante. Les règles de
transition prennent en compte le meilleur individu, ainsi que le
meilleur de chaque groupe d'individus, groupes déterminés
par une distance ou bien arbitrairement au départ .
- le "space partition algorithm" (SPA), qui
réalise une partition de l'espace en raffinant les
régions où la fonction à optimiser est la
meilleure et en fusionnant les autres. Les individus de la population
sont alors des blocs de tailles changeantes dont l'évaluation
est néanmoins moyennée aléatoirement en leur sein.
- le "macroevolutionary algorithm"
(MGA), inspiré par la dynamique des espèces,
heuristique dont le principe est de relier les individus par des poids
mesurant leurs influences mutuelles. Il y a, au cours des
générations, extinction ou bien application d'une sorte
de crossover continu entre individus.
- l' "évolution
différentielle" (DE), où les individus donnent naissance
à de nouveaux points de l'espace de recherche grâce
à une sorte de tétra-crossover.
- le "self organizing migration algorithm"
(SOMA), dont l'idée principale est de déterminer des
groupes à l'intérieur desquels chaque individu
réalise des "sauts" vers le meilleur du groupe et en
s'arrêtant sur la meilleure position rencontrée. Les
classes sont modifiées à chaque génération.
Enfin, nous comparons ces heuristiques avec
quelques algorithmes évolutionnaires classiques, notamment celui
SSGA, dont le renouvellement des générations est
régulier.
Mots clés : optimisation,
algorithmes évolutionnaires, opérateurs
génétiques, optimisation par essaims de particules