L'algorithme génétique (GA) est une méthode heuristique d'optimisation qui opère via des recherches non déterministes 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).
Figure 48.1. Diagramme structuré d'un algorithme génétique
| P(t) | génération des ancêtres au temps t |
| P''(t) | génération des descendants au temps t |
+=========================================+
|>>>>>>>>>>> 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 |
+===+=====================================+
Optimiseur génétique de requêtes (Genetic Query
Optimizer)
