Learning classifier systems for optimisation problems: A case study on fractal travelling salesman problem
This paper presents a set of experiments on the use of Learning Classifier Systems for the purpose of solving combinatorial optimisation problems. We demonstrate our approach with a set of Fractal Travelling Salesman Problem (TSP) instances for which it is possible to know by construction the optima...
Guardado en:
| Autores principales: | , |
|---|---|
| Publicado: |
2008
|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_97816055_v_n_p2039_Tabacman http://hdl.handle.net/20.500.12110/paper_97816055_v_n_p2039_Tabacman |
| Aporte de: |
| Sumario: | This paper presents a set of experiments on the use of Learning Classifier Systems for the purpose of solving combinatorial optimisation problems. We demonstrate our approach with a set of Fractal Travelling Salesman Problem (TSP) instances for which it is possible to know by construction the optimal tour regardless of the number of cities in them. This special type of TSP instances are ideal for testing new methods as they are well characterised in their solvability and easy to use for scalability studies. Our results show that an LCS is capable of learning rules to recognise to which family of instances a set containing a sample of the cities in the problem belongs to and hence automatically select the best heuristic to solve it. Moreover, we have also trained the LCS to recognise links belonging to the optimal tour. Copyright 2008 ACM. |
|---|