4.3 Exploitation et exploration
Les notions d'exploitation et d'exploration se sont apparues
avec l'arrivée des algorithmes génétiques. L'exploitation
(ou intensification) insiste sur la capacité d'examiner en profondeur
des zones de recherche particulières, ou plus exactement utiliser des
individus pertinents pour en produire d'autres, c'est-à-dire les
exploiter. L'exploration, par contre, met en avant la capacité de
découvrir des zones de recherche prometteuses (diversification). Il est
donc très important d'examiner les algorithmes évolutionnaires en
fonction de ces deux notions.
Bien que ces deux notions soient tellement
complémentaires, il est quand même difficile de trouver un
compromis ente elles. Mais il est remarquable que la préoccupation
majeure des algorithmes évolutionnaires est la conservation de la
diversité de la population. Ceci est du au fait que le rôle de
l'exploration est plus important que celui de l'exploitation, dans la mesure
où le premier est fondamental est le deuxième est moins
essentiel. En effet, une bonne exploration de l'espace de recherche va
permettre, tôt ou tard, de tomber sur une solution potentielle. Il est
vrai qu'une exploration aveugle peut passer juste à coter d'une bonne
solution sans qu'elle s'en rende compte, mais les bonnes solutions ont tendance
à se regrouper. C'est à ce niveau là qu'intervient
l'exploitation pour concentrer la recherche autour de ces solutions
potentielles. Tout cela
explique comment le rôle de la fonction d'exploration
est fondamental. Il ne sert à rien de penser à exploiter des bons
individus si l'on ne peut même pas tomber sur eux. De plus, et comme il a
été discuté au chapitre 2, l'abus de l'exploitation va
mettre la population dans un état très homogène et
l'empêcher d'évoluer.
C'est pour cette raison que les méthodes
évolutionnaire ont souvent recouert au scaling et au sharing pour
empêcher le regroupement prématuré des bons individus. On
ajoute à tous ça le fait que la notion de "bon individu" est
très relative. En effet, si un individu est considéré
comme étant bon dans sa population en cours, ceci ne signifie en aucun
cas qu'il est le meilleur. Ce qui nous mène au problème classique
des heuristiques d'optimisation : le piège de l'optimum local.
Dans les stratégies d'évolution, l'exploitation
est représentée principalement par l'opérateur de
recombinaison, et l'exploration par l'opérateur de mutation. Les
stratégies d'évolution se basent principalement sur
l'exploitation, vu que la mutation est l'opérateur de reproduction
fondamental. La mutation, en ajoutant des bruits aléatoires, permet une
diversification aléatoire aussi de la population. De sa part la
recombinaison permet d'orienter la recherche vers des zones prometteuses. De
cette façon les stratégies d'évolution constituent un bon
exemple de méthodes équilibrant entre l'exploitation et
l'exploration.
Il est aussi important de noter que le maintient des fonctions
d'auto-adaptation a un impact sur la diversification. Il peut être
considéré comme un outil supplémentaire d'exploitation,
puisqu'il permet d'utiliser la qualité globale de la population pour
diriger la recherche.
Les opérateurs de création et de duplication,
quoiqu'ils sont beaucoup moins fréquents, peuvent contribuer à
leur tours au maintient de la stabilité globale de la population. Bien
que la création ne soit souvent utilisée que lors de la
génération de la population initiale, la méthode peut lui
faire appel comme outil secondaire de diversification. En associant la
recombinaison à la mutation, la reproduction sera toujours basée
sur des bons individus. La création permet d'introduire des
éléments complètement nouveaux, et de rediriger certaines
parties de la recherche vers des régions totalement nouvelles. La
duplication quant à elle, permet de garder une trace de quelques
individus potentiels, pour garantir leur présence dans les prochaines
générations. La duplication ne peut pas avoir d'effets
destructifs : si les autres opérateurs produisent des individus moins
meilleurs, la duplication portera un grand intérêt en étant
la seule à produire quelque chose de bon. Dans le cas contraire,
c'est-à-dire si les éléments dupliqués sont
mauvais, la sélection s'en occupera.
Pour la programmation génétique, la recherche
est plutôt orientée vers l'exploitation. Malgré que le jeu
d'opérateur soit plus important ici que tous les autres algorithmes, la
mutation est le seul qui offre des possibilités d'exploration. Cette
orientation s'explique par le fait que la programmation génétique
a été conçue pour le développement automatique de
programmes, et montre encore une fois comment l'objectif initial d'une
méthode influence son orientation. En effet, dans le cas d'une
population de programmes, la notion de fonction peut s'agir d'une seule
instruction comme de plusieurs. Cette idée de groupe potentiel
d'individus n'a de sens que dans les programmes informatiques. Lorsque la
recherche tombe sur fonction potentielle regroupant plusieurs instructions, il
est important de la faire propager dans toute la population de façon
entière. Dans le cas contraire, il y a un grand risque que ce groupe
soit découpé et perde toute sont efficacité. La
programmation génétique tient donc à profiter de
façon maximale des capacités potentielles des sous-programmes
d'individus qu'elle manipule avant de chercher à produire de nouveaux
individus. Il convient aussi de prendre en compte que la structure arborescente
de ses individus offre plus de possibilités de variation que les
vecteurs, notamment dans le cas des programmes informatiques. Il suffi en effet
d'une simple permutation entre deux arbres pour pouvoir changer radicalement la
sémantique du programme, et donc de donner naissance à un
individu tout à fait différent.
Pour conclure, nous dirons que le choix de la stratégie
de recherche a été effectué dans les deux méthode
de telle façon à ce qu'il soit le mieux convenable à la
nature des problèmes auxquels chacune d'elles a été
dédiée. Les stratégies d'évolution ont suivit une
stratégie favorisant l'exploration pour échapper au piège
de l'optimum local des problèmes d'optimisation. De son coté, la
programmation génétique a pris en considération la nature
générale de ses individus, et adopté une stratégie
de recherche basée sur l'exploitation. Il ne reste donc à dire
que l'usage approprié de l'une des deux méthodes impliquerait un
choix judicieux de la stratégie de recherche.
| 
