Perfeccionando algoritmos heurísticos para el problema NP-C E-TSP

Improving heuristic algorithms for NP-C E-TCP problem

El desarrollo de algoritmos heurísticos eficientes y exactos, de orden polinomial, que logren buenassoluciones para problemas complejos pertenecientes a la clase NP-C, continúa siendo un gran reto. Sepropone una estrategia para perfeccionar algoritmos heurísticos, específicamente para el problema delvendedor viajero euclidiano, conocido como E-TSP. Se define un conjunto de indicadores que informanen qué medida la heurística del programador se refleja en el algoritmo. La retroalimentación obtenida, alutilizar los indicadores, facilita el proceso de mejora del algoritmo inicial, lográndose mejores solucionesen promedio. Es factible obtener retroalimentación desde la propia ejecución del algoritmo heurístico ybasándose en tal información perfeccionar el algoritmo.

INTRODUCCIÓN

Existen problemas para los cuales no es posible encontrar una solución óptima en un tiempo razonable, circunstancia que justifica el desarrollo y perfeccionamiento de algoritmos capaces de abordar ese tipo de problemas que pertenecen a la clase NP-C [1]. Aquellos algoritmos son llamados heurísticos.

En este contexto, los problemas son tratables o del tipo P para los que existe un algoritmo de complejidad polinomial capaz de resolverlos; o son problemas NP para los cuales no se conoce un algoritmo de complejidad polinomial capaz de resolverlos. Adicionalmente existe un subconjunto de la familia NP, llamado NP-C, que presenta un mayor grado de dificultad de resolución [6-7].

Entre los problemas que se pueden resolver en tiempo polinomial se encuentran diversas variedades de orden, como los logarítmicos (log(n)), los lineales (n), los cuadráticos (n²), los cúbicos (n³). En los problemas NP la complejidad de los algoritmos es del tipo exponencial (2ⁿ) o factorial (n!), donde si se aumentan las variables de entrada (n), el tiempo de resolución del problema pudiese crecer significativamente. En general estos problemas se reducen a maximizar o minimizar una función objetivo sujeta a restricciones, por ejemplo, encontrar un camino óptimo, o de costo mínimo, al recorrer un conjunto de ciudades pasando solamente una vez por cada ciudad.

En la actualidad no se conoce un algoritmo capaz de encontrar soluciones óptimas para la familia de problemas pertenecientes a la clase NP-C, esto es, encontrar óptimos en tiempo polinomial, utilizando una máquina determinística, para instancias complejas.

Una instancia es la especificación de un problema en particular que pertenece a una familia de problemas, por ejemplo, la instancia indica la ubicación de ciudades y costo que demanda recorrerlas, otra instancia indicará otras ciudades y costos. Este tipo de especificación corresponde a instancias del Problema NP-C del Vendedor Viajero (PVV) o Traveling Salesman Problem (TSP) en inglés.