optimización mediante búsqueda tabú para problemas no...

Luis Ignacio Frisón Alegre

Director: Ricardo J. Rodríguez Fernández

Codirector: Javier Campos Laclaustra

Septiembre de 2017

Curso 2016/2017

Proyecto Fin de Carrera – Ingeniería en Informática

Escuela de Ingeniería y Arquitectura

Universidad de Zaragoza

Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri

Contenidos

1) Heurísticas y metaheurísticas

2) Búsqueda Tabú

3) Aplicación al análisis de prestaciones de Redes de Petri

4) Decisiones de implementación

5) Integración en PeabraiN

6) Evaluación del algoritmo

7) Conclusiones

8) Objetivos

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 1/32

Contenidos

1) Heurísticas y metaheurísticas

2) Búsqueda Tabú

3) Aplicación al análisis de prestaciones de Redes de Petri

4) Decisiones de implementación

5) Integración en PeabraiN

6) Evaluación del algoritmo

7) Conclusiones

8) Objetivos

Heurísitcas y metaheurísticas

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 2/32

Heurística vs metaheurística

Problemas difíciles: conocer solución exacta es "imposible" (mucho tiempo).

NP ?= P.

Heurística:

• Permite obtener soluciones (sub)óptimas de problemas difíciles.

• Tiempo de ejecución asequible.

• Ejemplos: algoritmos de resolución aproximada de problemas en NP.

Metaheurística:

• Técnica de resolución aplicable a familia de problemas.

• Esquema general, basado en heurísticas.

• Ejemplos: algoritmos voraces, algoritmos genéticos, búsqueda tabú, etc.

Heurísitcas y metaheurísticas

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 3/32

Contenidos

1) Heurísticas y metaheurísticas

2) Búsqueda Tabú

3) Aplicación al análisis de prestaciones de Redes de Petri

4) Decisiones de implementación

5) Integración en PeabraiN

6) Evaluación del algoritmo

7) Conclusiones

8) Objetivos

Búsqueda Tabú

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 4/32

Descripción de la Búsqueda Tabú

• Procedimiento iterativo de búsqueda local (en el vecindario) eficiente.

• Permite encontrar un óptimo global.

• Uso de estructuras de memoria:

-- Memoria reciente: concepto de tabú.

-- Memoria frecuente:

* Diversificación: apoya la búsqueda en regiones no visitadas.

* Intensificación: apoya los movimientos que históricamente han

sido buenos.

Búsqueda Tabú

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 5/32

Descripción de la Búsqueda Tabú

• Selección de la siguiente solución:

-- Se generan soluciones candidatas desde la actual, y se escoge la mejor.

• Lista tabú:

-- Evita ciclos durante la búsqueda.

-- Las últimas soluciones escogidas se marcan como "tabú", no pudiendo

ser escogidas durante X iteraciones.

• Criterio de aspiración

-- Se permite escoger una solución de la lista tabú si es mejor que la actual.

-- Diferentes criterios: por defecto, por objetivo, por dirección de

búsqueda.

Búsqueda Tabú

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 6/32

Descripción de la Búsqueda Tabú

En cada iteración:

1) Generar vecindario.

2) Ordenar vecindario.

3) Escoger primera solución no tabú o que cumpla con el criterio de aspiración.

4) Marcar dicha solución como tabú.

5) Actualizar matriz tabú.

Búsqueda Tabú

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 7/32

Aplicación al problema de las 8-reinas

PARÁMETROS:

Tenencia tabú = 8, número de vecinos = 4, número máximo de iteraciones = 3.

INICIALIZACIÓN:

Paso 1: solución inicial = [1, 3, 5, 7, 2, 4, 6, 8]

Paso 2: matriz tabú = [0, 0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0, 0]

Búsqueda Tabú

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 8/32

ITERACIÓN 1:

Paso 3: solución transitoria = [1, 3, 5, 7, 2, 4, 6, 8]

Paso 4: vecindario (reinas, función objetivo) = ([1, 3, 5, 7, 2, 8, 6, 4], 1)

([7, 3, 5, 1, 2, 4, 6, 8], 3)

([1, 3, 5, 4, 2, 7, 6, 8], 6)

([2, 3, 5, 7, 1, 4, 6, 8], 1)

Vecindario ordenado (reinas, función objetivo) = ([1, 3, 5, 7, 2, 8, 6, 4], 1)

([2, 3, 5, 7, 1, 4, 6, 8], 1)

([7, 3, 5, 1, 2, 4, 6, 8], 3)

([1, 3, 5, 4, 2, 7, 6, 8], 6)

Aplicación al problema de las 8-reinas

Búsqueda Tabú

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 9/32

Aplicación al problema de las 8-reinas

ITERACIÓN 1:

Paso 5: matriz tabú = Paso 6: matriz tabú =

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 8] [0, 0, 0, 0, 0, 0, 0, 7]

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

Búsqueda Tabú

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 10/32

ITERACIÓN 2:

Paso 3: solución transitoria = [1, 3, 5, 7, 2, 8, 6, 4]

