A Case-Based Reasoning approach to knowledge transfer in Tabu Search

S. Grolimund, J.-G. Ganascia

IBP-Laforia 1994/06: Rapport de Recherche Laforia / Laforia research reports
24 pages - Novembre/November 1994 - Document en anglais.

PostScript : 142 Ko /Kb

Titre / Title: A Case-Based Reasoning approach to knowledge transfer in Tabu Search

Résumé : Les méthodes de recherche tabou, une sous-classe des méthodes de recherche locales, font explicitement usage d'un transfert de connaissance entre des étapes successives de la recherche. Pour ce faire, elles se fondent sur des techniques d'apprentissage relativement simples et statistiques. Concernant une classe de problèmes proche de l'optimisation combinatoire, à savoir la génération de plans, les techniques d'apprentissage analytique comme l'apprentissage par explication se sont montrées performantes même sur des problèmes de grande taille.
Nous nous proposons de faire bénéficier les méthodes de recherche tabou des résultats obtenus en apprentissage analytique. Cela nous conduit à introduire une technique de raisonnement à partir de cas pour apprendre des connaissance de contrôle lors de la résolution de problèmes d'optimisation combinatoire. Une technique de décomposition de transitions est proposée afin de réduire la taille des voisinages sans avoir à recourir aux ensembles candidats classiques. Il est alors possible de maintenir notre méthode à un niveau de complexité acceptable. Tout comme, il devient possible d'utiliser des transitions plus complexes lors de la modélisation de problèmes. Cela est particulièrement intéressant lors de la spécification de la phase de diversification de la méthode tabou ainsi que pour la modélisation de problèmes d'optimisation industriels.

Abstract : Tabu search, a class of local search techniques, relies explicitly on knowledge transfer between search episodes in order to improve performances as search progresses. For this purpose, relatively simple, statistical learning techniques are used. On a problem class close to combinatorial optimisation, i.e. plan generation, analytical learning techniques like EBL or derivational analogy have shown to perform and scale up well.
In order to make tabu search-like techniques benefit from analytical learning, we propose a case-based reasoning approach for learning and reusing control knowledge for combinatorial optimisation problems. A move decomposition technique is used to reduce neighbourhood sizes without the need to call on candidate sets. It permits to cope with computational complexity due to learning, and to allow problem modelling with complex moves. This second point is especially interesting concerning diversification, a control strategy of tabu search, as well as concerning real life problems.

Publications internes Laforia 1994 / Laforia research reports 1994