ENUNCIADO:
Un
agente viajero, partiendo de su ciudad de origen, debe visitar exactamente una
vez cada ciudad de un conjunto de ellas (previamente especificado) y retornar
al punto de partida. Un recorrido con estas características, es llamado dentro
de este contexto un tour. El problema consiste en encontrar el tour para el
cual la distancia total recorrida sea mínima. Se asume que se conoce, para cada
par de ciudades, la distancia entre ellas.
La
primera solución reportada para resolver el problema del Agente Viajero fue en
1954, cuando George Dantzig, Ray Fulkerson, y Selmer Johnson publicaron
la descripción de un método de solución del PAV (Problema del Agente Viaje o
sus siglas en inglés TSP – Travel Sailsman Problem) titulado “Solutions of a
large scale traveling salesman problem“ (Soluciones de gran escala para el
problema del agente viajero) para resolver una instancia de 49 ciudades donde
un agente viajero desea visitar un conjunto de ciudades, asignándoles un costo
por visitar ciudades contiguas (distancia de traslado entre dos ciudades). Para
esta solución se propusieron 2 condiciones: regresar a
la misma ciudad de la cual partió y no repetir ciudades con el objetivo de
encontrar una ruta o un camino con el menor costo posible.
Por
ejemplo:
Si
tenemos 3 nodos (a, b y c) por visitar, entonces tendríamos una función de
combinaciones sin repetición c(3,2), es decir, tendríamos 6 posibles
soluciones: abc, acb, bac, bca, cab, cba, para el caso de 4 nodos tendríamos 12
combinaciones, para 10 nodos tendríamos 90 combinaciones, para 100
ciudades tendríamos 9,900 combinaciones y así sucesivamente. Como ejemplo
en el problema del Ulises de Homero que intenta visitar las ciudades
descritas en la Odisea exactamente una vez (16 ciudades) donde existen
múltiples conexiones entre las diferentes ciudades, Grötschel y Padberg (1993)
llegó a la conclusión de que existen 653,837’184,000 rutas distintas para la
solución de este problema.
ALGORITMOS
PARA LA SOLUCIÓN DEL TSP : HERUSTICA Y METAHERUSTICA
ü Heurísticas
de Propósito Especial
Empezaremos
describiendo algunas heurísticas de propósito especial que han sido propuestas
para resolver el TSP. Se llaman de propósito especial, porque explotan la
estructura y características particulares de cada problema.
La primera familia de esta clase de heurísticas que
describiremos pertencen a las heurísticas de tipo miope (greedy en inglés), son
llamadas así porque sólo se preocupan por hacer lo mejor que pueden localmente,
sin ver más allá de un cierto entorno muy cercano.
(a) El vecino más cercano: Se trata de un
procedimiento constructivo, se parte de elegir un vértice inicial, llamémoslo
j1. Una vez seleccionado, mediremos la distancia que hay de este vértice a los restantes,
y elegiremos ahora aquél cuya distancia al vértice inicial sea la mínima (es
decir elegimos al vecino más cercano), y lo llamaremos j2. De la misma forma,
construiremos una trayectoria j1, j2, j3,…jk, jk+1, …,jn, donde el vértice jk+1
se elige tomando la mínima distancia que hay desde jk hasta cada uno de los
vértices que sean distintos de los ya elegidos j1, j2, j3, jk. Al terminar, se
debe de agregar el arco que va del vértice jn., hasta el vértice j1. Con esto
habremos completado el tour. Esta heurística tiene una ventaja en las primeras
selecciones, sin embargo, el problema que presenta es que en los últimos pasos
puede elegir aristas de longitud muy grande, especialmente en la última.
(b) La inserción más cercana: Este procedimiento es
también constructivo, pero en contraste con el anterior, en el cual se tiene un
camino, y sólo al final se completa un tour, aquí tenemos subtours, los cuales
van creciendo hasta completar un tour que abarque todos los vértices. Iniciemos
con un subtour, al cual llamaremos T, queremos ahora insertar el nodo “más
cercano” a este subtour para ampliarlo. Así que examinemos primero todos los
nodos j que no estén aún incluidos en T.y vamos a definir para estos nodos, su
distancia a T de la siguiente manera: d( j,T) es la distancia mínima que hay
desde el nodo j a cualquiera de los nodos que pertenecen a T. Ordenamos las distancias
calculadas de menor a mayor, y llamemos j* al nodo que se encuentra al
principio de esta lista, este será el nodo “más cercano” a T. Vamos ahora a
seleccionar dentro de T al nodo que se encuentre “más cerca” de j*, esto es,
medimos la distancia desde j* a cada uno de los nodos de T, y llamaremos k*
aquel nodo dentro de T, cuya distancia a j* sea la menor de todas.
Ampliaremos ahora el subtour insertando a j* entre
k* y alguno de sus dos vecinos en T, esto es, si (k1, k*) y (k*, k2) son dos
aristas de T y la distancia de j* a k1, es menor o igual que la distancia de j*
a k2, entonces j* se inserta entre k1 y k*. El proceso terminará cuando se haya
construido un tour completo. Como en el caso anterior, no se puede garantizar
que se produzca una buena solución.
ü Metaheurísticas
Las metaheurísticas son una clase de métodos de
aproximación, que se diseñan para atacar problemas difíciles para los cuales
las heurísticas de propósito especial han fracasado en dar resultados efectivos
y eficientes. Las metaheurísticas proporcionan marcos generales que permiten crear
nuevos híbridos combinando diferentes conceptos derivados de las heurísticas
clásicas, la inteligencia artificial, la evolución biológica, los sistemas
neuronales, la mecánica estadística y el psicoanálisis freudiano. Estas
familias de enfoques incluyen, pero no están limitadas a algoritmos genéticos,
GRASP, redes neuronales, búsqueda tabú y recocido simulado.
El método metaheurístico que emplearemos aquí,
Búsqueda Tabú, fue propuesto por Fred Glover en 1986, y está basado en el
psicoanálisis freudiano.
Iniciaremos
describiendo qué es un método de búsqueda local. Se trata de un método
iterativo el cual da inicio desde una solución arbitraria, el procedimiento
consiste en explorar una vecindad previamente definida para cada punto del
espacio de soluciones y elige una nueva solución dentro de tal vecindad, la
cual mejora el valor que se tiene a mano. La búsqueda termina cuando se alcanza
una solución tal que es la mejor dentro de la vecindad predefinida, esto es ya
no puede seguirse mejorando. A esta solución se le llama un mínimo local. En
muchas ocasiones, este mínimo local será la solución óptima del problema, sin
embargo, no podemos esperar que siempre suceda esto. Al contrario es plausible
esperar que este mínimo local se encuentre lejos de la solución óptima del problema.
En el caso
particular del TSP, un método de búsqueda local sencilla, es el llamado 2-opt.
Este consiste en eliminar del tour un par de aristas que no sean adyacentes, y
reemplazarlas con el único par de aristas con el cual se puede formar
nuevamente un tour. Éste se ilustra en la siguiente figura.
(a) Solución inicial; (b) Eliminación de dos
aristas: (2,3) y (5,4);
(c) Nuevo tour sustituyendo con las aristas (2,5) y
(3,4)
TS guía un procedimiento de búsqueda local
para continuar más allá de óptimos locales, esto es al no poder seguir mejorando
la solución, se permite tomar otra solución aún cuando el valor no mejore, sino
que se degrade, esto permite salir del óptimo local encontrado, pero al mismo
tiempo se corre el peligro de caer en un ciclo, de mejorar-empeorar la
solución, para evitar esto, se emplea una estrategia que modifica las
vecindades a medida que la búsqueda avanza. TS utiliza estructuras de memoria
para determinar esta vecindad modificada, las soluciones permitidas se
determinan identificando soluciones encontradas dentro de un horizonte
especificado. En nuestro ejemplo, dada una solución particular, una vez
suprimido un par de aristas del tour, estas dos aristas no pueden formar parte
del tour por un determinado número de iteraciones, este número de iteraciones
se conoce como la permanencia tabú. Simétricamente cuando un par de aristas se
insertan en un tour, no podrán ser suprimidas durante un número de iteraciones.
Si la permanencia tabú se elige de manera adecuada, la búsqueda podrá continuar
más allá de los óptimos locales sin caer en ciclos, y eventualmente alcanzar, si
no el óptimo global del problema, sí soluciones que estén cerca de él.
Conclusión:
Este problema se me hace muy interesante, pues por lo que he investigado es muy complejo para su resolución cuando este se generaliza. En mi opinión la AI es una gran herramienta para llegar a la solución, a través de sus programas, pero hay que tomar en cuenta que esto no se llevaría a cabo sin primero tomar en cuenta la heurística que hay detrás de ella, para así poder plasmarlo en un operador.
Referencias:
http://yalma.fime.uanl.mx/~roger/work/Papers/article/article-inge-2000.pdf
http://www.uaeh.edu.mx/scige/boletin/tlahuelilpan/n3/e5.html
No hay comentarios:
Publicar un comentario