Recherche incomplète aidée par une base de conflits
1 : Institut de recherche en informatique de Toulouse
Université Fédérale Toulouse Midi-Pyrénées
2 : ONERA/DTIS
ONERA
3 : Institut de recherche en informatique de Toulouse
université Toulouse 1 Capitole, Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse - Jean Jaurès, Université Toulouse III - Paul Sabatier, Université Fédérale Toulouse Midi-Pyrénées : UMR5505, Centre National de la Recherche Scientifique, Institut National Polytechnique (Toulouse)
118 Route de Narbonne, F-31062 Toulouse Cedex 9 -
France
Dans ce travail, nous considérons la résolution de problème OPTW avec des méthodes de recherche incomplète aidées par une base de connaissances. L'objectif est d'extraire et de mémoriser des conflits au fur et à mesures des itérations dans une mémoire long-terme. Par rapport à des mécanismes de recherche tabou, l'enjeu est d'obtenir une base de conflits plus pérenne. Pour expérimenter cette approche sur les OPTW, nous proposons trois méthodes de gestion de la base de conflits et évaluons ses performances dans le solveur global. Ces conflits sont utilisés pour guider la recherche dans le futur, soit pour éviter de réexplorer des configurations non admissibles, soit pour identifier les zones les plus prometteuses dans l'espace de recherche.