Algoritmo memético

a Algoritmo memético (MA) en Informática e Investigación de Operaciones, es una extensión del algoritmo genético tradicional (GA) o el algoritmo evolutivo más general (EA). Puede proporcionar una solución suficientemente buena a un problema de optimización. Utiliza una técnica de búsqueda heurística o local adecuada para mejorar la calidad de las soluciones generadas por el EA y reducir la probabilidad de convergencia prematura.

Los algoritmos meméticos representan una de las áreas crecientes recientes de investigación en el cálculo evolutivo. El término MA ahora se usa ampliamente como una sinergia de enfoque evolutivo o basado en la población con aprendizaje individual separado o procedimientos de mejora local para la búsqueda de problemas. Muy a menudo, también se hace referencia a MAS en la literatura como algoritmos evolutivos de Baldwinian (EAS), EAS Lamarckian, algoritmos culturales o búsqueda local genética.

Introducción

Inspirado tanto en los principios darwinianos de la evolución natural como en los principios de Dawkins. Noción de meme, el término algoritmo memético (MA) fue introducido por Pablo Moscato en su informe técnico en 1989, donde veía al MA como algo cercano a una forma de algoritmo genético híbrido (GA) basado en la población. junto con un procedimiento de aprendizaje individual capaz de realizar refinamientos locales. Los paralelos metafóricos, por un lado, con la evolución darwiniana y, por el otro, entre los memes y las heurísticas de dominio específico (búsqueda local) se capturan dentro de los algoritmos meméticos, lo que genera una metodología que equilibra bien entre la generalidad y la especificidad del problema. Esta naturaleza de dos etapas los convierte en un caso especial de evolución de dos fases.

En el contexto de la optimización compleja, se han informado muchas instancias diferentes de algoritmos meméticos en una amplia gama de dominios de aplicación, que en general convergen en soluciones de alta calidad de manera más eficiente que sus contrapartes evolutivas convencionales.

En general, utilizar las ideas de la memética dentro de un marco computacional se denomina computación memética o computación memética (MC). 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 tratando áreas de algoritmos evolutivos que combinan otras técnicas de refinamiento deterministas para resolver problemas de optimización. MC extiende la noción de memes para cubrir entidades conceptuales de procedimientos o representaciones mejoradas por el conocimiento.

Antecedentes teóricos

Los teoremas de optimización y búsqueda del almuerzo gratis establecen que todas las estrategias de optimización son igualmente efectivas con respecto al conjunto de todos los problemas de optimización. A la inversa, esto significa que se puede esperar lo siguiente: cuanto más eficientemente un algoritmo resuelve un problema o clase de problemas, menos general será y más conocimiento específico del problema se basará. Esta idea conduce directamente a la recomendación de complementar las metaheurísticas de aplicación general con métodos o heurísticas específicas de la aplicación, lo que encaja bien con el concepto de MA.

El desarrollo de las maestrías

1ª generación

Pablo Moscato caracterizó un MA de la siguiente manera: "Los algoritmos meméticos son un matrimonio entre una búsqueda global basada en la población y la búsqueda heurística local realizada por cada uno de los individuos.... Los mecanismos para hacer local La búsqueda puede ser alcanzar un óptimo local o mejorar (con respecto a la función de costos objetivo) hasta un nivel predeterminado." Y enfatiza "No estoy limitando un MA a una representación genética.". Esta definición original de MA, aunque abarca características de evolución cultural (en forma de refinamiento local) en el ciclo de búsqueda, puede no calificar como un verdadero sistema en evolución según el darwinismo universal, ya que todos los principios básicos de herencia/transmisión memética, variación y faltan 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. El siguiente pseudocódigo correspondería a esta definición general de MA:

