Registro:
| Documento: | Tesis de Grado |
| Disciplina: | computacion |
| Título: | Learning classifier systems for optimisation problems : a case study on fractal travelling salesman problem |
| Título alternativo: | Learning classifier systems for optimisation problems: a case study on fractal travelling salesman problem |
| Autor: | Tabacman, Maximiliano |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2022-07-05 |
| Fecha de defensa: | 2008-08-07 |
| Fecha en portada: | 2008 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Director: | Krasnogor, Natalio; Loiseau, Irene |
| Idioma: | Inglés |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000370_Tabacman |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000370_Tabacman.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000370_Tabacman |
| Ubicación: | Dep.COM 000370 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Tabacman, Maximiliano. (2008). Learning classifier systems for optimisation problems : a case study on fractal travelling salesman problem. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000370_Tabacman |
Resumen:
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.
Abstract:
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.
Citación:
---------- APA ----------
Tabacman, Maximiliano. (2008). Learning classifier systems for optimisation problems : a case study on fractal travelling salesman problem. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000370_Tabacman
---------- CHICAGO ----------
Tabacman, Maximiliano. "Learning classifier systems for optimisation problems : a case study on fractal travelling salesman problem". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2008.https://hdl.handle.net/20.500.12110/seminario_nCOM000370_Tabacman
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000370_Tabacman.pdf
Distrubución geográfica
