Integrating Case Based Reasoning and Tabu Search for Solving Optimisation Problems

S. Grolimund, J.-G. Ganascia

IBP-Laforia 1995/25: Rapport de Recherche Laforia / Laforia research reports
11 pages - Janvier/January 1996 - Document en anglais.

PostScript : 60 Ko /Kb

Titre / Title: Integrating Case Based Reasoning and Tabu Search for Solving Optimisation Problems

Résumé : La Recherche Tabal est une heuristique établie permettant d'optimiser des problèmes pour lesquels des algorithmes exacts ne sont pas utilisables. Elle appartient à la même famille de techniques que le recuit simulé et les algorithmes génétiques. Cette méthode étend le cycle basic d'amélioration itérative en recourant à des techniques d'apprentissage de contrôle de recherche. Une parmi ces dernières, l'intensification tente d'acquérir de l'expérience de contrôle à partir d'une analyse fréquentielle de la recberche antérieure. Cette expérience est ensuite réutilisée afin de mieux guider la recherche ultérieure sur la même instance de problèmes.
Dans cet article, nous introduisons une technique de raisonnement à partir de cas pour l'apprentissage de contrôle dans la méthode tabou. Les cas représentent l'expérience relative a la séblection des opérateurs. Ils sont réutilisés afin d'améliorer la résolution de conflits. La méthode étant indépendante du domaine, nous l'illustrons par son application au problème NP-dur de placement et d'allocation d'entités. Les résultats expérimentaux montrent que l'ajout de la méthode proposée, à une technique de recherche tabou simple, améliore la qualité des solutions identifiées pour des problèmes de références. L'écart entre les solutions produites et la solution optimale se trouve réduit peu ou prou d'un facteur 2.

Abstract : Tabu search is an established heuristic optimisation technique for problems wbere exact algarithms are not available. It belongs to the same family as simulated annealing ar genetic algorithms. It extends the basic iterative improvement scheme by adding control learning. A technique of this kind, intensification, captures experience established an a frequency-based analysis of past search. Experience is reused while the same optimisation process is going on in order to guide search to better solutions.
In this paper, we introduce a case-based reasoning approach for cantrol learning in tabu search. Search experience concerns operator selection and is represented by cases. The aim of case reuse is to improve conflict resolution. While the proposed method is domain independent, we present its application to the NP-hard uncapacitated facility location problem. Experimental results show that adding our approach to a basic tabu search optimisation significantly improves solution quality on the evaluated benchmark problems. It reduces the gap to the optimal solution by a factor af nearly 2.

Publications internes Laforia 1995 / Laforia research reports 1995