Metodologías

Esta página contiene una breve descripción de algunas metodologías metaheurísticas en Español. El objetivo es ser un punto de partida para los que deseen iniciarse en estas técnicas. Hemos limitado esta lista a los métodos más establecidos y probados en publiciones contrastadas. Ha sido posible por la contribución de varios compañeros de la red. Si quieres contribuir con descripciones o materiales para ayudar a los lectores, envía un mensaje a rafael.marti@uv.es.

El área de la optimización heurística está creciendo de un modo un tanto descontrolado, en donde en ocasiones vemos métodos cuyo mayor mérito es imitar un fenómeno o población natural, pero en nuestra opinión no han probado científicamente su solvencia. No incluimos tales métodos. Podéis consultar el curioso bestiario de métodos evolutivos que están haciendo algunos compañeros.

Estimation Distribution Algorithms (EDA)

Algoritmos de Estimación de Distribuciones

Los Algoritmos de Estimación de Distribuciones (EDA, del inglés Estimation Distribution Algorithms) son algoritmos evolutivos basados en poblaciones al igual que los algoritmos genéticos, en los que la transición de una generación a otra ha sido modificada. En este caso no hay operadores de cruce ni de mutación. En su lugar, la nueva población de individuos se muestrea a partir de una distribución de probabilidad, que se estima a partir de una base de datos formada por individuos de generaciones anteriores. Además, las interrelaciones se expresan de forma implícita en la distribución de probabilidad conjunta asociada a los individuos seleccionados en cada iteración.


Referencias y enlaces
  • http://www.iba.t.u-tokyo.ac.jp/english/EDA.htm
  • http://www.cs.bham.ac.uk/~axk/EC_eda.ppt
  • http://www.sc.ehu.es/ccwbayes/docencia/mmcc/docs/t3edas.pdf
  • http://neo.lcc.uma.es/pdf-charlas/EDA.pdf
  • Algoritmos de Estimación de Distribuciones en Problemas de Optimización Combinatoria. P. Larrañaga, J.A. Lozano y H. Mühlenbein. Inteligencia artificial: Revista Iberoamericana de Inteligencia Artificial, Vol. 7, Nº. 19, 2003 , págs. 149-168
  • Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation (Genetic Algorithms and Evolutionary Computation). P. Larrañaga and J.A. Lozano. 2001, Springer

Evolutionary Algorithms

Algoritmos Evolutivos

Los algoritmos evolutivos (EA, del inglés Evolutionary Algorithm) son técnicas heurísticas avanzadas. Este paradigma, también conocido como computación evolutiva, consiste en la utilización de algoritmos de búsqueda estocástica (probabilística) que se basan en la abstracción de ciertos procesos de la teoría de la evolución darwiniana. Bajo la denominación genérica de EA se agrupa un cierto número de técnicas diferenciadas, las cuales parten todas de la misma idea fundamental, pero que suelen distinguirse tanto por sus características propias como por motivos históricos. Los EA realizan una búsqueda global, ya que trabajan con una población de soluciones candidatas, más que trabajar con una sola solución candidata. Esto, junto con su naturaleza estocástica, reduce la probabilidad de quedarse atascados en óptimos locales e incrementa la probabilidad de encontrar el óptimo global.


Referencias y enlaces
  • http://www.cleveralgorithms.com/nature-inspired/evolution.html
  • http://www.cs.sandia.gov/opt/survey/ea.html
  • http://natcomp.liacs.nl/EA/
  • http://www.geatbx.com/docu/index.html
  • Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. T. Bäck. 1995
  • Evolutionary Algorithms. E. Alba and C. Cotta. Handbook of Bioinspired Algorithms and Applications, S. Olariu, A.Y. Zomaya. (eds.), pp. 3-19, Chapman & Hall/CRC, Boca Ratón FL, 2006

Genetic Algorithms

Algoritmos Genéticos

Los algoritmos genéticos nacieron con el objetivo de imitar los procesos adaptativos de los sistemas naturales mediante el diseño de sistemas artificiales que retengan los mecanismos importantes de dichos sistemas naturales. Los algoritmos genéticos son métodos sistemáticos para la resolución de problemas de búsqueda y optimización que aplican a estos, los mismos principios de la evolución biológica: selección basada en la población, reproducción y mutación.


Referencias y enlaces
  • http://geneura.ugr.es/~jmerelo/ie/ags.htm
  • http://http://geneticprogramming.com/
  • http://www.obitko.com/tutorials/genetic-algorithms/
  • An Introduction to Genetic Algorithms. M. Mitchell. MIT Press. 1998.
  • Genetic Algorithms. C. Reeves. Chapter 3 In: F. Glover and G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 55-82

GRASP

Greedy Randomized Adaptive Search Procedures

