Représentation du génotype
L'une des décisions les plus importantes à prendre lors de la mise en œuvre d'un algorithme génétique est de décider de la représentation que nous utiliserons pour représenter nos solutions. Il a été observé qu'une représentation incorrecte peut conduire à une mauvaise performance de l'AG.
Par conséquent, le choix d'une représentation appropriée, ayant une définition appropriée des mappages entre les espaces phénotype et génotype est essentiel pour le succès d'une AG.
Dans cette section, nous présentons certaines des représentations les plus couramment utilisées pour les algorithmes génétiques. Cependant, la représentation est très spécifique au problème et le lecteur peut trouver qu'une autre représentation ou un mélange des représentations mentionnées ici pourrait mieux convenir à son problème.
Représentation binaire
C'est l'une des représentations les plus simples et les plus utilisées dans les GA. Dans ce type de représentation, le génotype est constitué de chaînes de bits.
Pour certains problèmes lorsque l'espace de solution est constitué de variables de décision booléennes - oui ou non, la représentation binaire est naturelle. Prenons par exemple le problème du sac à dos 0/1. S'il y a n éléments, nous pouvons représenter une solution par une chaîne binaire de n éléments, où le x ème élément indique si l'élément x est choisi (1) ou non (0).
Pour d'autres problèmes, en particulier ceux traitant des nombres, nous pouvons représenter les nombres avec leur représentation binaire. Le problème avec ce type de codage est que différents bits ont une signification différente et que, par conséquent, les opérateurs de mutation et de croisement peuvent avoir des conséquences indésirables. Cela peut être résolu dans une certaine mesure en utilisantGray Coding, car un changement en un seul bit n'a pas d'effet massif sur la solution.
Représentation valorisée réelle
Pour les problèmes où nous voulons définir les gènes en utilisant des variables continues plutôt que discrètes, la représentation réelle valorisée est la plus naturelle. La précision de ces nombres réels ou à virgule flottante est cependant limitée à l'ordinateur.
Représentation entière
Pour les gènes à valeurs discrètes, nous ne pouvons pas toujours limiter l'espace de solution au binaire «oui» ou «non». Par exemple, si nous voulons encoder les quatre distances - Nord, Sud, Est et Ouest, nous pouvons les encoder comme{0,1,2,3}. Dans de tels cas, une représentation entière est souhaitable.
Représentation de permutation
Dans de nombreux problèmes, la solution est représentée par un ordre d'éléments. Dans de tels cas, la représentation par permutation est la plus appropriée.
Un exemple classique de cette représentation est le problème du voyageur de commerce (TSP). En cela, le vendeur doit faire le tour de toutes les villes, visiter chaque ville exactement une fois et revenir à la ville de départ. La distance totale du circuit doit être minimisée. La solution à ce TSP est naturellement un ordre ou une permutation de toutes les villes et donc l'utilisation d'une représentation par permutation a du sens pour ce problème.
