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

Este documento presenta los resultados obtenidos por cuatro algoritmos basados en trayectorias para la resolución del problema conocido como “p-hub”. Se realizará un estudio con tres casos del problema y las distintas técnicas implementadas. Al final, se expondrán los resultados obtenidos que serán analizados para obtener unas conclusiones sobre éstos métodos de búsqueda.

PALABRAS CLAVES: Optimización, búsqueda heurística, búsqueda basada trayectoria, problema p-hub

1. Introducción

El problema del “p-hub” [1], 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. 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 cuatro métodos de búsqueda basados en trayectorias diferentes: búsqueda multiarranque básica, grasp, grasp extendido e ils. También se usarán otros algoritmos de comparación como son el greedy, greedy más búsqueda local, greedy más búsqueda local extendida.

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:

3. Diseño / Implementación

Representación de la solución

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

Dicha solución integra a las matrices X e Y de modo que un hub es identificado porque en la posición que le corresponde aparece su mismo identificador. Un nodo normal presenta en la posición de su representación al hub que tiene asignado.

Operadores de vecindad

Para el problema del p-hub se presentan dos operadores de vecindad:

1) Cambio de conexión del nodo (L) : se cambia el hub al que esta conectado un nodo

2) Intercambio de hub (R) : se elige a un nodo aleatoriamente y se convierte en hub. Del mismo modo, se elige un hub de entre los que existan en la solución y se convierte en nodo. Al resto de nodos que conectaban con este nodo, se direccional ahora al nuevo hub.

Operadores de mutación

Algunos de los algoritmos presentados necesitan de una operación especial de mutación que les permita explorar el espacio de búsqueda. Esta operación se basa en aplicar el operador de vecindad en sus dos variantes de forma reiterativa durante cierto número de veces, obteniéndose soluciones que pueden ser explotadas por una búsqueda local.

Dicha operación ha sido estudiada a fondo en las diferentes implementaciones y para los todos los casos de estudio. En el anexo I pueden verse los resultados obtenidos.

Función objetivo

Se hace necesario resaltar en este punto que la función con la que han sido evaluados los casos de estudio que se van a estudiar no ha sido localizada, por lo que se ha tomado una función de evaluación que es la siguiente:

Cabría esperar que la misma función en la que se sustenta el p-hub fuera la función de evaluación con la que se han logrado los resultados óptimos para los citados casos de estudio, pero no ha sido así.

3.1. Búsqueda Multiarranque Básica

El algoritmo de Búsqueda Multiarranque Básica (BMB en adelante) empleado consiste en generar un conjunto de soluciones iniciales aleatorias y optimizar cada una de ellas con una búsqueda local [3]. Al final, el algoritmo da como resultado la mejor solución encontrada durante todo el proceso.

Este proceso se realizó con 50 soluciones aleatorias y con búsqueda local de 1600*nodos iteraciones, 100 iteraciones de no mejoría para acelerar la búsqueda local y 5, 10, 15 y 20 vecinos de exploración.

3.2. GRASP

El algoritmo de Búsqueda Aleatoria Adaptativa Greedy (GRASP) se basa en construir soluciones greedy de manera probabilística y aplicarles una búsqueda local como en la BMB para optimizarlas. La obtención de las soluciones iniciales greedy, selecciona a los nodos con mayor potencial de flujo como hubs y asigna el resto como nodos a los hubs con menor costo.

El carácter probabilístico se aplica a la elección de los hubs. Éstos se almacenan en una lista de mayor a menor potencial de flujo. Se eligen los l mejores hubs (siendo l >= p). A continuación, se seleccionarán los p hubs que conforman parte de la solución del problema.

Posteriormente a este proceso, el resto de nodos no conectores se asocia, mediante un procedimiento similar al expuesto, a los hubs. Se añaden a una lista ordenados por menor coste y se eligen r nodos (siendo r <= p). Por último, se eligen al azar un nodo de dicha sublista para realizar la asignación. Este procedimiento se aplica a todos los nodos no conectores hasta completar una solución para el problema.

Del mismo modo que para BMB, se han creado 50 soluciones iniciales sobre los que la búsqueda local ha realizado 1600*nodos iteraciones, 200 iteraciones de no mejoría y 5, 10, 15 y 20 vecinos de exploración.

3.3. GRASP Extendido

Este algoritmo es exactamente igual que el presentado en el apartado anterior, excepto por la incorporación del operador de mutación. Dicho operador se aplica tras la obtención de la solución greedy probabilística. De esta manera, la búsqueda local que se realiza posteriormente recibe una solución mutada para que sea explorada.

