Métaheuristiques pour l’optimisation multiobjectif

Métaheuristiques pour l’optimisation multiobjectif

 Les méthodes de recherche locale

La première classe de métaheuristiques présentée regroupe les méthodes utilisant les principes de la recherche locale. Ces méthodes résolvent le problème d’optimisation de manière itérative. Elles font évoluer la configuration courante en la remplaçant par une autre issue de son voisinage. Ce changement de configuration est couramment appelé un mouvement. Nous commençons par présenter une étape commune à toutes les techniques de recherche locale, à savoir la détermination du voisinage, avant de passer à la présentation de quelques unes comme le recuit simulé et la recherche tabou.

Déterminer le voisinage

Toutes les approches de recherche locale utilisent la notion de voisinage. Un aspect fondamental de ces approches est donc la détermination de ce voisinage. Le voisinage d’une solution courante x, que l’on note V(x), est un sous-ensemble de solutions qu’il est possible d’atteindre par une série de transformations données. Il existe une 21 infinité de manières de choisir V, il faut adapter ce choix au problème, c’est-à-dire choisir la meilleure fonction V selon le problème considéré.

Le recuit simulé

Le recuit simulé s’inspire du processus du recuit thermique. Le processus du recuit simulé répète une procédure itérative qui cherche des configurations de coût plus faible, tout en acceptant de manière contrôlée des configurations qui dégradent la fonction de coût [Kirkpatrick et al., 83]. 

La recherche Tabou

La recherche Tabou examine toutes les configurations appartenant à un voisinage V(x) de x et retient la meilleure x0 même si x0 est plus mauvaise que x. Cependant, cette stratégie peut entraîner des cycles. Pour pallier ce problème, on mémorise les k dernières configurations visitées dans une mémoire à court terme et on interdit de retenir toute configuration qui en fait déjà partie. Cette mémoire, appelée la liste Tabou, est une des composantes essentielles de la méthode.

En effet, elle permet d’éviter tous les cycles de longueurs inférieures à k, k étant un paramètre déterminé en fonction du problème [Glover et al., 97]. La mémorisation de configurations entières serait trop coûteuse en temps de calcul et en place mémoire. Il est préférable de mémoriser des caractéristiques des configurations au lieu de configurations entières. Plus précisément, il est possible de mémoriser uniquement un attribut de la configuration.

Il en résulte que toutes les configurations possédant cet attribut, y compris celles qui n’ont pas encore été rencontrées, deviennent, elles aussi, tabou. Pour pallier à ce problème, un mécanisme particulier, appelé l’aspiration, est mis en place. Ce mécanisme consiste à révoquer le statut Tabou d’une configuration à certains moments de la recherche. La fonction d’aspiration la plus simple consiste à enlever le statut Tabou d’une configuration si celle-ci est meilleure que la meilleure configuration trouvée jusqu’alors (voir Algorithme 2).

Il existe aussi d’autres techniques permettant d’améliorer les performances de la méthode Tabou, en particulier, l’intensification et la diversification. L’intensification permet de se focaliser sur certaines zones de l’espace de recherche en apprenant des propriétés favorables, par exemple les propriétés communes souvent rencontrées dans les meilleures configurations visitées. La diversification est un processus inverse de l’intensification. En effet, elle cherche à diriger la recherche vers des zones inexplorées, en modifiant par exemple la fonction d’évaluation. L’intensification et la diversification jouent donc des rôles complémentaires [Glover et al., 97].