Adaptation de TRIBES à l’optimisation multiobjectif

Comme nous l’avons vu dans le chapitre précédent, la famille des métaheuristiques a été utilisée efficacement pour la résolution des problèmes d’optimisation multiobjectif. Elles présentent actuellement un sujet de recherche privilégié. En effet, elles ont été intensément exploitées et elles ont atteint aujourd’hui leurs limites. De ce fait, de nouveaux axes de recherche sont explorés afin de dépasser les restrictions imposées par les algorithmes tels qu’ils ont été initialement définis. Ces nouveaux axes de recherche visent à faciliter la prise en main des métaheuristiques. Parmi les améliorations possibles, la réduction du nombre de paramètres des algorithmes apparaît comme un enjeu majeur. En effet, la résolution d’un problème donné passe toujours par une étape primordiale qui définit un jeu de paramètres optimal. Cette étape nécessite une connaissance approfondie des mécanismes de l’algorithme utilisé. D’où le succès modéré de ces techniques dans le monde de l’industrie où seules la performance, l’efficacité et la rapidité comptent. Afin de résoudre un problème d’optimisation donné, l’utilisateur doit tout d’abord décrire les données spécifiques à ce problème. En effet, il doit délimiter l’espace de recherche, souvent en précisant pour chaque dimension l’intervalle des valeurs admissibles. Il doit également préciser la fonction objectif et le critère d’arrêt.

Un algorithme sans paramètres de contrôle signifie que l’utilisateur intervient uniquement dans l’étape de description du problème. Il n’a aucun paramètre à définir par la suite. De ce fait, l’algorithme doit être capable de définir ces paramètres. Pour ce faire, il doit incorporer des règles définissant comment, à chaque itération de l’algorithme, l’essaim va évoluer et se comporter, tout en intégrant les informations progressivement recueillies au cours du traitement. Ce point de vue consiste à chercher un compromis entre la performance et la facilité de prise en main de l’algorithme. Dans ce cadre se situe TRIBES, un algorithme d’OEP sans paramètres de contrôle et conçu par Clerc [Clerc, 06]. En fait, TRIBES est défini comme une boîte noire, pour laquelle l’utilisateur n’a qu’à spécifier le problème à résoudre. Proposer une OEP adaptative impose de répondre à deux types de questions : Comment la structure de l’essaim évolue au cours du temps ? et Quel comportement doit adopter une particule ? La première question est relative à la définition du nombre de particules de l’essaim et de la topologie de voisinage. La deuxième question est relative à la définition des paramètres w, c1, c2 et Vmax. Deux types d’adaptations sont alors définis : les adaptations structurelles et les adaptations comportementales. Ces deux types d’adaptations sont détaillés dans les sections suivantes. de tailles différentes, qui évoluent au cours du temps. Le but est d’explorer simultanément plusieurs régions de l’espace de recherche, généralement des optima locaux, avant de prendre une décision globale. Pour ce faire, les tribus doivent être capables d’échanger les informations recueillies tout au long du traitement. La structure de l’essaim est présentée dans la figure 3.1. A cet effet, deux types de communication sont nécessaires : la communication intra-tribu et la communication inter-tribu.

La communication intra-tribu désigne l’échange d’informations entre les particules formant la même tribu. Chaque tribu présente une topologie complètement connectée. En effet, chaque particule est capable de connaître la meilleure et la plus mauvaise position jamais atteintes par la tribu. Chaque particule dispose de trois types d’informateurs dans l’essaim. En effet, elle est informée par elle-même (mémoire cognitive p), par tous les éléments de sa tribu (appelés informateurs internes), et, si cette particule est un chaman (i.e. la meilleure particule d’une tribu), alors elle est aussi informée par les chamans des autres tribus (appelés informateurs externes). L’évolution des tribus signifie l’ajout ou la suppression de particules. Ceci étant assuré en définissant des règles d’adaptation structurelles pour l’essaim. Pour ce faire, on définit deux indicateurs de qualité, un pour les particules et un pour les tribus. Une particule est dite bonne si elle a amélioré sa meilleure performance au cours de la dernière itération. Dans le cas contraire, elle est dite neutre. Cet indicateur est purement qualitatif, car il est basé sur l’évolution de la performance et non sur la performance elle-même. En plus de cet indicateur, la meilleure et la plus mauvaise position de la tribu sont stockées. L’intérêt de la destruction des particules est de minimiser le nombre des particules de l’essaim. Le but de cette opération est de minimiser le nombre d’évaluations de la fonction objectif et de gagner par la suite du temps lors de l’exécution de l’algorithme. Donc, aussitôt qu’une occasion de supprimer une particule avec presqu’aucun risque ne surgit, elle doit être saisie. Notons qu’il vaut mieux conserver une particule par erreur (dans le pire cas, le nombre d’évaluations de la fonction objectif pour atteindre la solution optimale augmentera) plutôt que supprimer une particule par erreur (au risque de complètement manquer la solution optimale).