Código Pseudo

 Procedimiento Algoritm memético
 Inicializar: Generar una población inicial, evaluar a las personas y asignarles un valor de calidad;
 mientras Las condiciones de suspensión no están satisfechas do Evolve una nueva población usando operadores de búsqueda estocástica.
 Evaluate todos los individuos de la población y asignarles un valor de calidad.
 Seleccione el subconjunto de individuos, ${\displaystyle Omega _{il}$, que debe someterse al procedimiento de mejora individual.
 para cada individuo en ${\displaystyle Omega _{il}$ do Perform aprendizaje individual usando meme(s) con frecuencia o probabilidad de ${\displaystyle f_{il}$, con una intensidad ${\displaystyle t_{il}$. Procede con aprendizaje de Lamarckian o Baldwinian.
 final for terminar mientras

El aprendizaje lamarckiano en este contexto significa actualizar el cromosoma de acuerdo con la solución mejorada encontrada por el paso del aprendizaje individual, mientras que el aprendizaje Baldwiniano deja el cromosoma sin cambios y utiliza sólo la aptitud mejorada. Este código pseudo deja abierto los pasos que se basan en la aptitud de los individuos y que no lo son. Se trata de la evolución de la nueva población y de la selección de ${\displaystyle Omega _{il}$.

Dado que la mayoría de las implementaciones de MA se basan en EA, el código pseudo de un representante correspondiente de la primera generación también se proporciona aquí, siguiendo Krasnogor:

Código Pseudo

 Procedimiento Algoritmo memético basado en un EA
 Iniciación: ${\displaystyle t=0}$; // Iniciación del contador de generación
Generar aleatoriamente una población inicial ${\displaystyle P(t)}$;
Computar la aptitud ${\displaystyle f(p)\\\\forall p\in P(t)}$;
 mientras Las condiciones de suspensión no están satisfechas do Selección: En consecuencia, ${\displaystyle f(p)}$ elegir un subconjunto de ${\displaystyle P(t)}$ y guardarlo en ${\displaystyle M(t)}$; - Sí. Recombine and mutate individuals ${\displaystyle p\in M(t)}$ y guardarlos en ${\displaystyle M'(t)}$; Aprender: Mejora ${\displaystyle p'}$ por búsqueda local o heurística ${\displaystyle \forall p'\in M'(t)}$;
 Evaluación: Computar la aptitud ${\displaystyle f(p')\\\\forall p'\in M'(t)}$; si Lamarckian learning entonces Actualización cromosoma de ${\displaystyle p'}$ según la mejora ${\displaystyle \forall p'\in M'(t)}$; fi Nueva generación: Generar ${\displaystyle P(t+1)}$ seleccionando a algunos individuos ${\displaystyle P(t)}$ y ${\displaystyle M'(t)}$; ${\displaystyle t=t+1}$; // Incremento del contador de generación
 terminar mientras Regreso mejor individual ${\displaystyle p\in P(t-1)}$ como resultado;

Hay algunas alternativas para este esquema MA. Por ejemplo:

• Todos o algunos de los individuos iniciales pueden ser mejorados por el meme(s).
• Los padres pueden ser mejorados localmente en lugar de la descendencia.
• En lugar de todos los descendientes, sólo una fracción seleccionada aleatoriamente o dependiente de la aptitud puede experimentar mejoras locales. Este último requiere la evaluación de la descendencia en ${\displaystyle M'(t)}$ antes del Aprender paso.

2da generación

Los MA multimeme, hiperheurísticos y meta-lamarckianos se conocen como MA de segunda generación y exhiben los principios de transmisión y selección memética en su diseño. En Multi-meme MA, el material memético está codificado como parte del genotipo. Posteriormente, el meme decodificado de cada individuo/cromosoma respectivo se utiliza para realizar un refinamiento local. Luego, el material memético se transmite a través de un mecanismo de herencia simple de padres a hijos. Por otro lado, en MA hiperheurístico y meta-Lamarckiano, el grupo de los memes candidatos considerados competirán, en función de sus méritos pasados en generar mejoras locales a través de un mecanismo de recompensa, y decidirán qué meme se seleccionará para proceder con futuras mejoras locales. Los memes con una recompensa mayor tienen más posibilidades de seguir utilizándose. Para una revisión sobre MA de segunda generación; es decir, MA que considera múltiples métodos de aprendizaje individuales dentro de un sistema evolutivo, se remite al lector.

3ra generación

Las MA de coevolución y autogeneración pueden considerarse MA de tercera generación donde se han considerado los tres principios que satisfacen las definiciones de un sistema básico en evolución. A diferencia del MA de segunda generación, que supone que los memes que se utilizarán se conocen 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

El método de aprendizaje/meme utilizado tiene un impacto significativo en los resultados de mejora, por lo que se debe tener cuidado al decidir qué meme o memes usar para un problema de optimización en particular. 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 determinado. Claramente, un aprendizaje individual más intenso proporciona mayores posibilidades de convergencia hacia 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 configurar estos dos parámetros para equilibrar el presupuesto computacional disponible para lograr el máximo rendimiento de búsqueda. Cuando solo una parte de la población aprende, es necesario considerar qué subconjunto de individuos mejorar para maximizar la utilidad de la búsqueda MA. Por último, pero no menos importante, hay que decidir si el éxito del aprendizaje debe cambiar al individuo en cuestión (aprendizaje lamarckiano) o no (aprendizaje baldwiniano). Por lo tanto, se deben responder las siguientes cinco preguntas de diseño, la primera de las cuales es abordada por todos los representantes de segunda generación mencionados anteriormente durante una ejecución de MA, mientras que la forma extendida de aprendizaje meta-lamarckiano expande esto a las primeras cuatro decisiones de diseño.

Selección de un método de aprendizaje individual o meme que se utilizará para un problema o individuo en particular

En el contexto de la optimización continua, el aprendizaje individual existe en forma de heurísticas locales o métodos enumerativos exactos convencionales. Ejemplos de estrategias de aprendizaje individuales incluyen la escalada de colinas, el método Simplex, el método Newton/Quasi-Newton, los métodos de puntos interiores, el método de gradiente conjugado, la 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 comúnmente existen 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 del gen k, el intercambio de bordes, la primera mejora y muchos otros.

Determinación de la frecuencia de 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, se consideró el efecto de la frecuencia de aprendizaje individual en el rendimiento de la búsqueda de MA cuando se investigaron varias configuraciones de la frecuencia de aprendizaje individual en diferentes etapas de la búsqueda de MA. Por el contrario, en otro lugar se demostró que puede valer la pena aplicar el aprendizaje individual a cada individuo si la complejidad computacional del aprendizaje individual es relativamente baja.

Selección de los individuos a los que se aplica el aprendizaje individual

Sobre la cuestión de seleccionar individuos apropiados entre la población de EA que deberían someterse a un aprendizaje individual, se estudiaron estrategias basadas en la aptitud y 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. ampliando el trabajo a problemas de optimización combinatoria. Bambha et al. 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.

Especificación de la intensidad del aprendizaje individual

Intensidad de aprendizaje individual, ${\displaystyle t_{il}$, es la cantidad de presupuesto computacional asignado a una iteración de aprendizaje individual; es decir, el presupuesto computacional máximo permitido para el aprendizaje individual para gastar en mejorar una sola solución.

Elección entre aprendizaje lamarckiano o baldwiniano

Hay que decidir si una mejora encontrada se debe únicamente a una mejor aptitud física (aprendizaje baldwiniano) o si también el individuo se adapta en consecuencia (aprendizaje lamarckiano). En el caso de una EA, esto significaría un ajuste del genotipo. Esta cuestión ha sido discutida de manera controvertida para los EA en la literatura ya en la década de 1990, afirmando que el caso de uso específico juega un papel importante. El trasfondo del debate es que la adaptación del genoma puede promover una convergencia prematura. Este riesgo puede mitigarse eficazmente con otras medidas para equilibrar mejor las búsquedas amplias y profundas, como el uso de poblaciones estructuradas.

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.

Los investigadores han utilizado algoritmos meméticos para abordar muchos problemas clásicos de NP. Para citar algunos de ellos: particiones gráficas, knapsack multidimensional, problema de vendedor itinerante, problema de asignación cuadrática, problema de encubrimiento de conjuntos, coloración de gráficos mínimos, problema de conjunto máximo independiente, problema de empaquetado de basura y problema de asignación generalizado.

Las aplicaciones más recientes incluyen (entre otros) análisis de negocios y ciencia de datos, capacitación de redes neuronales artificiales, reconocimiento de patrones, planificación de movimiento robótico, orientación del haz, diseño de circuitos, restauración de servicios eléctricos, sistemas de expertos médicos, programación de una sola máquina. , Timetable automático (en particular, el calendario para la NHL), la programación de mano de obra, la optimización de la lista de enfermeras, la asignación de procesadores, la programación de mantenimiento (por ejemplo, de una red de distribución eléctrica), programación de múltiples flujos de trabajo a recursos heterogéneos restringidos, problema multidimensional de onda, VLSI VLSI, VLSI. Diseño, agrupación de perfiles de expresión génica, selección de características/genes, determinación de parámetros para la inyección de fallas de hardware y selección de características múltiples de clase múltiple.

Actividades recientes en algoritmos meméticos

• IEEE Workshop on Memetic Algorithms (WOMA 2009). Sillas del programa: Jim Smith, Universidad del Oeste de Inglaterra, U.K.; Yew-Soon Ong, Universidad Tecnológica de Nanyang, Singapur; Gustafson Steven, Universidad de Nottingham; U.K.; Meng Hiot Lim, Universidad Tecnológica de Nanyang, Singapur; Natalio Krasnogor, Universidad de Nottingham, U.K.
• Memetic Computing Journal, first issue appeared in January 2009.
• 2008 IEEE World Congress on Computational Intelligence (WCCI 2008), Hong Kong, Special Session on Memetic Algorithms.
• Edición especial sobre 'Emerging Trends in Soft Computing - Memetic Algorithm' Archived 2011-09-27 en el Wayback Machine, Soft Computing Journal, Completed ' In Press, 2008.
• IEEE Computational Intelligence Society Emergent Technologies Task Force on Memetic Computing Archived 2011-09-27 en el Wayback Machine
• IEEE Congress on Evolutionary Computation (CEC 2007), Singapore, Special Session on Memetic Algorithms.
• 'Memetic Computing' de Thomson Scientific's Essential Science Indicators como Emerging Front Research Area.
• Edición Especial sobre Algoritmos Meméticos, Transacciones IEEE en Sistemas, Hombre y Cibernética - Parte B: Cibernética, Vol. 37, No. 1, febrero 2007.
• Recent Advances in Memetic Algorithms, Series: Studies in Fuzziness and Soft Computing, Vol. 166, ISBN 978-3-540-22904-9, 2005.
• Edición Especial sobre Algoritmos Meméticos, Evolutionary Computation Fall 2004, Vol. 12, No. 3: v-vi.