Algoritmos meméticos adaptativos

El termino algoritmo memético, inspirado en el concepto de meme descrito en el libro “El gen egoísta” de Richard Dawkins, fue introducido por Pablo Moscato, en el reporte técnico escrito el año 1989 titulado “Sobre la evolución, búsqueda, optimización, algoritmos genéticos y las artes marciales: Hacia los algoritmos meméticos”, para describir a los algoritmos evolutivos en los cuales la búsqueda local juega un rol muy importante. Un algoritmo memético intenta simular la evolución cultural de los individuos, así como un algoritmo genético intenta simular la evolución biológica. Dawkins, en el último capítulo del libro mencionado, introduce la palabra meme para denotar la idea de una unidad de imitación en la transmisión cultural, la cual es análoga al gen en ciertos aspectos. Una diferencia clave existente entre los genes y los memes es la siguiente: antes de que un meme sea traspasado, típicamente es adaptado a los pensamientos y comprensiones de la persona que lo transmite; mientras que un gen es pasado como un todo, prácticamente sin modificaciones. Moscato asemejo este pensamiento al proceso de refinamiento local y por ello promovió el término algoritmo memético para describir a los algoritmos evolutivos que usan fuertemente la búsqueda local.

Moscato, en el libro escrito el año 1999 titulado “Nuevas ideas en optimización”, y Krasnogor, en su tesis de doctorado escrita el año 2002 relacionada con “Estudios sobre la teoría y espacio de diseño de los algoritmos meméticos”, propusieron crear algoritmos puramente meméticos, haciendo referencia a la capacidad de utilizar múltiples memes en un simple algoritmo. La selección del meme a utilizar se aprende durante el proceso de búsqueda. En general, según el investigador Ong y sus colegas en el estudio escrito el año 2006 sobre la “Clasificación de algoritmos meméticos adaptativos: Un estudio comparativo”, a los algoritmos meméticos que poseen la capacidad de seleccionar dinámicamente los memes se los denomina algoritmos meméticos adaptativos. Con la aparición de los teoremas denominados “No Free Lunch”, propuestos por Wolpert y Macready el año 1997, se acepta que un algoritmo memético, al igual que cualquier otro algoritmo, es lo suficientemente bueno únicamente en la medida que pueda ser adaptado a las características específicas de un problema. Este ingrediente se acentúa en los algoritmos meméticos, donde frecuentemente es necesario realizar minuciosos refinamientos en los parámetros de control para obtener resultados útiles en cada instancia particular de un problema. En palabras de Ong y sus colegas, en el estudio citado anteriormente, uno de estos parámetros son los memes; los memes, en el contexto de los algoritmos meméticos adaptativos, denotan la estrategia a utilizar para realizar la búsqueda local. A estos se les atribuye el mayor impacto en el rendimiento de los algoritmos. Es por eso que surge el interés por producir algoritmos meméticos que puedan adaptarse a las características de los problemas. Los algoritmos que cumplen con esta definición se denominan algoritmos meméticos adaptativos.

Uno de los componentes adaptables son los memes. En el área de la optimización combinatoria algunas investigaciones notables sobre la adaptación de memes son las siguientes: (1) Hiperheurísticas. Cowling y sus colegas, en el artículo escrito el año 2000 de nombre “Enfoque hiperheurístico para la planificación de ventas”, idearon el término hiperheurística para denominar a la estrategia que maneja la opción de que meme utilizar en un momento determinado, dependiendo de las características del espacio actualmente explorado. Los memes son seleccionados a partir de una colección de memes de acuerdo a distintos enfoques, los cuales son catalogados en tres diferentes categorías: enfoques aleatorios, enfoques voraces y enfoques basados en una función de selección. (2) Multimemes y Coevolución. Los investigadores Krasnogor y Smith, en el artículo escrito el año 2001 denominado “Emergencia de estrategias de búsqueda basadas en un mecanismo de herencia simple”, introdujeron un nuevo tipo de algoritmo memético en el cual, el meme a utilizar por cada individuo se aprende durante el proceso de evolución. El uso de múltiples memes, multimeme o memeplexe fue motivado por la idea de crear algoritmos verdaderamente meméticos. (3) Estructura de trabajo de Algoritmos Meméticos Adaptativos para Optimización Multi-Objetivo. Los investigadores Knowles y Corne, en el artículo escrito el año 2004 acerca de “Algoritmo memético para optimización multiobjetivo: resultados, métodos y prospectos”, propusieron una estructura de trabajo como guía para crear algoritmos meméticos multi-objetivo mucho más meméticos. Esta idea se basa en el uso de múltiples memes que puedan coexistir en un simple algoritmo y ser seleccionados de acuerdo a una medida del éxito de los mismos. La estructura de trabajo incluye el uso de seis planificadores diferentes, cada planificador realiza la selección a partir de un memeplexe de operadores, basándose en una estimación del éxito actual de estos operadores.