En informática y optimización matemática , una metaheurística es un procedimiento de nivel superior o heurística diseñado para encontrar, generar o seleccionar una heurística ( algoritmo de búsqueda parcial ) que puede proporcionar una solución suficientemente buena para un problema de optimización , especialmente con información incompleta o imperfecta. o capacidad de cálculo limitada. [1] [2] La metaheurística muestra un subconjunto de soluciones que, de otro modo, es demasiado grande para ser enumerado por completo o explorado de otro modo. Las metaheurísticas pueden hacer relativamente pocas suposiciones sobre el problema de optimización que se está resolviendo y, por lo tanto, pueden utilizarse para una variedad de problemas.[3]
En comparación con los algoritmos de optimización y los métodos iterativos , las metaheurísticas no garantizan que se pueda encontrar una solución globalmente óptima en alguna clase de problemas. [3] Muchas metaheurísticas implementan alguna forma de optimización estocástica , por lo que la solución encontrada depende del conjunto de variables aleatorias generadas. [2] En la optimización combinatoria , al buscar en un gran conjunto de soluciones factibles , las metaheurísticas a menudo pueden encontrar buenas soluciones con menos esfuerzo computacional que los algoritmos de optimización, los métodos iterativos o las heurísticas simples. [3] Como tales, son enfoques útiles para problemas de optimización. [2] Se han publicado varios libros y artículos de encuestas sobre el tema. [2] [3] [4] [5] [6]
La mayor parte de la literatura sobre metaheurística es de naturaleza experimental y describe resultados empíricos basados en experimentos informáticos con los algoritmos. Pero también están disponibles algunos resultados teóricos formales, a menudo sobre la convergencia y la posibilidad de encontrar el óptimo global. [3] Se han publicado muchos métodos metaheurísticos con afirmaciones de novedad y eficacia práctica. Si bien el campo también presenta investigaciones de alta calidad, muchas de las publicaciones han sido de mala calidad; los defectos incluyen vaguedad, falta de elaboración conceptual, experimentos deficientes e ignorancia de la literatura previa. [7]
Propiedades
Estas son las propiedades que caracterizan a la mayoría de las metaheurísticas: [3]
- Las metaheurísticas son estrategias que guían el proceso de búsqueda.
- El objetivo es explorar de manera eficiente el espacio de búsqueda para encontrar soluciones casi óptimas.
- Las técnicas que constituyen algoritmos metaheurísticos van desde simples procedimientos de búsqueda local hasta complejos procesos de aprendizaje.
- Los algoritmos metaheurísticos son aproximados y generalmente no deterministas.
- Las metaheurísticas no son específicas de un problema.
Clasificación
Existe una amplia variedad de metaheurísticas [2] y una serie de propiedades con respecto a las que clasificarlas. [3]
Búsqueda local frente a búsqueda global
Un enfoque consiste en caracterizar el tipo de estrategia de búsqueda. [3] Un tipo de estrategia de búsqueda es una mejora de los algoritmos de búsqueda local simples. Un algoritmo de búsqueda local bien conocido es el método de escalada que se utiliza para encontrar óptimos locales. Sin embargo, la escalada no garantiza la búsqueda de soluciones óptimas globales.
Se propusieron muchas ideas metaheurísticas para mejorar la heurística de búsqueda local con el fin de encontrar mejores soluciones. Tales metaheurísticos incluyen recocido simulado , Búsqueda Tabú , iterado de búsqueda local , búsqueda local variables , y GRASP . [3] Estas metaheurísticas pueden clasificarse como metaheurísticas de búsqueda local o global.
Otras metaheurísticas de búsqueda global que no se basan en búsquedas locales suelen ser metaheurísticas basadas en la población. Tales metaheurísticas incluyen optimización de colonias de hormigas , cálculo evolutivo , optimización de enjambres de partículas , algoritmo genético y algoritmo de optimización de ciclistas [9].
Solución única frente a basada en la población
Otra dimensión de clasificación es la solución única frente a las búsquedas basadas en población. [3] [6] Los enfoques de solución única se centran en modificar y mejorar una única solución candidata; Las metaheurísticas de solución única incluyen recocido simulado , búsqueda local iterada , búsqueda de vecindad variable y búsqueda local guiada . [6] Los enfoques basados en la población mantienen y mejoran múltiples soluciones candidatas, a menudo utilizando características de la población para guiar la búsqueda; Las metaheurísticas basadas en poblaciones incluyen computación evolutiva , algoritmos genéticos y optimización de enjambres de partículas . [6] Otra categoría de metaheurísticas es la inteligencia de enjambre, que es un comportamiento colectivo de agentes descentralizados y autoorganizados en una población o enjambre. Optimización de colonias de hormigas , [10] optimización de enjambres de partículas , [6] optimización cognitiva social son ejemplos de esta categoría.
Algoritmos de hibridación y meméticos
Una metaheurística híbrida es aquella que combina una metaheurística con otros enfoques de optimización, como algoritmos de programación matemática , programación de restricciones y aprendizaje automático . Ambos componentes de una metaheurística híbrida pueden ejecutarse simultáneamente e intercambiar información para guiar la búsqueda.
Por otro lado, los algoritmos meméticos [11] representan la sinergia de un enfoque evolutivo o basado en la población con el aprendizaje individual separado o los procedimientos de mejora local para la búsqueda de problemas. Un ejemplo de algoritmo memético es el uso de un algoritmo de búsqueda local en lugar de un operador de mutación básico en los algoritmos evolutivos.
Metaheurísticas paralelas
Una metaheurística paralela es aquella que utiliza las técnicas de programación paralela para ejecutar múltiples búsquedas metaheurísticas en paralelo; estos pueden variar desde esquemas distribuidos simples hasta ejecuciones de búsqueda simultáneas que interactúan para mejorar la solución general.
Metaheurísticas inspiradas en la naturaleza y basadas en metáforas
Un área de investigación muy activa es el diseño de metaheurísticas inspiradas en la naturaleza. Muchas metaheurísticas recientes, especialmente los algoritmos basados en la computación evolutiva, se inspiran en los sistemas naturales. La naturaleza actúa como una fuente de conceptos, mecanismos y principios para el diseño de sistemas informáticos artificiales para hacer frente a problemas computacionales complejos. Dichas metaheurísticas incluyen recocido simulado , algoritmos evolutivos , optimización de colonias de hormigas y optimización de enjambres de partículas . Un gran número de metaheurísticas inspiradas en metáforas más recientes han comenzado a atraer críticas en la comunidad investigadora por ocultar su falta de novedad detrás de una metáfora elaborada. [7]
Metaheurísticas de inspiración antigua
Parece que nos encontramos ante una nueva fuente de inspiración. Esto dará paso a muchos algoritmos inspirados en la antigüedad. Ha habido numerosas limitaciones en la era antigua, pero varias estructuras hechas por el hombre indican que las limitaciones y la falta de instalaciones han llevado a algún tipo de optimización. Una mirada más cercana a estas antiguas reliquias muestra que los métodos, estrategias y tecnologías utilizadas en la antigüedad son mucho más avanzados y optimizados de lo que hubiéramos imaginado. La ideología de inspiración antigua observa y reflexiona sobre las características y busca comprender las formas de gestionar el proyecto en ese momento. [12]
Aplicaciones
Las metaheurísticas se utilizan para la optimización combinatoria en la que se busca una solución óptima en un espacio de búsqueda discreto . Un ejemplo de problema es el problema del viajante de comercio donde el espacio de búsqueda de soluciones candidatas crece más rápido que exponencialmente a medida que aumenta el tamaño del problema, lo que hace inviable una búsqueda exhaustiva de la solución óptima. Además, los problemas combinatorios multidimensionales, incluyendo la mayoría de los problemas de diseño en ingeniería [13] [14] [15] como la búsqueda de formas y la búsqueda de comportamientos, sufren la maldición de la dimensionalidad , que también los hace inviables para una búsqueda exhaustiva o métodos analíticos . Las metaheurísticas también se utilizan ampliamente para la programación del taller y los problemas de selección de trabajos. [ cita requerida ] Las metaheurísticas populares para problemas combinatorios incluyen el recocido simulado de Kirkpatrick et al., [16] algoritmos genéticos de Holland et al., [17] búsqueda de dispersión [18] y búsqueda tabú [19] de Glover. La revisión de la literatura sobre optimización metaheurística, [20] sugirió que fue Fred Glover quien acuñó la palabra metaheurística. [21]
Marcos de optimización metaheurísticos (MOF)
Un MOF se puede definir como '' un conjunto de herramientas de software que proporcionan una implementación correcta y reutilizable de un conjunto de metaheurísticas, y los mecanismos básicos para acelerar la implementación de las heurísticas subordinadas de su socio (posiblemente incluyendo codificaciones de soluciones y operadores específicos de la técnica) , que son necesarios para resolver una instancia de problema en particular utilizando las técnicas proporcionadas ''. [22]
Hay muchas herramientas de optimización candidatas que pueden considerarse como un MOF de características variables: Comet, EvA2, evolvica, Evolutionary :: Algorithm, GAPlayground, jaga, JCLEC, JGAP, jMetal, n-genes, Open Beagle, Opt4j, ParadisEO / EO , Pisa, Relojero, FOM, Hypercube, HotFrame, Templar, EasyLocal, iOpt, OptQuest, JDEAL, Optimization Algorithm Toolkit, HeuristicLab, MAFRA, Localizer, GALIB, DREAM, Discropt, MALLBA, MAGMA, UOF [22] y OptaPlanner.
Contribuciones
Existen muchas metaheurísticas diferentes y continuamente se proponen nuevas variantes. Algunas de las contribuciones más significativas al campo son:
- 1952: Robbins y Monro trabajan en métodos de optimización estocástica. [23]
- 1954: Barricelli realiza las primeras simulaciones del proceso de evolución y las utiliza en problemas generales de optimización. [24]
- 1963: Rastrigin propone una búsqueda aleatoria . [25]
- 1965: Matyas propone la optimización aleatoria . [26]
- 1965: Nelder y Mead proponen una heurística simplex , que Powell demostró que converge en puntos no estacionarios en algunos problemas. [27]
- 1965: Ingo Rechenberg descubre el primer algoritmo de Estrategias de Evolución . [28]
- 1966: Fogel y col. proponer programación evolutiva . [29]
- 1970: Hastings propone el algoritmo Metropolis-Hastings . [30]
- 1970: Cavicchio propone la adaptación de los parámetros de control para un optimizador. [31]
- 1970: Kernighan y Lin proponen un método de partición de gráficos, relacionado con la búsqueda de profundidad variable y la búsqueda basada en prohibiciones (tabú) . [32]
- 1975: Holanda propone el algoritmo genético . [17]
- 1977: Glover propone la búsqueda por dispersión. [18]
- 1978: Mercer y Sampson proponen un metaplan para ajustar los parámetros de un optimizador mediante el uso de otro optimizador. [33]
- 1980: Smith describe la programación genética . [34]
- 1983: Kirkpatrick y col. proponer recocido simulado . [dieciséis]
- 1986: Glover propone la búsqueda tabú , primera mención del término metaheurística . [19]
- 1989: Moscato propone algoritmos meméticos . [11]
- 1990: Moscato y Fontanari, [35] y Dueck y Scheuer, [36] propusieron independientemente una regla de actualización determinista para el recocido simulado que aceleró la búsqueda. Esto llevó al umbral de aceptación de la metaheurística.
- 1992: Dorigo introduce la optimización de colonias de hormigas en su tesis doctoral. [10]
- 1995: Wolpert y Macready prueban los teoremas de no almuerzo gratis . [37] [38] [39] [40]
Ver también
- Búsqueda estocástica
- Meta-optimización
- Matemáticas
- Hiperheurística
- Inteligencia de enjambre
- Algoritmos genéticos
- Recocido simulado
- Modelado de fuerza laboral
Referencias
- ^ R. Balamurugan; AM Natarajan; K. Premalatha (2015). "Optimización de agujero negro de masa estelar para datos de expresión génica de microarrays biclustering". Inteligencia artificial aplicada . 29 (4): 353–381. doi : 10.1080 / 08839514.2015.1016391 . S2CID 44624424 .
- ^ a b c d e Bianchi, Leonora; Marco Dorigo; Luca Maria Gambardella; Walter J. Gutjahr (2009). "Una encuesta sobre metaheurísticas para la optimización combinatoria estocástica" (PDF) . Computación natural . 8 (2): 239–287. doi : 10.1007 / s11047-008-9098-4 . S2CID 9141490 .
- ^ a b c d e f g h yo j Blum, C .; Roli, A. (2003). "Metaheurística en optimización combinatoria: descripción general y comparación conceptual" . 35 (3). Encuestas de computación de ACM: 268–308. Cite journal requiere
|journal=
( ayuda ) - ^ Goldberg, DE (1989). Algoritmos genéticos en búsqueda, optimización y aprendizaje automático . Editores académicos de Kluwer. ISBN 978-0-201-15767-3.
- ^ Glover, F .; Kochenberger, GA (2003). Manual de metaheurística . 57 . Springer, Serie Internacional en Investigación de Operaciones y Ciencias de la Gestión. ISBN 978-1-4020-7263-5.
- ^ a b c d e Talbi, EG. (2009). Metaheurísticas: desde el diseño hasta la implementación . Wiley. ISBN 978-0-470-27858-1.
- ^ a b Sörensen, Kenneth (2015). "Metaheurística: la metáfora expuesta" (PDF) . Transacciones internacionales en investigación operativa . 22 : 3-18. CiteSeerX 10.1.1.470.3422 . doi : 10.1111 / itor.12001 . Archivado desde el original (PDF) en 2013-11-02.
- ^ Clasificación de metaheurísticas
- ^ D, Binu (2019). "RideNN: una nueva red neuronal basada en algoritmos de optimización de piloto para el diagnóstico de fallas en circuitos analógicos" . Transacciones IEEE sobre instrumentación y medición . 68 (1): 2-26. doi : 10.1109 / TIM.2018.2836058 . S2CID 54459927 .
- ^ a b M. Dorigo, Optimización, aprendizaje y algoritmos naturales , tesis doctoral, Politecnico di Milano, Italie, 1992.
- ^ a b Moscato, P. (1989). "Sobre evolución, búsqueda, optimización, algoritmos genéticos y artes marciales: hacia algoritmos meméticos" . Programa de Computación Concurrente de Caltech (informe 826).
- ^ "Algoritmo de construcción de pirámides de Giza (GPC)" . www.mathworks.com . Consultado el 28 de septiembre de 2020 .
- ^ Tomoiagă B, Chindriş M, Sumper A, Sudria-Andreu A, Villafafila-Robles R. Reconfiguración óptima de Pareto de sistemas de distribución de energía mediante un algoritmo genético basado en NSGA-II. Energías. 2013; 6 (3): 1439–1455.
- ^ Ganesan, T .; Elamvazuthi, I .; Ku Shaari, Ku Zilati; Vasant, P. (1 de marzo de 2013). "Inteligencia de enjambre y algoritmo de búsqueda gravitacional para la optimización multiobjetivo de la producción de gas de síntesis". Energía aplicada . 103 : 368–374. doi : 10.1016 / j.apenergy.2012.09.059 .
- ^ Ganesan, T .; Elamvazuthi, I .; Vasant, P. (1 de noviembre de 2011). Método evolutivo de intersección de límites normales (ENBI) para la optimización multiobjetivo del sistema de moldes de arena verde . 2011 IEEE International Conference on Control System, Computing and Engineering (ICCSCE) . págs. 86–91. doi : 10.1109 / ICCSCE.2011.6190501 . ISBN 978-1-4577-1642-3. S2CID 698459 .
- ^ a b Kirkpatrick, S .; Gelatt Jr., CD; Vecchi, MP (1983). "Optimización por recocido simulado". Ciencia . 220 (4598): 671–680. Código Bibliográfico : 1983Sci ... 220..671K . CiteSeerX 10.1.1.123.7607 . doi : 10.1126 / science.220.4598.671 . PMID 17813860 . S2CID 205939 .
- ^ a b Holanda, JH (1975). Adaptación en sistemas naturales y artificiales . Prensa de la Universidad de Michigan. ISBN 978-0-262-08213-6.
- ^ a b Glover, Fred (1977). "Heurística para la programación de enteros mediante restricciones sustitutas". Ciencias de la decisión . 8 (1): 156–166. CiteSeerX 10.1.1.302.4071 . doi : 10.1111 / j.1540-5915.1977.tb01074.x .
- ^ a b Glover, F. (1986). "Caminos futuros para la programación de enteros y vínculos con la inteligencia artificial". Investigación de Computación y Operaciones . 13 (5): 533–549. doi : 10.1016 / 0305-0548 (86) 90048-1 .
- ^ XS Yang, Optimización metaheurística, Scholarpedia, 6 (8): 11472 (2011).
- ^ Glover F., (1986). Caminos futuros para la programación de enteros y enlaces a la inteligencia artificial , Computers and Operations Research, 13, 533–549 (1986).
- ^ a b Moscato, P. (2012). "Marcos de optimización metaheurística una encuesta y evaluación comparativa". Soft Comput (2012) 16, 527–561 . 16 (3): 527–561. doi : 10.1007 / s00500-011-0754-8 . hdl : 11441/24597 . S2CID 1497912 .
- ^ Robbins, H .; Monro, S. (1951). "Un método de aproximación estocástico" (PDF) . Anales de estadística matemática . 22 (3): 400–407. doi : 10.1214 / aoms / 1177729586 .
- ^ Barricelli, NA (1954). "Esempi numerici di processi di evoluzione". Methodos : 45–68.
- ^ Rastrigin, LA (1963). "La convergencia del método de búsqueda aleatoria en el control extremo de un sistema de muchos parámetros". Automatización y Telemando . 24 (10): 1337-1342.
- ^ Matyas, J. (1965). "Optimización aleatoria" . Automatización y Telemando . 26 (2): 246-253.
- ^ Nelder, JA; Mead, R. (1965). "Un método simplex para la minimización de funciones". Revista informática . 7 (4): 308–313. doi : 10.1093 / comjnl / 7.4.308 . S2CID 2208295 .
- ^ Rechenberg, Ingo (1965). "Ruta de solución cibernética de un problema experimental". Establecimiento de aviones reales, traducción de bibliotecas .
- ^ Fogel, L .; Owens, AJ; Walsh, MJ (1966). Inteligencia artificial a través de la evolución simulada . Wiley. ISBN 978-0-471-26516-0.
- ^ Hastings, WK (1970). "Métodos de muestreo de Monte Carlo utilizando cadenas de Markov y sus aplicaciones". Biometrika . 57 (1): 97–109. Código bibliográfico : 1970Bimka..57 ... 97H . doi : 10.1093 / biomet / 57.1.97 . S2CID 21204149 .
- ^ Cavicchio, DJ (1970). "Búsqueda adaptativa mediante evolución simulada". Informe técnico . Universidad de Michigan, Departamento de Ciencias de la Computación y la Comunicación. hdl : 2027,42 / 4042 .
- ^ Kernighan, BW; Lin, S. (1970). "Un procedimiento heurístico eficiente para particionar gráficos". Revista técnica de Bell System . 49 (2): 291-307. doi : 10.1002 / j.1538-7305.1970.tb01770.x .
- ^ Mercer, RE; Sampson, JR (1978). "Búsqueda adaptativa mediante un metaplan reproductivo". Kybernetes . 7 (3): 215-228. doi : 10.1108 / eb005486 .
- ^ Smith, SF (1980). Un sistema de aprendizaje basado en algoritmos adaptativos genéticos (tesis doctoral). Universidad de Pittsburgh.
- ^ Moscato, P .; Fontanari, JF (1990), "Actualización estocástica versus determinista en recocido simulado", Physics Letters A , 146 (4): 204-208, Bibcode : 1990PhLA..146..204M , doi : 10.1016 / 0375-9601 (90) 90166-L
- ^ Dueck, G .; Scheuer, T. (1990), "Aceptación de umbral: un algoritmo de optimización de propósito general que parece superior al recocido simulado", Journal of Computational Physics , 90 (1): 161-175, Bibcode : 1990JCoPh..90..161D , doi : 10.1016 / 0021-9991 (90) 90201-B , ISSN 0021-9991
- ^ Wolpert, DH; Macready, WG (1995). "No hay teoremas de almuerzo gratis para la búsqueda". Informe técnico SFI-TR-95-02-010 . Instituto Santa Fe. S2CID 12890367 .
- ^ Igel, Christian, Toussaint, Marc (junio de 2003). "En clases de funciones para las que se mantienen los resultados de No Free Lunch" Cartas de procesamiento de información . 86 (6): 317–321. arXiv : cs / 0108011 . doi : 10.1016 / S0020-0190 (03) 00222-9 . ISSN 0020-0190 . S2CID 147624 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Auger, Anne, Teytaud, Olivier (2010). "Los almuerzos continuos son gratuitos más el diseño de algoritmos de optimización óptima". Algoritmica . 57 (1): 121-146. CiteSeerX 10.1.1.186.6007 . doi : 10.1007 / s00453-008-9244-5 . ISSN 0178-4617 . S2CID 1989533 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Stefan Droste; Thomas Jansen; Ingo Wegener (2002). "Optimización con heurísticas de búsqueda aleatorias: el teorema (A) de la NFL, escenarios realistas y funciones difíciles". Informática Teórica . 287 (1): 131-144. CiteSeerX 10.1.1.35.5850 . doi : 10.1016 / s0304-3975 (02) 00094-4 .
Otras lecturas
- Sörensen, Kenneth; Sevaux, Marc; Glover, Fred (16 de enero de 2017). "Una historia de la metaheurística" (PDF) . En Martí, Rafael; Panos, Pardalos; Resende, Mauricio (eds.). Manual de heurística . Saltador. ISBN 978-3-319-07123-7.
enlaces externos
- Fred Glover y Kenneth Sörensen (ed.). "Metaheurística" . Scholarpedia .
- Foro UE / ME para investigadores en el campo.