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