Subscribe:

domingo, 23 de noviembre de 2014

Recocido simulado aplicado a TSP - Prueba 1

El problema del agente viajero (Travel Salesman Problem a.k.a. TSP) es un problema de optimización combinatoria del tipo NP, en el cual se debe encontrar un camino que recorra todos los pueblos (vertices) de un mapa (grafo) con el menor costo posible. Para resolver este tipo de problemas se utilizan métodos Heurísticos (prueba y error para los cuates) debido a que un método exacto (por ejemplo una búsqueda exhaustiva) necesita una gran cantidad de tiempo en arrojar la respuesta, causando que cuando la tengamos ya no sea útil, o en el peor de los casos, que necesite de tiempos tan grandes como la vida del universo.

Entre los muchos métodos heurísticos que existen, hice la prueba para resolverlo con Recocido simulado (Simulated annealing). Escogí éste método debido a que nunca había intentado codificarlo, y realmente no lo entendía bien, y porque para mi proyecto final de Optimización tengo que aplicarlo a otro tipo de problema (Set covering); así que a grosso modo funciona de la siguiente manera.

Creamos una solución inicial aleatoria, y comenzaremos a buscar soluciones en la vecindad de la solución. Para cada solución nueva que encontremos, vamos a medirla con contra la solución actual con que contamos, y si resulta ser mejor (con menor costo en este caso) la tomaremos como nuestra solución actual. En caso contrario, usaremos el criterio (o paso) de Metropolis, que nos dirá si debemos darle esa nueva oportunidad. Esto para no quedar estancados en un óptimo local. Si el valor obtenido por exp(-1*((f'(x)-f(x))/T)) es menor a un valor aleatorio entre 0 y 1, entonces le damos la oportunidad, de lo contrario, descartamos esa solución. La T que aparece en la exponencial es un valor muy grande que simula ser la temperatura a la que se funden los metales (cabe mencionar que SA es un método derivado de del proceso de recocido del acero), esta temperatura se irá disminuyendo poco a poco hasta llegar a un punto en que se estabilizará, que es la condición que marca el fin del algoritmo (en este caso empieza con un valor de 10*(tamaño del grafo)^8, y disminuye multiplicando T por .99, hasta estabilizarse en un valor menor a 0.05).

Sin más por el momento, y esperando haber sido claro con el funcionamiento del algoritmo, aquí dejo el resultado. Cabe mencionar que no es perfecto y tiene varias cosas que se pueden mejorar, pero vaya que me sirvió para terminar de entender el funcionamiento del recocido, así como para poder plantear el proyecto final (que llevo postergando por 11 horas el día de hoy).

Dejaré en la pestaña de ayuda un libro que está bastante interesante por si a alguno le interesa el tema.

Saludos.

4 Comentarios:

Estefania López dijo...

Buenas estoy realizando un trabajo para la universidad y tengo este algoritmo con este problema con un algoritmo voraz pero tambien lo tengo que realizar para este, yo lo estoy haciendo en java pero me es de ayuda aunq sea en c lo que pasa que mi problema esq no e visto nunca c++ solo c y no se a que se refieren las lineas memcpy(probable,actual,sizeof(probable)); y swap(vect[inicio],vect[fin]); son funciones?

Fernando Soto dijo...

Hola Estefanía, memcpy es una función de C de la librería string.h (cstring en C++) que permite copiar el contenido de una dirección de memoria a otra ( del vector actual al probable, en este caso). y funciona de la siguiente manera

memcpy(dirección destino, dirección a copiar, tamaño de la dirección destino).

sizeof te retorna el tamaño de lo que envíes a la función, por eso lo puse dentro del memcpy.

Swap lo que hace es intercambiar dos datos, es como si escribieras (en este caso del algoritmo)

shuffle(int vec[]){
int inicio, fin, aux;
inicio = 1+rand()%(tam-2);
fin = 1+rand()%(tam-2);
//Aquí iría swap
aux = vec[inicio];
vec[inicio] = vec[fin];
vec[fin] = aux;
}

Cualquier duda que tengas, me puedes contactar por aquí o por mi correo: zomaotoko@gmail.com

Espero te sirva, saludos.

Unknown dijo...

Gracias fer, por ti pasaremos elvita :)

Anónimo dijo...

Gracias fer, por ti pasaremos elvita :) x2

Publicar un comentario