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

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