Optimisation multi-objectif par colonies de fourmis : cas des problèmes de sac à dos / Inès Alaya ; sous la direction de Christine Solnon et de Khaled Ghédira

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Programmation heuristique

Optimisation par colonies de fourmis

Optimisation combinatoire

Phéromones

Solnon, Christine (19..-.... ; chercheuse en informatique) (Directeur de thèse / thesis advisor)

Ghédira, Khaled (Directeur de thèse / thesis advisor)

Jolion, Jean-Michel (1961-....) (Président du jury de soutenance / praeses)

Deville, Yves (1960-....) (Rapporteur de la thèse / thesis reporter)

Ayeb, Béchir (Rapporteur de la thèse / thesis reporter)

Albert, Patrick (19..-....) (Membre du jury / opponent)

Université Claude Bernard (Lyon ; 1971-....) (Organisme de soutenance / degree-grantor)

Université de la Manouba (Tunisie) (Organisme de cotutelle / degree co-grantor)

École doctorale en Informatique et Mathématiques de Lyon (Ecole doctorale associée à la thèse / doctoral school)

LIRIS - Laboratoire d'Informatique en Image et Systèmes d'information (Rhône ; 2003-....) (Laboratoire associé à la thèse / thesis associated laboratory)

Institut Supérieur de Gestion : Stratégies d'Optimisation des Informations et de la connaissance (Tunisie) (Laboratoire associé à la thèse / thesis associated laboratory)

Résumé / Abstract : Dans cette thèse, nous nous intéressons à l'étude des capacités de la méta heuristique d'optimisation par colonie de fourmis (Ant Colony Optimization - ACO) pour résoudre des problèmes d’optimisation combinatoire multi-objectif. 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-objectif. 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-objectif

Résumé / 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 studydifferent pheromonal strategies for the case of mono-objective multidimensional knapsackproblem. We propose, finally, a generic ACO algorithm to solve multi-objective problems. Thisalgorithm is parameterised by the number of ant colonies and the number of pheromonestructures. This algorithm allows us to evaluate and compare new and existing approaches in thesame framework. We compare six variants of this generic algorithm on the multi-objectivemultidimensional knapsack problem