Documentation PostgreSQL 14.22 » Internes » Optimiseur génétique de requêtes (Genetic Query Optimizer) » Algorithmes génétiques

Précédent | Niveau supérieur | Suivant
60.1. Gérer les requêtes, un problème d'optimisation complexe | Sommaire | 60.3. Optimisation génétique des requêtes (GEQO) dans PostgreSQL

## 60.2. Algorithmes génétiques

L'algorithme génétique (GA) est une méthode d'optimisation heuristique qui opère par recherches 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. Figure 60.1 illustre ces étapes.

Figure 60.1. Structure d'un algorithme génétique

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).