Publicado el 18 de Julio del 2018
1.241 visualizaciones desde el 18 de Julio del 2018
2,8 MB
93 paginas
Creado hace 8a (10/01/2017)
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
Comentarios de: Metaheurísticas paralelas: optimización y aplicaciones (0)
No hay comentarios