CHAPITRE IV
Les algorithmes
génétiques
80
IV. Introduction
Dans la littérature, les méthodes
d'optimisation se répartissent généralement en deux
grandes catégories : déterministes et
non-déterministes.
Les méthodes déterministes se basent sur
la valeur de la fonction objective et des contraintes, ainsi que sur la valeur
de leurs dérivées premières et parfois leurs
dérivées secondes. Ce sont des méthodes itératives
convergeant vers un minimum local. La convergence vers un optimum global n'est
pas toujours assurée. Les méthodes déterministes sont
généralement efficaces quand l'évaluation de la fonction
objective est très rapide, ou quand sa forme est connue a priori. Dans
la plupart des problèmes d'optimisation rencontrés par les
ingénieurs, on ne possède pas suffisamment d'information sur la
fonction objectif ni sur ses dérivées.
Les cas d'optimisation complexes impliquant des temps
de calcul importants, de nombreux optima locaux ou des fonctions
non-dérivables, seront souvent traités plus efficacement par des
méthodes non-déterministes. Ces méthodes font appel
à des tirages de nombres aléatoires qui permettent d'explorer
l'espace de recherche plus efficacement. Elles sont faciles à implanter
pour le traitement des problèmes d'optimisation discrète, quand
l'espace de recherche devient non-convexe ou lorsque les gradients sont
discontinus.
IV.? Enoncé de l'exemple
Cet exemple sera illustré dans tout le
processus de l'algorithme génétique.
Je montrerai comment appliquer un algorithme
génétique au problème bien connu de "l'informaticien en
vacances", [web 8] inspiré du problème du voyageur de commerce.
L'informaticien en vacances doit visiter plusieurs villes durant ses vacances :
{ A,B,C,D,E,F,G,H,I,J }. Il cherche donc le chemin le plus court pour passer
par chacune d'elles. Il souhaite également assister à un maximum
de festivals musicaux (ayant lieu dans les villes A,B et C). Il s'agit donc
d'un problème bi-critères (la distance entre les villes à
minimiser et le nombre de festivals auxquels il pourra assisté à
maximiser). Chaque festival a lieu à une date donnée. Nous
connaissons aussi les distances entre toutes les villes.
IV.3 Algorithmes génétiques
Les techniques de recherche et d'optimisation sont en
général classées en trois catégories
[Coel & al. 02] :
énumératives, déterministes et stochastiques. Les AG font
partie de la troisième catégorie et quatre
caractéristiques les distinguent des autres techniques d'optimisation
[Gold, 89, 94] :
81
? ils utilisent un codage des paramètres et non
les paramètres eux-mêmes;
? ils travaillent sur une population d'individus (ou de
solutions);
? ils n'utilisent que les valeurs de la fonction à
optimiser, pas sa dérivée, ou une autre
connaissance auxiliaire;
? ils utilisent des règles de transition
probabilistes et non déterministes.
| 
