PDF de programación - Metaheurísticas paralelas: optimización y aplicaciones

Metaheurísticas paralelas: optimización y aplicaciones

Domingo Giménez

dis.um.es/~domingo

Grupo de Computación Científica y Programación Paralela

luna.inf.um.es/grupo investigacion

Departamento de Informática y Sistemas, Universidad de Murcia

Universidad Politécnica de Valencia, noviembre 2016

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

1 / 85

Contenidos

1 Metaheurísticas e Hiperheurísticas

Metaheurísticas
Metaheurísticas parametrizadas
Hiperheurísticas

2 Metaheurísticas paralelas

Memoria Compartida
Autooptimización en Memoria Compartida
Paso de Mensajes
Autooptimización de metaheurísticas con paso de mensajes
Metaheurísticas en manycore

3 Ejemplos de aplicaciones

Consumo de electricidad
Docking de moléculas
Análisis Envolvente de Datos (DEA)
Determinación de componentes por análisis de sedimentos

4 Créditos

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

2 / 85

Metaheurísticas e Hiperheurísticas

Contenidos

1 Metaheurísticas e Hiperheurísticas

Metaheurísticas
Metaheurísticas parametrizadas
Hiperheurísticas

2 Metaheurísticas paralelas

3 Ejemplos de aplicaciones

4 Créditos

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

3 / 85

Metaheurísticas e Hiperheurísticas Metaheurísticas

Metaheurísticas

Descripción

Utilizadas en problemas de optimización donde los métodos exactos
requieren de gran coste computacional (NP-hard).
Estrategias generales para la búsqueda de soluciones cercanas a
la óptima dentro del espacio de soluciones.

Tipos:

Distribuidas o basadas en población, capacidad de exploración.
Algoritmos Genéticos, Búsqueda Dispersa, Colonias de Hormigas,
Optimización de Partículas...
Locales o basadas en trayectoria, capacidad de explotación. Temple
Simulado, Ascensión de Colinas, Búsqueda Tabú...
Híbridas, combinan características de varias

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

4 / 85

Metaheurísticas e Hiperheurísticas Metaheurísticas

Algoritmos Genéticos

Esquema de AG

InicializarPoblación(S)
mientras (no CondiciónDeFin(S))
SS = SeleccionarElementos(S)
SS1 = CruzarElementos(SS)
SS2 = Mutar(SS1)
S = IncluirMejores(SS2)

Descripción

s Generación de población aleatoria.
s Se seleccionan los mejores o con método de ruleta.
s Se cruzan por pares para generar dos descendientes.
s Algunos de ellos se mutan para diversificar.
s Se seleccionan los mejores para la población.

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

5 / 85

Metaheurísticas e Hiperheurísticas Metaheurísticas

Ascensión de colinas

Esquema de AC

GenerarElemento(E )
mientras (no CondiciónDeFin(E ))

