Algoritmo memético
# Algoritmo memético

Los algoritmos meméticos son técnicas de optimización que combinan sinérgicamente conceptos tomados de otras metaheurísticas, tales como la búsqueda basada en poblaciones (como en los algoritmos evolutivos), y la mejora local (como en las técnicas de seguimiento del gradiente).

## Orígenes

Los orígenes de los algoritmos meméticos (MA) se remontan a finales de los años ochenta a pesar de que algunos trabajos en décadas anteriores también tienen características similares. En aquella época, el campo de la computación evolutiva estaba comenzando afianzarse sólidamente, una vez que el choque conceptual que había causado la introducción de estas técnicas al mundo de la optimización se iba atenuando.

Cabe resaltar que el origen de los algoritmos meméticos se encuentra bastante ligado a los más conocidos algoritmos genéticos (GA), puesto que los MA toman como base la anatomía de los GA e incorporan en muchos de los casos procedimientos heurísticos de búsqueda local que incrementan el desempeño del algoritmo general.

Por otra parte, la denominación de "memético" surge del término inglés "meme", acuñado por R. Dawkins como el análogo del gen en el contexto de la evolución cultural, ejemplos de ellos son melodías, modas, ideas, dichos, metodologías, etc.

## Algoritmo general

Los MA son metaheurísticas basadas en población, esto quiere decir que mantienen un conjunto de soluciones candidatas para el problema considerado. De acuerdo a la jerga utilizada en los algortimos evolutivos, a cada una de estas soluciones tentativas se les conoce como individuos. Ahora bien en el caso de los MA, el término individuo denota un ente más pasivo, por lo que en la literatura se le ha denominado de mejor forma como agente. Un agente implica un comportamiento más activo, ya que una de las premisas de los MA es buscar mejoras individuales de las soluciones en cada uno de los agentes junto con procesos de cooperación.

A continuación se puede apreciar una plantilla general de un MA:

## Aplicaciones

Actualmente existen cientos de aplicaciones de los MA en el ámbito de la optimización combinatoria. Esto no es sorprendente si consideramos que existen miles de problemas de optimización pertenecientes a la clase NP, donde los MA han mostrado gran valor.

Para ver la amplia cobertura que han tenido los MA resolviendo esta clase de problemas, se muestra a continuación una lista con las aplicaciones de mayor importancia:

* Problema del viajante de comercio
* Problemas de particionado de grafos
* Partición de números
* Conjunto Independiente de cardinalidad máxima
* Coloreado de grafos
* Recubrimiento de conjuntos
* Planificación de tareas en una máquina con tiempos de "set-up" y fechas de entrega
* Planificación de tareas en varias máquinas
* Problemas de asignación generalizados
* Problemas de mochila multidimensional
* Programación entera no-lineal
* Asignación cuadrática
