| ----------------------------------------------------------- =========================================================== ########################################################### 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 * autonomia situada (grey-walter@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 | | | | #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