SS = GenerarVecinos(E )
E 1 = MejorVecino(SS)
si (mejor(valor(E 1),valor(E ))

Descripción

E =E 1

s Generación aleatoria de posible solución.
s Se seleccionan una vecindad
s y el mejor vecino dentro de ella.
s Si ese vecino mejora a la solución actual
s se sigue la búsqueda por él.

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

6 / 85

Metaheurísticas e Hiperheurísticas Metaheurísticas

Esquema general

Esquema general de metaheurísticas

Inicializar(S)
mientras (no CondiciónDeFin(S)

SS = Seleccionar(S)
SS1 = Combinar(SS)
SS2 = Mejorar(SS1)
S = Incluir(SS2)

Ideass Se inicializa conjunto, población o elemento.
s Se seleccionan los mejores, todos, aleatorios, uno...
s Se combinan por pares, varios, se generan vecinos...
s Algunos elementos se mejoran analizando sus vecinos, mutando...
s Se incluyen los mejores, mejores y peores, el más prometedor...

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

7 / 85

Metaheurísticas e Hiperheurísticas Metaheurísticas

Aplicaciones en el grupo de CCPP

Numérico Optimización

Simulación climática
Hidrodinámica
Electromagnetismo
Representación del terreno
Tratamiento de señal acústica
Tratamiento de imágenes
docking de moléculas
Econometría
Análisis envolvente de datos
Constantes cinéticas
Consumo electricidad
Análisis de sedimentos

Con metaheurísticas empezamos en 2008, Tesis de Máster de José Ceferino
Ortega (luna.inf.um.es/grupo investigacion).
José-Ceferino Ortega, Domingo Giménez, Alejandro Álvarez-Melcón, Fernando
D. Quesada: Hybrid metaheuristics for the design of coupled resonator filters,
Applied Artificial Intelligence, Vol 27, Issue 5, pp 323-350, 2013

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

8 / 85

Metaheurísticas e Hiperheurísticas Metaheurísticas

Problemas en la aplicación de metaheurísticas

Para un problema hay que probar varias metaheurísticas.

Cada metaheurística tiene unos parámetros que hay que tunear.

Problemas de programación para desarrollar las metaheurísticas

y de tiempo de ejecución para probarlas y tunearlas.

Necesidad de explotación de paralelismo para reducir el tiempo de
ejecución.

Metaheurísticas parametrizadas:
Francisco Almeida, Domingo Giménez, Jose J. López-Espín and
Melquíades Pérez-Pérez: Parameterised schemes of metaheuristics: ba-
sic ideas and applications with Genetic algorithms, Scatter Search and
GRASP, IEEE Transactions on Systems, Man and Cybernetics, Part A:
Systems and Humans, Vol 43, Issue 3, pp 570-586, 2013

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

9 / 85

Metaheurísticas e Hiperheurísticas Metaheurísticas parametrizadas

Un esquema parametrizado de metaheurísticas

Esquema parametrizado

Inicializar(S,ParamIni)
mientras (no CondiciónDeFin(S,ParamFin))

SS = Seleccionar(S,ParamSel)
SS1 = Combinar(SS,ParamCom)
SS2 = Mejorar(SS1,ParamMej)
S = Incluir(SS2,ParamInc)

cambiando los parámetros ParamX .

s Fácil selección de diferentes metaheurísticas o combinaciones
s Adaptación sencilla de metaheurísticas a problemas específicos.
s Paralelización simultánea de distintas metaheurísticas si se
s Mismo esquema aplicable a hiperheurísticas para selecciona

paraleliza el esquema.

metaheurísticas satisfactorias.

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

10 / 85

Metaheurísticas e Hiperheurísticas Metaheurísticas parametrizadas

Espacio de metaheurísticas

Varias metaheurísticas básicas
e implementación de las funciones con parámetros
da lugar a un espacio de metaheurísticas básicas e híbridas.

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

11 / 85

Metaheurísticas e Hiperheurísticas Metaheurísticas parametrizadas

Inicialización

Se generan aleatoriamente varias (NIEIni) soluciones.
GA muchas, SS menos, GRASP varias para avance rápido.

Pueden seleccionarse varias (PEMIni) para mejorarlas.
GA no se mejoran, SS y GRASP sí se mejoran.

La mejora tiene un grado (IMEIni) de intensificación.

Se seleciona un subconjunto (NFEIni) para las sucesivas iteraciones.
GA suele ser grande, SS menor y en búsqueda local un único
elemento.

ParamIni = {NIEIni, PEMIni, IMEIni, NFEIni}

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

12 / 85

Metaheurísticas e Hiperheurísticas Metaheurísticas parametrizadas

Condición de Fin

Se establece un número máximo de iteraciones (MNIFin)

y número máximo de iteraciones sin mejorar la mejor solución
encontrada (MIRFin).

Se puede establecer un tiempo máximo.

ParamFin = {MNIFin, MIRFin}

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

13 / 85

Metaheurísticas e Hiperheurísticas Metaheurísticas parametrizadas

Seleccionar

Se selecciona un número de los mejores elementos (NMESel)
y otro de los peores (NPESel).

En GA normalmente se seleccionan los mejores o por la ruleta con
más probabilidad para los más prometedores.

En SS todos, o los mejores y los más distantes de ellos (dispersión).

ParamSel = {NMESel, NPESel}

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

14 / 85

Metaheurísticas e Hiperheurísticas Metaheurísticas parametrizadas

Combinar

Se combina un número de pares de mejores elementos (CMMCom)

de mejores con peores (CMPCom)

y de peores (CPPCom).

En GA combinaciones por pares por una posición de cruce.

En SS combinaciones entre todos, por pares o con más elementos.

ParamCom = {CMMCom, CMPCom, CPPCom}

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

15 / 85

Metaheurísticas e Hiperheurísticas Metaheurísticas parametrizadas

Mejorar

Se mejora un porcentaje (PEMMej) de los elementos generados
GA no se mejora, SS se mejoran todos.

con una cierta intensificación en la mejora (IMEMej).

Se puede diversificar un número de elementos (NEDMej)
En GA se corresponde con la mutación.

y realizar mejora en ellos con un cierto grado de intensificación
(IMDMej), para reducir la posibilidad de pérdida de los elementos
obtenidos.

ParamMej = {PEMMej, IMEMej, NEDMej, IMDMej}

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

16 / 85

Metaheurísticas e Hiperheurísticas Metaheurísticas parametrizadas

Incluir

Se selecciona un número (NMEInc) de los mejores elementos para
incluir en el conjunto de referencia para la siguiente iteración.
En GA se seleccionan todos los mejores, en SS una parte.

El resto hasta NFEIni se seleccionan del resto.
En SS se seleccionan los más “dispersos” respecto a los seleccionados,
utilizando alguna medida de distancia.

ParamInc = {NMEInc}

Domingo Giménez (UM)

Metaheurísticas Paralelas y Aplicaciones

UPV, 2016

17 / 85

Metaheurísticas e Hiperheurísticas Metaheurísticas parametrizadas

Ejemplos de parámetros

Parámetros de metaheurísticas y combinaciones

GR TS SS GA GR+TS GR+SS GR+GA TS+SS TS+GA

200 200 100 100
20 100

1

1

Ini

Sel

NEIIni
NEFIni
PEMIni
IMEIni
MCPIni
NEMSel
NEPSel

0
0
0

100 100 100
50
50
0
0
10 100
0
10
0
90
Com NMMCom 0
NMPCom 0
100
90
NPPCom 0
0
100 100