Modelos y herramientas de decisión : Introducción a MHD
Full text
1 Francisco Herrera Grupo de Investigación “Soft Computing and Intelligent Information Systems” Dpto. Ciencias de la Computación e I.A. Universidad de Granada 18071 – ESPAÑA [email protected] http://sci2s.ugr.es Introducción a los Algoritmos Metaheurísticos
2 Introducción a los Algoritmos Metaheurísticos Los algoritmos metaheurísticos son algoritmos aproximados de optimización y búsqueda de propósito general. Son procedimientos iterativos que guían una heurística subordinada combinando de forma inteligente distintos conceptos para explorar y explotar adecuadamente el espacio de búsqueda. En múltiples problemas de IA nos encontramos modelos asociados a problemas de optimización y búsqueda.
3 Introducción a los Algoritmos Metaheurísticos Los algoritmos metaheurísticos son algoritmos aproximados de optimización y búsqueda de propósito general. Son procedimientos iterativos que guían una heurística subordinada combinando de forma inteligente distintos conceptos para explorar y explotar adecuadamente el espacio de búsqueda. El objetivo de este tutorial presentar las líneas básicas de desarrollo de algoritmos metaheurísticos y su aplicabilidad en el ámbito de la Inteligencia Artificial. En múltiples problemas de IA nos encontramos modelos asociados a problemas de optimización y búsqueda.
4 1. Introducción a las Metaheurísticas. Resolución de Problemas Mediante Algoritmos de Búsqueda 2. MH I: Búsqueda Basada Trayectorias 3. MH II: Swarm Intelligence 4. MH III: Algoritmos Evolutivos 5. Limitaciones de los Algoritmos MH: Teorema NFL 6. MH IV: Algoritmos Híbridos: Poblaciones vs. Trayectorias 7. Consideraciones Sobre el Uso de las Metaheurísticas 8. Algunos Estudios/Extensiones de Interés 9. Comentarios Finales Introducción a los Algoritmos Metaheurísticos http://sci2s.ugr.es/docencia/metaheuristicas.php
5 1. Introducción a las Metaheurísticas. Resolución de Problemas Mediante Algoritmos de Búsqueda 2. MH I: Búsqueda Basada Trayectorias 3. MH II: Swarm Intelligence 4. MH III: Algoritmos Evolutivos 5. Limitaciones de los Algoritmos MH: Teorema NFL 6. MH IV: Algoritmos Híbridos: Poblaciones vs. Trayectorias 7. Consideraciones Sobre el Uso de las Metaheurísticas 8. Algunos Estudios/Extensiones de Interés 9. Comentarios Finales Introducción a los Algoritmos Metaheurísticos http://sci2s.ugr.es/docencia/metaheuristicas.php
6 Introducción a las Metaheurísticas Resolución de Problemas Mediante Algoritmos de Búsqueda: Introducción Metaheurísticas: Definición Funcionamiento de las Metaheurísticas Clasificación de las Metaheurísticas Ejemplo: El problema del viajante de comercio
7 Resolución de Problemas Mediante Algoritmos de Búsqueda: Introducción Existe una serie de problemas reales (de optimización combinatoria, de ingeniería, ..) de difícil solución que requieren de tareas tales como encontrar: el camino más corto entre varios puntos, un plan de mínimo coste para repartir mercancías a clientes, una asignación óptima de trabajadores a tareas a realizar, una secuencia óptima de proceso de trabajos en una cadena de producción, una distribución de tripulaciones de aviones con mínimo coste, el mejor enrutamiento de un paquete de datos en Internet, ...
8 Resolución de Problemas Mediante Algoritmos de Búsqueda: Introducción Estos problemas se caracterizan porque: suelen requerir agrupamientos, ordenaciones o asignaciones de un conjunto discreto de objetos que satisfagan ciertas restricciones, se encuentran en muchas áreas de aplicación, presentan una gran complejidad computacional (son NPduros) así, los algoritmos exactos (Programación Dinámica, Backtracking, Branch and Bound, ...) son ineficientes o simplemente imposibles de aplicar, en la práctica se resuelven mediante algoritmos aproximados que proporcionan buenas soluciones (no necesariamente la óptima) al problema en un tiempo razonable
9 Metaheurísticas: Definición Son una familia de algoritmos aproximados de propósito general. Suelen ser procedimientos iterativos que guían una heurística subordinada de búsqueda, combinando de forma inteligente distintos conceptos para explorar y explotar adecuadamente el espacio de búsqueda. Ventajas: Algoritmos de propósito general Gran éxito en la práctica Fácilmente implementables Fácilmente paralelizables Inconvenientes: Son algoritmos aproximados, no exactos Son no determinísticos (probabilísticos) No siempre existe una base teórica establecida
16 Clasificación de las Metaheurísticas Fuente de inspiración. Inspiración biológica. Ej. Algoritmos de Optimización basados en Colonias de Hormigas
17 Una posible clasificación: Basadas en métodos constructivos (Parten de una solución inicial vacía y van añadiéndole componentes hasta construir una solución): GRASP, Optimización Basada en Colonias de Hormigas Basadas en trayectorias (la heurística subordinada es un algoritmo de búsqueda local que sigue una trayectoria en el espacio de búsqueda. Parten de una solución inicial e iterativamente tratan de reemplazarla por otra solución de con mejor calidad): Búsqueda Local, Enfriamiento Simulado, Búsqueda Tabú, BL Iterativa, ... Clasificación de las Metaheurísticas
18 Una posible clasificación: Basadas en métodos constructivos (Parten de una solución inicial vacía y van añadiéndole componentes hasta construir una solución): GRASP, Optimización Basada en Colonias de Hormigas Basadas en trayectorias (la heurística subordinada es un algoritmo de búsqueda local que sigue una trayectoria en el espacio de búsqueda. Parten de una solución inicial e iterativamente tratan de reemplazarla por otra solución de con mejor calidad): Búsqueda Local, Enfriamiento Simulado, Búsqueda Tabú, BL Iterativa, ... Clasificación de las Metaheurísticas
19 Basadas en trayectorias local global Clasificación de las Metaheurísticas
20 Una posible clasificación: Basadas en métodos constructivos: GRASP, Optimización Basada en Colonias de Hormigas Basadas en trayectorias (la heurística subordinada es un algoritmo de búsqueda local que sigue una trayectoria en el espacio de búsqueda): Búsqueda Local, Enfriamiento Simulado, Búsqueda Tabú, BL Iterativa, ... Basadas en poblaciones (el proceso considera múltiples puntos de búsqueda en el espacio que evolucionan en paralelo): Algoritmos Genéticos, Scatter Search, Algoritmos Meméticos, PSO, ... Clasificación de las Metaheurísticas
21 Basadas en poblaciones I am not at the top. My high is better! I am at the top Height is ... I will continue Clasificación de las Metaheurísticas
22 Basadas en poblaciones Clasificación de las Metaheurísticas
23 Clasificación de las Metaheurísticas Metaherísticas inspiradas en la naturaleza: Algoritmos Bioinspirados • Swarm Intelligence (Algoritmos basados en la inteligencia de enjambre) • Optimización Basada en Colonias de Hormigas (constructivos) • Algoritmos basados en nubes de partículas (basados en poblaciones) • Algoritmos Evolutivos (basados en poblaciones)
24 Las heurísticas constructivas son más rápidas pero dan soluciones de peor calidad que la búsqueda basada en trayectorias Ambos son procesos de búsqueda efectuados sobre un espacio de soluciones al problema. En los métodos constructivos, el espacio es de soluciones parciales, mientras que en la búsqueda por trayectorias y poblaciones es de soluciones completas (candidatas) En este último caso el espacio de búsqueda suele ser de un tamaño exponencial con respecto al tamaño del problema Clasificación de las Metaheurísticas
25 En el viajante de comercio, se tiene una red de nodos, que pueden ser ciudades o simplemente lugares de una ciudad. Se parte de un lugar inicial, y deben recorrerse todos sin pasar más de una vez por cada lugar, volviendo al lugar inicial. Para cada arco, se tiene un valor Cij, que indica la distancia o el costo de ir del nodo i al nodo j. Es un problema muy estudiado al presentar aplicaciones reales tales como la fabricación en serie de tarjetas de ordenador (impresión de los buses de estaño) Ejemplo: El problema del viajante de comercio
32 DOMINIOS DE APLICACIÓN Optimización combinatoria Optimización en ingeniería Modelado e identificación de sistemas Planificación y control Aprendizaje y minería de datos Vida artificial Bioinformática …. Aplicaciones
33 B. Melián, J.A. Moreno Pérez, J.M. Moreno Vega. Metaheurísticas: un visión global. Revista Iberoamericana de Inteligencia Artificial 19 (2003) 7-28 C. Blum, A. Roli. Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput. Surv. 35:3 (2003) 268-308. Colin G. Johnson A design framework for metaheuristics. Artif Intell Rev (2008) 29:163–178 Lecturas http://sci2s.ugr.es/docencia/metaheuristicas.php Metaheuristics: From Design to Implementation El-Ghazali Talbi ISBN: 978-0-470-27858-1 593 pages July 2009
34 1. Introducción a las Metaheurísticas. Resolución de Problemas Mediante Algoritmos de Búsqueda 2. MH I: Búsqueda Basada Trayectorias 3. MH II: Swarm Intelligence 4. MH III: Algoritmos Evolutivos 5. Limitaciones de los Algoritmos MH: Teorema NFL 6. MH IV: Algoritmos Híbridos: Poblaciones vs. Trayectorias 7. Consideraciones Sobre el Uso de las Metaheurísticas 8. Algunos Estudios/Extensiones de Interés 9. Comentarios Finales Introducción a los Algoritmos Metaheurísticos http://sci2s.ugr.es/docencia/metaheuristicas.php
35 Búsqueda Basada en Trayectorias Búsqueda Local y Estructura de Entorno Características de Diferentes Algoritmos de Búsqueda Basada en Trayectorias Búsqueda Basada en Múltiples Trayectorias: Métodos Multiarranque Búsqueda Local Iterativa: ILS Bibliografía F. Glover, G.A. Kochenberger (Eds.). Handbook of Metaheuristics. Kluwer Academic Press, 2003. H.H. Hoos, T. Stützle. Stochastic Local Search. Morgan Kaufmann, 2004.
36 Término “LOCAL” El término “local” se utiliza frecuentemente en los estudios teóricos y prácticos de las metaheurísticas de búsqueda. Se asocia al uso de estructuras de entorno, reflejando el concepto de proximidad o vecindad entre las soluciones alternativas del problema. Todas las soluciones incluidas en el entorno de la solución actual, que viene delimitado por un operador de generación de soluciones, se denominan soluciones vecinas. Búsqueda Local y Estructura de Entorno
37 Término “LOCAL” Los algoritmos basados en trayectorias efectúan un estudio local del espacio de búsqueda, analizan el entorno de la solución actual para decidir cómo continuar el recorrido de la búsqueda. Búsqueda Local y Estructura de Entorno 3 σ )( 3 σN 2 σ )( 2 σN 1 σ )( 1 σN 0 σ )( 0 σN Solución inicial 4 σ )( 4 σN Óptimo local/global
38 Estructura de Entorno Basta con diseñar la estructura de entorno para obtener un modelo genérico de algoritmo de búsqueda. DESCRIPCIÓN Se fija una codificación para las soluciones. Se define un operador de generación de vecino y, en consecuencia, se fija una estructura de entorno para las mismas. Se escoge una solución del entorno de la solución actual hasta que se satisfaga el criterio de parada. Búsqueda Local y Estructura de Entorno
39 Procedimiento Búsqueda por Entornos Inicio GENERA(Solución Inicial) Solución Actual ← Solución Inicial; Mejor Solución ← Solución Actual; Repetir Solución Vecina ← GENERA_VECINO(Solución Actual); Si Acepta(Solución Vecina) entonces Solución Actual ← Solución Vecina; Si Objetivo(Solución Actual) es mejor que Objetivo(Mejor Solución) entonces Mejor Solución ← Solución Actual; Hasta (Criterio de parada); DEVOLVER (Mejor Solución); Fin Búsqueda Local y Estructura de Entorno
40 Figura que muestra una trayectoria de búsqueda basada en entornos Aceptación de soluciones mejores que la actual Aceptación de soluciones peores que la actual Búsqueda Local y Estructura de Entorno
41 SOLUCIONES: 3 opciones para salir de los óptimos locales Permitir movimientos de empeoramiento de la solución actual (Ejemplo: Enfriamiento Simulado, Búsqueda Tabú, …). Modificar la estructura de entornos (Ejemplo: Búsqueda Tabú, Búsqueda Descendente Basada en Entornos Variables: VND, Búsqueda en Entornos Variables: VNS, …). Volver a comenzar la búsqueda desde otra solución inicial (Ejemplo: Búsquedas Multiarranque, ILS, VNS, GRASP, Optimización Basada en Colonia de Hormigas, …). Características de Diferentes Algoritmos de Búsqueda Basada en Trayectorias
48 La aplicación de la ILS necesita de la definición de cuatro componentes: 1. Una solución inicial (usualmente, aleatoria) 2. Un procedimiento de modificación (mutación) que aplica un cambio brusco sobre la solución actual para obtener una solución intermedia 3. Un procedimiento de Búsqueda Local 4. Un criterio de aceptación que decide a qué solución se aplica el procedimiento de modificación En la mayoría de las aplicaciones, la mutación se aplica a la mejor solución encontrada H.R. Lourenço, O.C. Martin, T. Stützle, Iterated Local Search. En: F.Glover, G. Kochenberger (Eds.), Handbook of Metaheuristics. Kluwer Academic Publishers, 2003, pp. 321-353. H.H. Hoos, T. Stützle. Stochastic Local Search. Morgan Kaufmann, 2004. Búsqueda Local Iterativa: ILS
49 Figura: Representación del funcionamiento de la ILS Caída en el óptimo local s*. La perturbación/mutación conduce a s’. Después de aplicar la Búsqueda Local, se encuentra un nuevo óptimo s*’ que es mejor que s* Búsqueda Local Iterativa: ILS
50 Procedimiento Búsqueda Local Reiterada (ILS) Comienzo-ILS So Generar-Solución-Inicial S Búsqueda Local (So) Repetir S’ Modificar (S, historia) %Mutación S’’ Búsqueda Local (S’) S Criterio-Aceptación (S, S’’, historia) Actualizar (S, Mejor_Solución) Hasta (Condiciones de terminación) Devolver Mejor_Solución Fin-ILS Modelo General del Algoritmo ILS Búsqueda Local Iterativa: ILS
51 K.A. Dowsland, B.A. Díaz. Diseño de Heurísticas y Fundamentos del Recocido Simulado. Revista Iberoamericana de Inteligencia Artificial 19 (2003) 93-102. B. Suman, P. Kumar. A survey of simulated annealing as a tool for single and multiobjective optimization. Journal of the Operational Research Society 57:10 (2006) 1143-1160. F. Glover, B. Melián. Búsqueda Tabú. Revista Iberoamericana de Inteligencia Artificial 19 (2003) 29-48. M. Gendreau. Chapter 2: An Introduction to Tabu Search. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 37-54. M.G.C. Resende, C.S. Ribeiro. Chapter 8: Greedy Randomized Adaptive Search Procedure. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 221-249. R. Martí. Chapter 12: Multi-Start Methods. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 355-368. H.L. Lourenço, O.C. Martin, T. Stützle. Chapter 11: Iterated Local Search. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 321-353. P. Hansen, N. Mladenovic. Chapter 6: Variable Neighborhood Search. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 145-184. Lecturas http://sci2s.ugr.es/docencia/metaheuristicas.php
52 1. Introducción a las Metaheurísticas. Resolución de Problemas Mediante Algoritmos de Búsqueda 2. MH I: Búsqueda Basada Trayectorias 3. MH II: Swarm Intelligence 4. MH III: Algoritmos Evolutivos 5. Limitaciones de los Algoritmos MH: Teorema NFL 6. MH IV: Algoritmos Híbridos: Poblaciones vs. Trayectorias 7. Consideraciones Sobre el Uso de las Metaheurísticas 8. Algunos Estudios/Extensiones de Interés 9. Comentarios Finales Introducción a los Algoritmos Metaheurísticos http://sci2s.ugr.es/docencia/metaheuristicas.php
53 Swarm Intelligence Definición Swarm Intelligence Inspiración Biológica Sociedades de Insectos Técnicas Contextualización Comentarios Finales
54 “La inteligencia colectiva emergente de un grupo de agentes simples” “The emergent collective intelligence of groups of simple agents” “Algoritmos o mecanismos distribuidos de resolución de problemas inspirados en el comportamiento colectivo de colonias de insectos sociales u otras sociedades de animales”. (Bonabeau, Dorigo, Theraulaz, 1999) E. Bonabeau, M. Dorigo, G. Theraulaz Swarm Intelligence. From Nature to Artificial Systems. Oxford University Press, 1999. Introducción: Swarm Intelligence
55 Inspiración Biológica flocks of birds (bandadas de aves) herds of mammals (manadas de mamíferos) schools of fish (bancos de peces) sociedades de insectos (bees, wasps, ants, termites) (abejas, avispas, hormigas, termitas) Introduction: Swarm Intelligence
56 Insectos Llevan a cabo actuaciones colectivas que no serían posibles para un único individuo Proporcionan comportamientos adecuados para la computación distribuida El repertorio de comportamientos de cada insecto es limitado No existe acceso individual al estado completo de la colonia No pueden hacer una división efectiva de la labor a realizar No pueden garantizar el progreso de la colonia De las Sociedades de Insectos a los Sistemas Inteligentes de Enjambre
57 Comportamiento emergente Las colonias de insectos llevan a cabo actuaciones de nivel complejo de forma inteligente, flexible y fiable, actuaciones que no serían factibles si tuviesen que ser realizadas por un insecto de forma individual (éstos son no inteligentes, no fiables, simples). Los insectos siguen reglas simples, y utilizan comunicación local simple La estructura global (nido) emerge desde las acciones de los insectos (las cuales son no fiables atendidas individualmente) De las Sociedades de Insectos a los Sistemas Inteligentes de Enjambre
64 ¿Cómo puede ser coordinado el esfuerzo individual para alcanzar una tema común? Swarm Inspired Methods particle swarm optimization – PSO Optimización basada en nubes de partículas Conjunto de técnicas inspiradas en el comportamiento de las bandadas de aves o bancos de peces ant colony optimization – ACO Optimización basada en colonias de hormigas Conjunto de técnicas inspiradas por las actividades de una colonia de hormigas Swarm Intelligence: Técnicas
65 Ant Colony Optimization La analogía más cercana a ACO son los problemas de rutas en grafos Mientras las hormigas buscan comida, depositan rastros de feromona que atraen a otras hormigas. Desarrollan caminos mínimos entre la comida y el hormiguero.
66 Experimento con Hormigas reales. Como encuentran el camino mínimo (159 segundos) Ant Colony Optimization
67 PSO emula este escenario para resolver problemas de optimización. Cada solución (partícula) es un “ave” en el espacio de búsqueda que está siempre en continuo movimiento y que nunca muere. Particle Swarm Optimization
68 Particle Swarm Optimization 5 10 15 20 25 5 10 15 20 25 pbest gbest v(k) v(k+1) Particle Swarm Optimization (PSO) aplica conceptos de interacción social a la resolución de problemas de búsqueda/ optimización. En PSO, un enjambre de n individuos se comunica directa o indirectamente con otros vía las direcciones de búsqueda.
69 Particle Swarm Optimization 5 10 15 20 25 5 10 15 20 25 pbest gbest v(k) v(k+1) Las Particulas pueden ser simples agentes que vuelan a través del espacio de búsqueda y almacenan (y posiblemente comunican) la mejor solución que han descubierto. En PSO, las partículas nunca mueren. La pregunta es, “¿Cómo se mueve una partícula desde una localización a otro del espacio de búsqueda?
70 PSO emula este escenario para resolver problemas de optimización. Cada solución (partícula) es un “ave” en el espacio de búsqueda que está siempre en continuo movimiento y que nunca muere. Particle Swarm Optimization
71 Una definición de contexto de Swarm Intelligence en el ámbito de la Inteligencia Artificial AI MAS SI AI - Artificial Intelligence MAS - Multi Agent Systems SI - Swarm Intelligence Comentarios Finales
72 Swarm Intelligence (SI) es la propiedad de un sistema por la cual el comportamiento colectivo de agentes (no sofísticados) interactua localmente con el entorno proporcionando un patrón global de funcionamiento coherente como “emergente”. SI proporciona una base con la cual es posible explorar la resolución de problemas colectivamente (o de forma distribuida) sin un control centralizado ni un model global de comportamiento. Comentarios Finales
73 “Dumb parts, properly connected into a swarm, yield smart results”. “Partes tontas/mudas, conectadas adecuadamente en un enjambre, producen resultados elegantes/ inteligentes”. Comentarios Finales Bibliografía E. Bonabeau, M. Dorigo, G. Theraulaz. Swarm Intelligence. From Nature to Artificial Systems. Oxford Univ. Press, 1999. M. Dorigo, T. Stuetzle. Ant Colony Optimization. MIT Press, 2004. Kennedy, J., Eberhart, R. C., and Shi, Y.. Swarm intelligence. Morgan Kaufmann Publishers, 2001.
80 La selección natural es el enlace entre los cromosomas y la actuación de sus estructuras decodificadas. El proceso de reproducción es el punto en el cual la evolución toma parte, actúa. La evolución biológica no tiene memoria. Darwin, C. (1859). On the Origin of Species by Means of Natural Selection or the Preservations of Favored Races in the Struggle for Life. London: John Murray. EVOLUCIÓN NATURAL
81 EVOLUCIÓN NATURAL
82 EVOLUCIÓN ARTIFICIAL LA METÁFORA EVOLUCIÓN Individuo Adaptación Entorno RESOLUCIÓN DE PROBLEMAS Solución Candidata Calidad Problema
83 EVOLUCIÓN ARTIFICIAL t t + 1 mutación recombinación reproducción selección LOS INGREDIENTES RECOMBINACIÓN OPTATIVA
Ejemplo: Mutación para representación binaria 1 1 1 1 1 1 1 antes 1 1 1 0 1 1 1 después La mutación suele ocurrir con probabilidad pm para cada gen gen mutado EVOLUCIÓN ARTIFICIAL
85 Ejemplo: Recombinación para representación binaria Población: . . . Cada cromosoma se trocea en n partes las cuales son recombinadas. (Ejemplo para n=1) 1 1 1 1 1 1 1 0 0 0 0 0 0 0 padres corte corte 1 1 1 0 0 0 0 0 0 0 1 1 1 1 descendientes EVOLUCIÓN ARTIFICIAL
86 Recombinación Mutación Selección Reemplazamiento EVOLUCIÓN ARTIFICIAL PADRES POBLACIÓN DESCENDIENTES El ciclo de la Evolución
87 EVOLUCIÓN ARTIFICIAL Existen cuatro paradigmas básicos: Algoritmos Genéticos que utilizan operadores genéticos sobre cromosomas. 1975, Michigan University Estrategias de Evolución que enfatizan los cambios de comportamiento al nivel de los individuos. 1964, Technische Universität Berlin Programación Evolutiva que enfatizan los cambios de comportamiento al nivel de las especies. 1960-1966, Florida Programación Genética que evoluciona expresiones representadas como árboles. 1989, Stanford University John Holland Inventor of genetic algorithms Professor of CS and Psychology at the U. of Michigan. Ing. Ingo Rechenberg Bionics & Evolutiontechnique Technical University Berlin http://www.bionik.tu-berlin.de/ Hans-Paul Schwefel Universität Dortmund Lawrence J. Fogel, Natural Selection, Inc. Inventor of Evolutionary Programming John Koza Stanford University. Inventor of Genetic Programming Inventors of Evolution Strategies
88 EVOLUCIÓN ARTIFICIAL Existen otros múltiples Modelos de Evolución de Poblaciones: EDA: Estimation Distribution Algorithms (Algoritmos basados en Estimación de Distribuciones) DE: Differential Evolution (Evolución Diferencial) Algoritmos Evolutivos Culturales Algoritmos Meméticos Scatter Search – Búsqueda Dispersa
89 EVOLUCIÓN ARTIFICIAL
96 Thomas Bäck, Ulrich Hammel, Hans-Paul Schwefel. Evolutionary Computation: Comments on the History and Current State. IEEE Transactions on Evolutionary Computation 1:1 (1997) 3-17. C. Reeves. Chapter 3: Genetic Algorithms. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 55-82. F. Herrera, M. Lozano, A.M. Sánchez. A Taxonomy for the Crossover Operator for RealCoded Genetic Algorithms: An Experimental Study. International Journal of Intelligent Systems 18 (2003) 309-338R. Storn, K. Price. Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization 11 (1997) 341-359. Lecturas http://sci2s.ugr.es/docencia/metaheuristicas.php
97 1. Introducción a las Metaheurísticas. Resolución de Problemas Mediante Algoritmos de Búsqueda 2. MH I: Búsqueda Basada Trayectorias 3. MH II: Swarm Intelligence 4. MH III: Algoritmos Evolutivos 5. Limitaciones de los Algoritmos MH: Teorema NFL 6. MH IV: Algoritmos Híbridos: Poblaciones vs. Trayectorias 7. Consideraciones Sobre el Uso de las Metaheurísticas 8. Algunos Estudios/Extensiones de Interés 9. Comentarios Finales Introducción a los Algoritmos Metaheurísticos http://sci2s.ugr.es/docencia/metaheuristicas.php
98 Limitaciones los Algoritmos de Metaheurísticos Algoritmos Metaheurístico Genérico Algoritmos Especializados Dominio de Problemas Comportamineto Sobre el Comportamiento de los Algoritmos Metaheurísticos
99 No Free Lunch Theorem (1995): E c f m a E c f m b f f ( / , , ) ( / , , ) = ∑ ∑ William G. Macready David. H. Wolpert No free lunch theorems for optimization Wolpert, D.H.; Macready, W.G.; Evolutionary Computation, IEEE Transactions on 1:1, April 1997, 67 – 82 "...for any algorithm, any elevated performance over one class of problems is exactly paid for in performance over another class.“Wolpert and Macready (1997) Limitaciones de los Algoritmos de Metaheurísticos
100 Implicaciones de NFL (I) Superioridad del Algoritmo A Superioridad del Algoritmo B Comportamiento + = A B E c f m a E c f m b f f ( / , , ) ( / , , ) = ∑ ∑ Limitaciones los Algoritmos de Metaheurísticos
101 Dominio de Problemas Comportamiento A1 A2 A3 A1 A2 A3 Implicaciones de NFL (II): Ganar en un cierto dominio implica perder en los restantes Limitaciones los Algoritmos de Metaheurísticos
102 Discusión ¿La búsqueda aleatoria se comporta como nuestro algoritmo? ¡Hay que discultir algunas cuestiones en el teorema de NFL! Limitaciones los Algoritmos de Metaheurísticos
103 Consideremos los diferentes grados de conocimiento del problema: 1. Conocimiento perfecto 2. Conocimiento parcial 3. Poco conocimiento 4. Muy poco conocimiento 5. Ningún conocimiento (NFL) Los resultados del teorema NFL son críticos tanto en cuanto (2) es comparado con (5). El conocimiento sobre el problema debe ser incluido en el algoritmos de búsqueda. Limitaciones los Algoritmos de Metaheurísticos
104 1. Introducción a las Metaheurísticas. Resolución de Problemas Mediante Algoritmos de Búsqueda 2. MH I: Búsqueda Basada Trayectorias 3. MH II: Swarm Intelligence 4. MH III: Algoritmos Evolutivos 5. Limitaciones de los Algoritmos MH: Teorema NFL 6. MH IV: Algoritmos Híbridos: Poblaciones vs. Trayectorias 7. Consideraciones Sobre el Uso de las Metaheurísticas 8. Algunos Estudios/Extensiones de Interés 9. Comentarios Finales Introducción a los Algoritmos Metaheurísticos http://sci2s.ugr.es/docencia/metaheuristicas.php
105 Algoritmos evolutivos son buenos exploradores Algoritmos de búsqueda local son malos exploradores Búsqueda global Exploración Búsqueda local Explotación Algoritmos evolutivos son malos explotadores Algoritmos de búsqueda local son buenos explotadores Algoritmos Híbridos: Poblaciones vs Trayectorias
112 Búsquedas basadas en trayectorias/entornos Búsquedas basadas en poblaciones Consideraciones sobre el uso de las MH Lectura: A. Hertz, M. Widmer. Guidelines for the use of meta-heuristics in combinatorial optimization. European Journal of Operational Research 151 (2003) 247-252.
113 Debería ser fácil generar una solución al problema En algunos problemas, generar una solución factible resulta en sí mismo un problema NP-duro Igualmente, en estos casos resulta complejo aplicar un operador de vecino que garantice obtener una solución factible En estos casos, puede ser más útil relajar las restricciones del problema permitiendo generar soluciones no válidas, y añadir una penalización en la función objetivo que evite aceptar estas soluciones Búsquedas Basadas en Trayectorias/Entornos
114 A partir de cada solución, debería poder trazarse un camino que lleve esta solución a una solución óptima El operador de vecino empleado debe permitir que aplicándolo sucesivas veces se alcance un óptimo Cualquier solución del entorno generado a partir de una solución actual debe estar relativamente cercana a ésta El operador de vecino debe hacer cambios “suaves” Búsquedas Basadas en Trayectorias/Entornos
115 La topología generada a partir de la función de coste sobre el conjunto de soluciones factibles no debería ser demasiado plana En algunos problemas, la función de coste es, por ejemplo, del tipo “minimizar la máxima distancia entre dos puntos” Este tipo de funciones genera planicies haciendo que distintas soluciones tengan el mismo valor objetivo Sin embargo, unas soluciones estarán más cerca (desde el punto de vista de la codificación) que otras de la solución óptima En estos casos, se puede añadir una segunda componente a la función objetivo que discrimine entre estas soluciones Búsquedas Basadas en Trayectorias/Entornos
116 Debe transmitirse la información relevante en la fase de cooperación (combinación) En algunos problemas, no basta con asegurar que los descendientes contengan parte de la codificación de los padres, sino que sea la información contenida en los padres la que realmente se transmita Búsquedas Basadas en Poblaciones La combinación de dos padres equivalentes no debería producir un descendiente diferente a los padres Debe mantenerse diversidad en la población para evitar que el algoritmo se estanque (convergencia prematura)
117 1. Introducción a las Metaheurísticas. Resolución de Problemas Mediante Algoritmos de Búsqueda 2. MH I: Búsqueda Basada Trayectorias 3. MH II: Swarm Intelligence 4. MH III: Algoritmos Evolutivos 5. Limitaciones de los Algoritmos MH: Teorema NFL 6. MH IV: Algoritmos Híbridos: Poblaciones vs. Trayectorias 7. Consideraciones Sobre el Uso de las Metaheurísticas 8. Algunos Estudios/Extensiones de Interés 9. Comentarios Finales Introducción a los Algoritmos Metaheurísticos http://sci2s.ugr.es/docencia/metaheuristicas.php
118 Algunos Estudios/Extensiones de Interés Diversidad versus Convergencia Problemas Multimodales Problemas Multiobjetivo Algoritmos Evolutivos Paralelos Coevolución
119 Diversidad Convergencia Equilibrio D/C Diversidad vs. Convergencia
120 Algunas propuestas en el ámbito de los Algoritmos Evolutivos: Diversidad con la Mutación Diversidad con el Cruce Separación Espacial Adaptación, Auto-adaptación, Metaevolución Estrategias de Reemplazamiento Diversidad vs. Convergencia
121 Problemas Multimodales Muchos problemas interesantes tienen más de una solución localmente óptima. Son problemas que tienen multiples óptimos locales o múltiples optimos globales (multiples soluciones al problema). En la resolución del problema se desea obtener varios de esos óptimos locales o globales. Técnica: Niching Genetic Algorithms
128 Comentarios Finales En la actualidad, los algoritmos metaheurísticos constituyen una de las áreas de investigación más activas en el ámbito de los problemas de optimización y búsqueda. Su progreso está siendo rápido, surgiendo continuamente nuevas ideas en un intento de alcanzar una mayor eficiencia en el proceso de resolución de problemas. Desde una perspectiva aplicada, el conjunto de áreas de aplicación es muy amplio, encontrándonos múltiples aplicaciones en los diferentes ámbitos de la ingeniería, hibridaciones con técnicas de Inteligencia Computacional e Inteligencia Artificial, …
129 Introducción a los Algoritmos Metaheurísticos http://sci2s.ugr.es/docencia/metaheuristicas.php