1 Software para Computación evolutiva J. J. Merelo Depto. Arquitectura y Tecnología de Computadores Universidad de Granada http://geneura.ugr.es/~jmerelo [email protected] Curso de Verano Computación Natural
2 JJ Merelo [email protected] CV El Escorial, Computación Natural 2 Esquema IntroducciónIntroducción Lenguajes de programaciónLenguajes de programación TecnologíasTecnologías AplicacionesAplicaciones FuturoFuturo
3 JJ Merelo [email protected] CV El Escorial, Computación Natural 3 Introducción Programación dirigida a objetos. Elementos de programación para computación evolutiva. Clases básicas Clases auxiliares Patrones de programación
4 JJ Merelo [email protected] CV El Escorial, Computación Natural 4 Programación dirigida a objetos Principal paradigma de programación, hoy en día. Procedural: algoritmos + estructuras de datos = programas (Wirth) PDO: algoritmos U estructuras de datos = objetos
5 JJ Merelo [email protected] CV El Escorial, Computación Natural 5 Programación dirigida a objetos II Representa mejor el dominio del problema. Hace más fácil la reutilización de código, haciendo explícita la relación e interacción entre objetos. Facilita la depuración.
6 JJ Merelo [email protected] CV El Escorial, Computación Natural 6 PDO III: conceptos Herencia: Relación es-un Encapsulación El interface regula el acceso a las variables de instancia Interfaces Tipos de datos abstractos Lenguajes: SmallTalk, Modula2,C++, Java
7 JJ Merelo [email protected] CV El Escorial, Computación Natural 7 PDO II: Terminología Las clases se instancian en objectos y pueden implementar interfaces. La clase madre es la superclase y la hija la subclase, la subclase hereda de la superclase.
8 JJ Merelo [email protected] CV El Escorial, Computación Natural 8 Clases I: Individuo El que sufre la evolución. Representa una solución al problema. Representación interna Binaria, punto flotante, árbol, cualquier otra estructura de datos. Fitness: un objeto comparable eoBit indi; // EO en C++ DoubleVectorIndividual ind; //ECJ (en Java)
9 JJ Merelo [email protected] CV El Escorial, Computación Natural 9 Clases II: Operadores Cambio (mutación) Incluye todo tipo de operadores específicos. Intercambio (crossover) Cualquier operador que incluya material de más de un individuo Operadores específicos: orgía, con restricciones, permutaciones // EO eoBitMutation > mutation(P_MUT_PER_BIT); mutation( indi ); eo1PtBitXover > xover; xover( indi1, indi2); // ECJ ind.defaultMutate( state, thread );
10 JJ Merelo [email protected] CV El Escorial, Computación Natural 10 Clases III: poblaciones Conjuntos de individuos A veces llamada isla o deme No suele tener estructura, salvo orden // EO eoPop > pop; // ECJ DoubleVectorIndividual pop[POPSIZE];
11 JJ Merelo [email protected] CV El Escorial, Computación Natural 11 Clases IV: algoritmos Son un contenedor para todo tipo de transformaciones de la población. reproductor, un transformador y un reemplazador. Condiciones de terminación. Evaluador. Operadores específicos. // EO typedef eoBit Indi; eoDetTournamentSelect selectOne(T_SIZE); eoSelectPerc select(selectOne); eoSGATransform transform(xover, P_CROSS, mutation, P_MUT); eoGenContinue genCont(MAX_GEN); eoGenerationalReplacement replace; eoEvalFuncPtr & > eval(binary_value); eoEasyEA gga(genCont, eval, select, transform, replace); apply (eval, pop);
12 JJ Merelo [email protected] CV El Escorial, Computación Natural 12 Clases V: auxiliares Parsers para ficheros de configuración y de línea de comandos. Checkpointing: paro y continuación del algoritmo. Generación de números aleatorios. Interfaces gráficos para salida y parámetros.
13 JJ Merelo [email protected] CV El Escorial, Computación Natural 13 Patrones de software Singleton: clase de la que puede haber una sola instancia. Población, parser Constructor: es capaz de crear otros objetos. Generadores de individuos de la población.
14 JJ Merelo [email protected] CV El Escorial, Computación Natural 14 Adaptador: Cambia interfaz Usado para adaptar operadores en EO Estrategia: encapsula el esqueleto de un algoritmo Usado en los algoritmos, habitualmente. Patrones de software II
15 JJ Merelo [email protected] CV El Escorial, Computación Natural 15 Lenguajes de programación: C++ Usado por su velocidad y su madurez EO (http://eodev.sourceforge.net)http://eodev.sourceforge.net Desarrollada por Maarten Keijzer, March Schoenauer y otros. La más completa y flexible. GAlib: (http://lancet.mit.edu/ga/)http://lancet.mit.edu/ga/ Más usada que EO, menos flexible
16 JJ Merelo [email protected] CV El Escorial, Computación Natural 16 El más popular últimamente. Estable, bien conocido, comunicación fácil, portable. ECJ 7 ES, GP, GA Groovy Java Genetic Programming JDEAL Lenguajes de programación: Java
17 JJ Merelo [email protected] CV El Escorial, Computación Natural 17 Lenguajes de programación: alternativos Python: dirigido a objetos, popular en la Web. Librería GAS, JGRP. PERL: más popular; diversos módulos. Visual Basic for Applications: GAPPT puede ejecutarse desde PowerPoint.
18 JJ Merelo [email protected] CV El Escorial, Computación Natural 18 Mutación y crossover
19 JJ Merelo [email protected] CV El Escorial, Computación Natural 19 Ejemplo: algoritmo genético en VBA Cadena a buscar Población Prob. Mutación Prob. Crossover Generación # Generaciones
20 JJ Merelo [email protected] CV El Escorial, Computación Natural 20 XSLT: lenguaje de transformación de documentos XML. Http://geneura.ugr.es/cgi-bin/ga-xsl/ga-xsl.cgi JavaScript: se ejecuta dentro del navegador. Eiffel, Delphi, Objective C... Lenguajes de programación: alternativos II
21 JJ Merelo [email protected] CV El Escorial, Computación Natural 21 Tecnologías I: Algoritmos genéticos distribuidos DGA dan mejores resultados que los serie; se consiguen speedup superlineales. PVM (parallel virtual machine) o MPI (message passing interface), Otras tecnologías: RMI (remote method invocation, Java), RPC, sockets.
22 JJ Merelo [email protected] CV El Escorial, Computación Natural 22 Agentes código móvil. Generalmente basados en Java. Permiten cálculo distribuido y anónimo: P2P DREAM: http://dr-ea-m.sourceforge.net Tecnologías II: Agentes
23 JJ Merelo [email protected] CV El Escorial, Computación Natural 23 Interfaz para computación evolutiva. Applets en Java: se pueden usar como “clientes de cálculo”. Aplicaciones: Layout página web. Asignación servidores. Navegación sitio web. Tecnologías III: Web
24 JJ Merelo [email protected] CV El Escorial, Computación Natural 24 Simple Object Access Protocol: Convierte la internet en una galaxia de servicios. Más allá de RPC: acceso a objetos remotos. Similar a CORBA y COM. Usa cualquier transporte, y la mayoría de los lenguajes. Tecnologías IV: SOAP
25 JJ Merelo [email protected] CV El Escorial, Computación Natural 25 El nuevo conjunto de estándares de internet. Estructuras de datos. Documentos de intercambio entre librerías CE. Generación de código. Especificación experimental. Tecnologías V: XML
26 JJ Merelo [email protected] CV El Escorial, Computación Natural 26 Aplicaciones Inclusión en los sistemas operativos, para tareas de optimización básicas Scheduler para Linux Optimizador de queries para PostgreSQL Generación automática de código. EASEA
27 JJ Merelo [email protected] CV El Escorial, Computación Natural 27 Futuro Programación Visual CE transparente: integrada en dispositivos y programas. Integración con XML. Grid computing: uso de recursos computacionales diversos, desde un solo interfaz.
28 JJ Merelo [email protected] CV El Escorial, Computación Natural 28 Futuro II Reuso de código: librerías de componentes para CE. Estandarización, y uso en aplicaciones industriales. Implementación en hardware, usando FPGAs o similares
29 Sacabó