miércoles, 5 de febrero de 2014

Comerciales viajeros y colinas peligrosas




El Sr. Lego no paraba de agitarse inquieto en su asiento, como esperando algo. Así llevaba ya un buen rato cuando me decidí a preguntarle si tenía algún problema o podía ayudarlo en alguna cosa.
Nada, nada -me respondío inquieto- cosas mías.
Con esas traté de meterme de nuevo en el código en el que estaba trabajando, pero los movimientos casi espasmódicos del Sr. Lego empezaban a ponerme nervioso. ¿Seguro que no le pasa nada Sr. Lego?
Al hacerle la pregunta volvió su cara y pude ver una mirada suplicante: Es que... esto no termina...
Me levanté y vi como estaba ejecutando un programa. Por lo menos llevaba una hora en ejecución.
Es que estoy tratando de resolver un problema para ganar un concurso que he encontrado en esta página.
El concurso consistía en encontrar la solución al conocido problema TSP (Traveling Salesman Problem). El problema consiste en una serie de ciudades que un viajante de comercio tiene que recorrer. El recurrido tiene que cumplir tres requisitos, que el número de kilómetros recorridos sea el mínimo posible, que el viajante no pase dos veces por la misma ciudad y que el viajante regrese a la ciudad de inicio.
¿Cómo está tratando de resolverlo Sr. Lego? -pregunté.
Estoy tratando de hacer una búsqueda en el espacio de estado del problema con las técnicas de búsqueda de las que hablamos hace algún tiempo.
Verá Sr. Lego, no creo que aquellas técnicas de búsqueda le sean muy útiles en este problema concreto, que pertenece a una clase de problemas que en Ciencias de la Computación se denomina "intratable", o más técnicamente, NP-Dificil.
NP-¿qué? -se extrañó el Sr. Lego.
Verá, hay problemas que son tan complejos que son computacionalmente irresolubles. Por mucho tiempo que dejara su ordenador funcionando jamás encontraría la respuesta, o en el mejor de los casos, tardaría miles o millones de años. Recuerde que ya lo comentamos el día que hablamos de la búsqueda en árboles.