GRASP es una metodología multiarranque basada en la construcción y mejora de múltiples soluciones. Su nombre podría traducirse como Procedimiento de Búsqueda Adaptativo Aleatorizado y Voraz. Tienen una componente de aleatoriedad controlada y enmarcada dentro de un proceso constructivo básicamente voraz. GRASP consiste en repetir múltiples veces un esquema de dos fases: construir una solución semi-aleatoria y aplicarle búsqueda local.


Referencias y enlaces
  • http://www.cleveralgorithms.com/nature-inspired/stochastic/grasp.html
  • http://mauricio.resende.info/grasp/index
  • GRASP: Procedimientos de búsquedas miopes aleatorizados y adaptativos, José Luis González Velarde, Mauricio G.C. Resende, Revista Iberoamericana de Inteligencia Artificial, Vol. 7, Nº. 19, 2003.
  • Greedy Randomized Adaptive Search Procedure. M.G.C. Resende and C.S. Ribeiro. Chapter 8. In: F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 221-249.

Iterated Greedy

Construcción iterada voraz

La búsqueda o construcción voraz iterarada (IG, del inglés Iterated Greedy) es un concepto muy sencillo que se fundamenta en generar soluciones a distintos problemas de optimización iterando un proceso de destrucción parcial y reconstrucción voraz sobre una solución de partida. Más detalladamente, a partir de una solución inicial (normalmente construida con una heurística capaz), se destruyen algunos elementos de esta solución para después volverlos a reconstruir, usando también una heurística voraz de alta calidad. La nueva solución se compara con la anterior y se aplica un criterio de aceptación. Una destrucción y reconstrucción completa de la solución en cada iteración tendría muchas similitudes con GRASP mientras que una perturbación en vez de una destrucción-reconstrucción sería similar a ILS. La metodología IG es muy sencilla de implementar una vez se conoce una heurística constructiva capaz y normalmente resulta en algoritmos con muy pocos parámetros, fáciles de extender a otros problemas y con muy buenos rendimientos. Dada su simplicidad, esta metodología se ha inventado y reinventado varias veces por varios autores, con nombres tan dispares como “Ruin and recreate”, "Oscilación estratégica" o “Iterative flattening”. Actualmente IG se ha aplicado con éxito a un gran número de problemas de optimización.


Referencias y enlaces
  • Ruiz, R. and Stutzle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3), 2033-2049.
  • Bouamama, S., Blum, and C., Boukerram, A. (2012). A population-based iterated greedy algorithm for the minimum weight vertex cover problem. Applied Soft Computing Journal, 12(6), 1632-1639.
  • Fanjul, L. and Ruiz, R. (2010). Iterated greedy local search methods for unrelated parallel machine scheduling. European Journal of Operational Research, 207(1), 55-69.
  • García-Martínez, C., Rodríguez, F.J. and Lozano, M. (2014). Tabu-enhanced iterated greedy algorithm: A case study in the quadratic multiple knapsack problem. European Journal of Operational Research, 232(3), 454-463.
  • Lozano, M., Molina, D. and García-Martínez, C. (2011). Iterated greedy for the maximum diversity problem. European Journal of Operational Research, 214(1), 31-38.

Iterated Local Search

Búsqueda local iterativa

La Búsqueda Local Iterativa (ILS) se basa en combinar una fase de perturbación, en la que se genera una nueva solución a partir de la transformación notable de una solución base, con una fase de búsqueda local en la que se intenta mejorar la solución generada mediante pequeños cambios de la misma. Habitualmente, con el fin de escapar de posibles mínimos locales, también se contempla una fase de aceptación mediante la cual se acepta empeorar la solución base. Esta metaheurística destaca por su excelente relación en sencillez de implementación versus calidad de las soluciones obtenidas y velocidad de ejecución. Es además una metaheurística que suele requerir pocos parámetros, y que se puede combinar fácilmente con estrategias como procesos de destrucción-reconstrucción (para la fase de perturbación), sistemas de simulación (SimILS) o aleatorización sesgada (para la fase de reconstrucción o de búsqueda local).


Referencias y enlaces
  • https://en.wikipedia.org/wiki/Iterated_local_search
  • Lourenço H.R., Martin O. and Stützle T. (2010), Iterated Local Search: Framework and Applications. In Handbook of Metaheuristics, 2nd. Edition. Vol.146. M. Gendreau and J.Y. Potvin (eds.), Kluwer Academic Publishers, International Series in Operations Research & Management Science, pp. 363-397.
  • Juan, A.; Pascual, I.; Guimarans, D.; Barrios, B. (2015), Combining Biased Randomization with Iterated Local Search for solving the Multi-Depot Vehicle Routing Problem. Int. Transactions in Operational Research, 22 (4): 647-667, doi: 10.1111/itor.12101.
  • Grasas A., Juan, A.A. and Lourenço H.R. (2016), SimILS: A Simulation-based extension of the Iterated Local Search metaheuristic for Stochastic Combinatorial Optimization, Journal of Simulation 10(1), 69–77 doi:10.1057/jos.2014.25.
  • Dominguez, O.; Juan, A.; Nuez, I.; Ouelhadj, D. (2015), An ILS-Biased Randomization algorithm for the Two-dimensional Loading HFVRP with Sequential Loading and Items Rotation. Journal of the Operational Research Society, 67 (1): 37-53.

