983 3755 1 PB 2

Serie Científica de la Universidad de las Ciencias Informáticas
http://publicaciones.uci.cu/index.php/SC | seriecientifica@uci.cu
No. 8, Vol. 5, Año: 2012
ISSN: | RNPS:

Tipo de artículo: Artículo original
Temática: Inteligencia artificial
Recibido: 27/06/2012 | Publicado: 31/08/2012

Algoritmo genético para el problema
aprovechando las capacidades de GEOQ

del

agente

viajero

Genetic algorithmfor the traveling salesman problem using the
capabilities of GEOQ
Ailema Vázquez García
1

Estudiante. Facultad 6. Universidad de las Ciencias Informáticas, Carretera a San Antonio de los Baños, km 2 ½,

Torrens, Boyeros, La Habana, Cuba. CP.: 19370
avgarcia@estudiantes.uci.cu

Resumen
Este trabajo presenta el diseño de un algoritmo genético mejorado con heurísticas constructivas para lainicialización
de la población, y que incorpora dos nuevos operadores de cruzamiento y dos de mutación. Los resultados permiten
corroborar que las técnicas propuestas mejoran el desempeño de los algoritmos genéticos tradicionales en la
resolución del problema, Problema del Agente Viajero.
Palabras clave: Algoritmo genético, problema del agente viajero, sistema de información geográfica.
Abstract
Thispaper presents the design of an improved genetic algorithm constructive heuristic initialization of the
population, and incorporates two new operators of crossover and two mutations. The results corroborate that the
proposed techniques improve the performance of traditional genetic algorithms in solving the Traveling Salesman
Problem, problem.
Keywords: Genetic algorithms, geographic informationsystems, traveling salesman problem.

Serie Científica de la Universidad de las Ciencias Informáticas
http://publicaciones.uci.cu/index.php/SC | seriecientifica@uci.cu
No. 8, Vol. 5, Año: 2012
ISSN: | RNPS:

Introducción
Los Problemas de Optimización de Rutas (POR) continúan siendo de gran interés para investigadores en el área de
Optimización Combinatoria (Sánchez, 2007) por la complejidad queimplica el gran volumen de información con la
que se trabaja hoy día. Uno de estos problemas, el Problema del Agente Viajero (TSP, por sus siglas en inglés), que
consiste en encontrar el recorrido de menor costo de un conjunto de puntos, sin repetirlos y terminando en el punto
inicial, constituye el campo de estudio de esta investigación.
La comunidad científica ha mostrado gran interés en el empleo demetaheurísticas para dar solución a este tipo de
problemas. Las metaheurísticas son estrategias de alto nivel que usan diferentes métodos para explorar el espacio de
búsqueda de forma eficiente y explotan las zonas más prometedoras (Valero, 2008). Casi todas las técnicas
metaheurísticas han sido utilizadas para resolver POR, los Algoritmos Genéticos (AG) son una de las más usadas
(Bryant, 2000;Karova, 2005; Acuña, 2010). El paralelismo con que opera la población y el hecho de que resultan
menos afectados por los óptimos locales (Londoño, 2006; J., et al., 2004), los convierten en una opción viable para el
tratamiento de estos problemas.
Por otro lado, el surgimiento y desarrollo de los Sistemas de Información Geográfica (SIG) ha dado una potencialidad
adicional a las herramientas queresuelven POR (WU, et al., 2000). En el SIG GeoQ, las capacidades de manipulación
de datos y de visualización de las rutas no son explotadas al máximo para solucionar el problema TSP.
En este trabajo, se proponen modificaciones en tres componentes del AG básico: inicialización de la población,
cruzamiento y mutación. Los experimentos computacionales descubren cuáles de ellas aumentan la efectividaddel
algoritmo para resolver el problema TSP. El SIG GeoQ será utilizado para el pre-procesamiento de la información
geográfica asociada (puntos y rutas entre puntos) antes de ejecutarse el algoritmo.

Desarrollo
Esta sección ofrece una breve descripción de aquellos contenidos que sirvieron como base para la realización de la
presente investigación. Además, se introducen las distintas técnicas...