Para medir la complejidad de un problema usamos la notación O (O grande), también conocida como cota superior asintótica.
La cara del Sr. Lego no dejaba lugar a dudas de que estaba a punto de abandonar su idea de resolver el problema que tenía entre manos.
No se asuste -continué- una función O(x) es cota superior de otra f(x) cuando para cualquier valor que pueda tomar f(x), la función O(x) siempre será mayor. Por ejemplo:
O(x)=4X² es cota superior de f(x)=4x, ya que sea cual sea x, O(x) tendrá un valor superior que f(x).
Se trata pues de buscar una función O(x) que nos sirva para medir, en el caso de que x tienda a infinito, cómo se comportaría nuestro programa en cuanto a operaciones que tendría que ejecutar. En el caso del TSP, usted está probando todas las combinaciones posibles de recorridos de ciudades, es decir, si tengo 5 ciudades necesito probar 5! (leído 5 factorial) combinaciones. Es decir, 120 combinaciones, nada que cualquier ordenador de andar por casa no pueda hacer en un plis plas.
¿Entonces? -preguntó confundido el Sr.Lego- ¿Por qué tarda tanto en terminar mi programa?
Verá, con tan sólo 20 ciudades tenemos 20! = 2432902008176640000 permutaciones. Si su ordenador puede realizar una permutación cada milisegundo, tardará aproximadamente 77.146.817 años en obtener la respuesta. ¡Más de 77 millones de años!. ¿Supongo que querrá irse hoy a comer? -bromeé.
En general, para n ciudades, usted necesitará n! combinaciones, por lo tanto, la complejidad de su programa usando la notación O será O(n!), que será cota superior de la complejidad del problema TSP usando una búsqueda como la que usted ha programado. Como le decía, es un problema intratable incluso para un número de ciudades moderado.
O sea, que no hay forma de resolverlo... -concluyó el Sr. lego.
Yo no he dicho eso. En realidad, si podemos permitirnos obtener una solución que sea buena aunque no sea la óptima, hay métodos que nos permiten acercarnos bastante a la solución, y en el mejor de los casos, incluso llegar a la solución óptima. Aunque casi nunca podremos tener la certeza de que la respuesta obtenida es la mejor posible.
Si quiere, Sr. Lego, le puedo mostrar una técnica llamada Hill Climbing, o escalada de la colina en español, para que pueda resolver su problema TSP.
Está bien, pero no pienso compartir el premio -dijo medio en broma, medio en serio.
Podríamos hacer una analogía con los problemas de optimización que nos hacían resolver en el instituto ¿los recuerda?
Sí, esos en los que había que encontrar el área máxima que podíamos hallar con x metros de alambrada ¿no?
Efectivamente, se trataba de encontrar el máximo o el mínimo de una función dada. Aquí podríamos decir que buscamos minimizar la suma de distancias que hay hay que recorrer para pasar por todas las ciudades. El problema es que no tenemos una función matemática que describa el problema. ¿Cómo encontrar entonces el máximo en este caso?
El Sr. Lego se quedó esperando a que continuara sin mediar palabra.
Imagine que en una noche oscura está usted perdido en el campo. No ve más allá de unos metros por delante, pero sabe que está en una colina y que en lo más alto hay un refugio ¿cómo trataría de llegar a ella si no puede orientarse?
Trataría de tomar el camino que tiene una pendiente ascendente más acusada. Si subo siempre acabaré llegando a lo más alto de la colina -me explicó el Sr. Lego.
¡Muy bien! Esta misma estrategia podemos aplicarla a nuestro problema, pero primero planteemos el problema en términos que nos permitan tratarlo convenientemente.
Diremos que una solución válida es un recorrido cualquiera que cumpla las condición de pasar por todas las ciudades sin repetir ninguna.
La función de evaluación que nos dirá cuánto de buena es esa solución será la suma de todas las distancias que hay que recorrer entre cada ciudad.
Además, para generar todas las combinaciones (estados) posibles, usaremos un operador consistente en permutar dos ciudades cualesquiera. Diremos que un estado es vecino de otro si entre ellos sólo se han permutado dos ciudades cualesquiera.
Era aparente que el Sr. Lego se esforzaba por anotar mentalmente lo que le estaba contando.
Se trata ahora de, partiendo de un estado, escoger el camino de máxima pendiente (o mínima pendiente si queremos minimizar la función). Esto es, trata de escoger aquel vecino que nos acerca más a nuestro destino. Por ejemplo, si tengo la siguiente ruta en la que cada número representa una ciudad: 1-5-3-4-2 cuya función de evaluación es 45Km (suma de las distancias), y evaluamos los siguientes vecinos (sólo evaluaremos 3 de todos los posibles para simplificar):

5-1-3-4-2 (47Km)
1-3-5-4-2 (26Km)
1-5-2-4-3 (39Km)