Memetic Algorithms

Algoritmos meméticos

Los orígenes de los algoritmos meméticos (MA) se remontan a finales de los años ochenta. La idea básica que sustenta a los MA consiste en combinar conceptos y estrategias de diferentes metaheurísticas para intentar aunar las ventajas de las mismas. Fundamentalmente se basan en mejorar individualmente las soluciones junto con procesos de cooperación y competiciones de tipo poblacional. En este sentido, los MA combinan conceptos de diferentes metaheurísticas, existiendo en particular una muy estrecha relación con el modelo de los algoritmos evolutivos.


Referencias y enlaces
  • http://www.lcc.uma.es/~ccottap/papers/memeticos.pdf
  • http://www.ntu.edu.sg/home/asysong/MC/memetic_algorithm_framework.htm
  • Recent Advances in Memetic Algorithms (Studies in Fuzziness and Soft Computing). W.E. Hart, N. Krasnogor and J.E. Smith.
  • Algoritmos Meméticos (2003-12-16) C. Cotta y E. Alba.

Path Relinking

Rencadenamiento de trayectorias

Path Relinking (PR) fue propuesto originalmente dentro del contexto de la metaheurística Búsqueda Tabú, donde uno de los principales objetivos es realizar un balance entre la búsqueda en intensificación y diversificación. PR se basa en la generación de nuevas soluciones mediante la exploración de trayectorias que conectan soluciones de calidad elevada, iniciando la búsqueda desde una de estas soluciones, llamada solución inicial, y generando un camino en el espacio de vecindario que dirige la búsqueda hacia las otras soluciones, denominadas soluciones guía. Especial atención merece el método híbrido GRASP con PR que ha sido aplicado en numerosos problemas.


Referencias y enlaces
  • http://leeds-faculty.colorado.edu/glover/
  • http://leeds-faculty.colorado.edu/glover/SSandPRFundamentals.pdf
  • Fundamentals of Scatter Search and Path Relinking. F. Glover, M. Laguna and R. Martí. Control and Cybernetics, volume 29, number 3, pp. 653-684, 2000.
  • GRASP and Path Relinking for 2-layer straight line crossing minimization. M. Laguna and R. Martí. INFORMS Journal on Computing, 11, 1, pp. 44-52, 1999.

Scatter Search

Búsqued Dispersa

La Búsqueda Dispersa (SS, del inglés Scatter Search) es un método evolutivo que ha sido aplicado en la resolución de un gran número de problemas de optimización. Los conceptos y principios fundamentales del método, fueron propuestos a comienzo de la década de los setenta, basados en estrategias para combinar reglas de decisión, especialmente en problemas de secuenciación, así como en la combinación de restricciones (como el conocido método de las restricciones subrogadas). Se basa en el principio de que la información sobre la calidad o el atractivo de un conjunto de reglas, restricciones o soluciones puede ser utilizado mediante la combinación de éstas. En concreto, dadas dos soluciones, se puede obtener una nueva mediante su combinación de modo que mejore a las que la originaron. Mantiene un conjunto de soluciones y realiza combinaciones con éstas; las elecciones son sistemáticas y estratégicas y se realizan sobre un conjunto relativamente pequeño de soluciones.


Referencias y enlaces
  • Scatter Search and Path Relinking: Advances and Applications. F. Glover, M. Laguna and R. Martí. Chapter 1: In F. Glover, G.A. Kochenberber, (Eds.). Handbook of Metaheuristics. Kluwer Academics. (2003) 1-35.
  • Scatter Search: Diseño Básico y Estrategias Avanzadas. Revista Iberoamericana de Inteligencia Artificial 19 (2003) 123-130. F. Glover, M. Laguna y R. Martí..
  • Scatter Search. Methodology and Implementations in C. M. Laguna and R. Martí. Kluwer Academic Publishers, Cambridge (2003).

SimHeuristics

Heuristicas y Simulación

Las simheurísticas combinan metaheurísticas con técnicas de simulación para abordar, de forma natural, problemas de optimización en escenarios con incertidumbre. Así, por ejemplo, las simheurísticas permiten resolver problemas en los que la función objetivo incluye variables aleatorias, y también aquellos en los que el modelo matemático contiene restricciones probabilísticas. Habitualmente, la simulación se utiliza no sólo para estimar el valor de una solución generada por la metaheurística en un escenario estocástico, sino también para guiar el proceso de búsqueda de la propia metaheurística. Además, la información que proporciona la simulación permite realizar un análisis de riesgo / fiabilidad de las mejores soluciones estocásticas encontradas. Este análisis es relevante ya que, en escenarios estocásticos, conviene tener información sobre la variabilidad de la solución propuesta.


