algoritmos geneticos,introduccion a la robotica inteligente

Vista previa del material en texto

Algoritmos Genéticos
Introducción a la Robótica Inteligente
Álvaro Gutiérrez
13 de abril de 2018
aguti@etsit.upm.es
www.robolabo.etsit.upm.es
N
Índice
1 Introducción
2 Algoritmos Genéticos
3 Algunos Fundamentos Matemáticos
4 Conclusiones
N
1 Introducción
2 Algoritmos Genéticos
3 Algunos Fundamentos Matemáticos
4 Conclusiones
N
Definición
I Los algoritmos genéticos son algoritmos de búsqueda
probabilística u optimización que transforman
iterativamente un conjunto (llamado población) de objetos
matemáticos, cada uno con un valor de “coste” (fitness)
asociado, en una nueva población de descendientes
usando principios Darvinianos de selección natural y
usando operaciones genéticas naturales tales como
“crossover” (reproducción sexual) y mutación.
N
AGs de un vistazo
I Premisa
I La evolución funcionó una vez, puede ser que funcione de
nuevo
I Lo esencial
I Una pila de soluciones
I Combinar las soluciones existentes para producir nuevas
soluciones
I Mutar soluciones actuales para diversidad a largo plazo
I Sacrificar a la población
N
AGs de un vistazo (cont.)
I Primeras Ideas: John H. Holland
I Adaptation in Natural and Artificial Systems
I Otros nombres: K. DeJong y D. Goldberg
I Típicamente usado en optimización discreta
I Características:
I No son muy rápidos
I Búsqueda en paralelo
I Características especiales:
I Combinaciones de buenas soluciones
I Muchas variantes. e.g.: modelos reproductivos,
operadores, ...
N
Introducción General
I Son una sub-clase de la computación
evolutiva
I Están basados en la teoría de la evolución
de Darwin
I Historia:
I La computación evolutiva se desarrolló
en los 60’s
I Los algoritmos genéticos en los 70’s
N
Introducción Biológica - Célula
I Todo animal está compuesto de células trabajando
conjuntamente
I El centro de cada célula es el núcleo
I El núcleo contiene la información genética
N
Introducción Biológica - Cromosomas
I La información genética se almacena
en los cromosomas
I Cada cromosoma está compuesto de
ADN
I Los cromosomas en los humanos
forman pares
I Los cromosomas están divididos en
partes: Genes
I Cada gen puede adquirir diferentes
valores: alelos
I Cada gen tiene una única posición
(locus) en cada cromosoma
N
Introducción Biológica - Genética
I El conjunto de todos los genes es un genotipo
I Cada genotipo desarrolla un fenotipo
I Los alelos pueden ser dominantes o recesivos
I Los dominantes siempre se expresan en el fenotipo
I Los recesivos pueden mantenerse durante generaciones
sin “dar la cara”
N
Introducción Biológica - Reproducción
I Meiosis: Un tipo de reproducción celular en el que el
número de cromosomas es reducido a la mitad separando
cromosomas homólogos
I Mitosis: Un tipo de reproducción asexual en el que la
célula se divide creando una réplica (copia exacta) con el
mismo número de cromosomas
N
Introducción Biológica - Reproducción
I Durante la reproducción ocurren combinaciones y errores
I Gracias a estas, la variedad existe
I Los más importantes:
I Cross-over
I Mutación
N
Introducción Biológica - Selección Natural
I Se preservan las variaciones favorables y se rechazan
las variaciones no favorables
I Cada generación nacen nuevos individuos, por lo que
existe una lucha permanente
I Los individuos con ventajas tienen una mayor posibilidad
de supervivencia: Supervivencia del más adecuado
I Aspectos importantes:
I Adaptación al entorno
I Aislamiento de especies con las que no se puede
reproducir
N
1 Introducción
2 Algoritmos Genéticos
3 Algunos Fundamentos Matemáticos
4 Conclusiones
N
Differencias con otros algoritmos
I Los AGs trabajan con una codificación del conjunto de
parámetros, no con los parámetros mismos
I Los AGs buscan en un conjunto de puntos, no un único
punto
I Los AGs utilizan una función objetivo, no derivadas,
funcionales u otras funciones
I Los AGs utilizan reglas de transicción probabilística, no
determinísticas.
N
Espacio de Búsqueda
I Cada individuo busca la mejor solución en un conjunto
I Este espacio es el espacio de búsqueda
I Cada punto en el espacio de búsqueda es una posible
solución
I Cada punto tiene un valor de “fitness”(encaje) asociado
I Los algoritmos genéticos buscan soluciones en paralelo
I Los problemas:
I Óptimos locales
I Condiciones iniciales
N
Algoritmo Básico
I Se comienza con una población aleatoria de n
individuos
I Se evalúa cada individuo
I Se crea una nueva generación
I Selección: Los mejores
I Recombinación: Entre los mejores
I Mutación: Aleatoria
I Se evalúa la nueva generación
I Repetimos para m generaciones
N
Codificación
I Los cromosomas se codifican en cadenas de bits
I Cada cromosoma representa un individuo
I Cada individuo es una solución, aunque no la mejor
I La codificación depende del problema a resolver
1 0 0 1 1
N
Selección
I Principal idea: Los mejores tienen más posibilidades de
ser seleccionados
I Típicamente la ruleta
I Asigna a cada individuo una parte de la ruleta
I Girar la ruleta n veces para crear una población de n
individuos
N
Crossover
I Se seleccionan 2 individuos
I Se realiza un cruce con probabilidad Pc
I Pc típicamente en el rango (0.6, 0.9)
I Se selecciona un punto de cruce aleatorio
N
Mutación
I Alterar cada gen con probabilidad Pm
I Pm típicamente en el rango ( 1Long.Poblacion ,
1
Long.Cromosoma )
N
Un Primer Ejemplo - Definición
I Un ejemplo sencillo: max(x2) donde x ∈ {0, 1, ..31}
I Algoritmo genético
I Codificación en 5 bits, e.g. 01101↔ 13
I Población de 4 individuos
I Inicio aleatorio
I Selección por ruleta
I Crossover
I Mutación
N
Un Primer Ejemplo - Selección
N
Un Primer Ejemplo - Crossover
N
Un Primer Ejemplo - Mutación
N
Otro ejemplo sencillo - TSP
I El problema del vendedor viajero (Travelling Salesman
Problem)
I Dado un conjunto de ciudades encontrar un recorrido de
tal manera que:
I Cada ciudad sólo se visite una vez
I La distancia recorrida se minimice
N
TSP - Representación
I Representación en una lista ordenada
1) Londres 3) Madrid 5) Pekín 7) Tokio
2) Venecia 4) Singapur 6) Nueva York 8) El Cairo
I Individuo1: ( 3 5 7 2 1 6 4 8 )
I Individuo2: ( 2 5 7 6 8 1 3 4 )
I ...
N
TSP
I Generación 0
N
TSP
I Generación 1
N
TSP
I Generación 30
N
TSP
I Generación 43
N
TSP
I Generación 100
N
1 Introducción
2 Algoritmos Genéticos
3 Algunos Fundamentos Matemáticos
4 Conclusiones
N
Fundamentos Matemáticos - Introducción
I Suponemos el cromosoma A = a1a2a3 · · · an
I Supongamos ai ∈ {0, 1}
I Denotaremos ∗ al alelo que puede tomar valor 0 o 1
I Definimos un schema H como el cromosoma
representando un conjunto de cromosomas con alelos
idénticos
I e.g. *01**1
I Definimos el orden del esquema H, o(H), como el número
de posiciones fijas
I e.g. *01**1→ 3
I Definimos la longitud del esquema H, δ(H), como la
distancia entre la primera y última posición fija del
cromosoma
I e.g. *01**1→ 6− 2 = 4
N
Fundamentos Matemáticos - Selección
I Suponemos que en un instante t tenemos m individuos de
un schema H en una población A(t) de n individuos,
escribimos m = m(H, t)
I En la reproducción, un individuo es seleccionado con una
proporción directa a su “fitness”
I Ai es seleccionado con probabilidad pi = fi/
∑
f
I Después de generar una nueva generación tenemos
m(H, t + 1) representantes del schema H.
I m(H, t + 1) = m(H, t) · n · f (H)/
∑
f , donde
I f (H) es la media de los valores de “fitness” de los
individuos representados por el schema H en t
I Definimos la “fitness” media de toda la población como
f̄ =
∑
f/n
I m(H, t + 1) = m(H, t) f (H)f̄
N
Fundamentos Matemáticos - Selección
I Un schema crece en proporción a la relación entre la
“fitness” media del schema y la “fitness” media de la
población
I Un schema con “fitness” media superior a la media de la
población representará a más individuos en la siguiente
población.
I Un schema con “fitness” media inferior a la media de la
población representará a menos individuos en la siguiente
población.
ISi suponemos f (H) = f̄ + cf̄
I m(H, t + 1) = m(H, t) f̄ +c̄ff̄ = (1 + c) · m(H, t)
I Si suponemos c constante
I m(H, t) = m(H, 0) · (1 + c)t
N
Fundamentos Matemáticos - Crossover
A = 0 1 1 | 1 0 0 0
H1 = * 1 * | * * * 0
H2 = * * * | 1 0 * *
I δ(H1) = 5
I δ(H2) = 1
I Probabilidad de morir
I pd1 = δ(H1)/(l− 1)
I pd2 = δ(H2)/(l− 1)
I Probabilidad de sobrevivir:
I psi = 1− pdi = 1− δ(Hi)/(l− 1)
I Como probabilidad de crossover es pc
I ps ≥ 1− pc · δ(H)l−1
I Por lo tanto:
I m(H, t + 1) ≥ m(H, 0) · (1 + c)t · [1− pc · δ(H)l−1 ]
N
Fundamentos Matemáticos - Mutación
I Probabilidad de mutación: pm
I El schema sobrevive si cada uno de los o(H) bits sobrevive
I Probabilidad de supervivencia
I ps = (1− pm)o(H)
I Por lo tanto:
I m(H, t + 1) ≥ m(H, 0) · (1 + c)t · [1− pc · δ(H)l−1 ] · [(1− pm)
o(H)]
N
1 Introducción
2 Algoritmos Genéticos
3 Algunos Fundamentos Matemáticos
4 Conclusiones
N
Conclusiones
I Problemas de los AGs:
I Hay que elegir demasiadas cosas:
I representación
I tamaño de la población, prob. de crossover, prob. de
mutación,...
I operadores de selección, crossover, mutación,...
I Escalabilidad
I La solución sólo es tan buena como la función de “fitness”
I Normalmente la parte más difícil
N
Conclusiones
I Beneficio de los AGs:
I Sencillo de entender
I Modular, separado de la aplicación
I Permite optimización multi-objetivo
I Bueno en entornos con ruido
I Siempre hay una solución
I Distribuido, paralelo,...
N
Gracias
GRACIAS!!
N
Gracias
GRACIAS!!
N
	Introducción
	Algoritmos Genéticos
	Algunos Fundamentos Matemáticos
	Conclusiones