PDF de programación - Programación Genética - Introducción a la Computación Evolutiva

Introducción a la Computación Evolutiva

Cuarta Clase: Programación Genética

Programación Genética

• Desarrollados en USA durante los ´90
• Autores principales: J. Koza
• Aplicados típicamente a:

– Tareas de machine learning (predicción, clasificación, etc.)

• Características atribuidas:

– Compite con redes neuronales y técnicas similares
– Necesita poblaciones de gran tamaño (miles de individuos)
– Lento

• Características especiales:

– Cromosomas no lineales: árboles
– En general, no se utilizan mutaciones

PG: Resumen de Características

Representación

Árboles

Cruce

Mutación

Intercambio de sub-árboles

Cambio aleatorio en los árboles

Selección de Padres

Proporcional al Fitness

Selección de Sobrevivientes

Todos los hijos reemplazan a
los padres

1

Ejemplo inicial: puntuación crediticia

• Los bancos necesitan distinguir entre solicitantes de

créditos aptos y no aptos

• En base a la información histórica sobre los clientes, es

posible crear un modelo de clasificación

Nro. de
hijos

Salario

Estado civil

Categoría

(OK?

2
0
1

45000
30000
40000

Casado
Soltero

Divorciado

0
1
1

ID

ID-1
ID-2
ID-3
…

Ejemplo inicial: puntuación crediticia

• Un modelo posible podría ser el siguiente:

IF (NH = 2) AND (S > 80000) THEN good ELSE bad

• En general, el modelo tendrá la siguiente forma:
IF formula THEN good ELSE bad
• La fórmula es lo único desconocido en esta regla
• El objetivo es hallar la fórmula que clasifique

correctamente al mayor número de clientes conocidos

• El espacio de búsqueda es el conjunto de todas las

fórmulas posibles (fenotipos)

• El fitness de una fórmula es el porcentaje de clientes

correctamente clasificados por el modelo que ella establece

• Las fórmulas son representadas (genotipos) mediante

árboles sintácticos (parse trees)

Ejemplo inicial: puntuación crediticia

La fórmula

IF (NH = 2) AND (S > 80000) THEN good ELSE bad

Puede ser representada mediante el siguiente árbol

AND

=

>

NH

2

S

80000

2

Ejemplo inicial: puntuación crediticia

• Esta representación difiere de las utilizadas en AGs en dos

aspectos importantes:
– Los cromosomas son estructuras no lineales, mientras en AGs ellos

son generalmente vectores lineales

– Los cromosomas pueden diferir en tamaño, medido por el número
de nodos del árbol, mientras en AGs la longitud del cromosoma es
generalmente fija

• Este nuevo tipo de representación requiere de nuevos
operadores de variación que sean válidos para árboles

• Como los esquemas de selección son independientes de la
representación, cualquier esquema de selección utilizado
en otros AEs puede ser aplicado en PG

Representación basada en árbol

• Los árboles representan expresiones en una sintaxis formal dada
• Dependiendo del problema …

– Expresiones aritméticas

2

xπ
(
+⋅

⎛
⎜
⎝

+

)3

−

y
15
+

⎞
⎟
⎠

– Fórmulas en lógica de predicados
de primer orden

(x ∧ true) → (( x ∨ y ) ∨ (z ↔ (x ∧ y)))

– Código escrito en un lenguaje
de programación

i =1;
while (i < 20)
{

i = i +1

}

Representación basada en árbol

2

+π⋅

(

⎛
⎜
⎝

3x

+

)

−

y
15
+

⎞
⎟
⎠

3

Representación basada en árbol

(x ∧ true) → (( x ∨ y ) ∨ (z ↔ (x ∧ y)))

Representación basada en árbol

i =1;
while (i < 20)
{

i = i +1

}

Representación basada en árbol

• En AGs, EEs, y PE los cromosomas son

estructuras lineales (strings de bits, strings de
números enteros o reales, permutaciones)
• Los cromosomas en forma de árboles son

estructuras no lineales

• En AGs, EEs, y PE el tamaño de los cromosomas

es fijo

• Los árboles en PG pueden variar en cuanto a su

profundidad y amplitud

4

Representación basada en árbol

Las expresiones simbólicas son definidas mediante …

–
–

Un conjunto de símbolos terminales T
Un conjunto de funciones F (incluyendo la aridad de cada
símbolo de función)

Adoptando la siguiente definición recursiva
1.
2.

Cada t ∈ T es una expresión correcta
f(e1, …, en) es una expresión correcta si f ∈ F, aridad(f) = n y
e1, …, en son expresiones correctas

3. No existen otras formas de expresiones correctas
En la definición anterior, no se distingue entre diferentes
tipos de expresiones. Cada función puede tomar
cualquier expresión como argumento (terminal o
función)

•

•

•

–

Esta característica es conocida como la propiedad de clausura

Esquema de creación de hijos

• Diferencia entre AGs y PG

– En el esquema de un AG, en cada ciclo se

utiliza cruce y mutación de manera secuencial
(son aplicados en base a una probabilidad dada)

– En el esquema de un PG, en cada ciclo se

utiliza cruce o mutación (son elegidos en base a
una probabilidad dada)

Esquema de creación de hijos

AG

PG

5

Mutación

• Mutación más común: reemplazar un sub-árbol elegido

aleatoriamente por un árbol generado aleatoriamente

Mutación

• Mutación tiene dos parámetros

– Probabilidad pm de elegir a la mutación vs. el cruce
– Probabilidad de elegir a un nodo interno del padre

como la raíz del sub-árbol a ser reemplazado

• Se suele recomendar fuertemente que pm sea 0
(Koza ’92) o que adquiera un valor muy bajo
como, por ejemplo, 0.05 (Banzhaf et al. ’98)

• El tamaño del hijo puede exceder el tamaño del

padre

Cruce

• Cruce más común: intercambiar entre los padres

dos sub-árboles elegidos aleatoriamente

• El cruce tiene dos parámetros

– Probabilidad pc de elegir al cruce vs. a la mutación
– Probabilidad de elegir un nodo interno dentro de cada

padre como punto de cruce

• El tamaño de los hijos puede exceder al tamaño de

los padres

6

Cruce

Padre 1

Padre 2

Hijo 1

Hijo 2

Selección de Padres

• Selección de padres: típicamente, en PG se utiliza selección

proporcional al fitness

• Para poblaciones de gran tamaño (1000 o más): se utiliza un método

llamado “over-selection”
– La población es ordenada por fitness y luego dividida en dos grupos

• Grupo 1: contiene a los mejores de la población (x %)
• Grupo 2: contiene al resto de la población (100-x)%

– Cuando los padres son seleccionados …

• El 80% de las operaciones de selección se realizan sobre el Grupo 1
• El otro 20% se realiza sobre el Grupo 2

– Los valores de x son definidos empíricamente y dependen del tamaño de

• Para un tamaño = 1000, 2000, 4000, 8000 x = 32%, 16%, 8%, 4%
• La presión selectiva se incrementa dramáticamente para las poblaciones más

la población

grandes

– Motivación del método: incrementar la eficiencia

Selección de Sobrevivientes

• Típicamente: se utiliza el esquema generacional
(la población actual es reemplazada por los hijos
generados a partir de ella)

• Recientemente: el esquema steady-state se ha
vuelto popular debido a su elitismo implícito

7

Inicialización

• Método más común: “ramped half and half”

– Se elige un nivel de profundidad máximo para los árboles (Dmax)
– Luego, cada miembro de la población es creado a partir de los
conjuntos F y T usando alguno de los dos métodos siguientes (se
decide qué método usar en base a una probabilidad 0.5)

– Método Full (cada rama del árbol tiene una profundidad Dmax): el

contenido de …
• Los nodos que se encuentran a un nivel d < Dmax es elegido
• Los nodos que se encuentran a un nivel d = Dmax es elegido

aleatoriamente de F

aleatoriamente de T

– Método Grow (cada rama del árbol puede tener una profundidad

diferente, deben ser ≤ Dmax): el contenido de …
• Los nodos que se encuentran a un nivel d < Dmax es elegido
• Los nodos que se encuentran a un nivel d = Dmax es elegido

aleatoriamente de F ∪ T

aleatoriamente de T

Efecto Bloat

• Un efecto de variar los tamaños de los cromosomas en PG

es que dichos tamaños tienden a crecer a lo largo del
tiempo (evolución)
– El tamaño promedio de los árboles existentes en la población crece

durante el proceso de búsqueda

• Este fenómeno es conocido como bloat
• Es necesario tomar medidas para reducir el rango de

crecimiento de los árboles
– Prohibir a los operadores de variación que generen hijos cuyo

tamaño sea superior a un tamaño máximo prefijado

– Introducir un término de penalidad en la fórmula de fitness que

reduzca el fitness de los cromosomas más grandes

– Utilizar técnicas multiobjetivo

Problemas que involucran
ambientes físicos o simulados

• Árboles (programas) que son realmente ejecutables
• La ejecución de una expresión puede cambiar el ambiente
→ el cálculo del fitness de la expresión depende de dichos
cambios

• Ejemplo: controlador de un robot
• El cálculo del fitness de una expresión, desarrollado

principalmente por simulación, es muy costoso en relación
al tiempo requerido

• Esta desventaja es compensada por la alta calidad de los

resultados evolucionados (ej.: excelente desempeño de un
equipo de robots que juegan al fútbol mediante un
controlador evolucionado)

8

Ejemplo de Aplicación:
Regresión Simbólica

• Dados algunos puntos en R2, (x1, y1), … , (xn, yn)
• Encontrar una función f(x) tal que ∀i = 1, …, n :

f(xi) = yi

• Solución PG posible:

– Representación

• F = {+, -, *, /, exp, sin, cos}
• T = {x} ∪ R (sólo una variable y algunas constantes)

– Fitness

• Lo más natural es basar el fitness de un cromosoma f sobre alguna medida

del error de ajuste (debe ser minimizado)

• Una medida de error válida es :

err

(

f

)

n

= ∑

i

1
=

(

xf
(
i

)

−

y

i

2

)

Ejemplo de Aplicación:
Regresión Simbólica

• Operadores de variación: los operadores de

mutación y cruce vistos

• Operadores de selección: los operadores vistos

para AGs

• Inicialización: ramped half and half

– Tamaño de la población: 1000 individuos

• Condición de terminación:

– Alcanzar una función f con n “aciertos”

• Un acierto ocurre si | f(xi) – yi | < 0.0001

– Alcanzar un número máximo de evaluaciones de fitness

(ej.: 50000)

Discusión

• La PG es:

Una variante de AGs con una representación diferente

(árboles)?

Programación de computadoras mediante selección

natural?

Evolución automática de programas de computadora?

9