Informations
Directeur de thèse :
Année de début :
Fin 2012
Université :
Université Constantine 2
Soutenance
Date de soutenance :
23 Février 2017
Membres de Jury :
Nacer-Eddine Zarour
Foudil Cherif
Salim Bitam
Amer Draa
Abdesslem Layeb
Manuscrit
Téléchargement :
Détails
Titre :
Méthodes bio-inspirées pour le problème du plus court chemin multi-objectif

Résumé :

Le problème du plus court chemin constitue l’un des problèmes d’optimisation les plus étudiés depuis les années cinquante. Son importance réside dans l’étendue des capacités à refléter d’autres problèmes aussi bien académiques que réels. La variante la plus connue est le problème du voyageur de commerce qui consiste à trouver le chemin optimal reliant tous les nœuds dans un graphe en se basant sur un seul objectif. Cependant, la complexité du monde réel nécessite la prise en compte de plusieurs autres critères, souvent conflictuels, tels-que ceux liés à l’aspect économique, environnemental et social. Le problème du voyageur de commerce multi-objectif (Multi-Objective Traveling Salesman Problem MOTSP) est NP difficile et nécessite donc pour le résoudre le recours aux méthodes d’optimisation multi-objectif.

Dans cette optique nous proposons, dans cette thèse, deux méthodes bio-inspirées multi-objectifs pour la résolution du MOTSP, à savoir l’algorithme d’optimisation multiobjectifparlesréactionschimiques(MOCRO)etl’algorithmed’optimisationmulti-objectif par les réactions chimiques basé décomposition (MOCRO/D). La première méthode est une adaptation de l’algorithme mono-objectif des réactions chimiques à travers l’intégration des concepts multi-objectifs de NSGA2 [Deb et al., 2002]. En outre, une version simplifiéedeMOCROaétéproposéepourminimiserlenombredesparamètresutilisés.La deuxième méthode MOCRO/D s’articule sur les concepts des réactions chimiques et les principes de l’algorithme évolutionnaire multi-objectif basé décomposition [Zhang et Li, 2007]. MOCRO/D décompose le MOTSP en sous-problèmes et les traite en intégrant des connaissances spécifiques pour cibler les régions prometteuses du domaine de recherche. Les études expérimentales des approches proposées ont montré de bonnes performances en matière de convergence et de diversité.

Finalement, comme application directe au problème du plus court chemin multi-objectif, nous nous sommes intéressés aux énormes impacts négatifs sociaux et environnementaux causés par le transport. A ce titre, nous proposons une nouvelle variante socio-environnementale du MOTSP. Pour résoudre ce problème, MOCRO a été utilisé et a donné de bons résultats.


Mots clés :
Optimisation multi-objectif Problème du voyageur de commerce multi-objectif Optimisation inspirée des réactions chimiques Impacts socio-environnementaux.


Abstract:

The shortest path problem is one of the most studied optimization problems since the fifties. Its importance is in its ability to reflect other problems both academic and real. The best-known variant is the traveling salesman problem that consists on finding the optimal path between all nodes in a graph based on one objective. However, the complexity of the real world requires the consideration of several criteria, frequently conflicting, such-as criteria related to the economic, environmental, and societal aspects. The multi-objective traveling salesman problem (MOTSP) is NP-hard and requires the use of multi-objective optimization methods.

In this context, two bio-inspired multi-objective methods for solving the MOTSP are proposed in this thesis. The first one is the multi-objective chemical reaction optimization (MOCRO). It represents an adaptation of the mono-objective chemical reaction algorithm to the multi-objective optimization through the integration of NSGA2 multi-objective concepts [Deb et al., 2002]. In addition, a simplified version of MOCRO has been proposed to reduce the number of its parameters. The second method is the multi-objective chemical reaction optimization-based decomposition (MOCRO/D). It uses the concepts of chemical reactions and the characteristics of the multi-objective evolutionary algorithm-based decomposition [Zhang et Li, 2007]. MOCRO/D decomposes the MOTSP into a set of sub-problems and processes by the incorporation of specific knowledge to target the promising areas. Experimental studies of the proposed approaches have shown a good performance in terms of convergence and diversity.

Finally, as direct application to the problem of the multi-objective shortest path, we are interested in societal and environmental negative impacts of transport. In this way, we have proposed a new societal and environmental variant of MOTSP. In order to solve this problem, MOCRO is used and it gives good results.


Keywords:
Multi-objective optimization Multi-objective traveling salesman problem Chemical reaction optimization Social and environmental impacts.