Maximiliano Tabacman

Junio 2009

¿Por qué se llaman así?¿Quién los inventó?¿Cómo reconocer uno cuando lo vemos?¿Cómo se implementan?¿Qué variantes existen?¿Dónde se usan?¿Dónde podemos buscar más información?

Meme (R. Dawkins, 1976)“Unidad de transmisión cultural o imitación”

Ejemplos clásicos: melodías, modas, ideas, dichos, metodologías

Al igual que el gen, se caracteriza por:LongevidadFecundidadFidelidad de copiado

On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms (P. Moscato, 1989)

Primer paper que utiliza el término “Algoritmo memético”

Analiza varios papers existentesEncuentra muchos algoritmos genéticos con

algo nuevo en común

Un algoritmo memético es la cruza de:Una búsqueda global basada en poblacionesUna heurística de búsqueda local (realizada por

cada individuo)

A tener en cuenta:La búsqueda global no implica necesariamente un

algoritmo genéticoLa ejecución de la búsqueda local representa el

“uso/aplicación” del meme por parte del individuo

En la literatura, aparecen como sinónimos:

Algoritmos Genéticos HíbridosBuscadores Locales GenéticosAlgoritmos Genéticos LamarckianosAlgoritmos Genéticos BaldwinianosAlgoritmos Meméticos

1. Inicialización de la población

Puede ser: Aleatoria Predeterminada Aplicando alguna heurística

2. Cada individuo realiza una búsqueda local

Analogía con Evolución Cultural Aprendizaje

Puede ser: Hasta encontrar un óptimo local Hasta lograr una mejora determinada

Equivalente a la mutación en un Algoritmo Genético

Diferencia: la exploración local es guiada

Búsqueda Local = Aprendizaje del Individuo

3. Los individuos interactúan entre sí

Competencia Equivalente a la Selección en un Algoritmo Genético

Cooperación Equivalente al Cruzamiento en un Algoritmo Genético

La implementación es la misma La literatura aún se refiere a estos pasos como selección y cruzamiento

Esquema Básico de Código:t = 0Repetir hasta (criterio de parada)

Calcular fitness f(p) para la población P(t)Elegir un subconjunto de P(t) de acuerdo a f(p)Guardarlo en M(t)Recombinar y variar los individuos de M(t)Guardarlos en M’(t)Mejorar los individuos de M’(t) con búsqueda localCalcular fitness f(p) para los individuos en M’(t)Generar P(t+1) con individuos elegidos de P(t) y M’(t)t = t +1

Devolver el mejor individuo de P(t-1)

Studies on the Theory and Design Space of Memetic Algorithms (N. Krasnogor, J.E. Smith, 2002)

Resume el Estado del ArteSugiere un Modelo SintácticoCategoriza las Variantes PosiblesPresenta un Análisis de ComplejidadPropone Algoritmos Multi-Meme (Algoritmos

“Verdaderamente Meméticos”)

Scheduler

Función de alto ordenDetermina cómo, cuándo y con qué parámetros

se aplica Búsqueda LocalPuede conocer varios algoritmos de Búsqueda

Local (memes)

Fine Grain Scheduler fS

Trabaja durante la mutación (fSM) y el cruzamiento (fSR

)

Típicamente conoce a lo sumo a 2 individuos

Coarse Grain Scheduler cS

Trabaja durante la selección de padres e hijos para construir una nueva generación

Conoce a todos los individuos de una generación

Meta Scheduler mS

Trabaja después de la selección, usando información histórica Memoria Evolutiva

Conoce a todos los individuos desde la generación inicial

Número de Índice (D)Número de 4 bitsDescribe la arquitectura del Algoritmo MeméticoD = bmS bcS bfSR bfSM

bi

1 si el algoritmo incluye el Scheduler i

0 si noEjemplo: Algoritmo Genético con búsqueda local

durante la mutación o cruzamientoAlgoritmo Memético con D = 0011 = 3

Ciclo de un Algoritmo Evolutivo

Ciclo de un “Verdadero Algoritmo Memético”

Protein FoldingGraph ColoringVehicle RoutingTravelling Salesman ProblemTimetablingColoreo de GrafosRuteo de VehículosQuadratic Assignment ProblemMolecular Design Problem

Multi-Objective Memetic Algorithms (2009, Springer)

Knapsack ProblemTime-TablingAirport Gate AssignmentFeature SelectionEconomic DispatchTravelling Salesman ProblemAirfoil Shape

Libros

MeméticaThe Selfish Gene (Richard Dawkins, 1976, Oxford

University Press)The Meme Machine (Susan Blackmore, 2000,

Oxford University Press)

Algoritmos MeméticosRecent Advances in Memetic Algorithms (Hart,

Krasnogor, Smith, 2005, Studies in Fuzziness and Soft Computing , Vol. 166, Springer)

Internet

Memetic Algorithms' Home Page (P. Moscato - desactualizada)http://www.densis.fee.unicamp.br/~moscato/memetic_home.html

Natalio Krasnogor's WebPagehttp://www.cs.nott.ac.uk/~nxk/index.html

Conferencias

International Workshop on Memetic Algorithms (WOMA)

http://www.ieee-ssci.org/Genetic and Evolutionary Computation

Conference (GECCO)http://www.sigevo.org/gecco-2009/

International Workshop on Nature Inspired Cooperative Strategies for Optimisation (NICSO)

http://www.nicso2010.org/