CHAPITRE II. METHODES D'OPTIMISATION
solutions simultanément. C'est le calcul de la fonction
de performance qui est le plus pénalisant, et on optimise
généralement l'algorithme de façon à éviter
d'évaluer trop souvent cette fonction. Le grand avantage des algorithmes
génétiques est qu'ils parviennent à trouver de bonnes
solutions sur des problèmes très complexes, où un grand
nombre de paramètres entrent en jeu, et où l'on a besoin
d'obtenir de bonnes solutions en quelques itérations.
Les algorithmes de colonies de fourmis offrent beaucoup de
souplesse, et il est possible de les adapter à tous les grands
problèmes combinatoires classiques. En effet, ils ont été
appliqués avec succès sur les problèmes d'affectation, de
routage et de planification, et ils ont été la source
d'inspiration de nouvelles méta-heuristiques.
La méthode GRASP est relativement simple à
programmer, et permet d'améliorer les résultats d'une simple
recherche locale. Elle permet également de faire intervenir une
heuristique spécialisée. Elle ne nécessite que peu de
paramétrage : la taille de la liste, qui permet d'équi-librer la
quantité d'adaptabilité (l'heuristique) et le facteur
stochastique. Elle est en revanche moins performante que d'autres
méta-heuristiques, du fait de son absence de mémoire : comme avec
une recherche locale simple, rien ne garantit que l'algorithme ne fait pas des
cycles et retomber sur les mêmes minima locaux.
La méthode de l'évolution différentielle
utilise les mêmes Opérateurs que les algorithmes
génétiques. La différence principale en construisant de
meilleures solutions est que les algorithmes génétiques se
fondent sur le croisement tandis que le DE se fonde sur l'opération de
mutation, cette opération principale est basée sur la
différence des paires de solutions aléatoirement
prélevées dans la population.
II.3 Les algorithmes évolutionnaires
Les algorithmes évolutionnaires sont des algorithmes
d'optimisation stochastiques itératifs inspirés de la
théorie darwinienne de l'évolution naturelle. Selon Darwin, les
individus les plus compétant survivent à la sélection
naturelle et se reproduisent d'une génération à une autre.
Par analogie, l'évolution artificielle se traduit par un processus
itératif de recherche de l'optimum dans un espace de recherche.
II.3.1 Terminologie spécifique aux EAs
Une solution possible à un problème est un point
de l'espace de recherche, ce point est nommé individu,
l'ensemble des individus constituent une population. La fonction
objectif à optimiser est appelée fonction de performance
(fitness en anglais), le calcul de cette fonction est appelé
évaluation. Une Génération Correspond
à une population en une seule itération. Le processus
itératif de recherche des individus optimaux est appelé une
évolution. Les Opérateurs de variation sont
utilisés pour générer de nouveaux individus, il existe
deux opérateurs: le croisement, qui consiste à
échanger des composants entre deux individus et la mutation qui
consiste à modifier un ou plusieurs composants d'un individu. Le choix
des individus est appelé sélection, elle est
basée généralement sur la valeur de fitness. La
formation d'une nouvelle génération à partir des parents
et des enfants consiste à les remplacer par ceux qui sont
sélectionnés.
16
| 
