Modèles de parallélisme pour les métaheuristiques multi-objectifs

Depuis de nombreuses années, les chercheurs s’intéressent à des problèmes complexes qui se composent de plusieurs objectifs à atteindre simultanément. La résolution de tels problèmes représente encore aujourd’hui un défi important puisqu’ils se retrouvent dans de nombreux domaines tels que la médecine, la chimie ou encore l’industrie. Les objectifs associés à ces problèmes sont souvent contradictoires, de sorte qu’il est très difficile de trouver une unique solution optimisant chacun des objectifs. Dans un tel contexte, il convient généralement de chercher les solutions qui représentent les meilleurs compromis entre les objectifs. En recherche opérationnelle, ce genre de problème est appelé problème multiobjectifs et l’ensemble de solutions de meilleurs compromis est communément nommé ensemble de solutions Pareto optimales en référence à son créateur Vilfredo Pareto (Pareto, 1876).

Une majorité de problèmes, en plus d’être multi-objectifs, sont également des problèmes NP-Difficiles et ne sont pas résolubles de manière exacte en raison d’un temps de calcul excessif. Néanmoins, des méthodes approchées telles que les métaheuristiques permettent de proposer des solutions acceptables à ces problèmes en un temps qualifié de raisonnable. Les métaheuristiques s’inspirent de phénomènes naturels réels et se classent en plusieurs familles. Parmi les métaheuristiques les plus étudiées dans la littérature se trouvent l’optimisation par colonies de fourmis (Dorigo et Gambardella, 1997), les algorithmes évolutionnaires (Goldberg, 1989) basés sur la théorie de l’évolution proposée par Darwin ou encore les algorithmes par essaim particulaire (Eberhart et Kennedy, 1995). Ces métaheuristiques à base de population sont particulièrement adaptées pour résoudre des problèmes multi-objectifs puisqu’elles permettent d’approximer l’ensemble des solutions Pareto optimales en une seule exécution.

Pour résoudre des problèmes réels à grande échelle, le temps de résolution des métaheuristiques multi-objectifs peut demeurer prohibitif, notamment car ces méthodes ne cherchent pas à approximer une unique solution optimale mais l’ensemble des meilleurs compromis. De ce fait, des alternatives doivent être employées pour réduire le temps d’exécution et ainsi permettre la résolution efficace de problèmes multi-objectifs de grande taille. L’émergence des architectures parallèles qui sont de plus en plus puissantes et accessibles de nos jours a permis, en ce sens, de rendre la parallélisation des métaheuristiques populaire. En plus de réduire le temps pour optimiser un problème, les modèles parallèles pour les métaheuristiques multi-objectifs ont pour but (Talbi et al., 2008) (i) d’améliorer la qualité des solutions obtenues en fournissant une approximation plus proche des meilleures solutions, mais également en proposant un ensemble de solutions mieux diversifié (ii) de répondre à des instances de problème plus grandes qui ne peuvent pas être traitées sur des processeurs monocœur (iii) d’améliorer la robustesse des approches sur différents types de problème. En suivant ces objectifs et depuis les années 2000, plusieurs méthodes de parallélisation ont été proposées pour améliorer les performances des métaheuristiques multi-objectifs. Bien que ces approches aient apporté une contribution significative au domaine de l’optimisation multi-objectifs (Talbi, 2018), elles restent perfectibles en ce qui concerne leur extensibilité et l’exploitation efficace de multiples unités de calcul.

L’OPTIMISATION MULTI-OBJECTIFS PAR LES MÉTAHEURISTIQUES 

Beaucoup de problèmes pratiques nécessitent l’optimisation de plusieurs objectifs qui sont conflictuels, car essayer d’en améliorer un risque d’en dégrader un autre. En recherche opérationnelle, ces problèmes sont appelés problèmes multi-objectifs. Depuis les années 70, les chercheurs s’intéressent à ces problèmes que ce soit dans des domaines comme l’industrie (Stewart et al., 2008), la médecine (Ehrgott et Winz, 2008) ou encore l’économie (Metaxioti et Liagkouras, 2012). De ce fait, le développement d’algorithmes multi-objectifs pour les résoudre devient une nécessité. La principale utilisation de l’optimisation multi-objectifs dans la littérature est naturellement de résoudre de tels problèmes. Cependant, comme le soulignent Handl et Knowles (2008), il existe également une autre utilisation de l’optimisation multi-objectifs qui consiste à transformer la nature d’un problème uni-objectif pour le rendre multi-objectifs et faciliter sa résolution. Par exemple, il est possible de retirer les contraintes d’un problème en associant chacune d’entre elles à une nouvelle fonction objectif (MezuraMontes et Coello, 2008a).

