Personal tools
Laboratoire d'InfoRmatique en Image et Systèmes d'information

Skip to content. | Skip to navigation

Laboratoire d'InfoRmatique en Image et Systèmes d'information
UMR 5205 CNRS / INSA Lyon / Université Claude Bernard Lyon 1 / Université Lumière Lyon 2 / École Centrale de Lyon
You are here: Home > publis

PhD thesis

Optimisation multi-objectifs par colonies de fourmis : cas des problèmes de sac à dos [PDF]
Ines Alaya [LIRIS]
5/2009
Établissement : Université Claude Bernard Lyon 1 et ENSI Tunis
Soutenue le May 05, 2009
Jury
M. Albert Patrick, IBM/Ilog, Paris Examinateur
M. Deville Yves, UCL, Louvain-la-neuve, Belgique Rapporteur
M. Jolion Jean-Michel, LIRIS, Lyon Président
M. Ghédira Khaled, ENSI, Tunis, Tunisie Co-directeur
Mme Solnon Christine, LIRIS, Lyon Directeur
Contact : christine.solnon@liris.cnrs.fr

TEL : tel-00603780

Résumé

Dans cette thèse, nous nous intéressons à l'étude des capacités de la métaheuristique d'optimisation par colonie de fourmis (Ant Colony Optimization - ACO) pour résoudre des problèmes d’optimisation combinatoires multi-objectifs. Dans ce cadre, nous avons proposé une taxonomie des algorithmes ACO proposés dans la littérature pour résoudre des problèmes de ce type. Nous avons mené, par la suite, une étude expérimentale de différentes stratégies phéromonales pour le cas du problème du sac à dos multidimensionnel mono-objectif. Enfin, nous avons proposé un algorithme ACO générique pour résoudre des problèmes d'optimisation multi-objectifs. Cet algorithme est paramétré par le nombre de colonies de fourmis et le nombre de structures de phéromone considérées. Il permet de tester et de comparer, dans un même cadre, plusieurs approches. Nous avons proposé six variantes de cet algorithme dont trois présentent de nouvelles approches et trois autres reprennent des approches existantes. Nous avons appliqué et comparé ces variantes au problème du sac à dos multidimensionnel multi-objectifs. Après une étude comparative des différentes variantes suivant différentes métriques de performance, nous avons trouvé qu’une nouvelle variante proposée trouve globalement les meilleurs résultats. Cette variante utilise une idée relativement nouvelle puisqu'elle utilise une seule colonie de fourmis et une structure de phéromone pour chaque objectif, et les fourmis considèrent aléatoirement à chaque étape de construction un objectif à optimiser.

Abstract

In this thesis, we investigate the capabilities of Ant Colony Optimization (ACO) metaheuristic to solve combinatorial and multi-objective optimization problems. First, we propose a taxonomy of ACO algorithms proposed in the literature to solve multi-objective problems. Then, we study different pheromonal strategies for the case of mono-objective multidimensional knapsack problem. We propose, finally, a generic ACO algorithm to solve multi-objective problems. This algorithm is parameterised by the number of ant colonies and the number of pheromone structures. This algorithm allows us to evaluate and compare new and existing approaches in the same framework. We compare six variants of this generic algorithm on the multi-objective multidimensional knapsack problem.

BibTex

Download

@PhDThesis{Liris-4147,
  title         = {{Optimisation multi-objectifs par colonies de fourmis : 
    cas des problèmes de sac à dos}},
  author        = {Ines {Alaya}},
  year          = {2009},
  month         = may,
  school        = {Université Claude Bernard Lyon 1 et ENSI Tunis},
  type          = {Thèse de Doctorat en Informatique},
   language      = {fr},
  url           = {http://liris.cnrs.fr/publis/?id=4147}
}