Práctica 1 de Algoritmos Heurísticos y de Búsquedas

Eduardo Moreno Díaz Alumno Ingeniería Informática Universidad de Huelva

eduardo.diaz@alu.uhu.es

Resumen

El objetivo de este documento es el de presentar los resultado obtenidos en la práctica número uno de la asignatura Algoritmos Heurísticos y de Búsqueda en el curso 2010/2011. Se trata de resolver el problema conocido como “p-hub” a través de la implementación de los diferentes algoritmos estudiados en clase. Se realizará un estudio comparativo entre los diferentes casos del problema y las diferentes técnicas implementadas. Al final, se expondrán las conclusiones a las que hemos llegado partiendo desde la premisa de que los resultados se han obtenido a partir de una parametización proporcionada por el profesor y no se ha modificado en ningún momento.

1. Introducción

El problema del “p-hub”, también conocido como problema de nodos conectores y concentradores, modela la situación cuando n nodos pueden interactuar solamente a través de un conjunto de p hubs completamente conectados; estos dos conjuntos, hubs y nodos, y sus respectivos arcos de unión, conforman un grafo totalmente interconectado. Usando la cantidad de flujo y el coste por unidad de flujo entre dos nodos en una red, se debe decidir sobre la localización de hubs y sobre la asignación de cada nodo que no es hub a aquéllos que lo son [1]. Además, también se usan una serie de costes adicionales que influyen en la evaluación de la solución final. Estos costes son el de recogida, distribución y entrega. En esta memoria, se van a estudiar los problemas CAB(25,4), AP(40,3) y AP(50,5)

Con el objetivo de resolver los casos indicados, se van a implementar 5 métodos de búsqueda diferentes: búsqueda aleatoria, búsqueda local, enfriamiento simulado y búsqueda tabú. También se usará un algoritmo de comparación greedy.

2. Descripción del problema

O’Kelly [2], describe el problema considerando los siguientes valores: Wij= número de unidades de tráfico que se envían desde el punto i al j. Cij= coste unitario por unidad de tráfico enviada sobre el arco (i,j).Las variables de decisión vienen definidas por:

1, si el punto i es asignado al hub j Xij =

0, en otro caso

1, si el punto j es hubYij =

0, en otro caso

La fórmula matemática corresponde a:

, donde β, γ, α representan los costes de recogida, distribución y entrega en este orden, y está sujeta a las siguientes restricciones:

La representación que se hará de una solución es la siguiente:

3. Búsqueda Aleatoria

El algoritmo de Búsqueda Aleatoria (BA en adelante) empleado consiste en generar una solución aleatoria en cada iteración. Para ello, selecciona aleatoriamente p nodos como hubs y les asigna también aleatoriamente un nodo de los restantes, asegurándose de que cada nodo esta conectado a un hub.

Procedure BA solucion = vacio hubs = vacio

hubs = Elegir p hubs y marcarlos como hubs;

Repetir (resto de nodos) hub = Elegir un hub de hubs solucion[nodo] = hub Fin Devolver solucionFin

Este proceso se realizó durante 1600*nodos iteraciones y con 10 semillas diferentes para el generador de aleatorios. Como resultado se devuelve el mejor resultado de todas ellas.

4. Búsqueda Local

La Búsqueda Local (BL) implementada parte de la solución generada por la BA y la modifica para ir explorando el vecindario de soluciones. Esta exploración consiste en cambiar bien a un nodo de hub o seleccionar a un hub y cambiarlo por otro que sea nodo. De esta forma, la relación exploración/explotación del vecindario queda satisfecha. Para que sea más eficiente, se ha especificado el número de vecinos que puede generar, oscilando dicho valor entre 2*p y n/2*p. Se preserva así la búsqueda de una solución en tiempo razonable y con coste computacional controlado.

Procedure BL solucion = solucionInicial; mejorSolucion = solucion

Repetir nuevaSol = MejorSolucionVecindario (solucion) Si coste (nuevaSol < mejorSolucion) mejorSolucion = nuevaSol Fin Incrementar it Hasta it <iteracionesFin

Procedure MejorSolucionVecindario(solucion) hubs = todos los hubs de solucion

Hacern = Elegir nodo de solucionSi (nodo = hub)

nuevoHub = Elegir un hub de hubs[] que no sea n

Convetir nuevoHub en hubSino

hub = Elegir un hub de hubs[]solucion[nodo] = hub

Fin

Si coste (solucion < mejorSolucion)mejorSolucion = solucion

Fin Mientras numeroVecinosAGenerar < n/2*p Devolver mejorsolucion;Fin

Al tratarse de un algoritmo que no reaprovecha las soluciones que va generando, se

hace necesario hacer gran número de iteraciones para que los resultados se consideren como buenos.

Del mismo modo que la BA, se ha realizado 1600*nodos iteraciones y con 10 semillas diferentes para el generador de aleatorios. La solución inicial se ha obtenido como resultado de una BA

