Les recherches locales sont des métaheuristiques qui se déplacent de voisin en voisin pour atteindre un optimum local. Dans la thèse de M-E. Marmion [Phd2011], il a été démontré qu’il était intéressant de s’intéresser aux voisins de même qualité (voisins neutres) afin d’améliorer la recherche locale. Il est alors nécessaire de définir une stratégie pour choisir la solution à explorer parmi toutes ses solutions neutres. Cependant, il est difficile d’évaluer le potentiel d’une solution à avoir de futurs voisins de bonnes qualités.
Nous proposons ici de nous intéresser à qualifier l'intérêt d’une solution voisine en apprenant le potentiel d’une solution à être intéressante (notion d'évolvabilité). Ce potentiel peut être déterminé par des méthodes d’apprentissage sur les solutions déjà visitées [Ejor2012]. Il faudra dans ce travail proposer grâce à des méthodes d’apprentissage un indicateur permettant de juger le potentiel d’une solution. Cette mesure d’intérêt d’une solution sera intégrée dans la métaheuristique VEGAS (Varying Evolvability-Guided Adaptive Search) [Gecco11], un algorithme de recherche locale avancé qui utilise ce type de mesure pour se guider dans l'exploration d'un voisinage. L’algorithme résultant sera testé sur des problèmes classiques de la littérature (flowshop, Nkq, coloration de graphe).
Le projet sera décomposé en différentes étapes:
- Prise en main de la problématique : relations entre neutralité et recherche locale, notion d'évolvabilité, VEGAS
- Analyse (statistique, apprentissage, datamining) de différentes mesures d'evolvabilité sur des échantillons de solutions complétement explorées
- Choix d'une (ou plusieurs) mesure(s) pertinente(s)
- Implémentation de cette mesure dans VEGAS
- Expérimentations et conclusions
Reférences
[Phd2011] Marie-Eléonore Marmion: Recherche locale et optimisation combinatoire : de l'analyse structurelle d'un problème à la conception d'algorithmes efficaces. These de doctorat de l'Université de Lille I, 2011.
[Gecco11] Marie-Eléonore Marmion, Clarisse Dhaenens, Laetitia Jourdan, Arnaud Liefooghe, Sébastien Vérel: The road to VEGAS: guiding the search over neutral networks. GECCO 2011: 1979-1986
[Ejor2012] David Corne, Clarisse Dhaenens, Laetitia Jourdan: Synergies between operations research and data mining: The emerging use of multi-objective approaches. European Journal of Operational Research 221(3): 469-479 (2012)
|
