IV.? Principe de base d'un AG standard
Un AG standard nécessite en premier le codage
de l'ensemble des paramètres du problème d'optimisation en une
chaîne de longueur finie. Le principe d'un AG est simple, il s'agit de
simuler l'évolution d'une population d'individus jusqu'à un
critère d'arrêt. On commence par générer une
population initiale d'individus (solutions) de façon aléatoire.
Puis, à chaque génération, des individus sont
sélectionnés, cette sélection est effectuée
à partir d'une fonction objectif appelée fonction d'adaptation.
Puis, les opérateurs de croisement et de mutation sont appliqués
et une nouvelle population est créée. Ce processus est
itéré jusqu'à un critère d'arrêt. Le
critère le plus couramment utilisé est le nombre maximal de
générations que l'on désire effectuer. La Figure 22
présente le principe de l'AG standard.
L'AG débute par la génération
d'une population initiale et l'évaluation de la fonction d'adaptation de
tous les individus qui composent cette première population. Puis, des
individus sont sélectionnés aléatoirement pour la
reproduction selon le principe de la survie du plus adapté. Ensuite, des
individus « enfants » (ou les descendants) sont
générés en appliquant les deux opérateurs
génétiques suivants : le croisement et la mutation. Ces enfants
sont placés dans une nouvelle population P(t) et vont se substituer, en
tout ou en partie, à la population de la génération
précédente. De nouvelles populations d'individus vont ensuite se
succéder, d'une génération (t) à la
génération (t+1), chaque génération
représentant une itération jusqu'à l'atteinte du
critère d'arrêt. L'AG présenté ci-dessus est dit
générationnel car tous les individus enfants
générés sont placés dans une population et vont
remplacer entièrement la population des individus parents.
On représente le principe fondamental de
fonctionnement d'un algorithme génétique dans la Figure 21 [web
8].
82
Figure 21 Schéma général d'un
algorithme génétique
Début
Population initiale de la génération t=0
Meilleur résultat
Création de la population
P(t)
Sélection des individus
Operateur de croisement et de mutation
Evaluation de la fonction
d'adaptation de
chaque
individu
t=t+1
Non
Oui
Critère
d'arrêt
respect
83
Fin
Figure 22 Organigramme d'un AG standard
84
IV.5 processus d'un algorithme génétique
IV.5.1 Création de la population initiale :
Pour démarrer un algorithme
génétique, il faut lui fournir une population à faire
évoluer. La manière dont le programmeur va créer chacun
des individus de cette population est entièrement libre. Il suffit que
tous les individus créés soient de la forme d'une solution
potentielle, et il n'est nullement besoin de songer à créer des
bons individus. Ils doivent juste fournir une réponse, même
mauvaise, au problème posé.
Par exemple, si vous cherchez un chemin entre 2
points, les individus créés devront simplement posséder le
bon point de départ et le bon point d'arrivée, peu importe par
où ils passent. De même si vous cherchez des solutions pour un jeu
d'échecs, il suffira que les individus créés
possèdent des mouvements autorisés sur des pièces
existantes. Même si les individus créés n'ont aucune chance
d'être des solutions acceptables pour le problème posé, ils
peuvent en avoir la forme. Il n'y a donc aucune objection à les mettre
dans la population initiale.
| 
