Case-Based Reasoning and Tabu Search for the Single Machine Scheduling Problem: first Results

S. Grolimund, J.-G. Ganascia

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

PostScript : 53 Ko /Kb

Titre / Title: Case-Based Reasoning and Tabu Search for the Single Machine Scheduling Problem: first Results

Résumé : L'optimisation combinatoire se distingue de la résolution de problèmes de par la nature des buts qu'elle poursuit. La difficulté qu'il y a à résoudre les problèmes d'optimisation combinatoire engendre une méfiance à l'égard des connaissances qui peuvent être apprises durant l'optimisation. I)e ce point de vue, les techniques d'apprentissage analytique classiques ne sont guère adaptées à la résolution de problèmes d'optimisation, alors qu'en revanche, les méthodes issues de la recherche opérationnelle s'y pretent. Cesdernieres n'intègrent cependant pas de techniques symboliques d'apprentissage.
Nous proposons une approche, intégrée dans la méthode Tabou, permettant l'apprentissage de connaissances de contrôle dans des problèmes d'optimisation en cours de résolution. Une technique d'apprentissage à partir de cas acquiert et réutilise des connaissances de contrôle à l'intérieur de la même instance de problèmes. L'approche, appelée ALOIS, ne transfert pas de connaissance d'une optimisation à l'autre. En outre, elle est indépendante du domaine grâce à l'utilisation d'un système à base de règles pour l'exploration de l'espace de recherche. Nous illustrons et commentons l'application d'ALOIS à un problème d'ordormancement de base.

Abstract : Combinatorial optimisation differs from general problem solving in the nature of goals to be achieved. The difficulty of achieving optimisation goals leads to a general lack of confidence concerning the knowledge that can be learned during optimisation. We point out that this makes analytical learning techniques, like EBL or derivational analogy, inappropriate to the resolution of optimisation problems. Operations research methods cope with combinatorial optimisation, however without using symbolic learning.
Integrated in the Tabu search framework, we propose a system that learns control knowledge in optimisation domains while the resolution is in progress. A casebased learning technique is used to store and reuse control knowledge within the same instance of an optimisation problem. The approach, called ALOIS, does not attempt to transfer the acquired case library to any otha instance of the same problem. ALOIS is designed to be domainindependert, using a general rulebased reasoner to explore the solution space. Its application to the single machine scheduling problem with variable setup times is illustrated and discussed.

Publications internes Laforia 1995 / Laforia research reports 1995