| Version imprimable |
| Etudes en recherche locale adaptative pour l'optimisation combinatoire (Study of local search adaptation for combinatorial optimization) | ||
Devarenne , Isabelle - (2007-11-30) / Université de Franche-Comté, UFC, UTBM - Etudes en recherche locale adaptative pour l'optimisation combinatoire en : Français Directeur(s) de thèse: Caminada , Alexandre Laboratoire : Laboratoire Système et Transports (SeT) Ecole doctorale : SPIM Classification : Informatique | ||
Mots-clés : optimisation combinatoire, méthode approchée, recherche locale, adaptation, mémoire, étude de comportement, coloration de graphes, affectation de fréquences Résumé : Toutes les méthodes d'optimisation ont des paramètres internes qui prennent une part prépondérante dans leurs performances. La difficulté pour les utilisateurs est de trouver un bon réglage pour chaque problème. Depuis quelques années une part importante de la recherche en optimisation combinatoire porte sur la conception de méthodes adaptives. L'objectif de cette démarche est de définir les procédés qui tentent d'adapter dynamiquement le paramétrage des méthodes en fonction du problème. Dans ce contexte, cette thèse porte sur les mécanismes de mémoire et d'adaptation dans le but de mettre au point une méthode de Recherche Locale Adapative (RLA) combinant des mécanismes d'extension et de restriction du voisinage. L'extension du voisinage est définie par une procédure de détection de blocage de la recherche en étudiant l'historique des choix effectués par la méthode afin d'intervenir sur son comportement. Le mécanisme de restriction quant à lui est basé sur l'utilisation d'une liste Tabou à paramétrage adaptatif pour gérer l'accès aux variables. La méthode ainsi obtenue a été appliquée à deux problèmes : un problème académique, la k-coloration de graphes, et un problème réel, l'affectation de fréquences en réseaux de radiocommunications. Plusieurs variantes de RLA ont élé développées et comparées à des résultats publics sur les deux problèmes. Résumé (anglais) : All optimization methods have internal parameters that influenced their performance. The challenge for users is to find a good adjustment for each problem. In recent years an important part of research in combinatorial optimization focuses on the conception of adaptive methods. The objective of the approach is to define processes that attempt to adapt dynamically parameters of methods according to each problem. In this context, this thesis focuses on the mechanisms of memory and adaptation in order to develop an Adaptative Local Search (ALS) method combining mechanisms of extension and restriction of the neighborhood. The neighborhood extension is defined as a procedure which detect blockage during the search by studying the historic of the choices made by the method in order to intervene on his behavior. The restriction mechanism is based on the use of an adaptative tabu list to manage access to the variables. The resulting method has been applied to two problems: an academic problem, graph k-coloring problem, and a real problem, the frequency allocation in radio networks. Several variants of ALS were developed and compared to public results on the two issues. Identifiant : UFC-583 | ||
| Exporter au format XML |