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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Tabacman, M., Bacardit, J., Krasnogor, N., Loiseau, I.
Formato: CONF
Materias:
Learning-classifier-systems
Machine learning
Optimization
Traveling-salesman-problem
Classifiers
Combinatorial optimization
Education
Fractals
Learning systems
Case studies
Combinatorial optimisation
Learning rules
Optimal tours
Optimisation
Travelling salesman problems
Traveling salesman problem
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_97816055_v_n_p2039_Tabacman
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_97816055_v_n_p2039_Tabacman
record_format dspace
spelling todo:paper_97816055_v_n_p2039_Tabacman2023-10-03T16:44:06Z Learning classifier systems for optimisation problems: A case study on fractal travelling salesman problem Tabacman, M. Bacardit, J. Krasnogor, N. Loiseau, I. 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 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. Fil:Tabacman, M. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Loiseau, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. CONF info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_97816055_v_n_p2039_Tabacman
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic 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
spellingShingle 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
Tabacman, M.
Bacardit, J.
Krasnogor, N.
Loiseau, I.
Learning classifier systems for optimisation problems: A case study on fractal travelling salesman problem
topic_facet 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
description 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.
format CONF
author Tabacman, M.
Bacardit, J.
Krasnogor, N.
Loiseau, I.
author_facet Tabacman, M.
Bacardit, J.
Krasnogor, N.
Loiseau, I.
author_sort Tabacman, M.
title Learning classifier systems for optimisation problems: A case study on fractal travelling salesman problem
title_short Learning classifier systems for optimisation problems: A case study on fractal travelling salesman problem
title_full Learning classifier systems for optimisation problems: A case study on fractal travelling salesman problem
title_fullStr Learning classifier systems for optimisation problems: A case study on fractal travelling salesman problem
title_full_unstemmed Learning classifier systems for optimisation problems: A case study on fractal travelling salesman problem
title_sort learning classifier systems for optimisation problems: a case study on fractal travelling salesman problem
url http://hdl.handle.net/20.500.12110/paper_97816055_v_n_p2039_Tabacman
work_keys_str_mv AT tabacmanm learningclassifiersystemsforoptimisationproblemsacasestudyonfractaltravellingsalesmanproblem
AT bacarditj learningclassifiersystemsforoptimisationproblemsacasestudyonfractaltravellingsalesmanproblem
AT krasnogorn learningclassifiersystemsforoptimisationproblemsacasestudyonfractaltravellingsalesmanproblem
AT loiseaui learningclassifiersystemsforoptimisationproblemsacasestudyonfractaltravellingsalesmanproblem
_version_ 1782024948348354560

Ejemplares similares