1 Magnetic Resonance Imaging: Diversity of Contrast Stéren CHABERT.
Panorámica de los procedimientos...
Transcript of Panorámica de los procedimientos...
![Page 1: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/1.jpg)
Panorámica de los procedimientos metaheurísticos
ABRAHAM DUARTE
1
www.grafo.etsii.urjc.es
![Page 2: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/2.jpg)
Optimización
o En lenguaje coloquial, optimizar significa mejorar
o En el contexto científico, es el proceso de tratar de encontrar la mejor solución posible para un problema determinado
![Page 3: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/3.jpg)
Problema de optimización
o El objetivo de un problema de optimización es encontrar la solución óptima dado un criterio para discriminarentre dos soluciones
o Es decir, se trata de encontrar el valor de unas variables de decisión (sujetas a restricciones) para los que una determinada función objetivo alcanza su valor máximo o mínimo
![Page 4: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/4.jpg)
Optimización
o Representación: codifica las soluciones factibles para su representación. Determina el tamaño del espacio de búsqueda del problema
o Objetivo: modelo matemático que expresa la tarea a realizar
o Función de evaluación: asocia a cada solución factible un valor que determina su calidad.
![Page 5: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/5.jpg)
Optimización
o Dado un dominio 𝑋 y una función
el objetivo es encontrar un 𝑥 que verifique
o Optimización combinatoria: consiste en encontrar un objeto en un conjunto finito de soluciones
𝑓 𝑋 : 𝑥 ∈ 𝑋 → 𝑅
𝑥⋆ ∈ 𝑋: 𝑓 𝑥⋆ ≥ 𝑓 𝑥 , ∀𝑥 ∈ 𝑋
![Page 6: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/6.jpg)
Tipos de problemas combinatorios
o Según la representación de la solución• Permutaciones: problemas de ordenación
• Binarios: problemas de pertenencia
• Enteros: problemas de cardinalidad
• Otros (mistos, subgrafos, árboles, etc.)
1221334
4433112
2214432
1112234
![Page 7: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/7.jpg)
Tipos de problemas
o Fáciles de resolver• Lineales: función objetivo y restricciones
lineales (método Simplex)
o Difíciles de resolver (𝑁𝑃-difícil)• No podemos garantizar encontrar la mejor
solución en un tiempo razonable
• La mayoría de problemas de aplicación práctica
• Desarrollamos procedimientos eficientes para encontrar soluciones de calidad©
![Page 8: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/8.jpg)
Tipos de problemas
![Page 9: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/9.jpg)
Tipos de problemas
𝑁𝑃-completo
𝑁𝑃-difícil
𝑃
𝑁𝑃𝑃 = 𝑁𝑃 =𝑁𝑃-completo
𝑁𝑃-difícil
𝑃 ≠ 𝑁𝑃 𝑃 = 𝑁𝑃
![Page 10: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/10.jpg)
Tipos de problemas
![Page 11: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/11.jpg)
Ejemplos de problemas
o Viajante
o Mochila
o Coloreado de grafos
o Partición de conjuntos
o Ordenación lineal
o Diversidad
o Enrutado de vehículos
o …
![Page 12: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/12.jpg)
Problema del viajante
o Travelling Salesman Problem, TSP. Un comerciante tiene que visitar n ciudades, comenzando y finalizando en su propia ciudad. Conociendo el coste de ir de una ciudad a otra, encontrar el recorrido de coste mínimo.
10
1
8
116 13
![Page 13: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/13.jpg)
Problema del viajante
![Page 14: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/14.jpg)
Problema del viajante
o Número de soluciones en el TSP• 10 ciudades. 105 (aprox.)
• 20 ciudades. 1012 (aprox.)
• 50 ciudades. 1062 (aprox.)
• Edad del universo. 15000 millones de años -> 1025 nanosegundos
![Page 15: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/15.jpg)
Problema de la mochila
o Knapsack Problem. Dados n objetos, cada uno con un peso wi y un valor vi, se debe seleccionar el conjunto de objetos que maximicen el valor, sin exceder el peso máximo W de la mochila
15 kg
4€12 kg
2€2 kg
2€1 kg
1€3 kg
10€4 kg
![Page 16: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/16.jpg)
Problemas de la diversidad
o Separación de antenas en redes de telecomunicaciones
• Determinar dónde colocar la antena para maximizar la cobertura de una región
• Si disponemos de N localizaciones, dónde colocamos las M antenas
• Objetivo: aumentar la distancia mínima entre cada par de antenas
![Page 17: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/17.jpg)
Problemas de la diversidad
o Ejemplo de modelado• 𝑁 = 6 localizaciones y hay que colocar 𝑀 = 4
antenas
• Se eligen las localizaciones 𝑒1, 𝑒2, 𝑒3 y 𝑒4, donde la mínima distancia es 𝑑 𝑒1, 𝑒2 = 𝑑 𝑒2, 𝑒3 = 3
• El objetivo del problema es aumentar la distancia
![Page 18: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/18.jpg)
Problema de la diversidad
o Seleccionar un conjunto de elementos de una colección de forma que los elementos seleccionados tengan las características más variadas entre sí
![Page 19: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/19.jpg)
Tipos de óptimos
o Óptimo global: se trata de la mejor solución que se puede encontrar a un problema
o Óptimo local: es la mejor solución de un problema dentro de una vecindad determinada
o Un óptimo global es óptimo local de cualquier vecindad
![Page 20: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/20.jpg)
Tipos de óptimos
![Page 21: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/21.jpg)
Vecindad
o Dada una solución 𝑥, la vecindad 𝑁(𝑥) de esa solución es un subconjunto del espacio de soluciones que contiene soluciones próximas a la original
![Page 22: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/22.jpg)
Movimiento
o En una vecindad 𝑁(𝑥) de una solución 𝑥se encuentran todas aquellas soluciones 𝑥′accesibles desde 𝑥 a través de un movimiento
o Dicho de otro modo, dada una solución 𝑥, cada solución de su vecindad 𝑥′ ∈ 𝑁(𝑥)puede obtenerse directamente desde 𝑥mediante una operación llamada movimiento
![Page 23: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/23.jpg)
Movimiento
![Page 24: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/24.jpg)
Distancia
o Es posible definir la distancia 𝑑𝑖𝑠𝑡(𝑥, 𝑥′)entre dos soluciones 𝑥, 𝑥′
o De la misma forma, podemos redefinir la vecindad como
o Ejemplos: distancia Euclídea, distancia de Hamming, etc.
𝑁 𝑥 = 𝑥′ ∈ 𝑆𝑆: 𝑑𝑖𝑠𝑡 𝑥, 𝑦 ≤ 𝜖
![Page 25: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/25.jpg)
Distancia
![Page 26: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/26.jpg)
Heurísticas y metaheurísticas
o Para la mayoría de los problemas con interés práctico, los algoritmos exactos no son una alternativa realista
• El tamaño del problema hace que éste sea ineficiente computacionalmente
• Ejemplo del viajante
![Page 27: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/27.jpg)
Heurísticas y metaheurísticas
o Hay condiciones difíciles de modelar que exigen flexibilidad
o Se necesitan soluciones aproximadascomo parte de un procedimiento global que garantice el óptimo
• El heurístico proporciona una buena solución inicial y participa en el paso intermedio del procedimiento
![Page 28: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/28.jpg)
Heurísticas y metaheurísticas
o Heurísticas: procedimientos simples basados en el sentido común que obtienen una buena solución a problemas difíciles de un modo sencillo y rápido
o Metaheurísticas: procedimiento iterativo maestro que guía y modifica las operaciones de una heurística subordinada para producir eficientemente soluciones de alta calidad
![Page 29: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/29.jpg)
Exacto vs heurístico
Exactos Heurísticos
Solución óptima Solución de calidad (óptimo no garantizado)
El tiempo invertido para obtener el óptimo de un problema difícil puede ser desproporcionado
El tiempo suele ser reducido
Útiles para problemas pequeños Útiles cuando el problema es grande y necesitamos generar soluciones en un corto espacio de tiempo
![Page 30: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/30.jpg)
Medidas de calidad
o Eficiencia: un esfuerzo computacional realista para obtener la solución
o Bueno: la solución debe estar, en promedio, cerca del óptimo
o Robusto: la probabilidad de obtener una mala solución debe ser baja
![Page 31: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/31.jpg)
Medidas de calidad
o Se mide, para cada ejemplo analizado, la desviación porcentual de la soluciónheurística frente a una referencia, calculando el promedio de las desviaciones
• Comparación con el óptimo
• Comparación con una cota
• Comparación con un método exacto truncado
• Comparación con otros heurísticos
• Análisis del peor caso
![Page 32: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/32.jpg)
Medidas de calidad
o La rapidez de un heurístico es tan importante como la calidad de la solución obtenida
• Un método heurístico es un procedimiento para resolver un problema de optimización bien definido mediante una aproximación intuitiva, en la que la estructura del problema se utiliza de forma inteligente para obtener una buenasolución.
![Page 33: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/33.jpg)
Clasificación de heurísticos
o Heurísticos constructivos: construyen una solución a un problema dado sin disponer de una solución previa. La construcción depende de la estrategia elegida
o Heurísticos de búsqueda: partiendo de una solución factible dada, intentan mejorarla
![Page 34: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/34.jpg)
Heurísticos constructivos
o Estrategia voraz: Partiendo de una semilla, construyen iterativamente una solución
o En cada paso, se añade a la solución el elemento que produzca la mayor mejoraen la solución parcial
o Visión miope: eligen la mejor opción para la siguiente iteración sin importar lo que suceda en el futuro
![Page 35: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/35.jpg)
Heurísticos constructivos
o Estrategia de descomposición: Se divide el problema en subproblemas más pequeños hasta que el tamaño del subproblema es trivial
o El algoritmo combina las soluciones en cada paso hasta obtener la solución al problema original
o Ejemplo: divide y vencerás
![Page 36: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/36.jpg)
Heurísticos constructivos
o Estrategia de reducción: identifican características que contienen las soluciones buenas conocidas y se asume que la solución óptima también las tendrá
• Reducción drástica del espacio de búsqueda
o Manipulación del modelo: simplifican el modelo del problema original, se soluciona el modelo simplificado y se extrapola al problema original
![Page 37: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/37.jpg)
Heurísticos constructivos
o Estrategia aleatorizada: dada una solución factible y una vecindad asociada, se seleccionan aleatoriamente soluciones dentro de la vecindad
o Su éxito depende de la selección de vecindades prometedoras
![Page 38: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/38.jpg)
Heurísticos de búsqueda
o First improvement: examina la vecindad de una solución y selecciona el primer movimiento que produce una mejora
o Best improvement: examina todos los posibles movimientos en una vecindad, seleccionando el que produce la mayor mejora
![Page 39: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/39.jpg)
Limitaciones de los heurísticos
o Dependen en gran medida del problema concreto para el que se han diseñado
o Las técnicas e ideas aplicadas a la resolución de un problema son específicasde éste
o Es difícil trasladar el aprendizaje a otros problemas
• Han de particularizarse para cada caso
![Page 40: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/40.jpg)
Limitaciones de los heurísticos
![Page 41: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/41.jpg)
Metaheurísticas
o Propósito: obtener mejores resultados que los obtenidos por los heurísticostradicionales
o El término fue introducido por Fred Gloveren 1986
o Los procedimientos se sitúan “por encima” de los heurísticos, guiando su comportamiento
![Page 42: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/42.jpg)
Metaheurísticas
![Page 43: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/43.jpg)
Taxonomía
![Page 44: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/44.jpg)
Ejemplos trayectoriales
o Búsqueda Tabu (Tabu Search – TS)
o Búsqueda de Vecindad Variable (Variable Neighborhood Search – VNS)
o GRASP - Greedy Randomized AdaptiveSerach Procedures
o Búsqueda local iterada (Iterated Local Search – ILS)
o Recocido Simulado (Simulated Annealing –SA)
![Page 45: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/45.jpg)
Ejemplos trayectoriales
o Tabu Search - TS
![Page 46: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/46.jpg)
Ejemplos trayectoriales
o Variable Neighborhood Search – VNS
![Page 47: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/47.jpg)
Ejemplos trayectoriales
o Iterated Local Search – ILS
![Page 48: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/48.jpg)
Ejemplos trayectoriales
o Guided Local Search – ILS
![Page 49: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/49.jpg)
Ejemplos poblacionales
o Búsqueda dispersa (Scatter Search – SS)
o Reencadenamiento de trayectorias (PathRelinking – PR)
o Algoritmos evolutivos (genéticos – GA y meméticos – MA)
o Optimización por colonias de hormigas (AntColony Optimization – ACO)
o Inteligencia de enjambre (Swarm Intelligence –SI)
![Page 50: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/50.jpg)
Ejemplos poblacionales
o Scatter Search - SS
![Page 51: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/51.jpg)
Ejemplos poblacionales
o Path Relinking – PR
![Page 52: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/52.jpg)
Ejemplos poblacionales
o Algoritmos evolutivos
![Page 53: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/53.jpg)
Ejemplos poblacionales
o Algoritmos por colonias de hormigas –ACO
![Page 54: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/54.jpg)
Nuevos métodos bioinspirados
o Hipótesis de partida• La similitud biológica/evolutiva es una fuente de
inspiración para nuevos métodos metaheurísticos
• Si ha funcionado en la naturaleza, ¿por qué no va a funcionar en optimización?
![Page 55: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/55.jpg)
Nuevos métodos bioinspirados
o Estrategias establecidas• Optimización por Colonias de abejas
• Algoritmo de la luciérnaga
• Búsqueda harmónica
• Búsqueda del cuco
![Page 56: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/56.jpg)
Nuevos métodos bioinspirados
o Inspiración física• Magnetic Inspired optimization Algorithms. Inspirado
en el movimiento de partículas en campos magnéticos
• Quantum Evolutionary Algorithms. Basados en bits cuánticos y superposición de estados
• Intelligent water drop. Basada en cómo los ríos encuentran casi el mejor camino a su desembocadura
• Gravitational search algorithm . Basado en teoría de gravitación Universal
• Charged System Search. Basado en la ley de Coulomb
![Page 57: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/57.jpg)
Nuevos métodos bioinspirados
o Inspiración de enjambre• Invasive weed optimization algorithms. Inspirada cómo
las semillas crecen en unos determinados terrenos
• Glowworms Colonies Optimization. Equivalente a ACO pero con larvas
• Monkey Search. Inspirada en cómo los monos trepan a los árboles para buscar comida
• Shuffled frog-leaping algorithm. Búsquedas locales en nenúfares (memeplexes) e intercambios de ranas
![Page 58: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/58.jpg)
Visión algorítmica unificada
![Page 59: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/59.jpg)
Conclusiones
o Optimización por colonias de hormigas: Inclusión de memoria tipo “soft”
o Optimización por enjambre de partículas: Nuevas formas de generar caminos entre soluciones
o Algoritmos genéticos híbridos: búsquedas locales, nuevos métodos de combinación, etc.
o Otros métodos sin inspiración biológica (IteratedGreedy)
![Page 60: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/60.jpg)
Conclusiones
o Limitaciones• No free lunch theorem
• Algoritmos competitivos
o Solución• Hibridaciones
• Implementaciones novedosas
• Paralelización
• Etc.
![Page 61: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/61.jpg)
Conclusiones
![Page 62: Panorámica de los procedimientos metaheurísticosweb.fdi.ucm.es/posgrado/conferencias/AbrahamDuarte-slides.pdf · Nuevos métodos bioinspirados o Inspiración física • Magnetic](https://reader034.fdocumento.com/reader034/viewer/2022052319/5bc2cfd209d3f291178cd312/html5/thumbnails/62.jpg)
Panorámica de los procedimientos metaheurísticos
ABRAHAM DUARTE
62
www.grafo.etsii.urjc.es