![Page 1: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/1.jpg)
Computación Evolutiva
Curso AprendizajeClase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas
![Page 2: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/2.jpg)
Motivación
Cual es el resolvedor de problemas mas poderoso del Universo? El cerebro humano: que creo la
rueda, las computadoras, etc El Mecanismo Evolutivo: Que
creo el cerebro humano
![Page 3: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/3.jpg)
Técnicas para Solución de Problemas Inspiradas en la Naturaleza
Cerebro Neuro-Computación Humano (Redes Neurales)
Evolución Computación Evolutiva
(Algoritmos Evolutivos)
![Page 4: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/4.jpg)
Computación Evolutiva
Area Interdisciplinaria: relacionada con Biología, Inteligencia Artificial, OptimizaciónEstudia métodos de búsqueda y resolución de problemas inspirados en los mecanismos de la Evolución Natural
![Page 5: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/5.jpg)
Criaturas Virutuales – Karl Sims
Cangrejo vs. Brazo
Culebra de agua
Saltador
Seguidor de 3 brazos
![Page 6: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/6.jpg)
Criaturas Virutuales – Karl Sims
![Page 7: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/7.jpg)
Evolución
Proceso de descendencia con cambio, y posiblemente diversificación
Componentes:PoblaciónVariación: en una o mas caracterísitcas Herencia: Transmisión padres - hijosSelección: Diferentes tasas de reproducción y sobrevivencia. Mas adaptados se reproducen mas
![Page 8: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/8.jpg)
Naturaleza / Computación
Nature ComputerIndividualPopulationFitnessChromosomeGene
Crossover andMutationNatural Selection
Solution to a problemSet of solutionsQuality of a solutionEncoding for a solutionPart of the encoding of asolutionSearch operators
Reuse of good (sub-)solutions
![Page 9: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/9.jpg)
Contenido
Historia, Paradigmas en Computación Evolutiva Estrategias Evolutivas (ES) Programación Evolutiva (EP) Algoritmos Genéticos (GAs) Ramificaciones de los GAs
Relación con otras áres (Busqueda, IA, Optimización, Heurísticas, Soft Computing, Computación Emergente)
![Page 10: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/10.jpg)
Breve Historia
En los 50s y 60s varios científicos de manera independiente estudiaron sistemas evolutivos, con la idea usar la evolución como método optimización en ingenieríaIdea: Evolucionar una población de posibles soluciones a un problema dado, utilizando operadores inspirados por la variación genética, y la selección natural
![Page 11: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/11.jpg)
Enfoques en Computación Evolutiva
EC = GA + ES + EPComputación
EvolutivaAlgoritmos Genéticos
(Holland, 75)
Estrategias Evolutivas
(Rechenberger, 73)
Programación Evolutiva
(Fogel, Owens, Walsh, 66)
Similares en un nivel abstracto, inspiradas en los principios de la Evolución Natural.
Diferencias a nivel de implementación. Aspectos de representación de las estructuras, operadores de variación, métodos de Selección, medidas de desempeño
![Page 12: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/12.jpg)
Ramas de Algoritmos Genéticos
Programación Genetica (Genetic Programming, GP) Jhon Koza, 1989. Espacio de búsqueda, programas de computación en un lenguaje que puede ser modificado por mutación y recombinaciónGAs basados en ordenamiento (Order based GAs): utilizados en optimización combinatoria. Espacio de búsqueda: permutacionesSistemas Clasificadores Genéticos (Classifier Systems). Especio de reglas de producción, sistema de aprendizaje, inducir y generalizar
![Page 13: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/13.jpg)
Esqueleto de un Algoritmo Evolutivo
Generate [P(0)]t 0WHILE NOT Termination_Criterion [P(t)] DO
Evaluate [P(t)]P' (t) Select [P(t)]P''(t) Apply_Variation_Operators
[P'(t)]P(t+1) Replace [P(t), P''(t)]t t + 1
ENDRETURN Best_Solution
![Page 14: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/14.jpg)
El Ciclo Evolutivo
Recombination
MutationPopulation
Offspring
ParentsSelection
Replacement
![Page 15: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/15.jpg)
Solución de Problemas usando Algoritmos Evolutivos
![Page 16: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/16.jpg)
Algoritmos Genéticos
Jhon Holland, 60s, y 70s, Univ. MichiganIdea original estudio teórico de la adaptación, no resolución de prolemasRepresentación genética independiente del dominio: cadenas de bitsEnfásis en recombinación, operador principal, mutación papel secundario aplicado con baja probabilidad, constanteSelección probabilistica
![Page 17: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/17.jpg)
Estrategias Evolutivas (1)ES, Evolution Strategies, Alemania. Evolutionstrategies
• Utilizadas para resolver problemas duros (sin solución anílitica) de optimización de parámetros (No. reales)
• Cromosoma = vector de parámetors (float)
• Auto-adaptación de las tasas de mutación, Mutación Distribución Normal, dos parámetros
• Selección (, )-ES, (+ )-ES
• Poblacion de padres e hijospuenden tener distinto tamaño
• Métodos determinísticos que excluyen definitivamente a los peores de la población
![Page 18: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/18.jpg)
Estrategias Evolutivas (2)(, )-ES: Los mejores individuos se escongen de los hijos, y se convierten en los padres de la siguiente Generación. Ej. (50,100)-ES
+ )-ES: Los mejores individuos se escongen delconjunto formado padres y hijos.Ej. (50+100)-ES
(, )-ES parece ser el mas recomendado para optimizar Funciones complejas y lograr la auto-adaptación de las tasas de mutación
![Page 19: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/19.jpg)
Estrategias Evolutivas (3)
El progreso del Algoritmo evolutivo, ocurre solo en una pequeña banda de valores para el paso de la mutación.
Por esta razón, se requiere de una regla auto-adaptiva para el ramaño de los pasos de mutación
![Page 20: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/20.jpg)
Programación Evolutiva
•Inicialmente, evolución a traves de mutaciones de maquinas de estado finito
•Representación adecuada al problema
•Mutación único operador de variación, distribución normal, Auto-adaptación
•Selección probabilistica
![Page 21: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/21.jpg)
ES EP GA
Representacion
Números Reales Números Reales Digitos Binarios
Auto-Adaptación
Desviaciones estándares y angulos de rotación
No (Standard EP)Varianzas (Meta EP)
No
Mutación Gaussiana, Operador principal
Gaussiana, Operador unico
Inversión de bit, operador secundario
Recombinación
Discreta (azar) Intermedia (promedio)
Sexual (2 padres), Panmicitica (Varios)
No Crossover de n-puntos, UniformeOperador principalSexual (2 Padres)
Selección Determinística, extintiva o basada en preservación
Probabilistica, extintiva
Probabilistica, basada en preservación
![Page 22: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/22.jpg)
Algoritmos Evolutivos y Métodos Tradicionales de Búsqueda
Búsqueda de datos almacenados: Accesar de manera eficiente información en la memoria del computador. Ej. Busqueda BinariaBúsqueda de rutas hacia metas: Encontrar de manera eficiente un conjunto de acciones que llevara de un estado inicial a uno final (meta). Ej. DFS, Branch-bound, A*Búsqueda de Soluciones: Mas general. Encontrar de manera eficiente la solución a un problema, en un espacio grande de soluciones candidatas. Ej. EAs, SA, HC, Tabu
![Page 23: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/23.jpg)
![Page 24: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/24.jpg)
Relación con Inteligencia Artificial
Enfoque Simbólico – top down Sistemas Expertos-Expert Systems (SE-ES)
Lógica Proposicional (Cálculo Proposicional) Lógica de Predicados (Cálculo de Predicados) Redes Semánticas Frames (Marcos)
Lógica difusa o borrosa-Fuzzy Logic (LD-FL)
Enfoque Subsimbólico – bottom up Redes Neurales Artificiales Computación Evolutiva
![Page 25: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/25.jpg)
Soft Computing
Difiere de la Computación tradicional (hard computing), en que es tolerante a imprecisiones, incertidumbre, aproximación, verdades parciales Modelo: mente humanaPrincipio Guía: aprovechar la tolerancia a los aspectos mencionados arriba, para lograr tratabilidad, robustez, bajo costo
SC = EC + ANN + FL
Soft Computin
g
Computación
Evolutiva
Redes Neurales Artificiale
s
Lógica Difusa
![Page 26: Computación Evolutiva Curso Aprendizaje Clase1: Introducción, Paradigmas de Computación Evolutiva, Relación con otras Areas](https://reader035.vdocumento.com/reader035/viewer/2022062409/5665b4681a28abb57c91494c/html5/thumbnails/26.jpg)
Computación EmergenteProcesos de cómputo que resultan de la actividad colectiva de muchas unidades computacionales sencillas con interacción localSistema dinámico, evoluciona en el espacio de estados bajo conjunto de reglas
- REDES NEURALES ARTIFICIALES- ALGORITMOS EVOLUTIVOS- AUTOMATAS CELULARES- MODELOS DE VIDA ARTIFICIAL.- RECOCIDO SIMULADO