grasp con pr para el srflp en el maeb 2016
TRANSCRIPT
GRASP con Reencadenamiento de Trayectorias para el
Single Row Facility Layout Problem
Micael GallegoManuel Rubio-Sánchez
Francisco GortázarAbraham Duarte
MAEB 201614-16 Sep 2016Salamanca (Spain)
2CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
GRASP con PR para el SRFLP
Single Row Location Facility Problem GRASP Reencadenamiento de trayectorias GRASP con PR Experimentos Conclusiones
3CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
Single Row Location Facility Problem
Disponer en una línea un conjunto de instalaciones de diferente anchura
Objetivo: Minimizar la suma ponderada de las distancias entre los centros de cada par de instalaciones
Ejemplos: Habitaciones en un pasillo, libros en estantes, máquinas en fábricas...
6CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
Single Row Location Facility Problem
• Estado del arte• Algoritmos exactos
• Óptimo conocido hasta 42 instalaciones
• Algoritmos aproximados• Kothari y Ghosh (2014)
• Memético (GENALGO)
• Búsqueda Dispersa (SS-2P)
7CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
GRASP con PR para el SRFLP
Single Row Location Facility Problem GRASP Reencadenamiento de trayectorias GRASP con PR Experimentos Conclusiones
8CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
GRASP
• Constructivo• Empieza con una solución vacía• Por cada instalación disponible, se calcula el coste de insertar esa instalación en todas las posibles posiciones (CL)
• Se escoge un % de las instalaciones y posiciones más favorables (minimizan el coste) (RCL)
• Se selecciona aleatoriamente de la RCL
9CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
GRASP
• Búsqueda Local• Movimientos de inserción (insert): Se elimina una instalación de su posición y se coloca en otra posición• First Improvement: Se evalúan los movimientos de
inserción y se aplica el primero que mejore la solución• Best Improvement: Se evalúan todos los movimientos de
inserción y se aplica el mejor de todos ellos• Híbrida (LS-HYBRID)*: Se selecciona una instalación al
azar (similar a First), se evalúan todos los movimientos de esa instalación y se aplica el mejor (similar a Best)
10CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
GRASP
• Algoritmo GRASP
• 1) Genera una solución con el constructivo• 2) Se selecciona una instalación al azar• 3) Se evalúan todos los movimientos de esa instalación• 4) Si existe movimiento de mejora, se aplica y se vuelve al paso 2
• 5) Si no existe movimiento de mejora y quedan instalaciones por evaluar, se vuelve al paso 2
• 6) Si no se alcanza el tiempo máximo, se vuelve al paso 1
11CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
GRASP
• Optimizaciones• Calculamos de forma eficiente (en tiempo lineal) el cambio del coste cuando una instalación se mueve únicamente una posición
• Se evalúan todas las posiciones moviendo de una en una
14CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
GRASP con PR para el SRFLP
Single Row Location Facility Problem GRASP Reencadenamiento de trayectorias GRASP con PR Experimentos Conclusiones
15CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
Reencadenamiento de Trayectorias
• Método que genera nuevas soluciones partiendo de dos soluciones
• Una solución (solución inicial) se modifica paso a paso para convertirse en la otra solución (solución guía)
• El proceso crea una trayectoria que conecta ambas soluciones y en esa trayectoria se encuentran nuevas soluciones de calidad
16CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
Reencadenamiento de Trayectorias
SoluciónInicial
SoluciónGuía
SolucionesIntermedias
…
17CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
Reencadenamiento de Trayectorias
• Se ha implementado un algoritmo basado en la distancia de Ulam entre dos permutaciones
• Esta distancia calcula el mínimo número de cambios que hay que hacer para convertir una permutación en otra
• Se basa en calcular la subsecuencia común más larga entre las dos permutaciones
18CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
Reencadenamiento de Trayectorias
SoluciónInicial
SoluciónGuía
Con 3 inserciones se puede convertir la solución inicial en la solución guía
{ 1,2,3,4,5 }
{ 5,1,4,3,2 }
19CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
{ 1,2,3,4,5 } { 5,1,4,3,2 }
{ 1,4,2,3,5 }
{ 1,3,2,4,5 }
{ 5,1,2,3,4 }
{ 1,3,4,5,2 }
{ 1,2,4,3,5 }
SoluciónInicial
SoluciónGuía
SoluciónAleatoria
{ 5,1,2,4,3 }
{ 1,4,3,5,2 }
SoluciónAletaria
•Selecciona la mejor solución en cada paso
SolucionesIntermedias
Reencadenamiento de Trayectorias
20CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
GRASP con PR para el SRFLP
Single Row Location Facility Problem GRASP Reencadenamiento de trayectorias GRASP con PR Experimentos Conclusiones
21CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
GRASP con PR
Genera Soluciones con
GRASP (Elite Set)
Genera una nueva solución
con GRASP
Aplica PR desde la nueva solución a todas las
del Elite Set
1 2 3
4 Actualiza el Elite Set si hay una nueva solución con suficiente calidad y diversidad
Repite desde el paso 2 con este nuevo Elite Set
23CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
GRASP con PR para el SRFLP
Single Row Location Facility Problem GRASP Reencadenamiento de trayectorias GRASP con PR Experimentos Conclusiones
24CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
Experimentos
● Métodos• GENALGO: Memético del estado del arte• SS-2P: Búsqueda dispersa del estado del arte• GRASP_PR: Propuesta
● Lenguaje de Programación: Todos los métodos en C compilados con gcc
● Entorno ejecución: Core TM i7-4712HQ 3.3 GHz y 16 GB de RAM
25CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
Experimentos
● Instancias
● Estado del arte● Anjos: 4x5 con n=60, 70, 75, 80● Sko: 4x5 con n=64, 72, 81, 100● Amaral: 3 con n=110
● Nuevas instancias grandes● Anjos-large: 5x8 n=150, 200, 300, 350, 400, 450, 500● Sko-large: 5x8 n=150, 200, 300, 350, 400, 450, 500
26CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
Experimentos
● Experimento 1: Comparativa con instancias del estado del arte (pequeñas)● Resultado
● GENALGO: Mejores soluciones en todas las instancias en 2723s
● SS-2P: Mejores soluciones excepto en 3 instancias en 47s● GRASP_PR: Mejores soluciones en todas las instancias en 38s
(Ejecutado con tiempo n/2 segundos)
● Conclusión● Las instancias son demasiado “fáciles” para discriminar la
calidad del los métodos
27CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
Experimentos
● Experimento 2: Comparativa con 40 instancias grandes.
● Tiempo: 1 hora por instancia
● Resultado● GENALGO: Mejor solución en 1 de 40 instancias● SS-2P: Peores soluciones en todas las instancias● GRASP_PR: Mejores soluciones en 39 de 40
instancias
30CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
Experimentos
● Experimento 2 ● Test Friedman: Ranking de cada método en
cada instancia
● GENALGO: 2.5● SS-2P: 2.46● GRASP_PR: 1.04 (El más cercano a 1)
● p-valor: 7 x 10-13
31CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
Experimentos
● Experimento 2 ● Test del signo: Comparación de cada par de
métodos
● GRASP_PR vs GENALGO: 39 con p-valor 3.7x10-11
● GRASP_PR vs SS-2P: 39 con p-valor 1.8x10-12
32CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
GRASP con PR para el SRFLP
Single Row Location Facility Problem GRASP Reencadenamiento de trayectorias GRASP con PR Experimentos Conclusiones
33CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
Conclusiones
● Método GRASP con PR para el SRFLP● Constructivo GRASP● Búsqueda Local híbrida eficiente● Reencadenamiento de trayectorias basado en la distancia
Ulam
● Calidad● Misma calidad en menor tiempo para instancias pequeñas● Mejor calidad en el mismo tiempo para instancias grandes
34CAEPIA / MAEB 2016
14-16 Sep 2016 Salamanca (Spain)
Conclusiones
● Versión más extensa de este trabajo• GRASP with path relinking for the
single row facility layout problem• Manuel Rubio-Sánchez, Micael
Gallego, Francisco Gortázar, Abraham Duarte
• Knowledge-Based Systems. Volume 106, 15 August 2016, Pages 1–13
• http://dx.doi.org/10.1016/j.knosys.2016.05.030