Download Algoritmos Meméticos

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:
 Longevidad
 Fecundidad
 Fidelidad 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 existentes
 Encuentra muchos algoritmos genéticos con algo nuevo
en común
 Un algoritmo memético es la cruza de:
 Una búsqueda global basada en poblaciones
 Una heurística de búsqueda local (realizada por cada
individuo)
 A tener en cuenta:
 La búsqueda global no implica necesariamente un
algoritmo genético
 La 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íbridos
 Buscadores Locales Genéticos
 Algoritmos Genéticos Lamarckianos
 Algoritmos Genéticos Baldwinianos
 Algoritmos Meméticos
1.
Inicialización de la población
Puede ser:
 Aleatoria
 Predeterminada
 Aplicando alguna heurística
Cada individuo realiza una búsqueda local
2.

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
Los individuos interactúan entre sí
3.

Competencia


Cooperación


Equivalente a la Selección en un Algoritmo Genético
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=0
 Repetir 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 local
 Calcular 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 Arte
 Sugiere un Modelo Sintáctico
 Categoriza las Variantes Posibles
 Presenta un Análisis de Complejidad
 Propone Algoritmos Multi-Meme (Algoritmos
“Verdaderamente Meméticos”)
 Scheduler
 Función de alto orden
 Determina cómo, cuándo y con qué parámetros se aplica
Búsqueda Local
 Puede conocer varios algoritmos de Búsqueda Local
(memes)
 Fine Grain Scheduler  fS
 Trabaja durante la mutación (fS ) y el cruzamiento (fS )
M
R
 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 bits
 Describe la arquitectura del Algoritmo Memético
 D = bmS bcS bfS bfS
 bi
R
M
1 si el algoritmo incluye el Scheduler i
 0 si no

 Ejemplo: Algoritmo Genético con búsqueda local
durante la mutación o cruzamiento
 Algoritmo Memético con D =
0011 = 3
 Ciclo de un Algoritmo Evolutivo
 Ciclo de un “Verdadero Algoritmo Memético”
 Protein Folding
 Graph Coloring
 Vehicle Routing
 Travelling Salesman Problem
 Timetabling
 Coloreo de Grafos
 Ruteo de Vehículos
 Quadratic Assignment Problem
 Molecular Design Problem
 Multi-Objective Memetic Algorithms (2009, Springer)
 Knapsack Problem
 Time-Tabling
 Airport Gate Assignment
 Feature Selection
 Economic Dispatch
 Travelling Salesman Problem
 Airfoil Shape
 Libros
 Memética
 The Selfish Gene (Richard Dawkins, 1976, Oxford University
Press)
 The Meme Machine (Susan Blackmore, 2000, Oxford
University Press)
 Algoritmos Meméticos
 Recent 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 WebPage
http://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/