culturales curso 2006 - cinvestavdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf ·...
TRANSCRIPT
![Page 2: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/2.jpg)
Introducción a la Computación
Evolutiva 2006 2
Organización de la Presentación
� Inspiración biológica.� Descripción de los algoritmos culturales.� Diseño de un algoritmo cultural.� Primer ejemplo: problemas de aprendizaje.� Convergencia con los algoritmos culturales.
![Page 3: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/3.jpg)
Introducción a la Computación
Evolutiva 2006 3
Organización de la Presentación
� Auto-adaptación.� Segundo ejemplo: optimización de problemas
evaluados en los reales.� Trabajo futuro.
![Page 4: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/4.jpg)
Introducción a la Computación
Evolutiva 2006 4
La Inspiración: Evolución Cultural
� Los estudios formales de la cultura datan de principios del siglo XX.
� Durham (1990) propuso un modelo de evolución cultural de dos niveles.� Nivel micro-evolutivo: es el componente biológico,
que determina características heredadas.� Nivel macro-evolutivo: es el componente
ideológico.
![Page 5: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/5.jpg)
Introducción a la Computación
Evolutiva 2006 5
Algoritmos Culturales
� Los algoritmos culturales son modelos computacionales de la evolución cultural.
� Sus componentes son:� Espacio de la población.� Espacio de creencias.� Protocolo de comunicación.
![Page 6: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/6.jpg)
Introducción a la Computación
Evolutiva 2006 6
Pseudocódigo de un Algoritmo Cultural
� Inicio� t = 0;� Inicializar población POP(t);� Inicializar espacio de creencias BLF(t);� Repetir
� Evaluar población POP(t);� Ajustar(BLF(t), Aceptados(POP(t)));� t = t + 1;� Influencia(OperadoresVariación(POP(t), POP(t-1)), BLF(t));
� Hasta que la condición de terminación sea verdadera
� Fin
![Page 7: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/7.jpg)
Introducción a la Computación
Evolutiva 2006 7
Componentes
Ajustar
Espacio de Creencias
Variación genética
Espacio de la Población
Función deAceptación
Función deInfluencia
Protocolo deComunicación
Función deAptitud
Recombinar,Mutar
![Page 8: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/8.jpg)
Introducción a la Computación
Evolutiva 2006 8
Características Generales
� Doble herencia (a nivel de población y de conocimiento).
� El conocimiento guía la evolución de la población.
� El conocimiento del dominio se codifica de manera separada de la población.
� Soporta auto-adaptación a varios niveles.
![Page 9: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/9.jpg)
Introducción a la Computación
Evolutiva 2006 9
Problemas Aptos para el uso de
Algoritmos Culturales
� Que contengan una cantidad significativa de conocimiento del dominio (e.g. optimización con restricciones).
� Sistemas complejos donde la adaptación pueda darse en distintos niveles y velocidades, tanto en el espacio de la población como en el espacio de creencias.
� Conocimiento en diferentes formas.� Si la solución del problema requiere múltiples
poblaciones y espacios de creencias que interactúen.
� Problemas estructurados jerárquicamente.
![Page 10: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/10.jpg)
Introducción a la Computación
Evolutiva 2006 10
Diseño de Algoritmos Culturales
� Elección o diseño del modelo en espacio de la población.� Particularmente importante es la representación.� Pueden diseñarse los operadores de variación básicos.
� Diseño del componente de conocimiento� Identificar componentes comunes en el dominio del
problema.� Diseño de la función de ajuste o actualización (qué se
puede modificar del espacio de creencias).� Diseño de la función de influencia.
![Page 11: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/11.jpg)
Introducción a la Computación
Evolutiva 2006 11
Diseño de Algoritmos Culturales
� Comenzar con el espacio de la población o con el espacio de creencias depende del problema.
� Es preferible comenzar con el más restringido.
� En cualquier caso, se puede iterar entre el diseño de los dos mientras se enriquece el algoritmo.
![Page 12: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/12.jpg)
Introducción a la Computación
Evolutiva 2006 12
Un Ejemplo: El Problema de Boole
� Una de las primeras aplicaciones de los Algoritmos Culturales fue resolver el problema de Boole (Reynolds 1994).
Problema de Boole: Inferir la función característica de un multiplexor booleanodesconocido.
![Page 13: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/13.jpg)
Introducción a la Computación
Evolutiva 2006 13
VGA y el Problema de Boole
� Para resolver el problema de Boole se diseñó un algoritmo cultural con:� Un algoritmo genético como espacio de la
población.� Los espacios de versiones de Mitchell (1979)
como espacio de creencias.
� A estos algoritmos se les llamó VGA (Versionspace guided Genetic Algorithm).
![Page 14: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/14.jpg)
Introducción a la Computación
Evolutiva 2006 14
VGA y el Problema de Boole
Cromosoma 1 1 0 1 0 0 0 1
Espacio de Versiones########
#######1 #######0
1######1 0######1 1######0 0######0
![Page 15: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/15.jpg)
Introducción a la Computación
Evolutiva 2006 15
Espacios de Versiones
Generalización
Especialización
![Page 16: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/16.jpg)
Introducción a la Computación
Evolutiva 2006 16
Funciones de Influencia y Aceptación
� La función de influencia afecta a los nuevos individuos generados realizando una búsqueda dentro del espacio de creencias, partiendo de la información del individuo de inicio.
� La función de aceptación proporciona una cota a partir de la cual un individuo se considera bueno (aceptable) o malo (no aceptable).
![Page 17: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/17.jpg)
Introducción a la Computación
Evolutiva 2006 17
Teorema de los Esquemas Modificado
para un VGA
� En la teoría de algoritmos genéticos existe una expresión para la velocidad en que los buenos esquemas se propagan.
� Reynolds (1994) revisó esta expresión para inferir que en un VGA los buenos esquemas se propagan a una velocidad mayor.
( ) ( ) ( ) ( ) ( )
−−
−≥+ Hoplen
Hdlenp
f
HftHmtHm mc 1
1,1,
![Page 18: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/18.jpg)
Introducción a la Computación
Evolutiva 2006 18
Algoritmos Culturales y Auto-adaptación
� Los algoritmos culturales soportan los tres niveles de auto-adaptación definidos por Angeline (1995):� Nivel de población.� Nivel de individuo.� Nivel de componente.
� Reynolds y Chung (1998) extendieron el modelo teórico de Angeline.
![Page 19: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/19.jpg)
Introducción a la Computación
Evolutiva 2006 19
Optimización de Problemas con Variables
Evaluadas en los Reales
� Se han desarrollado algoritmos culturales con los siguientes modelos en el espacio de la población:� Programación Evolutiva� Optimización mediante Cúmulos de Partículas� Evolución Diferencial
![Page 20: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/20.jpg)
Introducción a la Computación
Evolutiva 2006 20
Tipos de Conocimiento en el Espacio de
Creencias
� Conocimiento Circunstancial (SituationalKnowledge).
� Conocimiento Normativo.� Conocimiento Topográfico.� Conocimiento Histórico.� Conocimiento de Dominio.
![Page 21: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/21.jpg)
Introducción a la Computación
Evolutiva 2006 21
Conocimiento Circunstancial
Individuo de élite
![Page 22: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/22.jpg)
Introducción a la Computación
Evolutiva 2006 22
Conocimiento Circunstancial
� En la programación evolutiva
�
( )( )
>−<+
=circijiiiij
circijiiiijij xxNx
xxNxx
,,
,,
si1,0*
si1,0*'
σσ
![Page 23: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/23.jpg)
Introducción a la Computación
Evolutiva 2006 23
Conocimiento Normativo
![Page 24: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/24.jpg)
Introducción a la Computación
Evolutiva 2006 24
Conocimiento Normativo
� En la programación evolutiva
� ( )1,0' ,, Nxx normjiji σ+=
![Page 25: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/25.jpg)
Introducción a la Computación
Evolutiva 2006 25
Conocimiento Topográfico
x2
x1
![Page 26: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/26.jpg)
Introducción a la Computación
Evolutiva 2006 26
Conocimiento Topográfico
� En la programación evolutiva
�
( )( )
±+
=caso otroen 1,0
celdas mejores las de unaen está si1,0'
,
,, Nx
xNxx
cellji
jcellji
ji σσ
![Page 27: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/27.jpg)
Introducción a la Computación
Evolutiva 2006 27
Conocimiento Histórico
Óptimos localesEncontrados antes
![Page 28: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/28.jpg)
Introducción a la Computación
Evolutiva 2006 28
Conocimiento de Dominio
� Este tipo de conocimiento es muy específico del problema que se esté atacando
� Difícil de modelar si no se tiene suficiente conocimiento del problema.
� Se ha aplicado únicamente con el generador de funciones dinámicas de Morrison y DeJong (1999).
![Page 29: Culturales curso 2006 - CINVESTAVdelta.cs.cinvestav.mx/~ccoello/compevol/landa-clase2006.pdf · 2006. 7. 26. · Introducción a la Computación Evolutiva 2006 4 La Inspiración:](https://reader036.vdocumento.com/reader036/viewer/2022070109/6042c7e484f82c40cd4c1cbb/html5/thumbnails/29.jpg)
Introducción a la Computación
Evolutiva 2006 29
Trabajo Futuro
� Existen varios problemas aptos para la utilización de algoritmos culturales en los que no han sido aplicados.
� Mayor trabajo teórico y de modelado también está pendiente.