5. Enfriamiento Simulado

El algoritmo de Enfriamiento Simulado (ES) es un método de búsqueda por entornos caracterizado por un criterio de aceptación de soluciones vecinas que se adapta a lo largo de su ejecución.

El problema principal de los algoritmos de búsqueda local utilizados en problemas de optimización reside en que a partir de una solución inicial que se va modificando y sustituyendo por soluciones mejores, se llega a una solución óptima local no necesariamente global. Una manera de evitar esto es permitir que algunos movimientos se realicen hacia soluciones peores. Pero por si la búsqueda está yendo realmente hacia una buena solución estos movimientos de “escape” deben realizarse de un modo controlado [3].

Se hace uso de la llamada variable Temperatura, T, cuyo valor determina en qué medida pueden aceptarse nuevas soluciones vecinas L(T) peores que la actual. Esta Temperatura se inicializa aun valor alto:

T0 = μ / -log(Φ) * C(S0)donde C(S0) es el costo de la solución inicial y Φ[0,1] es la probabilidad de aceptar una solución un μ por 1 peor que la inicial.

Esta temperatura va decreciendo gradualmente a medida que avanza el algoritmo. Esta probabilidad de aceptación depende de la diferencia de coste en la solución actual y la vecina y la temperatura T.

P = e (-/T)

A mayor temperatura, mayor probabilidad de aceptación. Una vez finalizada la generación de soluciones vecinas, se decrementa la temperatura siguiendo un modelo, como puede ser Cauchy:

Tk = T0 / (1+k)

donde k la iteraron actual.

Normalmente el criterio de parada será un número de iteraciones dadas, aunque también puede utilizarse un nivel de temperatura, sólo que este último caso resulta complejo de manejar.

Procedure ES T = T0

Sact = S0

Mientras it < iteraciones Para c=1 Hasta L(T) Hacer Scand = generarSolucion(Sact) Si coste(Scand < Sact) ó criterioAceptación(Scand) Sact = Scand

Fin Fin T = ↓T Incrementar it FinFin

En la fase de experimentación se ha realizado este algoritmo con 80*n iteraciones, el número de soluciones vecinas L(T) = 20, μ = Ф = 0,3 con 10 semillas diferentes. En la generación de vecinos se han utilizado el mismo esquema de generación de vecinos que el los algoritmos ya presentados pero en dos versiones que alteran la probabilidad de convertir a hub o cambiar de hub entre 0.4 y 0.6 para la primera versión y 0.6 y 0.4 para la segunda. La solución inicial parte de una solución generada por BA.

6. Búsqueda Tabú

La Búsqueda Tabú (BT) es un procedimiento heurístico de memoria adaptativa que explora el espacio de soluciones a través de repetidos movimientos desde una solución a la mejor de sus vecinas tratando de evitar los óptimos locales. BT realiza una búsqueda por entornos en la cual se desplaza en cada iteración a la mejor solución no tabú del vecindario de la solución actual. Los principales atributos de cada solución visitada son almacenados en una lista tabú por un determinado número de iteraciones para evitar que estas soluciones sean re-visitadas, evitando ciclos en la búsqueda por entornos. Así, un elemento del vecindario de la solución actual es declarado tabú (prohibido) si alguno de sus atributos está en la lista tabú.

Para escapar de los óptimos locales, se ha implementado un conjunto de técnicas de reinicialización basadas en probabilidades. Estas técnicas retornan una solución a partir de la cual el algoritmo puede volver a ser lanzado. En esta implementación se ha optado por tres: aleatoria, que

genera una nueva solución partiendo de la resultante de una BA; mejor solución encontrada, que genera la nueva solución igualándola con la mejor encontrada durante todo el proceso del algoritmo; y memoria a largo plazo. Para este último caso, se va almacenando el número de veces que un nodo ha sido utilizado como hub, freci. Posteriormente, se aplica una fórmula y se ordenan en función del coste de aplicar dicha fórmula a cada nodo eligiéndose p hubs en orden decreciente.

Procedure BT Sact = So

Svecino = So

Mientras it < iteraciones Para c=1 Hasta vecinosAGenerar Hacer Scand = generarSolucion(Sact) Si (¬esTabu ó (esTabú ^ pruebaAspiración)) Si coste(Scand < Svecino) Svecino = Scand

ActualizarMLP(Sact) Fin Fin Fin Sact = Svecino

ActualizarListaTabu() Si Procede → Reinicialización() Incrementar it FinFin

Para este algoritmo, la estrategia de selección de vecinos se ha basado en evaluar a 40 vecinos generados de la misma forma que en el resto de implementaciones asignando los porcentajes para la estrategia de cambio de hub y conversión de hub al 50% cada una. La estrategia de reinicialización se he ejecutado cada 8*n iteraciones de las 40*n totales que se han ejecutado. Para la reinicialización aleatoria y mejor solución encontrada, se les ha dado una probabilidad de 0.25 mientras que el 0.5 restante se ha otorgado a la estrategia de memoria de largo plazo. También se ha repetido su ejecución con 10 semillas diferentes

