Opérateur génétique - Genetic operator
Un opérateur génétique est un opérateur utilisé dans les algorithmes génétiques pour guider l'algorithme vers une solution à un problème donné. Il existe trois principaux types d'opérateurs ( mutation , croisement et sélection ), qui doivent fonctionner en conjonction les uns avec les autres pour que l'algorithme réussisse. Les opérateurs génétiques sont utilisés pour créer et maintenir la diversité génétique (opérateur de mutation), combiner des solutions existantes (également appelées chromosomes ) en de nouvelles solutions (croisement) et choisir entre des solutions (sélection). Dans son livre sur l'utilisation de la programmation génétique pour l'optimisation de problèmes complexes, l'informaticien John Koza a également identifié un opérateur «d'inversion» ou de «permutation»; cependant, l'efficacité de cet opérateur n'a jamais été démontrée de manière concluante et cet opérateur est rarement discuté.
On dit que les opérateurs de mutation (ou de type mutation) sont des opérateurs unaires , car ils n'opèrent que sur un chromosome à la fois. En revanche, on dit que les opérateurs de croisement sont des opérateurs binaires , car ils opèrent sur deux chromosomes à la fois, combinant deux chromosomes existants en un nouveau chromosome.
Les opérateurs
La variation génétique est une nécessité pour le processus d' évolution . Les opérateurs génétiques utilisés dans les algorithmes génétiques sont analogues à ceux du monde naturel: survie du plus apte , ou sélection ; reproduction ( crossover , également appelé recombinaison); et la mutation .
Sélection
Les opérateurs de sélection privilégient les meilleures solutions (chromosomes), leur permettant de transmettre leurs «gènes» à la prochaine génération de l'algorithme. Les meilleures solutions sont déterminées à l'aide d'une certaine forme de fonction objective (également connue sous le nom de « fonction de fitness » dans les algorithmes génétiques), avant d'être transmises à l'opérateur de croisement. Il existe différentes méthodes pour choisir les meilleures solutions, par exemple la sélection proportionnée à la forme physique et la sélection de tournois ; différentes méthodes peuvent choisir différentes solutions comme étant «les meilleures». L'opérateur de sélection peut aussi simplement passer les meilleures solutions de la génération actuelle directement à la génération suivante sans être muté; c'est ce qu'on appelle l' élitisme ou la sélection élitiste .
Crossover
Le crossover est le processus qui consiste à prendre plus d'une solution mère (chromosomes) et à en produire une solution enfant. En recombinant des portions de bonnes solutions, l'algorithme génétique est plus susceptible de créer une meilleure solution. Comme pour la sélection, il existe un certain nombre de méthodes différentes pour combiner les solutions parentes, y compris l' opérateur de recombinaison d'arête (ERO) et les méthodes de «coupure et épissure croisée» et «croisée uniforme». La méthode de croisement est souvent choisie pour correspondre étroitement à la représentation chromosomique de la solution; cela peut devenir particulièrement important lorsque les variables sont regroupées sous forme de blocs de construction , qui pourraient être perturbés par un opérateur de croisement non respectueux. De même, les méthodes de croisement peuvent être particulièrement adaptées à certains problèmes; l'ERO est généralement considéré comme une bonne option pour résoudre le problème du voyageur de commerce .
Mutation
L'opérateur de mutation encourage la diversité génétique parmi les solutions et tente d'empêcher l'algorithme génétique de converger vers un minimum local en empêchant les solutions de devenir trop proches les unes des autres. Lors de la mutation du pool actuel de solutions, une solution donnée peut changer entièrement de la solution précédente. En faisant muter les solutions, un algorithme génétique peut atteindre une solution améliorée uniquement grâce à l'opérateur de mutation. Là encore, différentes méthodes de mutation peuvent être utilisées; ceux-ci vont d'une simple mutation de bits (retournement de bits aléatoires dans un chromosome à chaîne binaire avec une faible probabilité) à des méthodes de mutation plus complexes, qui peuvent remplacer les gènes dans la solution par des valeurs aléatoires choisies dans la distribution uniforme ou la distribution gaussienne . Comme avec l'opérateur de croisement, la méthode de mutation est généralement choisie pour correspondre à la représentation de la solution dans le chromosome.
Combinaison d'opérateurs
Alors que chaque opérateur agit pour améliorer les solutions produites par l'algorithme génétique travaillant individuellement, les opérateurs doivent travailler en collaboration les uns avec les autres pour que l'algorithme réussisse à trouver une bonne solution. L'utilisation de l'opérateur de sélection seul aura tendance à remplir la population de solutions avec des copies de la meilleure solution de la population. Si les opérateurs de sélection et de croisement sont utilisés sans l'opérateur de mutation, l'algorithme aura tendance à converger vers un minimum local , c'est-à-dire une bonne solution mais sous-optimale au problème. L'utilisation de l'opérateur de mutation seul conduit à une promenade aléatoire dans l'espace de recherche. Ce n'est qu'en utilisant les trois opérateurs ensemble que l'algorithme génétique peut devenir un algorithme d'escalade tolérant au bruit, offrant de bonnes solutions au problème.