PDF de programación - Introducción a la Computación Evolutiva

Imágen de pdf Introducción a la Computación Evolutiva

Introducción a la Computación Evolutivagráfica de visualizaciones

Publicado el 31 de Julio del 2017
516 visualizaciones desde el 31 de Julio del 2017
110,4 KB
8 paginas
Creado hace 7a (07/07/2012)
Introducción a la Computación Evolutiva

Quinta Clase: Programación Evolutiva

Programación Evolutiva

• Desarrollada en USA durante los años ’60
• Autores principales: D. Fogel
• Aplicada típicamente a:

– PE tradicional: tareas de machine learning mediante máquinas de

estado finito

– PE contemporánea: optimización (numérica)

• Características atribuidas:

– Framework muy abierto: se acepta cualquier representación y

cualquier operador de mutación

– Es difícil definir una variante algorítmica como versión estándar de

PE

• Características especiales:

– No utiliza cruce genético
– Auto-adaptación de parámetros estándar (PE contemporánea)

Características representativas de PE

Representación

Vector de valores reales

Cruce

Mutación

Ninguno

Perturbación Gaussiana

Selección de Padres

Deterministica

Selección de Sobrevivientes

Probabilística (µ+µ)

Especialidad

Auto-adaptación de los grados
de mutación

1

Perspectiva histórica de la PE

• PE fue desarrollada originalmente para simular a la

evolución como un proceso de aprendizaje
– Con el objetivo de generar inteligencia artificial
Inteligencia: capacidad de un sistema de adaptar su
comportamiento para lograr objetivos predefinidos en un
ambiente dado (comportamiento adaptado)



• La capacidad para predecir el ambiente fue considerada

como un requisito para lograr adaptabilidad
(comportamiento inteligente o adaptado)

• Por lo tanto, la capacidad para predecir el ambiente es

clave para lograr inteligencia

Predicción mediante

Máquinas de Estado Finito



Inicialmente en PE, los predictores fueron evolucionados
en la forma de máquinas de estado finito

• Máquina de Estado Finito (MEF)

– Estados (S)
– Entradas (I)
– Salidas (O)
– Función de transición δ : S x I → S x O
– Transforma una cadena de símbolos de entrada en una cadena de

símbolos de salida

• Pueden ser usadas para predicciones (ej.: predecir el

siguiente símbolo de entrada en una cadena de entrada)

Ejemplo de MEF

• Considerar la MEF con:

– S = {A, B, C}
– I = {0, 1}
– O = {a, b, c}
– δ especificada por el

diagrama

2

Ejemplo de una MEF como un predictor

• Considerar la siguiente MEF
• Tarea: predecir la siguiente entrada
• Calidad: % de in(i+1) = outi
• Estado inicial: C
• Secuencia de entrada: 011101
• Lleva a la salida: 110111
• Calidad lograda: 3 aciertos de 5

Ejemplo de aplicación:

Evolucionar MEFs para predecir números primos

• La tarea es predecir si la siguiente entrada en una

secuencia de números naturales es un número primo o no
lo es

• Para esta tarea:

– I = N = {1,2,3,…, n, …}
– O = {0,1}
– Predicción correcta: outi= P(in(i+1))

• P(n) = 1 si n es primo, 0 de otra manera

– Fitness: precisión de la predicción sobre la secuencia de entrada de

números naturales consecutivos 1, 2, 3, …, 202

• 1 punto por cada predicción correcta
• Ningún punto por cada predicción incorrecta

Ejemplo de aplicación:

Evolucionar MEFs para predecir números primos

• Selección de Padres: cada MEF en la población actual es mutada una

vez para generar un hijo

• Mediante este ejemplo se puede apreciar que un proceso evolutivo

simulado es capaz de crear buenas soluciones para una tarea inteligente

• Operadores de mutación considerados (se selecciona uno

aleatorimente):
– Cambiar un símbolo de salida
– Cambiar la dirección de una transición (cambiar el siguiente estado)
– Agregar un estado
– Eliminar un estado
– Cambiar el estado inicial

• Selección de Sobrevivientes: elegir a los mejores µ individuos de (µ

• Resultados: la mejor MEF obtenida logra valores de precisión

padres + µ hijos)

superiores a 81%

3

PE Actual

• Por razones históricas, la PE ha sido

asociada durante mucho tiempo a tareas de
predicción y al uso de MEF como su
representación

• A partir de los ’90, las variantes de PE para

optimización de vectores de parámetros
reales se han vuelto más frecuentes
– Estas variantes se han posicionado como

variantes estándar de PE

PE Actual

• Actualmente, se considera a la PE como un

framework muy abierto en términos de …
– Representación
– Operadores de mutación

• PE aplica auto-adaptación de los parámetros de

mutación

• A continuación, se presenta una variante

algorítmica representativa de PE más que una
variante estándar de PE

Representación

• La PE es frecuentemente utilizada para optimizar

funciones de parámetros continuos

• En este caso, los cromosomas consisten de dos

partes:
(xi ∈ R)
– Variables: x1,…, xn
– Grados de mutación: σ1,…,σn

• Estructura general de los individuos en PE

〈 x1,…, xn, σ1,…,σn 〉

4

Mutación

• Se presenta el operador más asociado con la