Paso 4: vecindario (reinas, función objetivo) = ([1, 3, 5, 2, 7, 8, 6, 4], 4)

([1, 3, 5, 7, 8, 2, 6, 4], 4)

([1, 3, 5, 7, 2, 8, 4, 6], 4)

([1, 3, 4, 7, 2, 8, 6, 5], 4)

Vecindario ordenado (reinas, función objetivo) = ([1, 3, 5, 2, 7, 8, 6, 4], 4)

([1, 3, 5, 7, 8, 2, 6, 4], 4)

([1, 3, 5, 4, 2, 8, 4, 6], 4)

([1, 3, 4, 7, 2, 8, 6, 5], 4)

Aplicación al problema de las 8-reinas

Búsqueda Tabú

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 11/32

Aplicación al problema de las 8-reinas

ITERACIÓN 2:

Paso 5: matriz tabú = Paso 6: matriz tabú =

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 8, 0, 0, 0] [0, 0, 0, 0, 7, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 7] [0, 0, 0, 0, 0, 0, 0, 6]

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

Búsqueda Tabú

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 12/32

ITERACIÓN 3:

Paso 3: solución transitoria = [1, 3, 5, 2, 7, 8, 6, 4]

Paso 4: vecindario (reinas, función objetivo) = ([1, 3, 6, 2, 7, 8, 5, 4], 5)

([1, 8, 5, 2, 7, 3, 6, 4], 2)

([1, 3, 5, 7, 2, 8, 6, 4], 1)

([1, 3, 2, 5, 7, 8, 6, 4], 5)

Vecindario ordenado (reinas, función objetivo) = ([1, 3, 5, 7, 2, 8, 6, 4], 1)

([1, 8, 5, 2, 7, 3, 6, 4], 2)

([1, 3, 6, 2, 7, 8, 5, 4], 5)

([1, 3, 2, 5, 7, 8, 6, 4], 5)

Aplicación al problema de las 8-reinas

Búsqueda Tabú

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 13/32

Aplicación al problema de las 8-reinas

ITERACIÓN 3:

Paso 5: matriz tabú = Paso 6: matriz tabú =

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 8, 0, 0, 0] [0, 0, 0, 0, 7, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 6] [0, 0, 0, 0, 0, 0, 0, 5]

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0]

Búsqueda Tabú

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 14/32

Aplicación al problema de las 8-reinas

SOLUCIÓN FINAL:

Paso 7: se alcanza el número máximo de iteraciones, con lo que el algoritmo

acaba.

Paso 8: nos quedamos con la menor función objetivo hallada hasta el

momento (1), correspondiente al vector de reinas [1, 3, 5, 7, 2, 8, 6, 4].

Búsqueda Tabú

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 15/32

Contenidos

1) Heurísticas y metaheurísticas

2) Búsqueda Tabú

3) Aplicación al análisis de prestaciones de Redes de Petri

4) Decisiones de implementación

5) Integración en PeabraiN

6) Evaluación del algoritmo

7) Conclusiones

8) Objetivos

Aplicación al análisis de prestaciones de Redes de Petri

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 16/32

El problema min-max de Bernardi y Campos

Γ(ti) >= Γlb(ti) = min max y * Pre * Dti

vti є domv y є domy

Sujeto a domy : {yT * C = 0, y * m0 = 1, y>=0}

domv : {R * vti = 0, C * vti = 0, vti >=0, vti(ti) = 1}

• ti es la transición sobre la que queremos hallar el tiempo de ciclo.

• y es un p-semiflujo del sistema.

• vti es el vector de ratios de visita normalizado para la transición ti.

• Dti = δ ʘ vti (producto de vectores por componentes) es el vector de demandas de servicio de transiciones medio.

• Pre es la matriz de Pre-incidencia del sistema.

• C es la matriz de incidencia del sistema.

• R es la matriz de enrutado del sistema.

• m0 es el marcado inicial del sistema.

Aplicación al análisis de prestaciones de Redes de Petri

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 17/32

Contenidos

1) Heurísticas y metaheurísticas

2) Búsqueda Tabú

3) Aplicación al análisis de prestaciones de Redes de Petri

4) Decisiones de implementación

5) Integración en PeabraiN

6) Evaluación del algoritmo

7) Conclusiones

8) Objetivos

Decisiones de implementación

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 18/32

Diagrama de ClasesDecisiones de implementación

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 19/32

Decisiones de implementaciónClase principal => WellFormedTabuSearch.

Método principal de la clase WellFormedTabuSearch => solve().

Pasos de solve():

1) Inicializar variables.

2) Copiar solución actual en transitoria.

3) Generar vecindario.

4) Ordenar vecindario (por función objetivo, de mayor a menor).

5) Escoger mejor solución.

6) Actualizar matriz tabú.

7) Incrementar contador de iteraciones. Ir a 2) hasta que se cumpla la condición de finalización del bucle.

8) Escoger como resultado la cota mínima alcanzada.

