Soutenance mémoire
La métrique d’Espacement
La métrique proposée par Deb et al. (2000) considère que l’ensemble PO théorique est connu. Elle mesure la distribution des solutions sur un ensemble PO. Essentiellement, la métrique calcule une distance euclidienne entre les solutions et normalise le résultat avec la cardinalité de l’ensemble PO théorique. Le principal défaut de cette métrique est qu’elle n’est adaptée que pour les problèmes à deux objectifs.
La dernière section a présenté trois métriques analysant la distribution et cinq métriques analysant la qualité des solutions d’ensembles PO. Les métriques choisies dans le cadre de l’analyse des résultats de ce mémoire sont l’Hypervolume, la Couverture et l’Espacement.
Objectifs et méthodologie de la recherche
La revue de la littérature a permis de faire ressortir plusieurs observations qui permettent de poser les différents objectifs. La première observation est que beaucoup d’entreprises de différents secteurs d’activité sont confrontées à des problèmes d’ordonnancement multi-objectifs. Les problèmes traités en théorie contiennent généralement des aspects se rapprochant des contextes réels. Toutefois, la simplification de certains aspects tels que la considération uni-objectif des problèmes éloigne la théorie de la pratique. Arroyo et al (2011) proposent un problème multi-objectifs (MURMO) qui considère plusieurs aspects des contextes réels dont la considération multi-objectifs. La seconde observation est qu’à notre connaissance, une seule méthode résout MURMO : le MOVNS3 (Arroyo et al. 2011), qui est une méthode de recherche dans la structure de voisinage utilisant l’approche Pareto. L’observation suivante concerne les approches Pareto, qui représentent une des façons de traiter la fonction objectif pour résoudre un PMO. Cette approche utilise la notion dominance qui est discutée à la Section 2.4. Pour finir les observations, plusieurs méthodes ont été adaptées pour solutionner des PMO avec une approche Pareto. Les AE connaissent de bons résultats avec NSGA-II (Deb et al. 2000), PMSMO(Zinflou et al. 2008), GISMOO (Zinflou et al. 2012), SPEA (Zitzler et al. 2001) et PESA-II (Corne et al. 2001). Également, plusieurs méthodes de la famille d’OCF Pareto sont présentées au Tableau 2. Parmi les méthodes multi-colonies, on rettrouve le Ant Colony Optimization for bi-objective Quadratic Assignment Problem (ACO-bQAP) (López-Ibáñez et al. 2004) et le Multi-Objective Ant Colony Optimization (MOACO) (Berrichi et al. 2010). En ce qui concerne les méthodes uni-colonie, le Multi-Objective-ant (MO-ant) (Liu et al. 2005) et le Crowding Population-based Ant colony Optimization (CPACO) (Angus 2007) sont par exemple identifiées.
L’objectif principal de ce mémoire est de proposer des approches de résolutions multi-objectives performantes afin de permettre un rapprochement entre la théorie et la pratique. La revue de la littérature a démontré qu’un écart entre la théorie et la pratique existe. Le problème MURMO, utilisé comme problème de support dans ce mémoire, permet de traiter certains aspects représentatifs de contexte réel.
La méthodologie utilisée pour atteindre cet objectif est de présenter des méthodes Pareto pour résoudre le problème de support MURMO. Étant donné qu’une seule méthode a été proposée jusqu’à maintenant pour le problème MURMO, le MOVNS3, ce mémoire propose donc l’adaptation de trois algorithmes de la littérature pour le problème afin d’avoir un ensemble de résultats de référence : NSGA-II (Deb et al. 2000), PMSMO (Zinflou et al. 2008) et GISMOO (Zinflou et al. 2012). Ces adaptations ont fait l’objet d’un acte de conférence avec comité de lecture pour la conférence ROADEF 2013 (Gagné et al. 2013).
L’objectif principal engendre plusieurs objectifs secondaires qui seront présentés dans les prochains paragraphes. Le premier est de résoudre efficacement un PMO ayant des aspects traitant de contextes réels. Les solutions d’une méthode de résolution Pareto doivent converger vers le front Pareto et être bien distribuées le long de la frontière. L’objectif suggère aussi que le PMO doit avoir des aspects se rapprochant des contextes réels. Le PMO choisi est le problème MURMO.
Pour évaluer l’efficacité d’une méthode, l’ensemble des solutions non-dominées est analysé. Cette analyse s’effectue à l’aide de différentes métriques. Dans le cadre de ce mémoire, les métriques employées qui évaluent la qualité des solutions sont : l’Hypervolume (Zitzler 1999) et la Couverture (Zitzler 1999). Pour l’évaluation de la distribution des solutions, la métrique est l’Espacement (Schott 1995).
Le deuxième objectif secondaire consiste à proposer une comparaison équitable entre une méthode multi-colonies et une méthode uni-colonie. La revue de la littérature du mémoire présente un regroupement des méthodes multi-objectifs de la famille d’OCF en deux groupes : les méthodes multi-colonies et les méthodes uni-colonie. Les conclusions du regroupement sont que la majorité des approches d’OCF sont basées sur l’AS, la version de base des algorithmes dans ce domaine, et que peu de méthodes utilisent des concepts AE Pareto.
La méthode multi-colonies choisie est le bi-criterion ant multi-colony (BCMC) de Iredi et al (2001). Le BCMC est choisi car c’est une méthode multi-objectifs n’utilisant pas de concepts empruntés aux AE Pareto. Pour représenter les groupes des méthodes uni-colonie, l’approche d’OCF ant colony immune system for multiple objective optimization (ACISMOO), qui est une transposition de GISMOO adapté au problème MURMO, est utilisée. GISMOO a été choisi, car il s’agit de la méthode qui s’est avérée la meilleure parmi NSGA-II (Deb et al. 2000), PMSMO (Zinflou et al. 2008) et GISMOO (Zinflou et al. 2012). Une comparaison équitable est proposée entre BCMC et ACISMOO pour le problème MURMO. Il est possible de qualifier la comparaison d’équitable car les conditions d’expérimentation sont équivalentes pour les deux méthodes (Section 4.1). Outre les conditions d’expérimentation, l’ensemble des méthodes comparées dans ce mémoire sont programmées à l’aide de MetLib. Cet outil propriétaire permet l’accès à plusieurs algorithmes tels que NSGA-II, PMSMO et GISMOO. Aussi, cette bibliothèque comprend plusieurs outils de gestion des solutions non-dominées. Un tel outil permet d’offrir un même environnement de programmation aux méthodes.
Le troisième objectif secondaire présente la transposition de concepts AE Pareto dans une approche d’OCF. La revue de la littérature démontre que peu d’approches d’OCF Pareto utilisent des concepts AE Pareto. Le tri par front du NSGA-II est utilisé dans les articles de Berrichi (2010) et Angus (2007). De plus, une méthode de niching comparable à un facteur d’isolement est employée dans l’article de Yang et al (2010). Toutefois, les concepts AE Pareto tels que le facteur de dominance et d’isolement améliorent les méthodes AE (Deb et al. 2000; Zinflou et al. 2012; Zinflou et al. 2008).
C’est par la transposition de GISMOO vers un ACS que cet objectif est répondu. Cette transposition permet l’utilisation de concepts AE Pareto tels que le facteur de dominance et le facteur d’isolement au sein de la méthode.
Le dernier objectif consiste à suggérer une bonification de la méthode ACISMOO. Les méthodes uni-colonie doivent permettre à chacune de leurs fourmis de converger vers le front Pareto ou de se diversifier. L’amélioration propose de faire varier les composantes de la fourmi de telle sorte qu’une fourmi peut converger ou se diversifier en cours d’exécution de la méthode. L’amélioration d’ACISMOO est comparée avec la version originale de l’algorithme. La performance des algorithmes est évaluée à l’aide des métriques.
La première amélioration d’ACISMOO est l’ajout de différentes visibilités. La seconde amélioration consiste à ce que chaque fourmi de la colonie calcule la visibilité de façon différente, donc si deux fourmis ont le même déterminant, elles ne sélectionnent pas nécessairement la même tâche. Ces améliorations apportent de la diversité à la version originale d’ACISMOO.
COMPARAISON MULTI/UNI-COLONIES POUR UN PROBLÈME DE MACHINE UNIQUE AVEC CARACTÉRISTIQUES SE RAPPROCHANT DE CONTEXTES RÉELS
Introduction
La machine unique est une configuration classique dans la littérature en ordonnancement. En industrie, les problèmes d’ordonnancement sont généralement plus complexes qu’une machine unique. Toutefois, il est possible de les décomposer en problèmes plus simples qui se modélisent en une machine unique. Par exemple, dans le problème de goulot d’étranglement dans un système de production complexe, le goulot peut être vu comme une machine unique. En optimisant le goulot, tout le système est optimisé (Pinedo 2012). D’ailleurs, la majorité des installations d’entreprises de service peuvent être modélisées avec une machine unique : coiffeuse, esthéticienne, garagiste, pour ne nommer que ceux-ci. L’intérêt académique est tout aussi grand. Pour une configuration de machine unique où chaque tâche a un temps d’exécution et une date de remise, l’objectif de minimisation du retard total est prouvé NP-difficile par Du et Leung (1990). Également avec la même configuration de machine unique, Wan et Yuan (2013) démontrent que la pénalité totale d’avance et retard est NP-difficile au sens fort. Des problèmes ayant une telle complexité créent une grande curiosité académique. Dans le but de se rapprocher des contextes réels, plusieurs extensions de la machine unique ont été proposées (Biskup et al. 2001; Graves et al. 1999; Hall et al. 1991; Liu et al. 2002; Tan et al. 1997). L’extension de la machine unique étudiée dans ce mémoire est celle proposée par Arroyo et al. (2011) intitulée MURMO et est présentée à la Section 3.2. Par la suite, une revue de la littéraire des méthodes traitant de ce problème est présentée à la Section 3.3. Le chapitre se poursuit avec une comparaison entre une méthode multi-colonies et une méthode uni-colonie pour la résolution du problème MURMO. Ces deux méthodes sont respectivement le bi-criterion ant multicolony (BCMC) à la Section 3.4.1 et le ant colony immune system for multiple objective optimization (ACISMOO) à la Section 3.4.2. Enfin, la Section 3.5 présente les améliorations proposées pour l’algorithme ACISMOO.
Définition du problème MURMO
Causé par des hypothèses simplificatrices émises en théorie de l’ordonnancement, l’écart entre les contextes pratique et académique est régulièrement présent. Toutefois, l’écart se réduit considérablement ces dernières années (Allahverdi et al. 2008). Le problème MURMO tend à réduire cet écart en proposant plusieurs caractéristiques associées aux contextes réels.
La première caractéristique est le réglage dépendant de la séquence. Son inverse, soit le réglage indépendant de la séquence, considère le temps de réglage comme négligeable ou inclus dans le temps d’exécution. Cependant, cette simplification n’est pas représentative de la plupart des contextes réels. Alors, il est nécessaire de considérer les temps de réglage comme étant distincts des temps d’exécution. Cette configuration du réglage est répandue en industrie car des activités industrielles ont des temps de réglage dépendant de la séquence par rapport à où toutes les activités ont des temps de réglage (Conner 2009; Panwalkar et al. 1973). D’ailleurs, plus de deux cents articles traitant de réglage dépendant de la séquence ont été dénombrés par Zhy et Wilhelm (2006).
La deuxième caractéristique est la présence d’une fenêtre d’échéance pour chaque tâche. Ces fenêtres génèrent des pénalités d’avance ou de retard, si la tâche ne se termine pas dans cette fenêtre d’échéance. Dans la littérature, il est courant de traiter les pénalités d’avance ou de retard avec une date de remise commune pour l’ensemble des tâches (Gordon et al. 2002). Que l’on soit dans le cas d’une date commune ou de fenêtres d’échéance, le traitement des pénalités d’avance et de retard est fréquent en industrie ayant un environnement de juste-à-temps. Ainsi, dans un tel environnement, une tâche doit se terminer le plus près possible de sa date de remise. Dans le cas qui occupe ce mémoire, la date de remise est représentée par une fenêtre d’échéance bornée par une date due au plus tôt et une date due au plus tard. Alors, la tâche doit se terminer aussi près que possible de la date due au plus tôt sans dépasser la date due au plus tard. Un temps de terminaison en avance occasionne des coûts supplémentaires de possessions de marchandises. Ces coûts sont traduits en théorie par une pénalité émise à la tâche ayant un temps de terminaison en avance. À l’inverse, un temps de terminaison en retard occasionne des pertes de clients et/ou de réputation. En théorie, cette perte est également traduite par une pénalité de retard émise à la tâche.
La troisième caractéristique associée aux contextes réels du problème MURMO est la possibilité d’insérer des temps morts dans l’ordonnancement de la machine unique. Les temps morts ne sont habituellement pas permis car ils augmentent le temps total passé dans le système des produits sans toutefois permettre d’en produire davantage. D’ailleurs, de tels temps morts portent les dernières tâches de l’ordonnancement à avoir des pénalités de retard. Néanmoins, pour le problème MURMO, les temps morts sont plus qu’utiles. Ils permettent d’ordonnancer les tâches dans leur fenêtre d’échéance et ainsi éviter les pénalités d’avance et de retard. Tel que l’illustre la Figure 10, la tâche n’aurait pas pu être insérée dans sa fenêtre d’échéance sans avoir préalablement inséré un temps mort.
En pratique, ces temps morts peuvent être utilisés pour la mise au point de la machine. Il est à noter que certains environnements industriels ne peuvent pas avoir de temps morts dans l’ordonnancement de leur machine, alors une forte pénalité peut être appliquée. Toutefois, cette configuration industrielle ne fait pas partie de ce mémoire.
La quatrième caractéristique est la nature multi-objectifs du problème MURMO. Arroyo et al. (2011) mentionnent que la majorité des travaux en machine unique sont uni-objectif. Toutefois, les décideurs sont appelés à résoudre des problèmes ayant plusieurs objectifs contradictoires et à optimiser simultanément. Dans l’ordonnancement de la machine unique, différentes natures d’objectifs peuvent être considérés. Les objectifs les plus fréquemment traités sont la minimisation du temps total de terminaison (makespan), la minimisation du temps total passé dans le système (flowtime) et la minimisation du retard total (total tardiness). Ces objectifs sont justifiés en pratique. Le makespan est lié à la maximisation de l’utilisation des ressources. Pour le flowtime, il est plutôt lié aux temps de production des produits. Aussi, le total tardiness est lié aux dates de remise. Il est à noter que l’objectif total tardiness est le plus important en ordonnancement (Wisner et al. 1995). Le problème visé par ce mémoire traite de la minimisation du flowtime et de la minimisation des pénalités d’avance et de retard.
Méthode de résolution du problème MURMO proposée dans la littérature
À la lumière de la revue de la littérature, très peu d’articles traitent de ce problème. Avec la présentation du problème MURMO, Arroyo et al.(2011) proposent le « multi-objective variable neighborhood search 3 » (MOVNS3). Cette méthode est une recherche dans le voisinage incluant un processus d’intensification basé sur la dominance au sens Pareto ainsi que deux structures de voisinage adaptées au problème. Étant donné le peu de recherches réalisées sur le problème MURMO, ce mémoire a généré un ensemble de résultats pouvant servir pour une comparaison future. Pour ce faire, ce mémoire propose l’adaptation de trois méthodes de la littérature pour le problème MURMO, soit NSGA-II (Deb et al. 2000), PMSMO (Zinflou et al. 2008) et GISMOO (Zinflou et al. 2012). Ces trois méthodes de la littérature sont comparées avec MOVNS3 sur les instances utilisées par Arroyo et al (2011). Les conditions d’expérimentation sont détaillées à la Section 4.1. Cette comparaison a fait l’objet d’un acte de conférence lors de la conférence ROADEF 2013 à Troyes.
Comparaison multi/uni-colonies
Tel qu’expliqué dans les sections précédentes, le problème traité (MURMO) contient plusieurs caractéristiques associées à des contextes réels. À notre connaissance, il y a une seule méthode qui résout le problème MURMO, le MOVNS3. Le mémoire propose l’adaptation de trois algorithmes de la littérature réputés performants : NSGA-II, PMSMO et GISMOO. L’étape suivante bonifie les méthodes de résolution du problème MURMO en proposant des méthodes de résolution constructives.
Dans l’optique d’enrichir la littérature, ce mémoire considère les méthodes de résolution dites constructives : les approches OCF. Lors de la création d’une méthode de résolution avec les approches OCF en multi-objectifs, plusieurs décisions doivent être prises : quelles approches d’OCF utiliser, combien de colonies ou quels concepts d’AE utilisés? Cette section présente deux méthodes de résolution à l’aide d’approche OCF : une première multi-colonies et une seconde uni-colonie. La comparaison de ces deux méthodes va permettre de connaître l’impact d’utiliser une ou plusieurs colonies dans la résolution du problème bi-objectifs MURMO. De plus, il sera testé si l’adaptation de concepts AE Pareto à des algorithmes d’OCF, tel que les facteurs de dominance et d’isolement, permet d’améliorer les résultats. Les résultats de ceux-ci sont présentés à la Section 4.2. Les Sections 3.4.1 et 3.4.2 présentent respectivement les approches multi-colonies et uni-colonie utilisées.
Méthode multi-colonies : bi-criterion ant multi-colony (BCMC) pour la résolution du problème MURMO
Cette approche a été proposé par Iredi et al (2001). Cette méthode a été choisie car elle n’utilise aucun concept d’AE Pareto. De plus, elle est basée sur l’approche d’OCF AS et elle est multi-colonies. Pour finir, le problème traité par les auteurs se rapproche du problème MURMO, donc permet une adaptation plus fidèle de la méthode. Cette section est réservée à l’adaptation du BCMC pour la résolution du problème MURMO.
BCMC est un algorithme multi-colonies, alors une règle d’échange entre les colonies est obligatoire pour s’assurer d’avoir un ensemble PO continu. La règle utilisée pour l’adaptation du problème MURMO est celle de l’Équation 2.14 présentée à la Section 2.6.2.1. Cette règle est choisie car elle est celle qui trouve un plus grand nombre de solutions dans le centre de l’ensemble PO sur de petits nombres de colonies (2 ou 5).
Dès que le nombre de colonies dépasse dix, la différence entre cette règle et celle de l’Équation 2.13 est minime (Iredi et al. 2001).
BCMC a pour base l’approche d’OCF AS, alors il y a présence d’une règle de choix dont la probabilité de sélectionner la tâche après la tâche dans la fourmi est décrite à l’Équation 3.3.
Méthode uni-colonie : ant colony immune system for multiple objectif optimization (ACISMOO) pour la résolution du problème MURMO
ACISMOO est une transposition de la méthode GSIMOO, présentée à la Section 2.5.3, vers un ACS. Pour permettre une comparaison équitable entre le BCMC et l’ACISMOO, la visibilité et l’évaluation de la fourmi (OTA) demeurent les mêmes. La transposition de GISMOO vers un ACS a été choisie car GISMOO est une méthode évolutionnaire multi-objectifs qui connaît les meilleurs résultats lors de la comparaison entre MOVNS3, NSGA-II ET PMSMO. Cette comparaison est présentée à la Section.
Également, cette transposition permet d’avoir une approche OCF qui utilise les facteurs de dominance et d’isolement dans son processus.
La transposition de GISMOO vers un ACS se réalise en remplaçant la partie génétique par un algorithme d’ACS Pareto. Dit autrement, 50% de la population (colonie) est construite à l’aide d’un ACS et l’autre 50% sera produite par un système immunitaire artificiel comme dans l’algorithme original. Le but est de spécialiser les fourmis (solutions) afin de permettre la convergence des fourmis vers l’ensemble PO ou afin de diversifier la recherche de solutions. La Figure 13 présente le pseudo-code d’ACISMOO.
Amélioration d’ACISMOOmodif
La version d’ACISMOO présentée à la Section 3.4.2 a été réalisée dans le but d’être une méthode proposant une comparaison équitable avec BCMC. La présente section propose des améliorations à ACISMOO au niveau de la visibilité, de l’emplacement dans l’algorithme pour calculer l’évaluation de la fourmi (OTA) ainsi qu’une amélioration au niveau de la variation des fourmis. La variation des fourmis est vue ici comme étant la modification à la fin de chaque cycle des paramètres dynamiques au sein des fourmis. L’intention derrière ces améliorations est de rendre les fourmis de la colonie plus spécialisées, ce qui va permettre d’augmenter leur convergence ou leur diversification.
L’amélioration de la visibilité se situe au niveau de la visibilité du premier objectif : la visibilité liée aux pénalités d’avance et de retard. L’initialisation du déterminant demeure telle qu’expliqué à la Section 3.4.1. La différence est qu’un déterminant considère plusieurs visibilités. Une telle considération permet à deux fourmis avec le même déterminant de sélectionner des tâches différentes, ce qui apporte de la diversité. Les prochains paragraphes définissent les déterminants ainsi que les visibilités considérées.
Le déterminant est initialisé quand l’ensemble des tâches à ordonnancer à une position dans la fourmi sont en avance. Dit autrement, l’ensemble des tâches disponibles à la position dans la fourmi seront ordonnancées avant leur fenêtre d’échéance. Il est de rigueur de rappeler que le calcul de l’avance est effectué tel que décrit l’Équation 3.12
Tel que le démontre le Tableau 8, certaines visibilités privilégient les petits temps d’exécution, ce qui permet aux autres tâches d’avoir la chance d’être insérées dans leur fenêtre d’échéance. D’autres visibilités vont privilégier un coût de pénalité de retard élevé. Cette stratégie permet d’ordonner une tâche qui a un coût de pénalité de retard élevé, donc il est sûr qu’elle ne sera pas en retard.
L’amélioration d’ACISMOO qui est maintenant présentée est l’emplacement de l’évaluation de la fourmi (OTA). L’ACISMOO présenté à la Section 3.4.2 et BCMC évaluent la fourmi quand celle-ci est entièrement construite. La faiblesse de cet emplacement est qu’OTA est un algorithme qui peut modifier considérablement les dates de fin des tâches ordonnancées en raison de l’insertion de temps mort. L’ordonnancement des tâches d’une fourmi qui semblent adéquate peut devenir désastreux après OTA. Toutefois, les résultats de ACISMOO de la Section 3.4.2 portent à croire qu’évaluer la fourmi après la construction génère quand même de bons résultats. Malgré ce point, la visibilité liée à la pénalité d’avance et de retard est basée en partie sur le temps d’exécution total de la fourmi à un moment précis. De ce fait, en évaluant la fourmi avec OTA après sa construction, la sélection d’une tâche à l’aide de la règle de transition utilise une approximation de . Avec ces points en main, une amélioration est proposée dans ce mémoire. L’évaluation de la fourmi peut être réalisée à deux emplacements différents : après la construction de la fourmi (comme ACISMOO de la Section 3.4.2 et BCMC) ou après l’insertion d’une tâche dans la fourmi. Ce dernier emplacement permet d’avoir un exact à chaque fois qu’une tâche est sélectionnée. Tel que dit précédemment, l’évaluation à la fin de la construction génère somme toute de bons résultats, donc chaque fourmi de la colonie a un emplacement pour l’évaluation qui est donné aléatoirement en début d’algorithme. L’emplacement donné à une fourmi ne varie pas au travers des cycles.
La dernière amélioration apportée à ACISMOO est la variation des fourmis. La phase de variation des fourmis demeure à la même place dans l’algorithme, soit à la fin de chaque cycle. Également, la variation d’une fourmi est dirigé par le nombre de solutions non-dominées insérées dans l’archive. L’amélioration proposée, dans cette section, est d’ajouter de nouveaux paramètres dynamiques à la fourmi. Ces nouveaux paramètres dynamiques représentent quelle visibilité est utilisée pour chaque déterminant. Des fourmis avec un même déterminant peuvent ainsi avoir une visibilité différente. Lors de la phase de variation, la visibilité peut être modifiée. Donc les paramètres dynamiques qui sont sujets à être modifiés pour chaque fourmi sont dorénavant : le seuil de la règle de transition , les exposants liées à l’importance de visibilité et ainsi que les visibilités pour chaque déterminant.
EXPÉRIENCES NUMÉRIQUES ET RÉSULTATS
Conditions d’expérimentation
Les méthodes de résolution ont été implémentées en C++ avec Visual Studio 2008 sur un ordinateur ayant un processeur Intel Core i-7-2600 @3.40ghz avec 12 go de RAM. Chacune des méthodes est exécutée cinq fois par instance pour plus de robustesse. Dans la même optique, le résultat maximal des cinq exécutions est conservé pour l’analyse. Les paramètres d’exécution sont divisés en trois catégories : ceux pour les méthodes NSGA-II, PMSMO et GISMOO, ceux pour la méthode BCMC ainsi que ceux pour les méthodes ACISMOO et ACISMOOmodif. Toutefois, le critère d’arrêt représenté par le nombre d’évaluation est déterminé à 100 000 et les mutations sont les mêmes pour l’ensemble des méthodes.
Les paramètres utilisées pour NSGA-II, PMSMO et GISMOO sont déterminés en tenant compte des recommandations des auteurs respectifs : la probabilité de mutation à 0,06, la taille de la population est de 100 individus et la méthode de croisement est le Random Maximal Preservative Crossover (RMPX) (Sioud et al. 2009). Le RMPX est démontré performant sur le problème d’expérimentation et ce dernier se rapproche du problème MURMO.
Résultats et analyse
Comparaison globale des solutions des méthodes adaptées
Plusieurs méthodes de résolution ont été adaptées pour le problème MURMO dans ce mémoire. Le Tableau 9 présente l’Hypervolume sous forme de trois groupes. Le premier est la méthode qui provient de la littérature dont les résultats ont été offerts par les auteurs, le MOVNS3 (Arroyo et al. 2011). Le deuxième groupe est l’ensemble de méthodes adaptées au problème MURMO dans l’optique de confectionner une collection de solutions pour comparaison future. Le troisième groupe est les approches d’OCF adaptées pour ce mémoire.
Les lignes du Tableau 9 représentent les groupes d’instances en fonction de la taille. En colonnes, il y a les méthodes. La moyenne des Hypervolumes se retrouve à la jonction d’une ligne et d’une colonne. Un bon Hypervolume est caractérisé par une grande aire sous la courbe de l’ensemble PO. L’analyse du Tableau 9 démontre que GISMOO (en gris) a un meilleur Hypervolume parmi toutes les méthodes. BCMC et MOVNS3 sont près l’une de l’autre en termes d’Hypervolume. ACISMOOmodif est légèrement supérieur à ACISMOO. Aussi, ACISMOOmodif a un Hypervolume similaire à celui de GISMOO.
Pour permettre une bonne lisibilité de la métrique Couverture (Tableau 10), trois méthodes sont retenues du Tableau 9. Le choix des méthodes est guidé par les performances des méthodes à la métrique Hypervolume et l’origine des méthodes. Les méthodes sont : MOVNS3 car elle est la méthode proposée dans le travail original de présentation du problème MURMO (Arroyo et al. 2011), GISMOO car elle est la meilleure méthode connue pour résoudre le problème MURMO et ACISMOOmodif car c’est la méthode parmi les approches d’OCF ayant eu la meilleure performance pour l’Hypervolume.
Comparaison BCMC et ACISMOO
Cette comparaison porte sur une approche OCF multi-colonies, le BCMC, avec une approche OCF uni-colonie, l’ACISMOO. L’analyse des ensembles PO à l’aide de métriques va permettre de voir les forces et faiblesses des deux approches. Cette section présente en premier les métriques évaluant la qualité des solutions des ensembles PO. En deuxième, à la Section 4.2.2.2 présente la métrique évaluant la distribution des solutions des ensembles PO. Étant donné la nature bi-objectifs du problème MURMO, il possible de représenter sur un plan les ensembles PO.
Métriques mesurant la qualité des solutions des ensembles PO
La qualité des solutions d’un ensemble PO par rapport à un autre permet de connaitre à quel point une méthode a généré des solutions qui ont convergé vers le front Pareto. La première métrique analysée est l’Hypervolume. Le Tableau 12 présente la comparaison entre l’Hypervolume d’ACISMOO et de BCMC.
Le Tableau 13 est sous la même forme que le Tableau 10, à la différence qu’il est pour deux méthodes. En moyenne, ACISMOO domine 56% des solutions de BCMC. Une telle dominance d’ACISMOO confirme les résultats de l’Hypervolume. Les résultats de ces deux métriques permettent de conclure que l’utilisation de concepts AE Pareto génère des solutions de meilleure qualité.
Métriques mesurant la distribution des solutions des ensembles PO
Un ensemble PO est évalué selon qu’il converge vers le front Pareto (qualité) et selon la répartition des solutions sur la frontière. Le Tableau 14 présente la métrique Espacement qui estime la distribution des solutions pour un ensemble PO.
Le Tableau 14 est sous la même forme que le Tableau 11. La première constatation est que les deux ensembles PO sont disjoints car la mesure de l’Espacement est loin de zéro. Généralement, la répartition des solutions d’ACISMOO est meilleure que BCMC. Rappelons qu’ACISMOO a un nombre total de fourmis fixe à 20 et BCMC a un nombre total de fourmis qui varie selon le groupe d’instance et est basé sur le nombre de tâches. Avec le même nombre total de fourmis, soit le groupe à 20 tâches, ACISMOO a une meilleure répartition. Ceci démontre que les mécanismes de diversité utilisés dans ACISMOO, tel que les paramètres dynamiques des fourmis et le nombre de clones selon le facteur d’isolement permettent de distribuer les solutions sur le front Pareto. Pour sa part, BCMC base essentiellement sa diversité sur le nombre total de fourmis, ce qui apporte peu de performance pour le problème MURMO.
|
Table des matières
CHAPITRE 1
INTRODUCTION
CHAPITRE 2
OPTIMISATION MULTI-OBJECTIFS ET MÉTAHEURISTIQUES PARETO
2.1. INTRODUCTION
2.2. PROBLÈME MULTI-OBJECTIFS (PMO)
2.3. CLASSIFICATION DES MÉTHODES DE RÉSOLUTION POUR PMO
2.3.1 Classification décideur
2.3.2 Classification concepteur
2.4. NOTION DE DOMINANCE ET OPTIMUM PARETO
2.5. ALGORITHME ÉVOLUTIONNAIRE (AE) PARETO
2.5.1. Non-dominated Sorting Genetic Algorith II (NSGA-II)
2.5.2. Pareto Memetic Strategy for Multiple Objective optimization (PMSMO)
2.5.3. Genetic Immune Strategy for Multiple Objective Optimization (GISMOO)
2.6. OPTIMISATION PAR COLONIE DE FOURMIS PARETO
2.6.1. Problème de voyageur de commerce (VC) pour des approches OCF
2.6.2. OCF multi-objectifs Pareto
2.7. LES MÉTRIQUES
2.7.1. La métrique Rapport d’erreur
2.7.2. La métrique Espacement
2.7.3. La métrique Hole Relative Size (HRS)
2.7.4. La métrique Hypervolume (H)
2.7.5. La métrique Couverture
2.7.6. La métrique Différence
2.7.7. La métrique de Laumanns
2.7.8. La métrique d’Espacement
2.8. OBJECTIFS ET MÉTHODOLOGIE DE LA RECHERCHE
CHAPITRE 3
COMPARAISON MULTI/UNI-COLONIES POUR UN PROBLÈME DE MACHINE UNIQUE AVEC CARACTÉRISTIQUES SE RAPPROCHANT DE CONTEXTES RÉELS
3.1 INTRODUCTION
3.2 DÉFINITION DU PROBLÈME MURMO
3.3 MÉTHODE DE RÉSOLUTION DU PROBLÈME MURMO PROPOSÉE DANS LA LITTÉRATURE
3.4 COMPARAISON MULTI/UNI-COLONIES
3.4.1 MÉTHODE MULTI-COLONIES : BI-CRITERION ANT MULTI-COLONY (BCMC) POUR LA RÉSOLUTION DU PROBLÈME MURMO
3.4.2 MÉTHODE UNI-COLONIE : ANT COLONY IMMUNE SYSTEM FOR MULTIPLE OBJECTIF OPTIMIZATION (ACISMOO) POUR LA RÉSOLUTION DU PROBLÈME MURMO
3.5 AMÉLIORATION D’ACISMOOMODI
CHAPITRE 4
EXPÉRIENCES NUMÉRIQUES ET RÉSULTATS
4.1 CONDITIONS D’EXPÉRIMENTATION
4.1.1. Les instances
4.2 RÉSULTATS ET ANALYSE
4.2.1. Comparaison globale des solutions des méthodes adaptées
4.2.2. Comparaison BCMC et ACISMOO
4.2.3. Amélioration ACISMOO
4.3 OBSERVATIONS LIÉES À LA CONCEPTION DES INSTANCES
4.4 TEMPS D’EXÉCUTION
CHAPITRE 5
CONCLUSION
BIBLIOGRAPHIE
Télécharger le rapport complet