es obvio que el segundo vecino que hemos evaluado es el que más nos acerca a nuestro destino, por lo tanto, lo escogemos y volvemos a evaluar los vecinos de este nuevo estado. Repetiremos esta operación hasta que encontremos un estado cuyos vecinos no mejoran la función de evaluación.
La cara del Sr. lego se iluminó de golpe. Sin decir nada corrió a su mesa y se puso a teclear como un poseso. No pasó mucho tiempo hasta que vino a enseñarme como había implementado el algoritmo.


  1. import math
  2. import random
  3. from Tkinter import Tk, Canvas, BOTH
  4.  
  5.  
  6. def euclidean_distance(coord1, coord2):
  7.   lat1=coord1[0]
  8.   lon1=coord1[1]
  9.   lat2=coord2[0]
  10.   lon2=coord2[1]
  11.   return math.sqrt((lat1-lat2)**2+(lon1-lon2)**2)
  12.  
  13. # calcula la distancia cubierta por una ruta
  14. def evaluate_route(ruta):
  15.   total=0
  16.   for i in range(0,len(ruta)-1):
  17.     ciudad1=ruta[i]
  18.     ciudad2=ruta[i+1]
  19.     total=total+euclidean_distance(coord[ciudad1], coord[ciudad2])
  20.   ciudad1=ruta[i+1]
  21.   ciudad2=ruta[0]
  22.   total=total+euclidean_distance(coord[ciudad1], coord[ciudad2])
  23.   return total
  24.  
  25.  
  26. def hill_climbing():
  27.   # crear ruta inicial aleatoria
  28.   ruta=[]
  29.   for ciudad in coord:
  30.     ruta.append(ciudad)
  31.   random.shuffle(ruta)
  32.  
  33.   mejora=True
  34.   while mejora:
  35.     mejora=False
  36.     dist_actual=evaluate_route(ruta)
  37.     # evaluar vecinos
  38.     for i in range(0,len(ruta)):
  39.       if mejora:
  40.         break
  41.       for j in range(0,len(ruta)):
  42.         if i!=j:
  43.           ruta_tmp=ruta[:]
  44.           ciudad_tmp=ruta_tmp[i]
  45.           ruta_tmp[i]=ruta_tmp[j]
  46.           ruta_tmp[j]=ciudad_tmp
  47.           dist=evaluate_route(ruta_tmp)
  48.           if dist<dist_actual:
  49.             # encontrado vecino que mejora el resultado
  50.             mejora=True
  51.             ruta=ruta_tmp[:]
  52.             break
  53.  
  54.   return ruta
  55.  
  56.  
  57. if __name__ == "__main__":
  58.   num_stops=15
  59.   res_x=400
  60.   res_y=400
  61.   coord={}
  62.   for i in range(num_stops):
  63.     coord['city '+str(i)]=(random.randint(1,res_x),random.randint(1,res_y))
  64.  
  65.   ruta = hill_climbing()
  66.   print ruta
  67.   print "Distancia total: " + str(evaluate_route(ruta))
  68.  
  69.   # mostrar mapa
  70.   root = Tk()
  71.   canvas = Canvas()
  72.   # dibujar ruta
  73.   last_city=()
  74.   for ciudad in ruta:
  75.     x=coord[ciudad][0]
  76.     y=coord[ciudad][1]
  77.     canvas.create_rectangle(x, y, x+5, y+5, outline="#000", fill="#fb0")
  78.     canvas.create_text(x, y-5, text=ciudad, fill="purple", font=("Helvectica", "8"))
  79.     if last_city:
  80.       canvas.create_line(last_city[0],last_city[1],x,y, arrow="last")
  81.     last_city=(x,y)
  82.   canvas.pack(fill=BOTH, expand=1)
  83.   root.geometry(str(res_x)+"x"+str(res_y))
  84.   root.mainloop()
  85.  



Ejecutamos el programa y obtuvimos una más que correctísima solución al problema TSP con 15 ciudades.





¿Nos atrevemos con 20 ciudades? A ver si es verdad que no tenemos que esperar 77 millones de años.
Al ejecutar el programa con 20 ciudades el resultado fué el siguiente.




Uhmmm, creo que empezamos a tener problemas -dije. Fijesé en ese cruce de flechas, no es buen presagio. Creo que hemos caído en un mínimo local.
¿Un qué? -dijo el Sr. Lego.
Imagine que sigue perdido en la misma colina de la que hablabamos antes. Usted llega a un pico, pero ¿podría asegurar que ese es el pico más alto de la colina?
No -respondió el Sr. Lego. Podría haber otro más alto, pero no podría verlo.
Exacto. Esto es lo que nos ha ocurrido al ejecutar el programa con las 20 ciudades. Hemos llegado a un mínimo (o máximo) relativo, también conocido como mínimo (o máximo) local.