Decisiones de implementación

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 20/32

Contenidos

1) Heurísticas y metaheurísticas

2) Búsqueda Tabú

3) Aplicación al análisis de prestaciones de Redes de Petri

4) Decisiones de implementación

5) Integración en PeabraiN

6) Evaluación del algoritmo

7) Conclusiones

8) Objetivos

Decisiones de implementación

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 21/32

Integración en PeabraiN

1) Crear la clase “WellFormedTabuSearch” y demás clases necesarias parala resolución del problema (“BCMinMaxSolver” y “Neighbour”).

2) Crear la clase “TabuSearchStrategy”, que se comunique apropiadamentecon la clase “WellFormedTabuSearch”.

3) Crear la clase “TabuSearchGUI”.

4) Crear la clase “TabuSearchModule”, que a su vez cree objetos de lasclases “TabuSearchStrategy” y “TabuSearchGUI” (uno por cada clase),para así permitir la comunicación entre capas dentro de estaarquitectura MVC.

Integración en PeabraiN

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 22/32

Contenidos

1) Heurísticas y metaheurísticas

2) Búsqueda Tabú

3) Aplicación al análisis de prestaciones de Redes de Petri

4) Decisiones de implementación

5) Integración en PeabraiN

6) Evaluación del algoritmo

7) Conclusiones

8) Objetivos

Evaluación del algoritmo

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 23/32

Red de pruebaEvaluación del Algoritmo

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 24/32

Resultados (50 a 1000 iteraciones)Evaluación del algoritmo

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 25/32

Tenencia Tabú

Máx. Iteraciones

0 1 2

50 1,388515 1,387779 0,929408

100 1,248233 1,248122 0,783353

250 1,118675 1,118800 0,677581

500 1,045956 1,045793 0,666841

1000 0,986608 0,986761 0,666662

Valor obtenido mediante GreatSPN: 1,20.

Valores aproximados con el algoritmo implementado (muchas iteraciones, transición dereferencia = T0, número de vecinos = 25, número de repeticiones del algoritmo = 100000):

Resultados (10 a 50 iteraciones)

Valor obtenido mediante GreatSPN: 1,20.

Valores aproximados con el algoritmo implementado (pocas iteraciones, transición dereferencia = T0, número de vecinos = 25, número de repeticiones del algoritmo = 100000):

Evaluación del algoritmo

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 26/32

Tenencia Tabú

Máx. Iteraciones

2 3

10 1,521364 0,978760

20 1,189235 0,679937

30 1,059817 0,655963

40 0,983820 0,648803

50 0,928446 0,641718

Contenidos

1) Heurísticas y metaheurísticas

2) Búsqueda Tabú

3) Aplicación al análisis de prestaciones de Redes de Petri

4) Decisiones de implementación

5) Integración en PeabraiN

6) Evaluación del algoritmo

7) Conclusiones

8) Objetivos

Conclusiones

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 27/32

Objetivos alcanzados

1) Se propuesto una técnica de Búsqueda Tabú.

2) Se ha aplicado dicha técnica al problema en cuestión.

3) Se ha integrado dicha técnica en la herramienta PeabraiN.

Conclusiones

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 28/32

Restricciones del algoritmo

1) Aproxima el valor del min-max, pero no llega a resolverlo.

--> Problema de complejidad teórica importante.

2) Afectado por crecimiento exponencial de p-(t-)semiflujos.

--> Limita aplicabilidad a ciertas clases de redes.

3) Se han implementado exclusivamente los conceptos de memoria reciente y aspiración por objetivo.

--> En otros problemas, se ha observado que el uso de la memoria frecuente y otros criterios de aspiración proporcionaban pocas ventajas.

Conclusiones

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 29/32

Contenidos

1) Heurísticas y metaheurísticas

2) Búsqueda Tabú

3) Aplicación al análisis de prestaciones de Redes de Petri

4) Decisiones de implementación

5) Integración en PeabraiN

6) Evaluación del algoritmo

7) Conclusiones

8) Objetivos

Objetivos

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 30/32

Trabajo futuro

Como trabajo futuro, plantearía los siguientes objetivos:

1) Resolver primeramente el problema de crecimiento exponencial.

2) Utilizar las herramientas de la Búsqueda Tabú de memoria frecuente ydistintos criterios de aspiración.

3) Definir estrictamente la función objetivo del problema min-max:

* Simplificada para facilitar la implementación.

* Técnica en dos pasos:

-- Cálculo inicial del p-semiflujo más lento.

-- Búsqueda de vectores "v" que cumplan el dominio sobre ese

p-semiflujo.

Objetivos

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 31/32

Horas de trabajoAnexo

Luis Ignacio Frisón Alegre Optimización mediante Búsqueda Tabú para problemas no lineales en Redes de Petri EINA 32/32

2016 2017

Sep Oct Nov Dic Ene Feb Mar Abr May Jun Jul Ago

Estudio

Análisis/Diseño

Implementación

Integración

Experimentación

Documentación

Horas totales = 472,5