2.6 Reproduction
Les algorithmes évolutionnaires utilisent les
informations recueillies dans les générations
précédentes pour créer l'ensemble des individus de la
prochaine génération. Les opérations associées sont
la création, la duplication, la mutation et la recombinaison (ou le
croisement).
2.6.1 Création et duplication
La création est la production brute d'un individu de
façon complètement aléatoire sans aucun modèle
préalable. C'est ce qui se passe lors de la génération de
la population initiale. Toutefois, le programme peut faire appel à la
création des générations qui suivent et ce afin de
préserver la diversité de la population. La duplication est
analogue à la division cellulaire. Elle est généralement
utilisée pour garantir la présence d'un nombre minimal de bons
individus en évitant leur disparition à force des mutations
successives.
2.6.2 Mutation
La mutation est un opérateur qui agit sur un seul
individu pour en produire un autre légèrement modifié.
C'est un opérateur purement aléatoire qui a pour rôle
d'éviter à l'algorithme de se retrouver dans des situations de
saturation et de préserver la
diversité de la population. Mais il peut cependant
constituer le principal, voir le seul, opérateur de reproduction.
Dans le cas du codage binaire, la mutation consiste à
inverser les bits d'un génotype avec une faible probabilité. La
mutation la plus employé dans les codages binaires est la mutation
stochastique qui inverse chaque bit indépendamment avec une certaine
probabilité relative à la taille du génotype. Un autre
type de mutation est l'inversion d'un seul bit choisi au hasard avec une
certaine probabilité.
La principale technique utilisée pour la mutation
réelle est l'ajout d'un bruit Gaussien aux différentes
composantes du vecteur. La difficulté de cette approche est l'ajustement
de l'écart-type du bruit généré. En effet, au
début de l'évolution d'une population, l'écart-type doit
être assez élevé pour générer de fortes
perturbations et ainsi explorer rapidement tout l'espace de recherche. Une fois
les pics de la fonction étudiée localisés, l'algorithme
doit être capable de déterminer avec précision les
solutions optimales.
2.6.3 Recombinaison
La recombinaison est utilisée pour créer de
nouveaux individus en combinant les éléments déjà
existant. Elle consiste à échanger un ou plusieurs fragments des
deux génotypes. Les croisements binaires les plus utilisés
opèrent sur un fragment, deux fragments ou sur tous les fragments
(croisement uniforme). Dans le cas de représentation réelle, il y
a deus manières de recombiner deux génotypes : choisir l'un des
deux individus (croisement discret ou par dominance), ou combiner
linéairement les deux (croisement intermédiaire ou
linéaire). Pour la représentation structurée comme le cas
des arbres binaires, la recombinaison se fait principalement par échange
de structures (sous arbres).
|