clase 5: algoritmos evolutivos: antecedentes y paradigmas computación evolutiva gabriela ochoa...
TRANSCRIPT
![Page 1: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/1.jpg)
Clase 5: Algoritmos Evolutivos: Antecedentes y ParadigmasComputación Evolutiva
Gabriela Ochoa
http://www.ldc.usb.ve/~gabro/
![Page 2: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/2.jpg)
Contenido
Inspiración biológica: La Teoría de la Evolución Natural
Algoritmos Evolutivos Paradigmas en Computación Evolutiva
Estrategias Evolutivas (ES) Programación Evolutiva (EP) Algoritmos Genéticos (GAs) Ramificaciones de los Gas
Relación con otras áreas: IA, Computación Emergente, Soft Computing
![Page 3: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/3.jpg)
Charles Darwin
1859: “The Origin of Species” Derrumba el Lamarckismo Evolución se origina a través de
cambios aleatorios de características hereditarias, combinados con un proceso de selección natural (Supervivencia de los más aptos)
![Page 4: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/4.jpg)
Selección Natural
Proceso natural por el cual los individuos mas aptos de un grupo de descendientes sobrevive para transferir sus rasgos heredados a las generaciones sucesivas
Mientras los menos aptos, mueren sin dejar descendientes y así se eliminan los rasgos característicos de los menos aptos
Este proceso explica los cambios en las características de las especies en el tiempo, y eventualmente produce especies y tipos nuevos de organismos
![Page 5: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/5.jpg)
Neo-Darwinismo
+
• Versión moderna de la Teoría Evolutiva de Darwin
• Síntesis entre el Darwinismo y la Genética Mendeliana
• Darwin desconocía los mecanismos de variación
![Page 6: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/6.jpg)
Evolución
Proceso de descendencia con cambio, y posiblemente diversificación
Evolución = Variación + Herencia + Selección
Población Variación: en una o mas características Herencia: Transmisión padres - hijos Selección: Diferentes tasas de reproducción y
supervivencia. Mas aptos se reproducen mas
![Page 7: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/7.jpg)
Computación Evolutiva
Años 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ía
Idea: 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 8: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/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: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/9.jpg)
Jhon Von Neumann (1)• Nació en Budapest Hungría en 1903
• Genio prematuro, a los 8 años leyó una enciclopedia de historia universal de 42 volúmenes
• Publicó su primer paper a los 18 años con su tutor
• Estudió química en la Universidad de Berlín hasta 1923
• Lugo viaja a Zurich, donde en 1925, recibe un título en Ing. Química
![Page 10: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/10.jpg)
Jhon Von Neumann (2)
1928: recibe doctorado en matemáticas de la Universidad de Budapest, a la edad 22 años
Instituto de Estudios Avanzados en Princeton, desde 1933. Hasta el final de su vida
Matemático mas brillante del siglo 20, contribuciones a la mecánica cuántica, análisis funcional y lógica matemática
Invento áreas nuevas como: la teoría de juegos, los autómatas celulares
La arquitectura von Neumann del computador, aun domina el área
![Page 11: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/11.jpg)
Jhon von Neumann (3)
150 publicaciones: 20 en Física y el resto distribuido mas o menos equitativamente entre: Matemáticas Puras: (set theory, logic, topological group,
measure theory, ergodic theory, operator theory, and continuous geometry)
Matemáticas Aplicadas: (statistics, numerical analysis, shock waves, flow problems, hydrodynamics, aerodynamics, ballistics, problems of detonation, meteorology, and two nonclassical aspects of applied mathematics, games and computers).
![Page 12: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/12.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 13: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/13.jpg)
Ramas de Algoritmos Genéticos
Programación Genética (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ón
GAs basados en ordenamiento (Order based GAs): utilizados en optimización combinatoria. Espacio de búsqueda: permutaciones
Sistemas Clasificadores Genéticos (Classifier Systems). Especio de reglas de producción, sistema de aprendizaje, inducir y generalizar
![Page 14: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/14.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 15: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/15.jpg)
El Ciclo Evolutivo
Recombination
MutationPopulation
Offspring
ParentsSelection
Replacement
![Page 16: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/16.jpg)
Solución de Problemas usando Algoritmos Evolutivos
![Page 17: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/17.jpg)
Algoritmos Genéticos
Jhon Holland, 60s, y 70s, Univ. Michigan Idea original estudio teórico de la adaptación, no
resolución de problemas Representación genética independiente del
dominio: cadenas de bits Énfasis en recombinación, operador principal,
mutación papel secundario aplicado con baja probabilidad, constante
Selección probabilística
![Page 18: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/18.jpg)
Estrategias Evolutivas (1)
ES, Evolution Strategies, Alemania. Evolutionstrategies
• Utilizadas para resolver problemas duros (sin solución analítica) de optimización de parámetros (No. reales)
• Cromosoma = vector de parámetros (float)
• Auto-adaptación de las tasas de mutación. Mutación con distribución Normal
• Selección (, )-ES, (+ )-ES
• Población de padres e hijospueden tener distinto tamaño
• Métodos determinísticos que excluyen definitivamente a los peores de la población
![Page 19: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/19.jpg)
Estrategias Evolutivas (2)
(, )-ES: Los mejores individuos se escogen de los hijos, y se convierten en los padres de la siguiente Generación. Ej. (50,100)-ES
+ )-ES: Los mejores individuos se escogen 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 20: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/20.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-adaptaba para el tamaño de los pasos de mutación
![Page 21: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/21.jpg)
Programación Evolutiva
•Inicialmente, evolución a través 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 probabilística
![Page 22: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/22.jpg)
ES EP GA
Representación 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 único
Inversión de bit, operador secundario
Recombinación Discreta (azar) Intermedia (promedio)
Sexual (2 padres), Panmicitica (Varios)
No Crossover de n-puntos, Uniforme
Operador principal
Sexual (2 Padres)
Selección Determinística, extintiva o basada en preservación
Probabilistica, extintiva
Probabilística, basada en preservación
![Page 23: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/23.jpg)
Algoritmos Evolutivos y Métodos Tradicionales de Búsqueda
Búsqueda de datos almacenados: Acceder de manera eficiente información en la memoria del computador. Ej. Búsqueda Binaria
Bú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, Tabú
![Page 24: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/24.jpg)
![Page 25: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/25.jpg)
Relación con Inteligencia Artificial
Enfoque Simbólico – top down Sistemas Expertos-Expert Systems (SE-ES)
Lógica Preposicional (Cálculo Preposicional) 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 26: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/26.jpg)
Soft Computing
Difiere de la Computación tradicional (hard computing), en que es tolerante a imprecisiones, incertidumbre, aproximación, verdades parciales Modelo: mente humana
Principio 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 27: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/27.jpg)
Computación Emergente
Procesos de cómputo que resultan de la actividad colectiva de muchas unidades computacionales sencillas con interacción local
Sistema 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
![Page 28: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/28.jpg)
Ciencias de la Complejidad
Estudio, en diferentes disciplinas, de cómo una colección de elementos simples, siguiendo reglas simples, producen un comportamiento emergente, colectivo y complejo Precesamiento y comunicación de información Formación de patrones complejos y cambiantes Aprendizaje y adaptación al ambiente
![Page 29: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/29.jpg)
Qué es Computación Emergente? Surge cuando acciones de componentes simples
con información y comunicación limitada, producen procesamiento coordinado y global de información
Resulta de la actividad colectiva en sistemas de muchas unidades de cómputo elementales en interacción local
El todo es más que la suma de las partes
![Page 30: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/30.jpg)
Sistema Nervioso
Neuronas
![Page 31: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/31.jpg)
Transacciones
Comportamiento de la Bolsa
![Page 32: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/32.jpg)
Colonias de Hormigas
Hormigas
![Page 33: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/33.jpg)
Rebaños
Cardúmenes
![Page 34: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/34.jpg)
Comportamiento de Bandadas Modelo computacional de movimiento
coordinado de animales (rebaños, bandadas) (C. Reinolds,1986) BOIDS
Modelo se basa en 3 comportamientos simples de dirección que describen como un individuo maniobra en base a las posiciones y velocidades de sus vecinos cercanos de vuelo
![Page 35: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/35.jpg)
Las 3 Reglas de Dirección
Separación: Evitar colisión con compañeros cercanos de vuelo
Alineación: Imitar dirección y velocidad promedio de los compañeros cercanos de vueloCohesión: Moverse hacia posición promedio de los compañeros cercanos de vuelo
![Page 36: Clase 5: Algoritmos Evolutivos: Antecedentes y Paradigmas Computación Evolutiva Gabriela Ochoa gabro](https://reader034.vdocumento.com/reader034/viewer/2022051418/5665b4821a28abb57c9216e7/html5/thumbnails/36.jpg)
Preguntas Centrales – Ciencias de la Complejidad
Cómo grandes redes con:• Componentes simples, Comunicación
limitada• Sin control central, Reglas simples de
operación
producen comportamientos complejos (vivos, inteligentes) que involucra• Computación y procesamiento de
información• Dinámicas y patrones complejos• Adaptación y Aprendizaje?
Existen principios generales que aplican a todos los sistemas complejos?