Chargement...
 

Recherche locale parallèle adaptative

Année scolaire 2008-2009

Stage Master 2 ou Ecole d'ingénieur


Contexte

Pour la résolution d'un ensemble de problèmes combinatoires, on dispose de H méta-heuristiques et de C resources de calcul, avec H >> C - situation de plus en plus fréquente du fait de la multiplication des solveurs pour de nombreuses classes de problèmes combinatoires d'une part, et de l'arrivée en masse de systèmes multi-coeurs à mémoire partagée d'autre part. On souhaite mettre au point une méthode permettant de choisir pour une instance donnée les C méta-heuristiques permettant la résolution de l'instance la plus rapide possible.

On suppose dans un premier temps que les diverses méta-heuristiques s'éxécutent indépendamment les unes des autres, et que l'on dispose déjà du résultat de tout ou partie de ces méta-heuristiques (en terme de temps de résolution) pour un ensemble de I instances de la même classe de problème. Le problème du choix, pour une nouvelle instance, des meilleures C méta-heuristiques peut alors être assimilé au problème de "collaborative filtering", illustré par exemple par les logiciels de recommandation de films à la NetFlix (dont la version de base peut se résumer en "étant donnés les avis de X personnes sur un (petit) nombre de films, quel film recommander à quelqu'un qui a aimé ...").

Déroulement du stage

Ce problème peut se formuler en deux temps: tout d'abord, l'information disponible étant représentée par la matrice de performance, de taille I x H, éventuellement très creuse, dont le terme (i,h) décrit le comportement de la méta-heuristique h sur l'instance (e.g. le temps de résolution), il s'agit de compresser cette matrice de manière algébrique en une matrice de taille plus réduite avec une perte minimale d'information. Cela revient à trouver des descripteurs cachés, du style "types d'instance" et "types de méta-heuristiques". Le premier travail du stagiaire sera d'examiner les diverses méthodes proposées dans la littérature pour cette compression, et en particulier les divers compromis entre taux de compression et perte d'information.

Ensuite, et dans le cas où on ne dispose pas d'information supplémentaire, une instance nouvelle sera simplement considérée comme uniformément répartie sur les divers type d'instances, et le choix optimal des C méta-heuristiques revient alors à résoudre un problème de minimisation en (0/1) sous contrainte (espérance du minimum de temps de résolution).

Cette approche sera testée sur des classes d'instances du problème SAT, sur lequel l'équipe d'accueil possède une grande expérience. Les différentes variantes retenues seront implantées et comparées expérimentalement à l'approche consistant à choisir le jeu de C méta-heuristiques les plus "complémentaires", i.e. ayant la covariance minimale sur les expériences passées.

De plus, cette approche peut également prendre en compte sans effort supplémentaire d'éventuels descripteurs d'instance dépendant de la classe de problèmes considérée, en les rajoutant comme autant de colonnes à la matrice de performance. Des descripteurs classiques et bien connus pour les problèmes SAT seront ainsi rajoutés dans un deuxième temps, et le gain par rapport à l'approche uniforme sera estimé.


Responsables du stage: Youssef Hamadi, Marc Schoenauer, Michèle Sebag
Lieu du stage: Laboratoire commun Microsoft-INRIA, Saclay
Rémunération: indemnités de stage au tarif syndical suivant ressources (entre 350 et 600 euros par mois)


Collaborateur(s) de cette page: evomarc .
Page dernièrement modifiée le Mardi 13 janvier 2009 08:16:46 CET par evomarc.