7. Algoritmo de comparación Greedy

Este algoritmo Greedy (GR) se basa en la heurística de seleccionar como hubs a los nodos con el flujo de unidades más alto y asignarlos a los nodos cuyo coste sea menor.

Procedure GR S0 = vacio lista = CalcularFlujoNodos() ordenarMayorAMenor(lista) hubs = coger los “p” primeros S0 = MarcarComoHubs(hubs)

Para c=1 Hasta nunNodos Hacer S0[c] = nodoMenorCosteA(hubs) FinDevolver S0

Fin

8. Experimentación

Se ha realizado una batería de pruebas sobre un ordenador portátil HP Compaq Presario V5000, procesador Dual Core a 1.66GHz, 1GB de memoria RAM, sistema operativo Windows XP SP2 bajo una implementación en Java JDK 1.6 y estos son los resultados obtenidos:

Tablas de resultados parciales

CAB-25-4 AP-40-3 AP-50-5

Coste

Búsqueda Aleatoria

Búsqueda Local

Enfriamiento Simulado

Búsqueda Tabú

Comparativa todos los algoritmos e instancias (media geo.)

Anexo I. Comparativa de resultados de manera global

8. Conclusiones

Llegado este punto se hace necesario notar que las conclusiones aquí expuestas se basan en sólo tres instancias de poca complejidad del problema del “p-hub”. No deben tomarse como referencia en ningún caso puesto que no conforma una batería de pruebas de media o extensa magnitud.

Se observa que existen dos partes bien diferenciadas, la primera referente a los algoritmos que no usan las soluciones que van creando y la segunda que sí los usa. Por tanto, este hecho demuestra que aquellos algoritmos que construyen nuevas soluciones a partir de las que descubren obtienen mejores soluciones.

Todos ellos marcan una fuerte robustez puesto que sus medias no difieren en demasía indicando que los valores medios obtenidos en las ejecuciones no dependen de la semilla que se use para la inicialización de los objetos aleatorios empleados. Es en sus desviaciones típicas donde podemos ver que no suponen un más de un 30-35% de la diferencia que existe entre la mejor y peor solución obtenidas. Consecuentemente, la media es un valor que se podría dar como resultado para estos algoritmos.

Respecto al algoritmo GR, la heurística empleado no ha sido una mala elección ya que la diferencia entre sus resultados y los del resto no difiere mucho, incluso en problemas de mayo tamaño como es el caso del AP (50,5). Es por tanto una buena heurística para tomar como solución inicial en el resto de algoritmos.

También cabe notar que en el algoritmo de búsqueda local no se aprecia ninguna diferencia en la utilización de 2*p ó 20*p vecinos para la generación de nuevas soluciones. Este hecho puede deberse a que en problemas de complejidad baja, la aleatoriedad funciona lo suficientemente bien como para que no se haga necesario iterar sobre soluciones a priori malas.

9. Referencias

[1] David Agra Martínez, “Localización de centros de intercambio modal y plataformas logísticas”, Julio 2008[2] M.E. O'Kelly (1987). “A cuadratic integer program for the location of interacting hub facilities”. European Journal of Operational Research., 32(3):393-404.[3] N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller. Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21:1087–1092, 1953[4] Glover, Fred, "Tabu Search : A Tutorial", Interfaces, Vol 20, No. 4, pp. 74-94, July-August 1990.

Anexo I

Comparativa de resultados globales

La siguiente tabla recoge los datos obtenidos en la fase de experimentación de manera global, para que al lector le sea más fácil tener una visión general de los resultados

Para el algoritmo de BL se ha decidido coger de ente las tres pruebas realizadas, para estudiar cómo afecta el número de vecinos generados a la solución final, aquella cuya desviación típica es más próxima a 0, de esta forma, se apuesta por un algoritmo cuya media es representativa y elimina la relación que tiene con respecto a la semilla elegida. En este caso ha sido más robusto el que selecciona a 20*p vecinos.

Respecto al de ES, se ha decidido seguir el mismo criterio de selección que en el anterior, resultando elegido el que se realiza con las probabilidades 0.4 - 0.6. No obstante, cabe resaltar que este algoritmo en su otra variante, presenta uno rango de diferencias entre la mejor y peor solución menor que la variante seleccionada. Esto hecho es indicativo de la propia naturaleza del algoritmo. Si la se decide por priorizar al intercambio de un hub por otro es lógico que el algoritmo explore más una solución que en otro caso, las soluciones obtenidas varían más una a otras haciendo que se peguen saltos grandes por el dominio del problema, encontrándose así soluciones muy buenas y soluciones muy malas.