Propuesta De Tesis Generación Automática De Algoritmos Para El Problema Del Vendedor Viajero A Través De Programación Genética Y Elementos De Heurísticas Conocidas

GENERACIÓN AUTOMÁTICA DE ALGORITMOS PARA EL PROBLEMA DEL VENDEDOR VIAJERO A TRAVÉS DE PROGRAMACIÓN GENÉTICA Y ELEMENTOS DE HEURÍSTICAS CONOCIDAS

Índice

1 Objetivos del proyecto 3

1.1 Objetivo general 3
1.2 Objetivos específicos 3

2 Descripción del problema 4

2.1 Motivación 4
2.2 Definición del problema 5
2.3 Estado del arte 5

3 Descripción de la solución propuesta 73.1 Características de la solución 7
3.2 Propósitos de la solución 7
3.3 Alcances y limitaciones de la solución 7

4 Metodología, herramientas y ambiente de desarrollo 8

4.1 Metodología a usar 8
4.2 Herramientas de desarrollo 8
4.2.1 Requisitos de hardware 8
4.2.2 Requisitos de software 9
4.3 Ambiente de desarrollo 9

5 Plan de trabajo 10

6 Referencias 11

1Objetivos del proyecto 3

1.1 Objetivo general 3
1.2 Objetivos específicos 3

2 Descripción del problema 4

2.1 Motivación 4
2.2 Definición del problema 5
2.3 Estado del arte 5

3 Descripción de la solución propuesta 8

3.1 Características de la solución 8
3.2 Propósitos de la solución 8
3.3 Alcances y limitaciones de la solución 8

4 Metodología, herramientas yambiente de desarrollo 10

4.1 Metodología a usar 10
4.2 Herramientas de desarrollo 10
4.2.1 Requisitos de hardware 10
4.2.2 Requisitos de software 11
4.3 Ambiente de desarrollo 11

5 Plan de trabajo 12

6 Referencias 13

Objetivos del proyecto

1 Objetivo general

Analizar la capacidad de la programación genética (PG) para lograr algoritmos que resuelvan el problema delvendedor viajero usando elementos de heurísticas conocidas.

2 Objetivos específicos

• Estudiar y establecer un conjunto de heurísticas para obtener los elementos que se usarán como base del experimento de programación genética.
• Modelar, diseñar, implementar y evaluar un experimento computacional para resolver el problema del vendedor viajero utilizando programación genética.• Analizar los resultados obtenidos en los siguientes aspectos:
o Comparar con algoritmos existentes, utilizados como base en el diseño del experimento.
o Nuevos algoritmos que resuelvan el problema del vendedor viajero y que sean factibles de implementar.
• Evaluar el desempeño de la programación genética en la resolución del problema del vendedor viajero.Descripción del problema

1 Motivación

La PG es una técnica que permite obtener de forma automática muchas soluciones a un problema dado [REF1]. Lamentablemente no hay suficientes antecedentes acerca de la utilización de PG en el campo de la Optimización y los estudios que hay actualmente no son concluyentes al respecto.

Muchos campos han sido abordados usando PG, en [1], por ejemplo, se muestrauna serie de trabajos relativos principalmente al área de Electricidad; en el mismo documento, se proyecta el uso de la PG en áreas como la Bio-informática, Control, Diseño, Minería de Datos e Inteligencia Artificial. En el campo de la Optimización algunos de los estudios realizados se presentan en [2] para el problema de corte de piezas guillotinables y en [3] para el problema del vendedorviajero.

En [6] se muestra claramente el éxito que ha tenido la PG aplicada a diversos campos de la ingeniería. Se han logrando generar algoritmos que compiten con soluciones creadas anteriormente por humanos, esto según Koza se denomina “Algoritmos con competitividad humana”, actualmente se han obtenido mediante programación genética un conjunto de algoritmos para distintos dominios de problemas quelogran el mismo rendimiento de otros creados por humanos. Y no solo eso, también se consiguieron algoritmos que superan en rendimiento a los creados por humanos.

Estos resultados conducen a una serie de cuestionamientos acerca de la factibilidad de seguir mejorando una serie de soluciones que hasta hoy parecen ser lo suficientemente correctas como para aceptarlas y usarlas sin mayores...