48.2. Algorithmes g�n�tiques

L'algorithme g�n�tique (GA) est une m�thode heuristique d'optimisation qui op�re via des recherches d�termin�es au hasard. L'ensemble des solutions possibles pour le probl�me d'optimisation est consid�r� comme une population d'individus. Le degr� d'adaptation d'un individu dans son environnement est sp�cifi� par sa forme physique.

Les coordonn�es d'un individu dans l'espace de recherche sont repr�sent�es par des chromosomes, en fait un ensemble de cha�nes de caract�res. Un g�ne est une sous-section d'un chromosome qui code la valeur d'un seul param�tre en cours d'optimisation. Les codages typiques pour un g�ne pourraient �tre binary ou integer.

� travers la simulation des op�rations �volutives (recombinaison, mutation et s�lection), de nouvelles g�n�rations de points de recherche sont trouv�es affichant une meilleure forme physique que leurs anc�tres.

D'apr�s la FAQ de comp.ai.genetic, il ne peut pas �tre dit plus fortement qu'un GA n'est pas une recherche effectu�e seulement au hasard. Un GA utilise des processus stochastiques mais le r�sultat n'est pas du tout d� au hasard (mieux que cela).

+=========================================+
|>>>>>>>>>>>  Algorithme GA <<<<<<<<<<<<<<|
+=========================================+
| INITIALISE t := 0                       |
+=========================================+
| INITIALISE P(t)                         |
+=========================================+
| �value FORMEPHYSIQUE de P(t)            |
+=========================================+
| tant que pas ARRET CRITERE faire        |
|   +-------------------------------------+
|   | P'(t)  := RECOMBINAISON{P(t)}       |
|   +-------------------------------------+
|   | P''(t) := MUTATION{P'(t)}           |
|   +-------------------------------------+
|   | P(t+1) := SELECTION{P''(t) + P(t)}  |
|   +-------------------------------------+
|   | �value FORMEPHYSIQUE de P''(t)      |
|   +-------------------------------------+
|   | t := t + 1                          |
+===+=====================================+