LIP6 1997/030
- Thesis
Apprentissage de Connaissances de Contrôle pour l'Optimisation Combinatoire : Intégration du Raisonnement à Partir de Cas dans la Méthode Tabou - S. Grolimund
- 227 pages - 11/12/1997- document en - http://www.lip6.fr/lip6/reports/1997/lip6.1997.030.ps.gz - 789 Ko
- Contact : Stephan.Grolimund (at) nulllaforia.ibp.fr
- Ancien Thème : APA
- Keywords : Artificial Intelligence, Combinatorial Optimisation, Case-Based Reasoning, Tabu Search, Learning of Control Knowledge
- Publisher : Valerie.Mangin (at) nulllip6.fr
Tabu search is a meta-heuristic that is able to solve various NP-hard combinatorial optimisation problems. A variant of classical local search, tabu search constructs high quality, near to optimal solutions. In order to speed up the solution generation process, as well as to make its results more robust, tabu search employs particular learning techniques whilst optimisation is in progress. However, these learning schemes have to be specially adapted to each optimisation problem at hand.
This thesis studies the construction of a learning technique for tabu search which is problem independent. We introduce an algorithm that uses case-based reasoning. A case is constructed from the application of a transformation to a solution state. It has two parts, a description of the context in which the transformation applies, and a qualitative reward credited to it with regard to the results of the transformations application. Using this information available in the cases, the ongoing transformations are more deeply analysed with respect to available reward. The fully implemented system is evaluated on three classical combinatorial optimisation problems.
This thesis studies the construction of a learning technique for tabu search which is problem independent. We introduce an algorithm that uses case-based reasoning. A case is constructed from the application of a transformation to a solution state. It has two parts, a description of the context in which the transformation applies, and a qualitative reward credited to it with regard to the results of the transformations application. Using this information available in the cases, the ongoing transformations are more deeply analysed with respect to available reward. The fully implemented system is evaluated on three classical combinatorial optimisation problems.