[Grey-Walter] [doc] esquema charla algortimos genéticos
xabier at sindominio.net
xabier at sindominio.net
Thu Nov 21 18:11:06 CET 2002
A continuación os envio el esquema de la charla sobre algoritmos genéticos
que di en el hacklab de madrid hace un par de semanas.
Ahora que empezaremos con la lectura del Gen Egoista creo que puede
resultar interesante (del mismo modo que Lluís propuso ilustrar temas de
emergencia con CAs) leer a Dawkins con el chip de los algoritmos
genéticos.
Un saludos,
Xabier
|
-----------------------------------------------------------
===========================================================
###########################################################
A L G O R I T M O S G E N É T I C O S
introducción a la computación evolutiva y vida artificial
mad ::: wh2001 hl ::: vallecas hl ::: 05-11-02
###########################################################
===========================================================
-----------------------------------------------------------
===========================================================
0. PRESENTACIÓN
===========================================================
xabier barandiaran
* Nucleo Cero (grey-walter at sindominio.net)
* Metabolik BioHacklab
* sindominio.net
charla
* vida artificial
* teoría de la evolución mínima
* algoritmos genéticos
* ejemplos prácticos
===========================================================
1. INTRODUCCIÓN
===========================================================
COMO LA INFORMÁTICA A TRANSFORMADO LA CIENCIA
---------------------------------------------
* Computación masiva
* Exploración de sistemas complejos:
- calculo numérico de ecuaciones diferenciales
no-lineales
* Nuevo pensamiento:
50-60: cibernética
70-80: teoría de sistemas complejos
90s: vida artificial
¿ QUÉ ES LA VIDA ARTIFICIAL ?
-----------------------------
* Christopher Langton (Santafe Institute) 1989
"Artificial Life":
- "Life-as-it-could-be" vs. la vida-tal-como-es
- "Bottom-up sythetic approach" vs. método analítico
de descomposición
* Simulación de procesos complejos:
- Evolución
- Autoorganización
- Redes neuronales
- Automatas celulares
- Fractales
- Sistemas de agentes
¿ QUÉ SON LOS ALGORITMOS GENÉTICOS ?
------------------------------------
* Simulación de proceso evolutivo abstracto
* Algoritmo de optimización
- "problem space"
- algoritmo de búsqueda en ese espacio
* Método de diseño de sistemas complejos funcionales
=============================================================
2. TEORÍA DE LA EVOLUCIÓN
=============================================================
HISTORIA
--------
* S.XIX: Darwin "El origen de las especies"
* Neodarwinismo: mendel (herencia) + darwin (seleción)
* Descubrimiento del ADN
* Nueva popularización: Dawkins: selección genética
* Exploración computacional: vida artificial
PRINCIPIOS FUNDAMENTALES
------------------------
1. Reproducción con herencia
2. Selección
3. Variación
+-----------------------------------------------------+
| |
| REPRODUCCIÓN DIFERENCIAL SELECTIVA |
| |
+-----------------------------------------------------+
REPRODUCCIÓN CON HERENCIA
-------------------------
* ADN: Acido Desoxiribonucléico
- ADN --> ARN --> proteinas --> control metabólico
--> desarrollo morfológico --> fenotipo
* Proceso morfogenético
* Genotipo-Fenotipo: mapeo G-F
* Reproducción sexual: "genetic-crossover"
reconbinación genética
SELECCIÓN
---------
* Selección natural (ej: todo)
* Selección sexual (ej: pavo real)
* Selección artificial (ej: maíz)
VARIACIÓN
---------
* Mutación: radioactiva, química, defectos de copia...
* Recombinación en la reproducción
===================================================================
3. ESTRUCTURA BÁSICA DE UN A.G.
===================================================================
EL ALGORITMO
------------
1. Codificar gene / problema
|
|
2. Crear población aleatoria de genotipos
|
|
3. Evaluar soluciones genotipos <--+
3.1. Crear fenotipo |
3.2. Ejecutar fenotipo |
| |
| |
4. Seleccionar genotipos |
| |
| |
5. Reproducir genotipos |
| |
| |
6. Mutar nuevos genotipos |
| |
| |
7. Sustituir población -------------+
EJEMPLO
-------
* Aviones de papel
1. Codificación: doblar por al mitad, esquina,...
2. Creación aleatoria: tirando dados.
3.1. Crear aviones de papel
3.2. Lanzarlos por la ventana
4. Seleccionar los que lleguen más lejos y ordenarlos
5. Dar más probabilidad de reproducción a los que lleguen
más lejos. Elegir padres y recombinar genotipos
6. Mutar instrucciones
7. Volver a crear aviones e ir a 3.
1. CODIFICAR GENOTIPO / PROBLEMA
--------------------------------
* Es la parte más difícil
* Generalmente se crea una matriz:
- double/int genotipos[POP][TAM]
genotipo binario
+-------------------------------------------------------------+
| 0 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 1 1 0 1 0 |
+-------------------------------------------------------------+
2. CREAR POBLACIÓN ALEATORIA
----------------------------
* El tamaño de la población a partir de 200 no produce diferencias
* NOTA: sobre generadores de números pseudoaleatorios
"drand48()" devuelve un doble (0,1)
+--------------------------------------------------------------+
| |
| #include <time.h> |
| |
| #define RANDSEED 0 |
| |
| |
| /* para "sembrar" el generador, en "main" incluimos */ |
| |
| if(RANDSEED) srand48(RANDSEED); |
| else srand48(time(NULL)); |
| |
| |
| /* para utilizar "drand48" en cualquier función */ |
| |
| int int_aleatorio; // de 0 a N |
| double double_aleatorio; // de 0 a N |
| |
| int_aleatorio = drand48()*N; |
| double_aleatorio = drand48()*N; |
| |
+--------------------------------------------------------------+
* Así hacemos:
+--------------------------------------------------------------+
| for (i=0; i<POP; i++) { |
| for (j=0; j<TAM; j++) { |
| genotipo[i][j] = drand48()*N; |
| } |
| } |
+--------------------------------------------------------------+
3. CREAR FENOTIPO
-----------------
* Puede ser directo o indirecto.
* Indirecto necesita un mapeo G-F complejo
* Genetic regulatory network -- fenómenos de autoorganización
4. EVALUAR GENOTIPO: FUNCIÓN DE EVALUACIÓN
------------------------------------------
* Función de evaluación ("fitness function")
- Es lo más importante de un AG
- Sirve pare evaluar los fenotipos
* Puede ser implicíta o explicíta:
- Explícita: se evalúa directamente
- Implícita: función de energía
* La función de evaluación + prob. de reproducción:
- Definen la PRESIÓN SELECTIVA
* La función de evaluación crea un "fitness landscape"
- Paisaje adaptativo ¿?
5. REPRODUCIR
-------------
* Reproducción diferencial. Métodos:
- Ruleta
- Microbiano
- Número de descedientes prop. a la
* Recombinación:
- Punto por punto
- Cortar y pegar (un punto)
- Varios puntos
- Árbol genotípico
6. MUTACIÓN
-----------
* 1:100
* Si es muy grande demasiado caótico:
- los puntos se pierden en el espacio adaptativo
- la presión selectiva tiene que ser más fuerte
que la mutación: se pierden las variaciones favorables
* Si es muy pequeño:
- tarda demasiado
- también pueden perderse las mutaciones favorables
=================================================================
4. VARIACIONES DEL AG BÁSICO
=================================================================
POBLACIÓN ESPACIALMENTE DISTRIBUIDA
-----------------------------------
* Se distribuye la población en un espacio toroidal:
- genotipo[X][Y][TAM];
* Al reproducir se eligen padres en un radio pequeño
* Efecto:
- exploración paralela del "paisaje adaptativo"
- creación de especies y competición entre ellas
ELITISMO
--------
* Problema: se pueden perder los buenos genotipos por
la recombinación o mutación.
* Se copian a la siguiente generación los mejores de la
anterior.
VECTORES DE MUTACIÓN
--------------------
* Para genotipos no enteros... ¿cuál es el tamaño adecuado
de mutación?
* Se crea un operador de mutación de tamaño distribución
gaussiana normal. Se aplica el vector entero sobre el
genotipo
ALGORITMO MICROBIANO
--------------------
* Inman Harvey: "The Microbial Genetic Algorithm":
- 6 páginitas
- incluye código
- Inspirado en la evolución bacteriana (Margulis)
* Algoritmo:
1. Crear población
2. Elegir padre A y B
3. Si A es mejor que B infectar B con A. Sino inversa
4. Mutar el perdedor
yata (es contínuo)
* Ventajas:
- Elitismo gratis
- No demasiada presión selectiva.
- Es la versión más minimalista
- No hay competición sino colaboración
===================================================================
5. FENÓMENOS EVOLUTIVOS INTERESANTES
===================================================================
MAXIMO LOCAL
------------
* Estancamiento en un punto del "paisaje adaptativo"
- una colina
- si las mutaciones no son los suficientemente grandes no se
sale del máximo local
* Solución:
- mutación gaussiana
- algoritmos distribuidos
- transformar el "paisaje adaptativo" con coevolución
COEVOLUCIÓN
-----------
* Historia: Daniel Hillis (algoritmo de ordenar números)
* Se evalua contra un entorno ( o agentes ) que también
evolucionan. El éxito de unos castiga a otros y viceversa.
SALTOS EVOLUTIVOS
-----------------
=============================================================
6. REFERENCIAS
=============================================================
* Melanie Mitchell
"An introduction to genetic algorithms", MIT Press, 1998.
Tiene muchos e interesantísimos artículos online:
http://www.cse.ogi.edu/~mm/
* John Holland
"Adaptation in natural and artificial systems"
MIT Press, Cambridge, 1992.
* Inman Harvey
http://www.cogs.susx.ac.uk/users/inmanh
"Genetic Algorithms: a continuing SAGA"
* EvoWeb:
Excelente página web con espíritu de abrir el
conocimiento fuera de las universidades:
http://evonet.dcs.napier.ac.uk/
============================================================
7. FINAL
============================================================
APLICACIONES
------------
* Teóricas
- Genética de poblaciones (muy limitado)
- Efecto Baldwin
- Teoría de la selección
- Memética
- etc.
* Prácticas
- Solución de problemas complejos: el viajero, etc.
- Algoritmos de búsqueda/optimización
- Modelado sistemas complejos (robótica evolutiva)
- Alas de un avión
- Fenómenos sinergéticos: plantas medicinales
- Arte generativo-evolutivo.
More information about the Grey-Walter
mailing list