Afin de mieux comprendre les enjeux et les particularités de l’optimisation multi-objectifs, les concepts importants de ce domaine sont décrits dans la première partie de ce chapitre. La deuxième partie, quant à elle, expose différentes métriques qui permettent de mesurer la qualité d’un ensemble de solutions obtenues. Ensuite, une classification concepteur des méthodes de résolution est introduite et chaque catégorie de méthodes est brièvement présentée. Les deux dernières parties se focalisent principalement sur les métaheuristiques basées sur une population qui utilisent directement les notions de Pareto. Les techniques et stratégies utilisées par chacun des algorithmes sont décrites.

DÉFINITIONS ET CONCEPTS IMPORTANTS DE L’OPTIMISATION MULTIOBJECTIFS

FORMULATION D’UN PROBLÈME MULTI-OBJECTIFS

Un problème d’optimisation uni-objectif cherche à minimiser une fonction objectif f dans un espace de recherche S et sous certaines contraintes. Cette fonction associe à chaque solution réalisable, c’est-à-dire qui respecte les contraintes, une valeur de fonction objectif qui est généralement un réel. Un problème peut être associé à des variables de décision qui forment l’espace de recherche. Si le nombre de variables est au moins de deux, on peut alors parler de vecteur de décision. Ces variables de décision sont divisées en deux types : les variables discrètes et les variables continues. Les variables discrètes peuvent prendre des valeurs appartenant à un ensemble fini ou à un ensemble infini dénombrable (e.g. : ensemble des entiers naturels). Au contraire, les variables continues peuvent prendre une infinité de valeurs comprises dans un intervalle défini (e.g. ensemble des réels compris dans [0,5]). En fonction du type de variables utilisées, on parlera de problème à variables continues (problème continu), de problème à variables discrètes (problème combinatoire) ou encore de problème mixte qui utilise les deux types de variables.

Il faut noter que tout problème de maximisation peut se ramener à un problème de minimisation puisque max(f(x)) = −min(−(f(x))). En outre, résoudre un problème de minimisation uni-objectif revient à chercher l’optimum global de la fonction objectif, c’est-à-dire trouver une solution s∗ qui a la plus petite valeur de fonction objectif. Autrement dit, trouver s∗, tel que ∀s ∈ S, f(s∗) ≤ f(s). Cette recherche est possible, car il existe une relation d’ordre clairement définie dans l’ensemble R. Dans un problème multi-objectifs, contrairement à un problème uni-objectif, plusieurs fonctions objectif sont à minimiser.

À chaque vecteur de décision est associé un vecteur objectif y = (y1, y2,…, yM) où yi= fi(x). Le but de la résolution d’un problème multi-objectifs est de minimiser ce vecteur objectif. L’utopie serait de trouver le vecteur qui optimise chacune des fonctions objectif. Or, dans la plupart des problèmes de la vie réelle, ce vecteur n’existe pas, car les objectifs sont conflictuels. Par la suite, l’espace contenant les vecteurs objectif sera appelé espace objectif. De plus, alors que dans un problème uni-objectif, une relation d’ordre est clairement définie pour les valeurs de la fonction objectif (ensemble R), cette relation n’existe pas pour des vecteurs objectif. Il est donc nécessaire d’introduire différents concepts qui permettent tout de même de comparer des vecteurs objectif. Ces concepts sont utilisés par certains algorithmes de résolution présentés par la suite.

CARACTÉRISTIQUES DU FRONT PARETO

La facilité d’un algorithme à obtenir des solutions bien réparties dans l’espace objectif dépend, en partie, des caractéristiques du front Pareto. La structure de ce dernier peut être convexe ou non-convexe (concave) et continue ou discontinue. Pour un problème à deux objectifs, un front Pareto est dit convexe si, dans l’espace objectif, tout segment qui lie deux solutions Pareto optimales est inclus dans la région des solutions réalisables. Cette définition peut être étendue à plus de deux objectifs en augmentant le nombre de dimensions.

MÉTRIQUES POUR MESURER LA QUALITÉ D’UN ENSEMBLE DE SOLUTIONS

Les performances d’un algorithme de résolution uni-objectif s’évaluent essentiellement par sa capacité à fournir une solution qui minimise la fonction objectif. Il est plus difficile d’évaluer l’efficacité d’une heuristique multi-objectifs puisqu’il est nécessaire d’analyser un ensemble de solutions associées à des vecteurs objectif. Le but des approches de résolution est de trouver une approximation la plus proche possible du front Pareto et qui couvre une grande partie de l’espace objectif. Comme il n’est pas aisé d’évaluer ces deux aspects en même temps à travers une unique métrique, le calcul de plusieurs métriques est généralement nécessaire. Ainsi, dans la littérature, des métriques unaires et binaires ont été proposées pour évaluer les performances de méthodes de résolution et se focalisent soit sur la convergence soit sur la diversité des solutions. Il est important de noter que le calcul des métriques s’effectue dans la plupart des cas une fois l’exécution de l’algorithme de résolution terminé et donc n’altère pas le processus de recherche ni le temps de calcul. Par la suite, les métriques qui seront utilisées dans le cadre de cette thèse sont présentées. Elles constituent une liste non exhaustive des méthodes d’évaluation existantes et figurent parmi les plus utilisées dans la littérature.