representación anterior

• Este operador transforma …

〈 x1,…,xn, σ1,…,σn 〉 → 〈 x’1,…,x’n, σ’1,…,σ’n 〉

• Mediante las siguientes operaciones
σi’ = σi • (1 + α • N(0,1))
x’i = xi + σi’ • Ni(0,1)

α ≈ 0.2

Mutación

• Otras variantes propuestas y tratadas:

– Se han propuesto otras formas de modificar los

grados de mutación

– Utilización de varianzas en lugar de

desviaciones estándar como parámetros de
mutación

– Mutar al vector σ luego de mutar al vector x
– Utilizar otras distribuciones en lugar de la

Gaussiana

Cruce

• En PE no se utiliza cruce genético
• Actualmente, los argumentos de PE en contra del cruce son

más conceptuales que técnicos
– Se considera que un punto en el espacio de búsqueda no es un

individuo de una especie

– Se considera que un punto en el espacio es la abstracción de una

especie en si misma

– En consecuencia, el cruce no tiene sentido ya que éste no puede ser

aplicado sobre diferentes especies

• Muchos debates históricos sobre “mutación vs. cruce”
• Prevalece el enfoque pragmático

5

Selección de Padres

• En PE, a partir de cada miembro de la

población se genera exactamente un hijo
mediante mutación

• Por lo tanto, la selección …

– Es determinística
– Independiente del fitness

Selección de Sobrevivientes

• Operador de selección (µ + µ )

– Consiste en elegir a los mejores µ individuos de (µ padres + µ

hijos)

• Variante estocástica del operador anterior

– P(t): µ parents, P’(t): µ offspring
– Cada solución a ∈ P(t) ∪ P’(t) es comparada con otras q

soluciones elegidas al azar

– En cada comparación, si a supera a su oponente entonces obtiene

un punto

– Las µ soluciones con la mayor cantidad de puntos se transforman

en la siguiente población

• Parámetro q permite configurar la presión selectiva (cuanto

más alto es q mayor presión selectiva)

• En general, se recomienda q = 10

Ejemplo de Aplicación:

Función de Ackley (Bäck et al ’93)

• La función de Ackley (utilizada con n = 30):

xf
)(

−=

20




⎜⎜
exp




12.0
n



n



i

1
=

x
2
i


−⎟⎟



exp



1
n

n



i

1
=

cos(

x
2
π
i

)

20

+

e


+⎟


• Representación:

– 30 variables reales (-30 < xi < 30 )
– 30 varianzas como grados de mutación

• Mutación: se muta a las variables primero y luego a las varianzas
• Tamaño de población: 200
• Selección de sobrevivientes: q = 10
• Terminación: al alcanzar las 200000 evaluaciones de fitness
• Resultados: mejor solución promedio tiene un fitness de 1.4 • 10 –2

6

Ejemplo de Aplicación:

Jugadores de damas (Fogel ’02)

• Fogel abordó el desarrollo de un programa para jugar a las

damas

• Para poder jugar a las damas, el programa analiza el valor

a futuro de los posibles movimientos
– Calcula cuán prometedor es un estado del tablero que se logra

mediante un cierto movimiento

• A un estado del tablero se le asigna un valor mediante una

red neuronal
– La salida de la red representa cuán prometedor es el estado desde

la perspectiva del jugador que recién ha movido

• El estado del tablero es presentado a la red como un vector

de 32 elementos (32 posiciones en el tablero)

• De esta manera, la red define una “estrategia” para jugar el

juego, y esta estrategia es evolucionada con PE

Ejemplo de Aplicación:

Jugadores de damas (Fogel ’02)

• Para las redes neuronales se utilizó una estructura

fija que tiene un total de 5046 pesos
– Dichos pesos son evolucionados mediante PE

• Representación:

– Vector de 5046 números reales para las variables

(pesos)

• Mutación:

– Vector de 5046 números reales para los σ‘s

– El vector σ fue mutado antes que el vector de variables
– Las variables fueron mutadas utilizando la adición de

ruido Gaussiano

• Tamaño de la población: 15

Ejemplo de Aplicación:

Jugadores de damas (Fogel ’02)

• Selección de sobrevivientes

– q = 5
– Cada programa (cada red neuronal) juega vs. otros

programas, y se le asigna +1, 0, -2 si gana, empata y
pierde respectivamente

– Las 30 soluciones (15 padres y 15 hijos) fueron
ordenadas de acuerdo al puntaje que obtuvieron
mediante los 5 juegos

– Las mejores 15 soluciones se transformaron en la

siguiente población

7

Ejemplo de Aplicación:

Jugadores de damas (Fogel ’02)

• Luego de 840 generaciones (6 meses), la mejor

estrategia lograda fue evaluada vs. oponentes
humanos via internet

• Resultados:

– Luego de una serie de partidos, el programa fue

calificado como un jugador “experto” por el sitio web

– Superó al 99.61% de todos los jugadores calificados en

el sitio web

• Este trabajo es interesante en el contexto de

inteligencia artificial
– Las estrategias evolucionan compitiendo (jugando)

entre ellas sin necesidad de intervención humana

8
  • Links de descarga
http://lwp-l.com/pdf5917

Comentarios de: Introducción a la Computación Evolutiva (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad