Abstract:
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.
Registro:
| Documento: |
Conferencia
|
| Título: | Learning classifier systems for optimisation problems: A case study on fractal travelling salesman problem |
| Autor: | Tabacman, M.; Bacardit, J.; Krasnogor, N.; Loiseau, I. |
| Ciudad: | Atlanta, GA |
| Filiación: | Departamento de Computacion, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina
ASAP Research Group, Jubilee Campus, University of Nottingham, Nottingham, NG8 1BB, United Kingdom
Multidisciplinar Centre for Integrative Biology, School of Biosciences, University of Nottingham, Sutton Bonington, LE12 5RD, United Kingdom
|
| Palabras clave: | Learning-classifier-systems; Machine learning; Optimization; Traveling-salesman-problem; Classifiers; Combinatorial optimization; Education; Fractals; Learning systems; Case studies; Combinatorial optimisation; Learning rules; Learning-classifier-systems; Machine learning; Optimal tours; Optimisation; Travelling salesman problems; Traveling salesman problem |
| Año: | 2008
|
| Página de inicio: | 2039
|
| Página de fin: | 2046
|
| Título revista: | 10th Annual Genetic and Evolutionary Computation Conference, GECCO 2008
|
| Título revista abreviado: | GECCO: Genet. Evolut. Comput. Conf. - Proc. Annu. Conf. Genet. Evolut. Comput.
|
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_97816055_v_n_p2039_Tabacman |
Referencias:
- Bacardit, J., (2004) Pittsburgh Genetics-Based Machine Learning in the Data Mining era: Representations, generalization, and run-time, , PhD thesis, Ramon Llull University, Barcelona, Catalonia, Spain
- Bacardit, J., Analysis of the initialization stage of a Pittsburgh approach learning classifier system (2005) GECCO 2005: Proceedings of the Genetic and Evolutionary Computation Conference, 2, pp. 1843-1850. , ACM Press
- Bacardit, J., Krasnogor, N., Empirical evaluation of ensemble techniques for a Pittsburgh learning classifier system (2008) LNAI, , Proceedings of the 9th International Workshop on Learning Classifier Systems, to appear, Springer-Verlag
- Holland, J.H., Reitman, J.S., Cognitive systems based on adaptive algorithms (1978) Pattern-directed Inference Systems, pp. 313-329. , D. Hayes-Roth and F. Waterman, editors, Academic Press, New York
- Mariano, A., Moscato, P., Norman, M., Arbitrarily large planar etsp instances with known optimal tours (1995) Pesquisa Operacional, 15, pp. 89-96
- Mariano, A., Moscato, P., Norman, M., Using 1-systems to generate arbitrarily large instances of the euclidean traveling salesman problem with known optimal tours (1995) Anales del XXVII Simposio Brasileiro de Pesquisa Operacional, , Vitoria, Brazil, 6-8 Nov
- Moscato, P., Norman, M., An analysis of the performance of traveling salesman heuristics on infinite-size fractal instances in the euclidean plane (1994), Technical report, CeTAD, Universidad Nacional de La Plata; Norman, M., Moscato, P., The euclidean traveling salesman problem and a space-filling curve (1995) Chaos, Solitons and Fractals, 6, pp. 389-397
- Peitgen, H., Jürgens, H., Saupe, D., (2004) Chaos and Fractals, , Springer, February
- Smith, S., (1980) A Learning System Based on Genetic Algorithms, , PhD thesis, University of Pittsburgh
- Stout, M., Bacardit, J., Hirst, J.D., Krasnogor, N., Prediction of recursive convex hull class assignments for protein residues (2008) Bioinformatics, , In press
- Stout, M., Bacardit, J., Hirst, J.D., Smith, R.E., Krasnogor, N., Prediction of topological contacts in proteins using learning classifier systems. Soft Computing, Special Issue on Evolutionary and Metaheuristic-based Data Mining (EMBDM) (2008), In Press; Wolpert, D., Macready, W., No free lunch theorems for optimization (1997) IEEE Transactions on Evolutionary Computation, 1 (1), pp. 67-82. , April
Citas:
---------- APA ----------
Tabacman, M., Bacardit, J., Krasnogor, N. & Loiseau, I.
(2008)
. Learning classifier systems for optimisation problems: A case study on fractal travelling salesman problem. 10th Annual Genetic and Evolutionary Computation Conference, GECCO 2008, 2039-2046.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_97816055_v_n_p2039_Tabacman [ ]
---------- CHICAGO ----------
Tabacman, M., Bacardit, J., Krasnogor, N., Loiseau, I.
"Learning classifier systems for optimisation problems: A case study on fractal travelling salesman problem"
. 10th Annual Genetic and Evolutionary Computation Conference, GECCO 2008
(2008) : 2039-2046.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_97816055_v_n_p2039_Tabacman [ ]
---------- MLA ----------
Tabacman, M., Bacardit, J., Krasnogor, N., Loiseau, I.
"Learning classifier systems for optimisation problems: A case study on fractal travelling salesman problem"
. 10th Annual Genetic and Evolutionary Computation Conference, GECCO 2008, 2008, pp. 2039-2046.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_97816055_v_n_p2039_Tabacman [ ]
---------- VANCOUVER ----------
Tabacman, M., Bacardit, J., Krasnogor, N., Loiseau, I. Learning classifier systems for optimisation problems: A case study on fractal travelling salesman problem. GECCO: Genet. Evolut. Comput. Conf. - Proc. Annu. Conf. Genet. Evolut. Comput. 2008:2039-2046.
Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_97816055_v_n_p2039_Tabacman [ ]