La mejoría que pretende aportar este algoritmo es la de crear soluciones rápidamente de manera casi determinista pero otorgándoles cierto punto de aleatoriedad que la propia generación no puede y que resulta muy interesante de poder explorar.

Para la obtención de los resultados de este algoritmo, se ha partido de 10 soluciones iniciales a las que se les ha aplicado 5 veces el procedimiento de mutación y búsqueda local. Para la mutación se han utilizado todas las combinaciones posibles entre intercambio de hub como cambio de conexión. En el axexo I se muestran todos los valores utilizados.

Para la búsqueda local se han utilizado los mismos parámetros que en el GRASP.

3.4. ILS

El algoritmo de Búsqueda Iterativa Local (ILS) pretende dar pequeños saltos en el espacio de búsqueda de manera muy similar a como actúa la mutación en los algoritmos genéticos [4]. Para el caso que nos requiere, se parte de una solución aleatoria a la que se le aplica una búsqueda local. Una vez obtenida la solución optimiza, aplicamos una mutación sobre la mejor de entre la inicial o la optimizada. A continuación, se aplica de nuevo una búsqueda local y el proceso se repite siguiendo el criterio del mejor como condición de aceptación de soluciones.

El algoritmo ha aplicado 50 búsquedas locales, una a la solución aleatoria y 49 a las soluciones mutadas, con 1600*nodos iteraciones, 200 iteraciones de no mejoría y 5, 10, 15 y 20 vecinos en la exploración. Del mismo modo que el GRASP Extendido, se han aplicado todas las posibles combinaciones para el operador de mutación.

3.5. Greedy

Tanto este como los dos siguiente algoritmos, se utilizan en este estudio para compararlos con los procedimiento ya descritos en los puntos anteriores. Son algoritmos deterministas a las que se les ha aplicado técnicas como la búsqueda local y la mutación. El objetivo es comprobar si merece la pena la utilización de los métodos anteriores para la obtención de resultados.

El algoritmo Greedy (GR) implementado 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.

3.6. Greedy + BL

El algoritmo Greedy más Búsqueda Local consiste en ejecutar el algoritmo expuesto en el punto anterior y una búsqueda local para encontrar una solución optimizada.

Obviamente, si lo que se busca es una medida de comparación, los parámetros utilizados para la búsqueda local deben de ser los mismos que en los casos anteriores: 1600*nodos iteraciones, 200 iteraciones de no mejoría con 5, 10 15 y 20 vecinos en la exploración.

3.7. Greedy + BL Extendida

El algoritmo Greedy más Búsqueda Local Extendida no es más que el algoritmo GRASP Extendido expuesto anteriormente pero partiendo en este caso de una solución greedy determinista, proporcionada por el algoritmo GR.

Como se puede apreciar, estos dos últimos algoritmos son exactamente iguales al algoritmo GRASP y GRASP Extendido, salvo por la generación de la solución inicial que se utiliza en cada procedimiento.

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

4. Experimentación

Se ha realizado una batería de pruebas sobre los casos de estudio CAB-25-4, AP-40-3 y AP-50-5 con un PC de sobremesa con procesador Intel Pentium Dual Core a 2.33GHz, 2GB de memoria RAM, sistema operativo Windows XP SP2 con Java JDK 1.6. Los parámetros para la búsqueda local y la mutación que han aportado las mejores soluciones son por caso de estudio y algoritmo los siguientes:

CAB-25-4:- BMB: 10 Vecinos- Greedy + BL: 10Vecinos- Greedy + Bl Ext: 10Vecinos, L = 4, R = 4- Grasp: 10Vecinos, L = 8, R = 4- Grasp ext: 10Vecinos, L = 10, R = 9- Ils: 5 Vecinos, L = 8, R = 4

AP-40-3:- BMB: 5 Vecinos- Greedy + BL: 5 Vecinos- Greedy + Bl Ext: 5Vecinos, L = 4, R = 4- Grasp: 20Vecinos, L = 10, R = 4- Grasp ext: 20Vecinos, L = 7, R = 8- Ils: 20 Vecinos, L = 6, R = 4

AP-50-5:- BMB: 15 Vecinos- Greedy + BL: 20 Vecinos- Greedy + Bl Ext: 5Vecinos, L = 5, R = 5- Grasp: 10 Vecinos, L = 5, R = 5- Grasp ext: 5 Vecinos, L = 6, R = 5- Ils: 10 Vecinos, L = 7, R = 6

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

Método Coste Coste Coste

Óptimo 939 158830 132366

Greedy 7329 194494 136348

Búsqueda Local 8223 195185 199201

