Ingeniería Industrial · 2014

Implementación de un algoritmo evolutivo para el problema del agente viajero (tsp)

De acuerdo a su gran aplicabilidad en el ámbito comercial, industrial y académico, el problema del agente viajero demuestra ser uno de los problemas de optimización combinatoria mayormente estudiados por la comunidad científica en el campo de la investigación de operaciones, a tal fin, que últimamente ha venido siendo considerado como una prueba casi obligatoria para la validación de cualquier técnica de resolución de problemas enteros o combinatorios. En la presente investigación aplicada de pregrado, para hallar una solución aproximada al problema del agente viajero en su variante simétrica, se implementó el metaheurístico de búsqueda dirigida, el "Algoritmo Genético" para el procesamiento de un conjunto de 5 instacias TSPLIB utilizadas también en el desarrollo de la investigación "Un enfoque de búsqueda tabú por Jhon Gabriel" para efecto de comparación de resultados. Lo anterior, se logró mediante la inclusión de conceptos ajenos a su pseudocódigo tradicional, permitiendo así, la adopción de un modelo de búsqueda intensivo y exploratorio, donde entre estos, dichos conceptos fueron: 1. Individuo semilla o ancestro común para la generación de una población inicial de soluciones, 2. Población élite para el almacenamiento temporal de la información genética de las mejores respuestas, 3. Población inadaptada para la identificación y eliminación de las soluciones que degradan la calidad de la soluciones de la población en el proceso de evolución y 4. Utilización probabilística de dos operadores de cruce modificados. Además de que se evaluó cualitativamente el desempeño de dicho algoritmo evolutivo de acuerdo a la programación lineal del problema codificada GAMS, también se emitió para la instancia bays29 una configuración recomendada para los parámetros de entrada del Algoritmo Genético propuesto a partir del desarrollo de un diseño de experimentos de efectos fijos 2 a la k replicado bajo el enfoque de la metodología Branch & Bound.

Palabras clave