CHAPITRE II. METHODES D'OPTIMISATION
Algorithm : TABOU_SEARCH
1 : générer une solution initiale(s)
2 : poser T ? Ø et s* ? s
3 : repeat
4 : Choisir s'qui minimise f dans
VT(s)
5 : if f(s') <
f(s*) then
6 : s* ? s'
7 : s ? s'
8 : until (critère d'arrêt)
II.2.4 Les algorithmes génétiques
Les algorithmes génétiques (Genetic
Algorithms) sont des algorithmes évolutionnaires les plus connues
et les plus utilisés, ils sont présentés par Holland en
1975 et Goldberg en 1989. La particularité de ces algorithmes est qu'ils
font évoluer des populations d'individus codés
généralement par des chaînes de bits en utilisant des
opérateurs d'évolution génétique (la mutation et le
croisement).
Le principe est de partir d'une population de p
individus, on sélectionne ceux qui sont capable à se
reproduire. On croise ensuite ces derniers, de façon à obtenir
une population d'enfants, dont on peut faire muter aléatoirement
certains gènes. La performance des enfants est évaluée,
grâce à la fonction fitness, et on sélectionne, dans la
population totale résultante, les individus autorisés à
survivre, de telle manière que l'on puisse repartir d'une nouvelle
population de p individus.
Algorithm : BASIC_GENETIC_ALGORITHM
1 : generer(P0)
2 : repeat
3 : selection pour la reproduction
4 : croisement
5 : mutation
6 : selection pour le remplacement
7 : until (critère d'arrêt)
II.2.5 Les algorithmes de colonies de fourmis
Les algorithmes des colonies de fourmis (Ants System)
sont inspirés de la nature des insectes (les fourmis), ils ont
été proposés par Doringo au début des années
90. Leur principe repose sur le comportement particulier des fourmis qui, font
évoluer une population d'agents, selon un modèle stochastique :
lorsqu'elles quittent leur fourmilière pour explorer leur environnement
à la recherche de nourriture, finissent par élaborer des chemins
qui s'avèrent fréquemment être les plus courts pour aller
de la fourmilière à une source de nourriture intéressante.
Chaque fourmi laisse en effet derrière elle une traînée de
phéromone à l'attention de ses congénères. Les
fourmis choisissant avec une plus grande probabilité les chemins
contenant les plus fortes concentrations de phéromones.
Le premier algorithme conçu selon ce modèle
était destiné à résoudre le problème du
voyageur de commerce. Le principe consiste à lancer des fourmis
artificielles, et à les laisser élaborer
| 
