Upload
others
View
13
Download
0
Embed Size (px)
Citation preview
Algoritmos Culturales
Ricardo Landa Becerraemail: [email protected]
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.
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.
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.
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.
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
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
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.
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.
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.
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.
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.
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).
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
Introducción a la Computación
Evolutiva 2006 15
Espacios de Versiones
Generalización
Especialización
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).
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,
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.
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
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.
Introducción a la Computación
Evolutiva 2006 21
Conocimiento Circunstancial
Individuo de élite
Introducción a la Computación
Evolutiva 2006 22
Conocimiento Circunstancial
� En la programación evolutiva
�
( )( )
>−<+
=circijiiiij
circijiiiijij xxNx
xxNxx
,,
,,
si1,0*
si1,0*'
σσ
Introducción a la Computación
Evolutiva 2006 23
Conocimiento Normativo
Introducción a la Computación
Evolutiva 2006 24
Conocimiento Normativo
� En la programación evolutiva
� ( )1,0' ,, Nxx normjiji σ+=
Introducción a la Computación
Evolutiva 2006 25
Conocimiento Topográfico
x2
x1
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 σσ
Introducción a la Computación
Evolutiva 2006 27
Conocimiento Histórico
Óptimos localesEncontrados antes
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).
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.