Maximiliano Tabacman Junio 2009. ¿Por qué se llaman así? ¿Quién los inventó? ¿Cómo reconocer...
-
Upload
anselmo-pedraza -
Category
Documents
-
view
15 -
download
0
Transcript of Maximiliano Tabacman Junio 2009. ¿Por qué se llaman así? ¿Quién los inventó? ¿Cómo reconocer...
![Page 1: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/1.jpg)
Maximiliano Tabacman
Junio 2009
![Page 2: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/2.jpg)
¿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?
![Page 3: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/3.jpg)
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
![Page 4: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/4.jpg)
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
![Page 5: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/5.jpg)
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
![Page 6: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/6.jpg)
En la literatura, aparecen como sinónimos:
Algoritmos Genéticos HíbridosBuscadores Locales GenéticosAlgoritmos Genéticos LamarckianosAlgoritmos Genéticos BaldwinianosAlgoritmos Meméticos
![Page 7: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/7.jpg)
1. Inicialización de la población
Puede ser: Aleatoria Predeterminada Aplicando alguna heurística
![Page 8: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/8.jpg)
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
![Page 9: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/9.jpg)
Búsqueda Local = Aprendizaje del Individuo
![Page 10: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/10.jpg)
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
![Page 11: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/11.jpg)
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)
![Page 12: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/12.jpg)
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”)
![Page 13: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/13.jpg)
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)
![Page 14: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/14.jpg)
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
![Page 15: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/15.jpg)
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
![Page 16: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/16.jpg)
Ciclo de un Algoritmo Evolutivo
![Page 17: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/17.jpg)
Ciclo de un “Verdadero Algoritmo Memético”
![Page 18: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/18.jpg)
Protein FoldingGraph ColoringVehicle RoutingTravelling Salesman ProblemTimetablingColoreo de GrafosRuteo de VehículosQuadratic Assignment ProblemMolecular Design Problem
![Page 19: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/19.jpg)
Multi-Objective Memetic Algorithms (2009, Springer)
Knapsack ProblemTime-TablingAirport Gate AssignmentFeature SelectionEconomic DispatchTravelling Salesman ProblemAirfoil Shape
![Page 20: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/20.jpg)
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)
![Page 21: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/21.jpg)
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
![Page 22: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/22.jpg)
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/
![Page 23: 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.](https://reader033.fdocumento.com/reader033/viewer/2022061301/54dcd33649795947518b4a08/html5/thumbnails/23.jpg)