Referencias y enlaces
  • Grasas, A.; Juan, A.; Ramalhinho, H. (2016): “SimILS: A Simulation-based extension of the Iterated Local Search metaheuristic for Stochastic Combinatorial Optimization”. Journal of Simulation, 10(1): 69-77
  • Juan, A.; Faulin, J.; Grasman, S.; Rabe, M.; Figueira, G. (2015): “A review of Simheuristics: extending metaheuristics to deal with stochastic optimization problems”. Operations Research Perspectives, 2: 62-72, doi:10.1016/j.orp.2015.03.001
  • Juan, A.; Faulin, J.; Jorba, J.; Caceres, J.; Marques, J. (2013): “Using Parallel & Distributed Computing for Solving Real-time Vehicle Routing Problems with Stochastic Demands”. Annals of Operations Research, 207: 43-65
  • Juan, A.; Faulin, J.; Grasman, S.; Riera, D.; Marull, J.; Mendez, C. (2011): “Using Safety Stocks and Simulation to Solve the Vehicle Routing Problem with Stochastic Demands”. Transportation Research Part C, 19: 751-765

Simulated Annealing

Templado Simulado

El Templado o Recocido Simulado es una de las metaheurísticas más clásicas. Su simplicidad y buenos resultados en numerosos problemas, la han convertido en una herramienta muy popular, con cientos de aplicaciones en los más variados campos. Su fundamentación se basa en el trabajo de Metropolis et al. (1953) en el campo de la termodinámica estadística. Metropolis modeló el proceso de recocido simulando los cambios energéticos en un sistema de partículas conforme decrece la temperatura, hasta que converge a un estado estable (congelado). Cualquier implementación de búsqueda local puede convertirse en una implementación SA al elegir elementos del entorno de modo aleatorio, aceptar automáticamente todos los movimientos hacia una mejor solución, y aceptar los movimientos a una solución peor de acuerdo con una probabilidad.


Referencias y enlaces
    Optimization by Simulated Annealing. S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi. Science 220, 671-680, 1983.
  • http://mathworld.wolfram.com/SimulatedAnnealing.html
  • http://sci2s.ugr.es/sites/default/files/files/Teaching/GraduatesCourses/Algoritmica/Tema03-EnfriamientoSimulado-12-13.pdf

Tabu Search

Búsqueda Tabú

La Búsqueda Tabú (TS, del inglés Tabu Search) es un procedimiento metaheurístico cuya característica distintiva es el uso de memoria adaptativa y de estrategias especiales de resolución de problemas. Su filosofía se basa en la explotación de diversas estrategias inteligentes para la resolución de problemas basadas en procedimientos de aprendizaje. El marco de memoria adaptativa de TS explota la historia del proceso de resolución del problema haciendo referencia a cuatro dimensiones principales, consistentes en la propiedad de ser reciente, en frecuencia, en calidad, y en influencia.


Referencias y enlaces
  • http://www.inf.utfsm.cl/~mcriff/IA/tabu-search.html
  • http://www.cse.unt.edu/~garlick/teaching/4310/assign/TS%20-%20Tutorial.pdf
  • Glover F. and Laguna, M. (1997) Tabu Search, Kluwer Academic Publishers.
  • Glover F. and Melián, B. (2003).Búsqueda Tabú. Revista Iberoamericana de Inteligencia Artificial 19, 29-48.
  • http://www.cs.ucla.edu/~rosen/161/TabuSearch.ppt

Variable Neighborhood Search

Búsqueda de Entorno Variable

La Búsqueda de Entorno Variable (VNS, del inglés Variable Neighbourhood Search) es una metaheurística reciente para la resolución de problemas de optimización. VNS está basada en un principio simple: cambiar la estructura de entornos cuando la búsqueda local se estanca en un óptimo local. Se han realizado muchas extensiones de VNS, principalmente para permitir dar solución a problemas de gran tamaño, pero en la mayoría de ellas, se ha hecho un esfuerzo por mantener la simplicidad del esquema básico.


Referencias y enlaces
  • Variable Neighbourhood Search. N.Mladenovic and P. Hansen. Computers and Operations Research, 24, 1097-1100, 1997.
  • Búsqueda por Entornos Variables para Planificación Logística. J.A. Moreno y N. Mladenovic
  • http://webpages.ull.es/users/jamoreno/www/papers/VNS2PL.pdf.
  • http://www.sls-book.net/Slides/sls-ils+vns.pdf