En la investigación de operaciones y ciencias de la computación , un algoritmo memético (MA) es una extensión del algoritmo genético tradicional . Utiliza una técnica de búsqueda local para reducir la probabilidad de una convergencia prematura. [1]
Los algoritmos meméticos representan una de las áreas de investigación de reciente crecimiento en computación evolutiva . El término MA se usa ahora ampliamente como una 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. Muy a menudo, los MA también se denominan en la literatura algoritmos evolutivos baldwinianos (EA), EA lamarckianos, algoritmos culturales o búsqueda local genética.
Introducción
Inspirado tanto por los principios darwinianos de la evolución natural como por la noción de meme de Dawkins , el término algoritmo memético (MA) fue introducido por Pablo Moscato en su informe técnico [2] en 1989 donde veía MA como algo cercano a una forma de población. algoritmo genético híbrido (GA) basado en un procedimiento de aprendizaje individual capaz de realizar refinamientos locales. Los paralelos metafóricos, por un lado, con la evolución darwiniana y, por otro lado, entre memes y heurísticas específicas de dominio (búsqueda local) se capturan dentro de algoritmos meméticos, lo que genera una metodología que equilibra bien entre generalidad y especificidad del problema. Esta naturaleza de dos etapas los convierte en un caso especial de evolución de dos fases .
En un contexto más diverso, los algoritmos meméticos ahora se utilizan con varios nombres, incluidos algoritmos evolutivos híbridos, algoritmos evolutivos baldwinianos, algoritmos evolutivos lamarckianos, algoritmos culturales o búsqueda local genética. En el contexto de la optimización compleja, se han reportado muchas instancias diferentes de algoritmos meméticos en una amplia gama de dominios de aplicación , en general, convergiendo hacia soluciones de alta calidad de manera más eficiente que sus contrapartes evolutivas convencionales. [3]
En general, el uso de las ideas de la memética dentro de un marco computacional se denomina computación memética o computación memética (MC). [4] [5] Con MC, los rasgos del darwinismo universal se capturan de manera más apropiada. Visto desde esta perspectiva, MA es una noción más restringida de MC. Más específicamente, MA cubre un área de MC, en particular, se ocupa de áreas de algoritmos evolutivos que se casan con otras técnicas de refinamiento deterministas para resolver problemas de optimización. MC amplía la noción de memes para cubrir entidades conceptuales de procedimientos o representaciones mejorados por el conocimiento.
El desarrollo de MA
1ra generación
La primera generación de MA se refiere a algoritmos híbridos , un matrimonio entre una búsqueda global basada en la población (a menudo en forma de algoritmo evolutivo) junto con una etapa evolutiva cultural. Esta primera generación de MA, aunque abarca características de la evolución cultural (en forma de refinamiento local) en el ciclo de búsqueda, puede no calificar como un verdadero sistema en evolución de acuerdo con el darwinismo universal , ya que todos los principios básicos de la transmisión heredada / memética, la variación , y falta la selección. Esto sugiere por qué el término MA suscitó críticas y controversias entre los investigadores cuando se introdujo por primera vez. [2]
- Pseudocódigo
Procedimiento Inicializar algoritmo memético : Genere una población inicial; mientras no se satisfagan las condiciones de detención , evalúe a todos los individuos de la población. Desarrolle una nueva población utilizando operadores de búsqueda estocásticos. Seleccione el subconjunto de individuos, , que debe someterse al procedimiento de mejora individual. para cada individuo en no Realizar el aprendizaje individual utilizando meme (s) con la frecuencia o probabilidad de , por un período de. Continúe con el aprendizaje lamarckiano o baldwiniano. fin por fin mientras
2da generación
Los MA multimeme, [6] hiper-heurísticos [7] [8] y meta-Lamarckianos [9] se conocen como MA de segunda generación que exhiben los principios de transmisión memética y selección en su diseño. En Multi-meme MA, el material memético se codifica como parte del genotipo . Posteriormente, el meme decodificado de cada cromosoma / individuo respectivo se usa para realizar un refinamiento local. El material memético se transmite luego a través de un mecanismo de herencia simple de padres a hijos. Por otro lado, en la MA hiperheurística y metalamarckiana, el grupo de memes candidatos considerados competirá, en función de sus méritos pasados, para generar mejoras locales a través de un mecanismo de recompensa, decidiendo qué meme se seleccionará para proceder en el futuro local. refinamientos. Los memes con una recompensa más alta tienen una mayor probabilidad de ser replicados o copiados. Para una revisión sobre MA de segunda generación; es decir, MA considerando múltiples métodos de aprendizaje individuales dentro de un sistema evolutivo, se remite al lector. [10]
Tercera generación
La coevolución [11] y las MA autogeneradoras [12] pueden considerarse como MA de tercera generación cuando se han considerado los tres principios que satisfacen las definiciones de un sistema evolutivo básico. A diferencia del MA de segunda generación, que asume que los memes que se utilizarán son conocidos a priori, el MA de tercera generación utiliza una búsqueda local basada en reglas para complementar las soluciones candidatas dentro del sistema evolutivo, capturando así características o patrones que se repiten regularmente en el espacio del problema.
Algunas notas de diseño
La frecuencia y la intensidad del aprendizaje individual definen directamente el grado de evolución (exploración) frente al aprendizaje individual (explotación) en la búsqueda de MA, para un presupuesto computacional limitado fijo dado. Claramente, un aprendizaje individual más intenso proporciona una mayor posibilidad de convergencia con los óptimos locales, pero limita la cantidad de evolución que se puede gastar sin incurrir en recursos computacionales excesivos. Por lo tanto, se debe tener cuidado al establecer estos dos parámetros para equilibrar el presupuesto computacional disponible para lograr el máximo rendimiento de búsqueda. Cuando solo una parte de los individuos de la población se somete a aprendizaje, se debe considerar la cuestión de qué subconjunto de individuos mejorar para maximizar la utilidad de la búsqueda de MA. Por último, pero no menos importante, el procedimiento / meme de aprendizaje individual utilizado también favorece una estructura de vecindario diferente, de ahí la necesidad de decidir qué meme o memes usar para un problema de optimización dado.
¿Con qué frecuencia se debe aplicar el aprendizaje individual?
Una de las primeras cuestiones pertinentes al diseño de algoritmos meméticos es considerar con qué frecuencia se debe aplicar el aprendizaje individual; es decir, frecuencia de aprendizaje individual. En un caso, [13] se consideró el efecto de la frecuencia de aprendizaje individual sobre el rendimiento de la búsqueda de MA donde se investigaron varias configuraciones de la frecuencia de aprendizaje individual en diferentes etapas de la búsqueda de MA. A la inversa, se demostró en otro lugar [14] que puede ser útil aplicar el aprendizaje individual a cada individuo si la complejidad computacional del aprendizaje individual es relativamente baja.
¿En qué soluciones se debe utilizar el aprendizaje individual?
Sobre el tema de la selección de individuos apropiados entre la población de EA que deben someterse al aprendizaje individual, se estudiaron estrategias basadas en la aptitud y en la distribución para adaptar la probabilidad de aplicar el aprendizaje individual en la población de cromosomas en problemas de búsqueda paramétrica continua con Land [15]. extender el trabajo a problemas de optimización combinatoria . Bambha y col. introdujo una técnica de calentamiento simulado para integrar sistemáticamente el aprendizaje individual parametrizado en algoritmos evolutivos para lograr la máxima calidad de la solución. [dieciséis]
¿Cuánto tiempo se debe ejecutar el aprendizaje individual?
Intensidad de aprendizaje individual, , es la cantidad de presupuesto computacional asignado a una iteración de aprendizaje individual; es decir, el presupuesto computacional máximo permitido para que el aprendizaje individual gaste en mejorar una única solución.
¿Qué método de aprendizaje individual o meme debería usarse para un problema o individuo en particular?
En el contexto de la optimización continua, el aprendizaje individual existe en forma de heurística local o métodos convencionales de enumeración exacta. [17] Ejemplos de estrategias de aprendizaje individual incluyen escalada, método Simplex, método Newton / Quasi-Newton, métodos de puntos interiores, método de gradiente conjugado, búsqueda de líneas y otras heurísticas locales. Tenga en cuenta que la mayoría de los métodos de aprendizaje individuales comunes son deterministas.
En la optimización combinatoria, por otro lado, los métodos de aprendizaje individuales existen comúnmente en forma de heurísticas (que pueden ser deterministas o estocásticas) que se adaptan a un problema de interés específico. Los procedimientos y esquemas heurísticos típicos incluyen el intercambio de genes k, el intercambio de bordes, la primera mejora y muchos otros.
Aplicaciones
Los algoritmos meméticos se han aplicado con éxito a una multitud de problemas del mundo real. Aunque muchas personas emplean técnicas estrechamente relacionadas con los algoritmos meméticos, también se emplean nombres alternativos como algoritmos genéticos híbridos . Además, muchas personas llaman a sus técnicas meméticas algoritmos genéticos . [ cita requerida ]
Los investigadores han utilizado algoritmos meméticos para abordar muchos problemas NP clásicos . Por citar algunos de ellos: la partición gráfico , mochila multidimensional , problema del vendedor ambulante , problema de asignación cuadrática , conjunto problema de cobertura , coloración mínima gráfico , max problema conjunto independiente , los problemas de acumulación bin , y problema de asignación generalizada .
Las aplicaciones más recientes incluyen (pero no se limitan a) análisis de negocios y ciencia de datos , [3] entrenamiento de redes neuronales artificiales , [18] reconocimiento de patrones , [19] planificación de movimiento robótico , [20] orientación del haz , [21] diseño de circuitos. , [22] restauración del servicio eléctrico, [23] sistemas médicos expertos , [24] programación de una sola máquina , [25] programación automática de horarios (en particular, el horario de la NHL ), [26] programación de la mano de obra , [27] optimización de la lista de enfermeras , [28] asignación de procesadores , [29] programación de mantenimiento (por ejemplo, de una red de distribución eléctrica), [30] problema de mochila multidimensional, [31] diseño de VLSI , [32] agrupación de perfiles de expresión génica , [33] característica / gen selección, [34] [35] , determinación de parámetros para inyección de fallas de hardware, [36] y selección de características de múltiples clases y múltiples objetivos . [37] [38]
Actividades recientes en algoritmos meméticos
- Taller IEEE sobre algoritmos meméticos (WOMA 2009). Presidentes del programa: Jim Smith, Universidad del Oeste de Inglaterra, Reino Unido; Yew-Soon Ong, Universidad Tecnológica de Nanyang, Singapur; Gustafson Steven, Universidad de Nottingham; REINO UNIDO; Meng Hiot Lim, Universidad Tecnológica de Nanyang, Singapur; Natalio Krasnogor, Universidad de Nottingham, Reino Unido
- Memetic Computing Journal , el primer número apareció en enero de 2009.
- Congreso Mundial de Inteligencia Computacional del IEEE 2008 (WCCI 2008) , Hong Kong, Sesión especial sobre algoritmos meméticos .
- Número especial sobre 'Tendencias emergentes en Soft Computing - Algoritmo memético' , Soft Computing Journal, Completado y en prensa, 2008.
- Grupo de Trabajo de Tecnologías Emergentes de la Sociedad de Inteligencia Computacional IEEE sobre Computación Memética
- Congreso IEEE sobre Computación Evolutiva (CEC 2007) , Singapur, Sesión especial sobre algoritmos meméticos .
- 'Computación memética' de los Indicadores de ciencia esencial de Thomson Scientific como un área de investigación de frente emergente.
- Número especial sobre algoritmos meméticos , transacciones IEEE sobre sistemas, hombre y cibernética - Parte B: Cibernética, vol. 37, No. 1, febrero de 2007.
- Avances recientes en algoritmos meméticos , serie: Estudios en borrosidad y computación blanda, vol. 166, ISBN 978-3-540-22904-9 , 2005.
- Número especial sobre algoritmos meméticos , Computación evolutiva, otoño de 2004, vol. 12, núm. 3: v-vi.
Referencias
- ^ Poonam Garg (abril de 2009). "Una comparación entre el algoritmo memético y el algoritmo genético para el criptoanálisis del algoritmo estándar de cifrado de datos simplificado". Revista internacional de seguridad de redes y sus aplicaciones (IJNSA) . 1 (1). arXiv : 1004.0574 . Código Bibliográfico : 2010arXiv1004.0574G .
- ^ 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).
- ^ a b Moscato, P .; Mathieson, L. (2019). "Algoritmos meméticos para análisis de negocios y ciencia de datos: una breve encuesta". Analítica empresarial y del consumidor: nuevas ideas . Springer . págs. 545–608. doi : 10.1007 / 978-3-030-06222-4_13 . ISBN 978-3-030-06221-7.
- ^ Chen, XS; Ong, YS; Lim, MH; Tan, KC (2011). "Una encuesta multifacética sobre computación memética". Transacciones IEEE sobre computación evolutiva . 15 (5): 591–607. doi : 10.1109 / tevc.2011.2132725 .
- ^ Chen, XS; Ong, YS; Lim, MH (2010). "Frontera de investigación: computación memética - pasado, presente y futuro". Revista IEEE Computational Intelligence . 5 (2): 24–36. doi : 10.1109 / mci.2010.936309 .
- ^ Krasnogor N. (1999). "Coevolución de genes y memes en algoritmos meméticos". Taller para estudiantes de posgrado : 371.
- ^ Kendall G. y Soubeiga E. y Cowling P. Función de elección e hiperheurística aleatoria (PDF) . 4ª Conferencia de Asia y el Pacífico sobre evolución y aprendizaje simulados. SEAL 2002. págs. 667–671.
- ^ Burke EK; Gendreau M .; Hyde M .; Kendall G .; Ochoa G .; Ouml; zcan E .; Qu R. (2013). "Hiperheurística: un estudio del estado del arte". Revista de la Sociedad de Investigación Operativa . 64 (12): 1695-1724. CiteSeerX 10.1.1.384.9743 . doi : 10.1057 / jors.2013.71 .
- ^ Ong YS y Keane AJ (2004). "Aprendizaje metalamarckiano en algoritmos meméticos" (PDF) . Transacciones IEEE sobre computación evolutiva . 8 (2): 99-110. doi : 10.1109 / TEVC.2003.819944 .
- ^ Ong YS y Lim MH y Zhu N. y Wong KW (2006). "Clasificación de algoritmos meméticos adaptativos: un estudio comparativo" (PDF) . Transacciones IEEE sobre sistemas, hombre y cibernética - Parte B: Cibernética . 36 (1): 141-152. doi : 10.1109 / TSMCB.2005.856143 . PMID 16468573 .
- ^ Smith JE (2007). "Algoritmos meméticos coevolutivos: una revisión y un informe de progreso" (PDF) . Transacciones IEEE sobre sistemas, hombre y cibernética - Parte B: Cibernética . 37 (1): 6–17. doi : 10.1109 / TSMCB.2006.883273 . PMID 17278554 .
- ^ Krasnogor N. y Gustafson S. (2002). "Hacia algoritmos meméticos verdaderamente" meméticos ": discusión y prueba de conceptos". Avances en la computación inspirada en la naturaleza: los talleres de PPSN VII. PEDAL (Laboratorio de Arquitecturas Distribuidas y Emergentes Paralelas). Universidad de Reading .
- ^ Hart WE (1994). "Optimización Global Adaptativa con Búsqueda Local". Universidad de California. CiteSeerX 10.1.1.473.1370 . Cite journal requiere
|journal=
( ayuda ) - ^ Ku KWC y Mak MW y Siu WC (2000). "Un estudio de la evolución lamarckiana de redes neuronales recurrentes". Transacciones IEEE sobre computación evolutiva . 4 (1): 31–42. doi : 10.1109 / 4235.843493 . hdl : 10397/289 .
- ^ Land MWS (1998). "Algoritmos evolutivos con búsqueda local para optimización combinatoria". UNIVERSIDAD DE CALIFORNIA. CiteSeerX 10.1.1.55.8986 . Cite journal requiere
|journal=
( ayuda ) - ^ Bambha NK y Bhattacharyya SS y Teich J. y Zitzler E. (2004). "Integración sistemática de búsqueda local parametrizada en algoritmos evolutivos". Transacciones IEEE sobre computación evolutiva . 8 (2): 137-155. doi : 10.1109 / TEVC.2004.823471 .
- ^ Schwefel HP (1995). Evolución y búsqueda óptima . Wiley Nueva York.
- ^ Ichimura, T .; Kuriyama, Y. (1998). Aprendizaje de redes neuronales con GA híbrido paralelo utilizando una función de camino real . Conferencia conjunta internacional IEEE sobre redes neuronales. 2 . Nueva York, NY. págs. 1131-1136. doi : 10.1109 / IJCNN.1998.685931 .
- ^ Aguilar, J .; Colmenares, A. (1998). "Resolución de problemas de reconocimiento de patrones utilizando un algoritmo de aprendizaje de red neuronal aleatoria / genética híbrida". Análisis de patrones y aplicaciones . 1 (1): 52–61. doi : 10.1007 / BF01238026 .
- ^ Ridao, M .; Riquelme, J .; Camacho, E .; Toro, M. (1998). Un algoritmo de búsqueda local y evolutivo para planificar el movimiento de dos manipuladores . Apuntes de conferencias en informática. 1416 . Springer-Verlag. págs. 105-114. CiteSeerX 10.1.1.324.2668 . doi : 10.1007 / 3-540-64574-8_396 . ISBN 978-3-540-64574-0.
- ^ Haas, O .; Burnham, K .; Mills, J. (1998). "Optimización de la orientación del haz en radioterapia mediante geometría plana". Física en Medicina y Biología . 43 (8): 2179–2193. Código Bibliográfico : 1998PMB .... 43.2179H . doi : 10.1088 / 0031-9155 / 43/8/013 . PMID 9725597 .
- ^ Harris, S .; Ifeachor, E. (1998). "Diseño automático de filtros de muestreo de frecuencia mediante técnicas de algoritmos genéticos híbridos". Transacciones IEEE sobre procesamiento de señales . 46 (12): 3304–3314. Código Bibliográfico : 1998ITSP ... 46.3304H . doi : 10.1109 / 78.735305 .
- ^ Augugliaro, A .; Dusonchet, L .; Riva-Sanseverino, E. (1998). "Restauración de servicios en redes de distribución compensada mediante algoritmo genético híbrido". Investigación de sistemas de energía eléctrica . 46 (1): 59–66. doi : 10.1016 / S0378-7796 (98) 00025-X .
- ^ Wehrens, R .; Lucasius, C .; Buydens, L .; Kateman, G. (1993). "HIPS, un sistema experto híbrido autoadaptable para la interpretación del espectro de resonancia magnética nuclear utilizando algoritmos genéticos". Analytica Chimica Acta . 277 (2): 313–324. doi : 10.1016 / 0003-2670 (93) 80444-P . hdl : 2066/112321 .
- ^ França, P .; Mendes, A .; Moscato, P. (1999). Algoritmos Memetic para minimizar la tardanza en una sola máquina con tiempos de preparación dependientes de la secuencia (PDF) . Actas de la 5ª Conferencia Internacional del Instituto de Ciencias de la Decisión. Atenas, Grecia. págs. 1708-1710.
- ^ Costa, D. (1995). "Un algoritmo de búsqueda tabú evolutivo y el problema de programación NHL". Infor 33 : 161-178.
- ^ Aickelin, U. (1998). Lista de enfermeras con algoritmos genéticos . Actas de la conferencia de investigación operativa para jóvenes de 1998. Guildford, Reino Unido. arXiv : 1004.2870 .
- ^ Ozcan, E. (2007). "Memes, autogeneración y nómina de enfermeras". Práctica y teoría de la programación automatizada VI . Apuntes de conferencias en informática. 3867 . Springer-Verlag. págs. 85-104. doi : 10.1007 / 978-3-540-77345-0_6 . ISBN 978-3-540-77344-3.
- ^ Ozcan, E .; Onbasioglu, E. (2007). "Algoritmos meméticos para la optimización de código paralelo". Revista Internacional de Programación Paralela . 35 (1): 33–61. doi : 10.1007 / s10766-006-0026-x .
- ^ Burke, E .; Smith, A. (1999). "Un algoritmo memético para programar el mantenimiento planificado de la red nacional". Revista de algoritmos experimentales . 4 (4): 1–13. doi : 10.1145 / 347792.347801 .
- ^ Ozcan, E .; Basaran, C. (2009). "Un estudio de caso de algoritmos meméticos para la optimización de restricciones". Soft Computing: una fusión de fundamentos, metodologías y aplicaciones . 13 (8–9): 871–882. CiteSeerX 10.1.1.368.7327 . doi : 10.1007 / s00500-008-0354-4 .
- ^ Areibi, S., Yang, Z. (2004). "Algoritmos meméticos efectivos para la automatización del diseño VLSI = algoritmos genéticos + búsqueda local + agrupamiento multinivel". Computación evolutiva . 12 (3): 327–353. doi : 10.1162 / 1063656041774947 . PMID 15355604 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Merz, P .; Zell, A. (2002). "Agrupación de perfiles de expresión génica con algoritmos meméticos". Resolución de problemas paralelos desde la naturaleza - PPSN VII . Apuntes de conferencias en informática. 2439 . Springer . págs. 811–820. doi : 10.1007 / 3-540-45712-7_78 . ISBN 978-3-540-44139-7.
- ^ Zexuan Zhu, YS Ong y M. Dash (2007). "Algoritmo genético incrustado en la manta de Markov para la selección de genes". Reconocimiento de patrones . 49 (11): 3236–3248. doi : 10.1016 / j.patcog.2007.02.007 .
- ^ Zexuan Zhu, YS Ong y M. Dash (2007). "Algoritmo de selección de características de filtro de envoltura utilizando un marco memético". Transacciones IEEE sobre sistemas, hombre y cibernética - Parte B: Cibernética . 37 (1): 70–76. doi : 10.1109 / TSMCB.2006.883267 . hdl : 10338.dmlcz / 141593 . PMID 17278560 .
- ^ "Inteligencia artificial para la selección de parámetros de inyección de fallas | Marina Krček | Webinar Hardwear.io" . hardwear.io . Consultado el 21 de mayo de 2021 .
- ^ Zexuan Zhu, YS Ong y M. Zurada (2008). "Identificación simultánea de genes relevantes de clase completa y relevantes de clase parcial". Transacciones IEEE / ACM sobre biología computacional y bioinformática .
- ^ G. Karkavitsas y G. Tsihrintzis (2011). Clasificación automática de género musical mediante algoritmos genéticos híbridos . Sistemas y servicios multimedia interactivos inteligentes . Innovación, sistemas y tecnologías inteligentes. 11 . Saltador. págs. 323–335. doi : 10.1007 / 978-3-642-22158-3_32 . ISBN 978-3-642-22157-6.