Una posible solución es lanzar el algoritmo varias veces, pero cada vez empezando desde un estado distinto, y quedándonos con el mejor resultado de todos. Es lo que se llama Hill Climbing iterativo.
El Sr. Lego corrió de nuevo y modificó ligeramente el programa.


  1. import math
  2. import random
  3. from Tkinter import Tk, Canvas, BOTH
  4.  
  5.  
  6. def euclidean_distance(coord1, coord2):
  7.   lat1=coord1[0]
  8.   lon1=coord1[1]
  9.   lat2=coord2[0]
  10.   lon2=coord2[1]
  11.   return math.sqrt((lat1-lat2)**2+(lon1-lon2)**2)
  12.  
  13. # calcula la distancia cubierta por una ruta
  14. def evaluate_route(ruta):
  15.   total=0
  16.   for i in range(0,len(ruta)-1):
  17.     ciudad1=ruta[i]
  18.     ciudad2=ruta[i+1]
  19.     total=total+euclidean_distance(coord[ciudad1], coord[ciudad2])
  20.   ciudad1=ruta[i+1]
  21.   ciudad2=ruta[0]
  22.   total=total+euclidean_distance(coord[ciudad1], coord[ciudad2])
  23.   return total
  24.  
  25.  
  26. def hill_climbing():
  27.   # crear ruta inicial aleatoria
  28.   ruta=[]
  29.   for ciudad in coord:
  30.     ruta.append(ciudad)
  31.   random.shuffle(ruta)
  32.  
  33.   mejora=True
  34.   while mejora:
  35.     mejora=False
  36.     dist_actual=evaluate_route(ruta)
  37.     # evaluar vecinos
  38.     for i in range(0,len(ruta)):
  39.       if mejora:
  40.         break
  41.       for j in range(0,len(ruta)):
  42.         if i!=j:
  43.           ruta_tmp=ruta[:]
  44.           ciudad_tmp=ruta_tmp[i]
  45.           ruta_tmp[i]=ruta_tmp[j]
  46.           ruta_tmp[j]=ciudad_tmp
  47.           dist=evaluate_route(ruta_tmp)
  48.           if dist<dist_actual:
  49.             # encontrado vecino que mejora el resultado
  50.             mejora=True
  51.             ruta=ruta_tmp[:]
  52.             break
  53.  
  54.   return ruta
  55.  
  56.  
  57. if __name__ == "__main__":
  58.   num_stops=20
  59.   res_x=400
  60.   res_y=400
  61.   coord={}
  62.   for i in range(num_stops):
  63.     coord['city '+str(i)]=(random.randint(1,res_x),random.randint(1,res_y))
  64.  
  65.   best_route=[]
  66.   for i in range(20):
  67.     ruta = hill_climbing()
  68.     if best_route:
  69.       if evaluate_route(ruta)<evaluate_route(best_route):
  70.         best_route=ruta[:]
  71.     else:
  72.       best_route=ruta
  73.  
  74.   ruta = best_route
  75.   print ruta
  76.   print "Distancia total: " + str(evaluate_route(ruta))
  77.  
  78.   # mostrar mapa
  79.   root = Tk()
  80.   canvas = Canvas()
  81.   # dibujar ruta
  82.   last_city=()
  83.   for ciudad in ruta:
  84.     x=coord[ciudad][0]
  85.     y=coord[ciudad][1]
  86.     canvas.create_rectangle(x, y, x+5, y+5, outline="#000", fill="#fb0")
  87.     canvas.create_text(x, y-5, text=ciudad, fill="purple", font=("Helvectica", "8"))
  88.     if last_city:
  89.       canvas.create_line(last_city[0],last_city[1],x,y, arrow="last")
  90.     last_city=(x,y)
  91.   canvas.pack(fill=BOTH, expand=1)
  92.   root.geometry(str(res_x)+"x"+str(res_y))
  93.   root.mainloop()


Al ejecutarlo vimos que el programa ya se desenvolvía bien con un número de ciudades mayores. Aun así, mientras más ciudades, más posibilidades de cruce de caminos encontrábamos, y más iteraciones necesitábamos para obtener un buen resultado.

¿Y no hay forma de mejorar el algoritmo para que sea más eficiente con un número de ciudades muy alto? -preguntó el Sr. Lego.

Lo hay -dije- pero se acerca la hora de comer, así que si le parece, otro día exploramos otras técnicas que nos ayuden a evitar caer en estos mínimos (o máximos) locales.

1 comentario: