PROBLEMA DEL AGENTE VIAJERO MEDIANTE ALGORTIMO DE BÚSQUEDA TABÚ

PROBLEMA DEL AGENTE VIAJERO MEDIANTE ALGORTIMO DE BÚSQUEDA TABÚ

Heurísticas

El método heurístico esta relacionado con la tarea de resolver problemas inteligentes utilizando la información que se tiene disponible. Estos métodos aproximados son procedimientos eficientes para encontrar buenas soluciones aunque no se puedan comprobar que sean óptimas.

Metahurísticas

Su propósito es obtener mejor resultados que los alcanzados por los métodos heurísticos. En pocas palabras, las Metahurísticas son estrategias para diseñar o mejorar los procedimientos heurísticos para obtener un alto rendimiento.

Las Metahurísticas se dividen en:

1. Metahurísticas constructivas

2. Metahurísticas evolutivas

3. Metahurísticas de búsqueda

Para fines de este trabajo solo se describirá lo que es una Metahurística de búsqueda.

Estos métodos presuponen que existe una solución y realizan procedimientos de búsqueda, la diferencia con los métodos analíticos es que no necesariamente se encontrará solución óptima; aunque uno de los riesgos al usar un algoritmo de búsqueda es el de alcanzar un óptimo local del que ya no sea posible salir.

Las principales Metahurísticas de búsqueda global surgen de las tres formas principales de los óptimos locales:

a) Volver a comenzar la búsqueda desde la otra solución inicial.

b) Modificar la estructura de entornos

c) Permitir movimientos de empeoramiento de la solución actual

Algunos ejemplos de Metahurísticas de este tercer grupo son:

i. Búsqueda Tabú (Tabu Search)

ii. Templado Simulado (Simulated Annealing)

En este caso vamos solo a manejar Búsqueda Tabú para la solución del problema de agente viajero.

Búsqueda Tabú

La característica que distingue a este método de las otras Metahurísticas de búsqueda es el uso de memoria la cuál tiene una estructura basada en una lista tabú y mecanismos de selección; la memoria se implementa mediante estructuras simples con el objetivo de dirigir la búsqueda teniendo en cuenta la historia de esta, es decir, el procedimiento trata de extraer información de lo ya sucedido y actuar en consecuencia.

Una lista Tabú es una memoria de corto plazo que contiene las soluciones que fueron visitadas en el pasado reciente (menos n iteraciones atrás donde n es el número de soluciones previas que van a ser almacenadas).

...