Pour en finir avec la théorie sur les extremums locaux, je voudrais aujourd’hui parler des concepts d’exploration et d’exploitation.

Exploration versus exploitation

Je vais me resservir de quelques petits dessins que j’ai fait pour l’article précédent. Lorsqu’on lance des sondes au hasard le long de notre fonction, on est dans une phase d’exploration:

On explore toute la fonction.

À l’opposé, quand on se concentre sur une valeur de x et qu’on compare f(x) avec f(x + petite valeur) et f(x - petite valeur), on est dans une phase d’exploitation:

On exploite un petit morceau de la fonction. Plus la petite valeur ajoutée (ou retranchée) à x est petite, plus on exploite la fonction. (Si x peut-être un nombre entier, ajouter ou soustraire 1 à x est la plus grande exploitation possible.) Plus cette petite valeur augmente et moins on exploite, plus on se rapproche d’une exploration.

Il faut comprendre, et accepter, qu’à un moment donné, on ne peut pas à la fois explorer la fonction et l’exploiter. Il faut choisir entre les deux. L’exploration seule ne peut pas nous garantir qu’on va trouver un extremum (pas même un extremum local) et l’exploitation seule risque fort de trouver un extremum local (et non pas le global).

Pour donner une image -* toutes proportions gardées *- c’est un peu comme dans le monde quantique : vous ne pouvez pas mesurer à la fois la masse et la position d’une particule, vous devez choisir l’un ou l’autre. Une autre image, plus macroscopique, serait ces jeux vidéos où un brouillard de guerre masque la carte du monde : vous devez constamment choisir entre explorer le monde loin de vous et exploiter ce qui est tout près de vous.

Un bon algorithme génétique doit trouver le bon équilibre entre ses deux possibilités : exploration et exploitation. Et malheureusement pour nous, ce bon équilibre dépend des chromosomes, il est donc différent pour chaque problème.

La prochaine fois, fini la théorie, on verra comment un extremum local se manifeste en pratique dans l’algorithme génétique du problème des 8 dames.

À demain.