BMB 4870 144075 127637

Greedy + BL 5983 174463 133369

Greedy + BL Ext 4960 154868 128446

Grasp 6458 177018 179479

Grasp Ext 4571 147376 147089

Ils 7636 181601 178831

Tabla 1. Resultados Globales

0

30000

60000

90000

120000

150000

180000

210000

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

Co

ste

Óptimo

Greedy

Búsqueda Local

BMB

Greedy + BL

Greedy + BL Ext

Grasp

Grasp Ext

Ils

Gráfica 1. Resultados Globales

0

1000

2000

3000

4000

5000

6000

7000

8000

9000

CAB-25-4Coste

Greedy

Búsqueda Local

BMB

Greedy + BL

Greedy + BL Ext

Grasp

Grasp Ext

ILS

Gráfica 2. Resultados Cab-25-4 en detalle

0

50000

100000

150000

200000

250000

AP-40-4

Coste

Greedy

Búsqueda Local

BMB

Greedy + BL

Greedy + BL Ext

Grasp

Grasp Ext

ILS

Gráfica 3. Resultados Ap-40-3 en detalle

0

50000

100000

150000

200000

250000

AP-50-5

Coste

Greedy

Búsqueda Local

BMB

Greedy + BL

Greedy + BL Ext

Grasp

Grasp Ext

ILS

Gráfica 4. Resultados Ap-50-5 en detalle

5. Análisis de resultados

Lo primero que se observa en la gráfica 1 es que el óptimo ha sido alcanzado en varias ocasiones. Esto no es debido a que se haya encontrado una solución mejor, sino que como ya se ha comentado al principio del documento, la función de evaluación con la que se ha obtenido ese

óptimo no es la misma que se ha usado en este estudio.

También se aprecia que algoritmo BMB es el que presenta los mejores resultados para todos los casos de estudio. Cabe destacar que sólo se ha utilizado una semilla para la obtención de resultado.

Como puede observarse en la gráfica 1 , los algoritmos GRASP no están teniendo resultados de calidad. No mejoran a sus versiones simplificadas Greedy. La causa podría deberse a que la generación de la solución greedy probabilística no es adecuada. Se tendría que estudiar con mayor detenimiento este matiz.

En las graficas 5, 6 y 7, se muestra que la búsqueda local tiende a oscilar cuando se modifican el número de vecinos del entorno sobre los que se realiza la búsqueda, con lo que para obtener buenos resultados es muy importante determinar este cuál va a ser su valor. También es importante elegir un buen factor de mutación, ya que de él depende el número de vecinos que habría que utilizar en la búsqueda.

Cabe destacar que, a medida que crece el tamaño de nodos del problema, la mutación debe ser pequeña, ya que si no es así, la proporción exploración/explotación queda a favor de la exploración y nunca termina de explotar las soluciones que, a priori, presentan buena calidad.

Por último, resaltar que en los algoritmos Greedy + Bl Extendida y Grasp aplicar la variante de mutación de intercambio de hub no tiene influencia sobre el resultado de las soluciones que

se obtienen, como se aprecia en los gráficos 5, 6 y 7.

6. Conclusiones

El algoritmo BMB ha sido el que mejores resultados ha proporcionado en los casos estudiados.

Las versiones greedy implementadas han presentado resultados de mejor calidad que sus técnicas más sofisticadas Grasp y sus diferentes evoluciones.

Se muestra que la elección del número de vecinos empleados en las búsquedas locales es de vital importancia para la consecución de buenos resultados.

7. 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] E. M. Díaz (2011). Práctica 1 Algoritmos Heurísticos y de Búsquedas [4] E. M. Díaz (2011) Practica 2 Algoritmos Evolutivos y Bioinspirados

Anexo I

Comparativa de resultados globales

En este anexo se recogen todas las gráficas que se han generado durante el proceso de pruebas en las que se han estudiado en profundidad cómo afectan el número de vecinos y las dos opciones que proporciona el operador de mutación en el resultado final del algoritmo.

CAB-25-4

Gráfica 5. Resultado estudio para problema CAB-25-4

Gráfica 6. Resultado estudio para problema AP-40-3

Gráfica 7. Resultado estudio para problema AP-50-5

Los datos que aparecen en el eje horizontal corresponden el número de vecinos para el caso de los algoritmos BMB y Greedy + BL y al factor de mutación en el resto. Este factor corresponde al número de asignaciones de intercambio de conectores como parte izquierda y al número de cambios de hubs en la parte derecha. Asi el valor 4-5 representa a 4 cambios de asignación y 5 cambios de hubs.