Learning classifier systems for optimisation problems: A case study on fractal travelling salesman problem

Mostrar todas las versiones(4)

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, Maximiliano, Loiseau, Irene
Publicado: 2008
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: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:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_97816055_v_n_p2039_Tabacman
record_format dspace
spelling paper:paper_97816055_v_n_p2039_Tabacman2023-06-08T16:38:09Z Learning classifier systems for optimisation problems: A case study on fractal travelling salesman problem Tabacman, Maximiliano Loiseau, Irene 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. 2008 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
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, Maximiliano
Loiseau, Irene
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.
author Tabacman, Maximiliano
Loiseau, Irene
author_facet Tabacman, Maximiliano
Loiseau, Irene
author_sort Tabacman, Maximiliano
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
publishDate 2008
url 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
work_keys_str_mv AT tabacmanmaximiliano learningclassifiersystemsforoptimisationproblemsacasestudyonfractaltravellingsalesmanproblem
AT loiseauirene learningclassifiersystemsforoptimisationproblemsacasestudyonfractaltravellingsalesmanproblem
_version_ 1768546698355802112

Ejemplares similares