HEURÍSTICAS Y EL PROBLEMA DEL AGENTE VIAJERO

HEURÍSTICAS Y EL PROBLEMA DEL AGENTE VIAJERO

Los métodos heurísticos son preferibles a los métodos no informados en la solución de problemas difíciles para los que una búsqueda exhaustiva necesitaría un tiempo demasiado grande. Esto cubre prácticamente la
totalidad de los problemas reales que interesan en Inteligencia Artificial
El concepto de heurística es difícil de aprehender. Newell, Shaw y Simon en 1963 dieron la siguiente definición: "Un proceso que puede resolver un problema dado, pero que no ofrece ninguna garantía de que lo hará, se llama una heurística para ese problema"
Si nos planteamos seguir concretando como aprovechar la información sobre el problema en sistemas de producción, la siguiente idea consiste en concentrar toda la información heurística en una única función que se denomina  función de evaluación heurística. Se trata de una función que asocia a cada estado del espacio de estados una cierta cantidad numérica que evalúa de algún modo lo prometedor que es ese estado para acceder a un estado objetivo. Habitualmente, se denota esa función por h(e). La función heurística puede tener dos interpretaciones. Por una parte, la función puede ser una estimación de lo próximo que se encuentra el estado de un estado objetivo. Bajo esta perspectiva, los estados de menor valor heurístico son los preferidos. Pero en otros casos puede suceder que lo que convenga sea maximizar esa función.
El problema del viajante.

• Estado inicial: un viajante se encuentra en una capital de provincia.
• Estado meta: quiere viajar a otra capital por la mejor ruta posible (la más corta)
• Medios: Las capitales de provincia colindantes están unidas por carreteras; se dispone de un mapa con la disposición de las provincias y sus "coordenadas" en kilómetros respecto al "centro" (por ejemplo, Madrid, con coordenadas (0,0)).

• Una función heurística para ese problema consiste en asignar a cada estado un valor que es la distancia aérea (en línea recta) con el estado objetivo. Dicha distancia es la distancia euclídea entre las coordenadas de dos ciudades.

• Se elige una ciudad como siguiente en el camino cuando la suma de la distancia a la ciudad actual más la distancia aérea a la meta sea la menor.

• Cuatro alternativas en la primera etapa: Cáceres, Palencia, Zaragoza y Valencia.

• Función heurística considerando la distancia aérea: Distancia (Madrid, Santander)=Distancia(Madrid, Palencia)+Distancia aérea (Palencia, Santander) que es más pequeña que la obtenida a través de Cáceres Distancia (Madrid,Santander)=Distancia(Madrid, Cáceres)+Distancia aérea (Cáceres, Santander)

• Función heurística considerando distancias parciales: Distancia (Madrid, Santander)=Distancia(Madrid, Palencia)+Distancia (Palencia, Santander)

El problema del cartero viajante (Traveling Salesman Problem – TSP) es un problema típico de optimización. En este documento se presentan algunas técnicas heurísticas de optimización (Algoritmos Genéticos, Simulated Annealing, Colonia de Hormigas, Búsqueda Tabú y Grasp) aplicadas a la solución de este problema. La solución al problema consiste en encontrar la 

ruta óptima para recorrer n ciudades sin repetirlas finalizando en la ciudad de origen.

OPINIÓN:

A pesar de que el sistema de prueba es pequeño, se podrán establecer algunas conclusiones respecto a los métodos de optimización utilizados en su solución: Todos los métodos alcanzan la solución óptima, sin embargo, estos presentan inconvenientes si se implementan en su forma natural, por lo que tienen que ser usados operadores especializados, como en el caso de los AG, que requieren operadores especializados tanto para el crossover como para la mutación con el fin de evitar la generación de rutas infactibles, así todos los métodos usados requieren que el movimiento que se lleve a cabo no produzca infactibilidades, caso contrario no será posible encontrar la solución. 

El problema del viajante de comercio

EJEMPLO: Se conocen las distancias entre un cierto número de ciudades. Un viajante de comercio debe partir de una de ellas, visitar cada ciudad exactamente una vez, y regresar al punto de partida habiendo recorrido en total la menor distancia posible. Supondremos que la distancia entre dos ciudades nunca es negativa. Todos los algoritmos exactos conocidos necesitan un tiempo exponencial. Son inviables para ejemplares grandes del problema.
Se puede representar este problema mediante un grafo completo no dirigido con n vértices (el grafo sería dirigido si la matriz de distancias no fuese simétrica). Un posible algoritmo voraz escogería en cad iteración la arista más corta aún no considerada que cumpliera las dos condiciones siguientes:

• no formar un ciclo con las arista ya seleccionadas (excepto en la última iteración, que completa el viaje);
• no es la tercera arista que incide en el mismo vértice de entre los escogidos.

Por ejemplo, consideremos el problema con seis ciudades y con la siguiente matriz de distancias
 
 

Nodos	2	3	4	5	6
1	3	10	11	7	25
2		6	12	8	26
3			9	4	20
4				5	15
5					18

Se escogerían las aristas en el orden {1,2}, {3,5}, {4,5}, {2,3}, {4,6}, {1,6} para formar el ciclo (1,2,3,5,4,6,1) de longitud 58. La arista {1,5} sería rechazada porque formaría el ciclo incompleto (1,2,3,5,1) y además porque sería la tercera arista que incide en el vértice 5.
En este caso, el algoritmo voraz no encuentra el ciclo óptimo ya que, por ejemplo, el ciclo (1,2,3,6,4,5,1) tiene una longitud de 56.
Puedes ver el funcionamiento del algoritmo. Tienes que tener en cuenta que debes rellenar los datos tal como lo ves en la tabla anterior (de forma triangular), ya que como se ha comentado anteriormente, la matriz de distancias es simétrica. Puedes cambiar las distancias; el algoritmo siempre empezará el ciclo eligiendo la arista menor, por tanto el nodo de salida será el que forme parte de esa arista ( Si la arista de menor longitud fuese la formada por los nodos (3,5), el ciclo empezaría  con los nodos (3,5,.......).