2.5 Evaluation et Sélection
Dans les approches classiques, l'évaluation d'un
individu ne dépend pas de celle des autres. Le résultat fourni
par la fonction d'évaluation va permettre d'accepter ou de refuser un
individu pour ne garder que les individus ayant le meilleur coût en
fonction de la population courante. Cette méthode permet de conserver
les individus performants et d'éliminer progressivement les individus
peu adaptés. C'est donc la fonction qui permet de mesurer le
degré d'aptitude d'un individu à son environnement. Dans
plusieurs applications pratiques, cette qualité est croissante avec la
qualité de solution, mais dans certains problèmes, notamment ceux
d'optimisation, cette qualité peut être décroissante.
Le fait que le processus d'évaluation soit individuel a
sûrement ses avantages : l'algorithme n'a besoin ni de conserver des
historiques ni de prendre en compte le reste de la population. Cela permet de
gagner en mémoire et d'être indépendant de la taille de la
population. Cette individualité permet en outre de profiter davantage
des possibilités de parallélisassion.
A mesure de ne sélectionner que les meilleurs
individus, ces derniers peuvent tendre à se regrouper et à se
ressembler. Dans ce cas, la population risque de se trouver dans un cas
très homogène et de ne plus évoluer. Plusieurs techniques
ont été proposées pour pouvoir échapper à ce
problème de diversification. Ces techniques, comme le scaling et la
sharing[86, 148], utilisent des principes tels que l'historique
d'évaluation pour tenter d'incorporer plus d'informations et de
refléter, par conséquent, de façon plus
générale, l'état globale de la population.
La sélection permet de filtrer la population courante,
en se basant sur la fonction d'évaluation, de telle façon
à permettre aux bons individus de survivre et de devenir des parents. Il
existe un bon nombre de méthodes de sélection dans la
littérature, nous présentons brièvement quelques unes
ci-dessous.
2.5.1 Sélection par roulette
Il s'agit de la méthode la plus courante. Les individus
parents sont sélectionnés proportionnellement à leur
performance. Meilleur est le résultat fourni par l'évaluation
d'un individu, plus grande est sa probabilité d'être
sélectionné. Le nombre de fois qu'un individu sera
sélectionné est égal à son évaluation
divisée par la moyenne de l'évaluation de la population totale.
Plus exactement, la partie entière représente le nombre de fois
qu'il sera sélectionné, et la partie flottante la
probabilité qu'il aura d'être
sélectionné à nouveau. On peut comparer
cette méthode de sélection a une roulette de casino sur laquelle
sont placés tous les individus de la population, la largeur
allouée a chacun des individus étant en relation avec leur valeur
d'évaluation. Ensuite, la bille est lancée et s'arrête sur
un individu. Les meilleurs individus peuvent ainsi être tirés
plusieurs fois et les plus mauvais ne jamais être
sélectionnés.
| 
