2.4 Population et représentation des
individus
La population est la représentation de l'ensemble des
solutions possibles. Indépendamment, les individus sont des
éléments statiques qui ne peuvent pas s'adapter, c'est la
population qui forme donc l'unité d'évolution et d'adaptation.
C'est pour cette raison que la plupart des opérateurs de
sélection prennent en compte la totalité de la population. La
diversité d'une population est la mesure du nombre des
différentes solutions existantes. Il n'existe aucune façon de
mesurer la diversité d'une population, on se réfère
généralement au nombre d'aptitudes différentes, au
degré de cette différance ou au nombre d'individus
différents.[?]
A chaque itération d'un algorithmes
évolutionnaires, de nouveaux individus sont créés. A la
prochaine itération, les individus de la génération
précédente peuvent être conservés (avec de
mêmes ou de différentes chances que ceux de la
génération courante) ou tout simplement jetés. Les
algorithmes qui changent complètement de génération
(c'est-à-dire qui ne conservent que les nouveaux individus à la
prochaine itération) sont appelés algorithmes à
sélection générationnelle (Extinctive EA). Par contre,
ceux qui ne modifient qu'une partie de la population sont des algorithmes
à remplacement stationnaire ou préservatif (Préservative
EA). Dans ce cas la population de la prochaine génération est
constituée de la combinaison de la population courante et la nouvelle
génération.
Les algorithmes générationnelles à leur
tour peuvent être divisés en algorithmes à sélection
gauche ou droite. Dans le premier cas, les bons individus ne sont pas
autorisés à participer à la reproduction de la nouvelle
génération pour éviter une convergence
prématurée des individus. Contrairement, se sont les mauvais
individus qui n'ont pas le droit de participer à a reproductin pour
garantir une certaine qualité.
1. Résumé de Christian Gagné [26]
Il existe un autre type d'algorithmes évolutionnaires,
souvent appelés algorithmes élitistes(Elitist algorithms), qui
assurent qu'au moins une copie des meilleurs individus de la
génération courante sera présente dans la prochaine
génération. Les algorithmes évolutionnaires à
état stable (Steady-State EA ou SSEA) sont des algorithmes
préservatifs qi ont la particularité de produire un nombre
d'individus faible comparé au nombre d'individus qui ont
participés à leur production.
Le premier pas dans la définition d'un algorithmes
évolutionnaires est de lier le vrai monde au Monde des algorithmes
évolutionnaires. Il s'agit de définir une sorte de passerelle
entre le contexte original du problème et l'espace du problème
à résoudre où l'évolution aura lieu. Les objets qui
forment des solutions dans le contexte original sont appelés
phénotypes, et leurs représentations génotypes.
L'efficacité d'un algorithme dépend pleinement
du choix de codage. Trouver une structure de donnée et un codage
adéquat est dès lors un des objectifs les plus importants. En
organisant les données d'une certaine manière on favorise leur
traitement automatique efficace et rapide. Adopter une structure de
données appropriée pour un problème informatique peut
également contribuer à decomplexifier de manière
significative une application informatique et ainsi participer à la
diminution du taux d'erreurs.[142]
Il existe principalement trois types de représentations
dans l'ensemble des algorithmes évolutionnaires. La
représentation binaire est le cadre générale des
algorithmes génétiques classiques. Chaque individu est
représenté par un vecteur binaire où chaque
élément peut prendre la valeur 0 ou 1. Cette
représentation s'adapte bien à des problèmes où les
solutions potentielles ont une représentation binaires canoniques. Elle
s'applique aussi à des problèmes d'optimisation continus, mais il
est alors nécessaire d'adopter une technique de codage
approproiée.
Dans la représentation réelle, l'espace de
recherche est l'espace des réels ou un sous ensemble. Cette
représentation a été initialement introduite par les
stratégies d'évolution, mais son utilisation s'est rapidement
étendue aux autres types d'algorithmes évolutionnaires.
Le dernier type est celui utilisant une structure
arborescente. Ce type de codage est à la base de la programmation
génétique pour la représentation et l'évaluation
des instructions des programmes informatiques. Il a été en suite
utilisé comme une technique de codage supplémentaire dans les
algorithmes génétiques.
|