Es un algoritmo poblacional, que puede verse como una variante de los algoritmos genéticos.
La idea básica del algoritmo es la de incorporar la mayor cantidad de conocimiento del dominio que sea posible durante el proceso de generación de una nueva población.
Así como en búsqueda local teniamos definida una vecindad para un solo individuo, la vecindad de una población de individuos se puede obtener mediante la composición de los individuos.
La idea es crear un conjunto de soluciones nuevas a partir de las actuales. Esto se puede hacer identificando y combinano los atributos de las soluciones actuales.
Los operadores de recombinación ciegos, como los usados tradicionalmente por los algoritmos genéticos, no incorporan ningún conocimiento del dominio al momento de generar nuevos individuos, por ejemplo, cruza uniforme.
El argumento principal para no introducir conocimiento es para no sesgar la búsqueda, y evitar convergencias prematuras a soluciones subóptimas, sin embargo, esto último ha sido cuestionado últimamente.
Los operadores que introducen conocimiento se llaman heuristic o hybrid.
El conocimiento se puede incorporar en:
La tabla 9.4 describe una estructura genérica de un algoritmo poblacional. Se construye inicialmente una población, a partir de ésta, se crea una nueva población, y finalmente de decide que parte se reemplaza de la población anterior para quedarse con una nueva población y repetir el proceso. En caso de converger se puede reiniciar el proceso con otra población.
Para generar una población inicial, se puede hacer en forma aleatoria (mientras sean soluciones factibles), puede aplicarse a ésta búsqueda local, o de plano usar desde el principio GRASP.
Para generar una nueva población (reinicio), se pueden mantener algunos de los mejores individuos (inclusive uno solo) o se puede hacer una mutación muy fuerte.
Los dos tienen sus ventajas y desventajas. Cuando se deja uno o más anteriores, se tiene que tener cuidado de que no invadan rápidamente la población. Cuando se hace por mutción, se puede perder información valiosa con mucha mutación o se puede regresar al punto anterior con poca mutación.
Lo diferente viene en la generación de una nueva población a partir de operadores genéticos. Los algoritmos meméticos utilizan conocimiento del dominio para guiar mejor la búsqueda y decidir qué elementos incorporar y cuáles desechar al momento de crear nuevos individuos.
Los algoritmos meméticos se pueden ver como algoritmos genéticos en donde se introduce conocimiento del dominio para crear una nueva generación de individuos.
Son muy parecidos que scatter-search, pero las formas de crear nuevos algoritmos se basa en operadores genéticos más que en combinaciones lineales de soluciones.
