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

Mostrar todas las versiones(4)

El Problema del Viajante de Comercio (en inglés Travelling Salesman Problem o TSP)[21] implica encontrar un circuito Hamiltoniano de costo mínimo en un grafo completo Kn. Aunque su descripción a nivel matemático es simple, resolverlo es extremadamente costoso, ya que es uno de los problemas que se c...

Descripción completa

Detalles Bibliográficos
Autor principal: Tabacman, Maximiliano
Otros Autores: Krasnogor, Natalio
Formato: Tesis de grado publishedVersion
Lenguaje:Inglés
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2008
Acceso en línea:https://hdl.handle.net/20.500.12110/seminario_nCOM000370_Tabacman
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id seminario:seminario_nCOM000370_Tabacman
record_format dspace
spelling seminario:seminario_nCOM000370_Tabacman2025-05-09T18:45:11Z Learning classifier systems for optimisation problems : a case study on fractal travelling salesman problem Learning classifier systems for optimisation problems: a case study on fractal travelling salesman problem Tabacman, Maximiliano Krasnogor, Natalio Loiseau, Irene El Problema del Viajante de Comercio (en inglés Travelling Salesman Problem o TSP)[21] implica encontrar un circuito Hamiltoniano de costo mínimo en un grafo completo Kn. Aunque su descripción a nivel matemático es simple, resolverlo es extremadamente costoso, ya que es uno de los problemas que se conocen como NP-Hard. Esto nos lleva a la necesidad de buscar mejores maneras de encararlo, para reducir los tiempos de procesamiento y asegurar mejores resultados. En esta tesis se propone el uso de sistemas de clasificación (en inglés Learning Classifier Systems o LCS)[13]. Como un LCS recibe información en forma de atributos y una clase asociada, presentamos una manera de convertir instancias de TSP en dichos atributos, aprovechando un conjunto particular de TSP conocido como TSP Fractales. Luego de analizar diversos modelos de conversión y experimentación, podemos concluir que a partir de los parámetros y estructura adecuada, esta técnica de Machine Learning no solo obtiene resultados precisos sino también de fácil lectura, en la forma de conjuntos de reglas. Además de conseguir clasificar todas las entradas analizadas con total certeza, presentamos un sistema que aprovecha los resultados obtenidos, y constituye una prueba de concepto que muestra una manera de resolver problemas de optimización a través de sistemas de clasificación. The Traveling Salesman Problem implies nding a Hamiltonian cycle of minimum cost in a fully connected graph with costs associated to its edges. Although mathematically simple to describe, the TSP belongs to the group of NP-Hard computational problems. This means that exact solutions are costly in time and resources, and real world problems associated with it would be greatly benefited by faster and better approaches to solving it. In this thesis, we propose the use of a Learning Classifier System. Since an LCS requires information presented in the form of valued attributes and a corresponding class, we present a way of converting instances of TSP to such valued attributes, taking advantage of the group of TSP instances known as Fractal TSP. After dealing with varied conversion and experimentation models, it can be seen that with the right parameters and structure, this Machine Learning technique not only obtains highly accurate results but also delivers a human understandable explanation of the rules discovered. Apart from being able to classify with no chance of error the posible inputs, we present a system that uses the results obtained, serving as a proof of concept that shows a way to solve Optimisation Problems using Learning Classifier Systems. Fil: Tabacman, Maximiliano. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2008-08-07 info:eu-repo/semantics/bachelorThesis info:ar-repo/semantics/tesis de grado info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/seminario_nCOM000370_Tabacman
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Inglés
orig_language_str_mv eng
description El Problema del Viajante de Comercio (en inglés Travelling Salesman Problem o TSP)[21] implica encontrar un circuito Hamiltoniano de costo mínimo en un grafo completo Kn. Aunque su descripción a nivel matemático es simple, resolverlo es extremadamente costoso, ya que es uno de los problemas que se conocen como NP-Hard. Esto nos lleva a la necesidad de buscar mejores maneras de encararlo, para reducir los tiempos de procesamiento y asegurar mejores resultados. En esta tesis se propone el uso de sistemas de clasificación (en inglés Learning Classifier Systems o LCS)[13]. Como un LCS recibe información en forma de atributos y una clase asociada, presentamos una manera de convertir instancias de TSP en dichos atributos, aprovechando un conjunto particular de TSP conocido como TSP Fractales. Luego de analizar diversos modelos de conversión y experimentación, podemos concluir que a partir de los parámetros y estructura adecuada, esta técnica de Machine Learning no solo obtiene resultados precisos sino también de fácil lectura, en la forma de conjuntos de reglas. Además de conseguir clasificar todas las entradas analizadas con total certeza, presentamos un sistema que aprovecha los resultados obtenidos, y constituye una prueba de concepto que muestra una manera de resolver problemas de optimización a través de sistemas de clasificación.
author2 Krasnogor, Natalio
author_facet Krasnogor, Natalio
Tabacman, Maximiliano
format Tesis de grado
Tesis de grado
publishedVersion
author Tabacman, Maximiliano
spellingShingle Tabacman, Maximiliano
Learning classifier systems for optimisation problems : a case study on fractal travelling salesman problem
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
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2008
url https://hdl.handle.net/20.500.12110/seminario_nCOM000370_Tabacman
work_keys_str_mv AT tabacmanmaximiliano learningclassifiersystemsforoptimisationproblemsacasestudyonfractaltravellingsalesmanproblem
_version_ 1831983599957573632

Ejemplares similares