49.2. Algorithmes génétiques

L'algorithme génétique (GA) est une méthode d'optimisation heuristique qui opère par recherches non déterministes, aléatoires. L'ensemble des solutions possibles au problème d'optimisation est considéré comme une population d'individus. Le degré d'adaptation d'un individu à son environnement est indiqué par sa valeur d'adaptation (fitness).

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 de chromosome qui code la valeur d'un paramètre simple en cours d'optimisation. Les codages habituels d'un gène sont binary ou integer.

La simulation des opérations d'évolution (recombinaison, mutation et sélection) permet de trouver de nouvelles générations de points de recherche qui présentent une meilleure adaptation moyenne que leurs ancêtres.

Selon la FAQ de comp.ai.genetic, on ne peut pas réellement affirmer qu'un GA n'est pas purement une recherche aléatoire. Un GA utilise des processus stochastiques, mais le résultat est assurément non-aléatoire (il est mieux qu'aléatoire).

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