Mutation

La mutation (en algorithmie génétique) est un opérateur génétique utilisé pour maintenir la diversité génétique d'une génération d’une population de chromosomes d’algorithme génétique au nouveau.

C'est analogue à la mutation biologique. La mutation modifie une ou plusieurs valeurs de gène dans un chromosome à partir de son état initial. En mutation, la solution peut changer entièrement de la solution précédente. Par conséquent, GA peut apporter une meilleure solution en utilisant la mutation. La mutation se produit au cours de l'évolution selon une probabilité de mutation définissable par l'utilisateur. Cette probabilité doit être basse. Si la valeur est trop élevée, la recherche se transformera en une recherche aléatoire primitive.

L'exemple classique d’un opérateur de mutation implique une probabilité qu'un arbitraire bit dans une séquence génétique sera être modifié de son état d’origine. Une méthode courante d'implémentation de l'opérateur de mutation implique la génération d'une variable aléatoire pour chaque bit d'une séquence. Cette variable aléatoire indique si un bit particulier sera modifié ou non. Cette procédure de mutation, basée sur la mutation ponctuelle biologique, est appelée mutation ponctuelle. D'autres types sont l’inversion et la mutation en virgule flottante. Lorsque le codage du gène est restrictif, comme dans les problèmes de permutation, les mutations sont des échanges, des inversions et des brouillages.

Le but de la mutation dans les algorithmes génétiques est de préserver et d’introduire la diversité. La mutation devrait permettre à l’algorithme d’éviter les minima locaux en évitant que la population de chromosomes ne devienne trop similaire les unes aux autres, ce qui ralentirait voire arrêterait l’évolution.