Mutation (algorithme génétique)

La mutation est un opérateur génétique utilisé pour maintenir la diversité génétique des chromosomes d'une population d'un algorithme génétique ou, plus généralement, évolutif (EA). Elle est analogue à la mutation biologique .

L'exemple classique d'un opérateur de mutation d'un algorithme génétique codé binaire (AG) implique une probabilité qu'un bit arbitraire d'une séquence génétique soit inversé par rapport à son état d'origine. Une méthode courante de mise en œuvre de l'opérateur de mutation consiste à générer une variable aléatoire pour chaque bit d'une séquence. Cette variable aléatoire indique si un bit particulier sera inversé ou non. Cette procédure de mutation, basée sur la mutation ponctuelle biologique , est appelée mutation ponctuelle unique. D'autres types d'opérateurs de mutation sont couramment utilisés pour des représentations autres que binaires, telles que les codages à virgule flottante ou les représentations pour les problèmes combinatoires.

L'objectif de la mutation dans les EA est d'introduire de la diversité dans la population échantillonnée . Les opérateurs de mutation sont utilisés pour tenter d'éviter les minima locaux en empêchant la population de chromosomes de devenir trop semblable les uns aux autres, ce qui ralentit voire arrête la convergence vers l'optimum global. Ce raisonnement conduit également la plupart des EA à éviter de prendre uniquement les plus aptes de la population pour générer la génération suivante, mais plutôt à sélectionner un ensemble aléatoire (ou semi-aléatoire) avec une pondération en faveur de ceux qui sont les plus aptes.

Les exigences suivantes s'appliquent à tous les opérateurs de mutation utilisés dans un EA :

1. chaque point de l'espace de recherche doit être accessible par une ou plusieurs mutations.
2. il ne doit y avoir aucune préférence pour les parties ou les directions dans l'espace de recherche (pas de dérive).
3. les petites mutations devraient être plus probables que les grandes.

Différents types de mutations sont adaptés à différents types de génomes. Certaines mutations sont gaussiennes, uniformes, en zigzag, brouillées, par insertion, par inversion, par échange, etc. Un aperçu et d'autres opérateurs que ceux présentés ci-dessous peuvent être trouvés dans le livre d'introduction d'Eiben et Smith ou dans

La mutation des chaînes de bits s'effectue par le biais de retournements de bits à des positions aléatoires.

Exemple:

La probabilité d'une mutation d'un bit est , où est la longueur du vecteur binaire. Ainsi, un taux de mutation de par mutation et par individu sélectionné pour la mutation est atteint.

De nombreux algorithmes d'analyse, comme la stratégie d'évolution algorithmes génétiques codés en réel [ fonctionnent avec des nombres réels plutôt qu'avec des chaînes de bits. Cela est dû aux bonnes expériences qui ont été faites avec ce type de codage.

La valeur d'un gène à valeur réelle peut être modifiée ou redéterminée. Une mutation qui met en œuvre cette dernière ne doit être utilisée qu'en conjonction avec les mutations à valeur variable et seulement avec une probabilité relativement faible, car elle peut entraîner des changements importants.

Dans les applications pratiques, les variables de décision à modifier du problème d'optimisation à résoudre sont généralement limitées. Par conséquent, les valeurs des gènes associés sont chacune limitées à un intervalle . Les mutations peuvent ou non tenir compte de ces restrictions. Dans ce dernier cas, un post-traitement approprié est alors nécessaire comme décrit ci-dessous.

Un nombre réel peut être muté en utilisant une distribution normale en ajoutant la valeur aléatoire générée à l'ancienne valeur du gène, ce qui donne la valeur mutée :

Dans le cas de gènes avec une plage de valeurs restreinte, il est judicieux de choisir la taille du pas de la mutation de manière à ce qu'elle corresponde raisonnablement à la plage du gène à modifier, par exemple :

La taille du pas peut également être ajustée à la plage de modification autorisée plus petite en fonction de la valeur actuelle. Dans tous les cas, il est toutefois probable que la nouvelle valeur du gène se situe en dehors de la plage de valeurs autorisée. Un tel cas doit être considéré comme une mutation mortelle, car la réparation évidente en utilisant la limite violée respective comme nouvelle valeur du gène conduirait à une dérive. En effet, la valeur limite serait alors sélectionnée avec toute la probabilité que les valeurs se situent au-delà de la limite de la plage de valeurs.

La stratégie d'évolution fonctionne avec des nombres réels et des mutations basées sur une distribution normale. Les tailles de pas font partie du chromosome et sont soumises à l'évolution avec les variables de décision réelles.

Une forme possible de modification de la valeur d'un gène tout en tenant compte de sa plage de valeurs est le changement de paramètre relatif à la mutation de l'algorithme évolutionnaire GLEAM (General Learning Evolutionary Algorithm and Method), dans lequel, comme pour la mutation présentée précédemment, les petits changements sont plus probables que les grands.

Tout d'abord, une décision équitablement répartie est prise quant à savoir si la valeur actuelle doit être augmentée ou diminuée, puis l'intervalle de variation totale correspondant est déterminé. Sans perte de généralité , une augmentation est supposée pour l'explication et l'intervalle de variation totale est alors . Il est divisé en sous-zones de taille égale avec la largeur , à partir desquelles des sous-intervalles de variation de taille différente sont formés :

Ensuite, l'un des intervalles de sous-changement est sélectionné dans une distribution égale et un nombre aléatoire, également distribué de manière égale, en est tiré comme nouvelle valeur du gène. La somme des probabilités résultant des intervalles de sous-changement donne la distribution de probabilité des sous-zones pour le cas exemplaire illustré dans la figure ci-contre. Il ne s'agit pas d'une distribution normale comme précédemment, mais cette distribution favorise aussi clairement les petits changements par rapport aux plus grands.

Cette mutation pour des valeurs plus élevées de , telles que 10, est moins bien adaptée aux tâches où l'optimum se situe sur l'une des limites de la plage de valeurs. Cela peut être résolu en réduisant considérablement lorsque la valeur d'un gène se rapproche de ses limites.

Les mutations de permutations sont spécialement conçues pour les génomes qui sont eux-mêmes des permutations d'un ensemble . Elles sont souvent utilisées pour résoudre des tâches combinatoires. Dans les deux mutations présentées, des parties du génome sont tournées ou inversées.

La présentation de la procédure est illustrée par un exemple à droite :

La présentation de la procédure est illustrée par un exemple à droite :

L'exigence posée au début pour les mutations, selon laquelle les petits changements devraient être plus probables que les grands, n'est que partiellement satisfaite par les deux mutations par permutation présentées, car les longueurs des listes partielles et le nombre de positions de décalage sont déterminés de manière également distribuée. Cependant, plus la liste partielle et le décalage sont longs, plus le changement dans l'ordre des gènes est important.

On peut remédier à cela en procédant aux modifications suivantes. L'indice de fin des listes partielles est déterminé comme la distance par rapport à l'indice de début :

où est déterminé aléatoirement selon l'une des deux procédures de mutation des nombres réels de l'intervalle et arrondi.

Pour la rotation , elle est déterminée de manière similaire à la distance , mais la valeur est interdite.

Pour l' inversion , notez que doit tenir, donc pour la valeur doit être exclue.