Una metaheurística co-evolutiva para el problema del viajante de comercio

En este Trabajo de Grado se presenta una estrategia general (metaheurística) para la resolución del Problema del Viajante de Comercio. Éste es un problema clásico de optimización combinatoria, cuyo conjunto de soluciones posibles es finito, pero demasiado numeroso para ser manejado en forma directa...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Holstein, Diana
Otros Autores: Moscato, Pablo
Formato: Tesis Tesis de grado
Lenguaje:Español
Publicado: 1998
Materias:
Ciencias Informáticas
Heuristic methods
Problem Solving, Control Methods, and Search
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/2187
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-2187
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Español
topic Ciencias Informáticas
Heuristic methods
Problem Solving, Control Methods, and Search
spellingShingle Ciencias Informáticas
Heuristic methods
Problem Solving, Control Methods, and Search
Holstein, Diana
Una metaheurística co-evolutiva para el problema del viajante de comercio
topic_facet Ciencias Informáticas
Heuristic methods
Problem Solving, Control Methods, and Search
description En este Trabajo de Grado se presenta una estrategia general (metaheurística) para la resolución del Problema del Viajante de Comercio. Éste es un problema clásico de optimización combinatoria, cuyo conjunto de soluciones posibles es finito, pero demasiado numeroso para ser manejado en forma directa. Dado un conjunto de ciudades, y una medida de “costo” entre ellas, el problema consiste en hallar un camino cerrado (tour) de costo mínimo, que visite cada ciudad exactamente una vez. El costo puede estar representado por la distancia entre las ciudades, o por cualquier otra medida, tal como el tiempo que las separa o el costo de un pasaje entre ellas. Este problema puede aplicarse en muchas situaciones prácticas, tales como ruteo de vehículos, secuenciamiento de tareas, conexión de módulos electrónicos. Además reviste una importancia teórica para la Teoría de Complejidad, pues pertenece a la clase de los problemas combinatorios NP- Completos, para los cuales se conjetura que el tiempo de cómputo requerido para hallar la solución exacta crece al menos exponencialmente con el tamaño de la instancia considerada. Por esto es necesario buscar heurísticas que encuentren rápidamente tours cercanos al óptimo. En el contexto de los problemas de optimización combinatoria, se pueden definir las heurísticas como técnicas que producen soluciones factibles rápidamente, en cuanto al tiempo de cómputo requerido, pero tales soluciones no son necesariamente óptimas. Estos procedimientos tienen una justificación intuitiva. Las metaheurísticas son estrategias que generalmente guían otras heurísticas, y que no dependen de las características del problema a resolver. El desarrollo de metaheurísticas para resolver este problema, permite que las mismas técnicas puedan aplicarse a una gran variedad de problemas combinatorios. El Problema del Viajante de Comercio se ha utilizado siempre para ensayar diferentes enfoques de optimización combinatoria, incluyendo las técnicas clásicas de optimización local, así como variantes más recientes: Búsqueda Tabú, Redes Neuronales, Algoritmos Genéticos. Es un dominio atípico desde el punto de vista teórico y experimental. Luego de presentar el Problema del Viajante de Comercio, las secciones iniciales de este Trabajo describirán por separado los componentes de la metaheurística a desarrollar: heurísticas de búsqueda local, Búsqueda Local Guiada, Algoritmos Meméticos. En la Sección 6, se integrarán estos conceptos para diseñar una estrategia de resolución del Problema del Viajante de Comercio, que intenta aprovechar las mejores características de cada uno de estos enfoques. Las últimas secciones presentarán los resultados de los experimentos realizados y las conclusiones del trabajo.
author2 Moscato, Pablo
author_facet Moscato, Pablo
Holstein, Diana
format Tesis
Tesis de grado
author Holstein, Diana
author_sort Holstein, Diana
title Una metaheurística co-evolutiva para el problema del viajante de comercio
title_short Una metaheurística co-evolutiva para el problema del viajante de comercio
title_full Una metaheurística co-evolutiva para el problema del viajante de comercio
title_fullStr Una metaheurística co-evolutiva para el problema del viajante de comercio
title_full_unstemmed Una metaheurística co-evolutiva para el problema del viajante de comercio
title_sort una metaheurística co-evolutiva para el problema del viajante de comercio
publishDate 1998
url http://sedici.unlp.edu.ar/handle/10915/2187
work_keys_str_mv AT holsteindiana unametaheuristicacoevolutivaparaelproblemadelviajantedecomercio
bdutipo_str Repositorios
_version_ 1764820465055956993

Ejemplares similares