HEURISTICAS PARA EL
PROBLEMA DEL AGENTE VIAJERO
Se
denomina heurística a la capacidad de un sistema para realizar de forma
inmediata innovaciones positivas para sus fines. La capacidad heurística es un
rasgo característico de los humanos, desde cuyo punto de vista puede
describirse como el
arte y la ciencia del descubrimiento y de la invención o de resolver problemas mediante la creatividad y el pensamiento
lateral o pensamiento divergente.
Las
restricciones que fastidian por su cantidad y estructura son las ultimas (las
de destrucción de sub-recorridos). Lo que queda sin ellas es un simple Problema
de Asignación (flujo en redes). Que se resuelve fácilmente. Entonces es natural
que los algoritmos de B + B o de planos cortantes para el PAV utilicen algún
esquema de relajación - restricción que siga estas líneas.
Los algoritmos modificados relajan estas
restricciones y resuelven la relajación (asignación). Si la solución obtenida
es un recorrido, tenemos COR, listo. Caso contrario, añadir restricción que
destruya algún sub-recorrido (si se hace directo es planos cortantes, si se
hace a través de cotas y en subgrafos es B+B) y proceder con la nueva relajación.
Estos algoritmos son computacionalmente aplicables s´olo a problemas con unos
pocos cientos de ciudades. Para problemas m´as grandes se necesitan métodos heurísticos.
ALGUNAS HEURISTICAS PARA EL PAV:
Las
heurísticas a ser discutidas se pueden clasificar en dos tipos: Las que
construyen recorridos y las que los mejoran. Comenzamos con las primeras.
La
idea se puede resumir así:
1.
Encontrar un sub-recorrido inicial (basta que tenga dos ciudades pero puede ser
de más).
2.
Seleccionar una ciudad a ser añadida al sub-recorrido, usando alguna regla de selección.
3.
Insertar el nodo correspondiente en el sub-recorrido, basándose en un criterio
de inserción.
4.
Si se tiene un recorrido, parar. Caso contrario ir a 2.
Las
distintas reglas de selección y criterios de inserción dan lugar a diferentes heurísticas.
Veamos una de ellas: La heurística de inserción más barata.
Se
comienza con un sub-recorrido T con dos ciudades i1 e i2, tales que
di1i2
+ di2i1 = mın/i=j (dij + dji)
Es
decir, el sub-recorrido más cortó entre dos ciudades. Luego se busca el costo mínimo
de inserción en el sub-recorrido:
ck∗ = mın/(i, j)∈T (dik
+ dkj − dij)
Y
se selecciona un nodo k∗ con ese costo. Luego se
inserta el nodo entre las ciudades involucradas en el cálculo de ck∗. Finalmente se repite este proceso (con los sub-recorridos
que se van generando) hasta construir un recorrido.
EJEMPLO DE LA HEURÍSTICA DE INSERCIÓN
MÁS BARATA
Consideremos
el PAV dado por la siguiente matriz de distancias:
En
primer lugar tenemos que encontrar el sub-recorrido más barato con dos
ciudades. Esto se hace calculando mıni6=j (dij + dji) que corresponde a sumar
elementos simétricos de la matriz D y ver cuál nos da menor. En este caso el más
pequeño es d78 + d87 = 3 + 1 = 4.
Calculemos
ahora el mínimo costo de inserción: ck∗ =
mın(i, j)∈T (dik + dkj − dij) :
De donde el mínimo valor es 12 y se obtiene de tres
formas. Seleccionamos la inserción del nodo 1 entre los nodos 8 y 7. Las
restantes iteraciones se muestran en la siguiente tabla:
Dando como recorrido final: 1 → 2 → 3 → 7 → 8 → 6 → 4 → 5
→ 1. Este recorrido, casualmente, es óptimo. No siempre se corre con la misma
suerte. Note que en la tercera columna se calcula, en cada fila y para cada k,
el mínimo costo de inserción de ese k particular (en algunos casos hay empate y
el k se repite), y luego se toma el mínimo de todos ellos.
OPINION SOBRE EL TEMA
La heurística se puede describir como el arte y la
ciencia del descubrimiento y de invención de resolver problemas mediante la
creatividad y el pensamiento. En si las heurística y el problema del agente
viajero se clasifican en dos tipos las que construyen recorridos y las que la
mejoran. El problema del agente viajero consiste en encontrar el recorrido más
corto.
BIBLIOGRAFIA
No hay comentarios.:
Publicar un comentario