Programmation génétique

Contenus

L’algorithme de programmation génétique s’inspire de la génétique des populations (y compris l’hérédité et les fréquences des gènes) et de l’évolution au niveau de la population, ainsi que de la compréhension mendélienne de la structure (comme les chromosomes, les gènes, les allèles) et des mécanismes (comme la recombinaison et la mutation ). Il s’agit de la soi-disant synthèse nouvelle ou moderne de la biologie évolutive.

Les individus d’une population apportent leur matériel génétique (appelé le génotype) proportionnel à la pertinence de leur génome exprimé (appelé leur phénotype) à leur environnement. La prochaine génération est créée par un processus d’accouplement qui implique des opérateurs génétiques tels que la recombinaison des génomes de deux individus dans la population et l’introduction d’erreurs de copie aléatoires (appelées mutations). Ce processus itératif peut entraîner une amélioration de l’adaptation entre les phénotypes des individus d’une population et l’environnement.

La programmation génétique peut être développée et utilisée dans un processus adaptatif secondaire, où une évaluation des candidats à la fin de ce processus adaptatif secondaire est utilisée pour le succès reproductif différentiel dans le premier processus évolutif. Ce système peut être compris comme les interdépendances vécues dans le développement évolutif où l’évolution opère sur un embryon qui à son tour se développe en un individu dans un environnement qui peut éventuellement se reproduire.

L’objectif de l’algorithme de programmation génétique est d’utiliser l’induction pour concevoir un programme informatique. Ceci est réalisé en utilisant des opérateurs évolutifs sur des programmes candidats avec une structure arborescente pour améliorer l’adaptation entre la population de programmes candidats et une fonction objective. L’évaluation d’une solution candidate implique son exécution.

Le programme génétique utilise des expressions symboliques de type LISP appelées expressions S qui représentent le graphique d’un programme avec des nœuds de fonction et des nœuds terminaux. Pendant que l’algorithme est en cours d’exécution, les programmes sont traités comme des données et lorsqu’ils sont évalués, ils sont exécutés. La traversée d’un graphe de programme est toujours la première profondeur, et les fonctions doivent toujours renvoyer une valeur.

L’algorithme de programmation génétique a été conçu pour la programmation automatique inductive et est bien adapté à la régression symbolique, à la conception de contrôleurs et aux tâches d’apprentissage automatique sous le nom plus large d’approximation de fonction.

L’évaluation (affectation de la fitness) d’une solution candidate prend généralement en compte la structure du programme, récompensant la parcimonie.

Le processus de sélection doit être équilibré entre la sélection aléatoire et la sélection gourmande pour biaiser la recherche vers des solutions candidates plus fines (exploitation), tout en favorisant une diversité utile dans la population (exploration).

Un programme peut répondre à zéro ou plusieurs valeurs d’entrée et peut produire une ou plusieurs sorties.

Toutes les fonctions utilisées dans l’ensemble de nœuds de fonction doivent renvoyer un résultat utilisable. Par exemple, la fonction de division doit renvoyer une valeur sensible (telle que zéro ou un) lorsqu’une division par zéro se produit.