Personal tools
You are here: Home Teaching / Enseignement files IAD Projets M2-IAD 2007-2008 Projets Méthodes de recherche locale à voisinage variable
Navigation
Log in


Forgot your password?
 
Document Actions

Méthodes de recherche locale à voisinage variable

by François Rioult last modified 2007-11-05 08:48

To:

Introduction :


Les méthodes de recherche locale, appelées aussi méthodes de recherche par voisinages, partent d’une solution initiale et, par transformations successives, construisent des suites de solutions de coûts décroissants (pour un problème de minimisation). Le processus s’arrête lorsque on ne peut plus améliorer la solution courante ou parce que le nombre maximal d’itérations (fixé au départ) est atteint.


Bien que ces méthodes ne soient pas complètes (rien n’assure qu’elles pourront trouver toutes les solutions existantes) ni n’assurent la preuve d’optimalité (qui ne peut être effectuée sans information extérieure supplémentaire), de telles méthodes produisent très souvent des solutions de (très) bonne qualité dans des temps de calcul « raisonnables ».



Objectifs :


Etudier différentes méthodes de recherche locale comme Tabou, VNS (Variable Neighborhood Search), LNS (Large Neighborhood Search), en comprendre les principes et les appliquer sur des problèmes « en vrai grandeur » : emplois du temps, allocation de ressources dans les réseaux, allocation de fréquences radio, ….


On pourra aussi comparer les résultats obtenus avec ceux obtenus par des méthodes de recherche arborescentes en termes de qualité de solution et du temps de calcul nécessaire.



« June 2011 »
Su Mo Tu We Th Fr Sa
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30
 

Powered by Plone, the Open Source Content Management System

This site conforms to the following standards: