Programación Genéticajabaier.sitios.ing.uc.cl/iic2622/gp.pdfProgramación Genética Programaci´on...

Programación Genética

Programacion Genetica consiste en la evolucion automatica de programas usandoideas basadas en la seleccion natural (Darwin).

No solo se ha utilizado para generar programas, sino que cualquier otro tipo desoluciones cuya estructura sea similar a la de un programa. Por ejemplo, formulasmatematicas, circuitos electronicos.

La evolucion se produce en la naturaleza gracias a que:

• Existe reproduccion entre individuos de una poblacion.• Las caracterısticas de los individuos afectan su probabilidad de supervivencia.• Existe herencia.• Existen recursos finitos, que ocasiona competencia.

En programacion genetica se busca que poblaciones de programas evolucionen,transmitiendo su herencia de manera que se adapten mejor al medio.

Los mejores individuos tienen mayores probabilidades de reproducirse. La medidade calidad del individuo dependera del tipo de problema.

Jorge Baier Aranda, PUC 17

Una mirada general

Un algoritmo de programacion genetica sigue el siguiente esquema:

1. Genera una poblacion inicial.2. Mientras no se cumple el criterio de terminacion:a) Seleccionar individuos (para reproduccion y eliminacion), considerando su

calidad.b) Combinar y/o variar individuos nuevos.c) Agregar y eliminar individuos.


Representación

En programacion genetica, los programas (o individuos) se representan comoarboles.

Es ası como el segmento de codigo

while (a<10) {print(a);a++

}

puede representarse por el arbol

while

<

10

print

aa


Terminales y Funciones

El conjunto de terminales esta compuesto por las entradas posibles al individuo,constantes y funciones de aridad 0.

El conjunto de funciones esta compuesto por los operadores constructos yfunciones que pueden componer a un individuo. Ejemplos:

Funciones booleanas: AND, OR, NOT, XOR.Funciones aritmeticas: PLUS, MINUS, MULT, DIV.Sentencias condicionales: IF, THEN, ELSE, CASE, SWITCHSentencias para iteraciones: WHILE, FOR, REPEAT..UNTIL

El conjunto de terminales y funciones elegidos para resolver un problema particulardebe ser, obviamente, suficiente para representar una solucion al problema.

Por otro lado, no es conveniente usar un numero grande de funciones, debido aque esto aumenta el tamano del espacio de busqueda (principio de parsimonia).

Ademas es deseable las funciones puedan manejar todos los argumentos queeventualmente podrıan llegar a tener.


Inicialización

El primer paso en programacion genetica consiste en formar la poblacion inicialde individuos.

Uno de los parametros principales para un algoritmo genetico es el tamanomaximo de un programa. Este lımite puede estar impuesto sobre el numero denodos o sobre la profundidad del arbol.

Usualmente, se utilizan dos metodos para generar esta poblacion, el metodo degrow y el full .


El métodogrow

Sea T el conjunto de terminales y F el conjunto de funciones.

Se elige aleatoriamente un elemento de F para que conforme la raız del arbol.

El contenido de los nodos hijos de la raız se elige desde F ∪ T . Si el valor elegidoes una funcion, se repite este procedimiento con los hijos. (si el valor elegido esuna constante, se termina esa rama del arbol.)


El métodofull

El metodo full hace crecer el arbol en forma similar al metodo grow , pero siemprese eligen elementos del conjunto de funciones, a menos que el nodo este aprofundidad maxima, en cuyo caso solo se eligen elementos de T .

El resultado de este metodo son siempre arboles balanceados de profundidadmaxima.

Si se usa el numero de nodos como lımite de tamano, el crecimiento se terminacuando el tamano arbol ha alcanzado el lımite.


Operadores Genéticos

Los operadores basicos de programacion genetica son:

• Crossover .• Mutacion.• Reproduccion.


Crossover

El operador de cruza (crossover) combina el material genetico de individuosintercambiando pedazos dos progenitores para producir dos descendientes.

Si los individuos se representan como arboles, se elige al azar un nodo de cadaarbol y luego se intercambian los subarboles bajo estos nodos.

El intercambio se muestra en la siguiente figura:


AND

n

s

NOT

sw

AND

n

s

NOT

sw

AND

nne

AND

nne

OR

e

AND

OR

e ne

AND

OR

e ne

OR

e

Padres

Descendientes


Mutación

Actua sobre un solo individuo, generalmente, uno resultante de un crossover .

La mutacion actua con una probabilidad, en general, muy baja y que es unparametro del algoritmo de programacion genetica.

Un tipo de mutacion consiste en escoger en forma aleatoria un nodo del arbol ygenerar bajo este otro subarbol (por ejemplo, usando el metodo grow).

En la siguiente tabla se muestran otros tipos de mutacion:

Nombre del operador Descripcion del efecto

Mutacion puntual Un solo nodo es intercambiado por otro de la misma clase

Permutacion Los argumentos de un nodo son permutados

Levantamiento Nuevo individuo es generado a partir de un subarbol

Expansion Un terminal es cambiado por un arbol generado al azar

Colapso Subarbol es intercambiado por un terminal

Mutacion de Subarbol Subarbol es reemplazado por otro generado al azar.

Duplicacion de Gen Subarbol es reemplazado por un terminal al azar.


Reproducción

Es el operador mas simple de todos.

Se selecciona un individuo y se lo duplica, quedando dos copias dentro de lapoblacion.


Función de Calidad

La calidad es la medida usada por el algoritmo de programacion genetica durantela evolucion simulada para medir que tan buena es una solucion.

Una funcion de calidad se dice estandarizada positiva si es que siempre asignael valor 0 al individuo que es mejor solucion para el problema.

Una funcion de calidad se dice normalizada si es que siempre asigna el valoresentre 0 y 1.

Si f es una funcion estandarizada, entonces g = 11+f es una funcion normalizada

que asigna valor 1 al individuo de mayor calidad.

Si el objetivo de la PG es aprender una funcion matematica g, entonces unamedida de calidad puede ser el error cuadratico medio.

Ası, I es un conjunto de entradas y g(i) = oi es la salida para una entrada i,


entonces podemos medir la calidad de un programa p por

fp =∑i∈I

(pi − oi)2,

donde pi es la salida del programa ante la entrada i.

La funcion de calidad depende claramente del tipo de problema. Por ejemplo, enun problema de clasificacion en bases de datos, la calidad puede estar medida porel numero de ejemplos bien clasificados.


Selección

La seleccion es el proceso por el cual se transmiten individuos de una generaciona otra.

Hay distintos tipos de seleccion tipos de seleccion.

El primero de ellos se basa en algoritmos geneticos. Para una poblacion de Nindividuos:

1. Elegir a dos individuos progenitores, privilegiando los con mejor calidad.Esto se hace eligiendo al individuo i con probabilidad.

Pr(i) =f(i)∑i f(i)

Donde f(i) es la medida de calidad1

2. Aplicar crossover (si corresponde, probabilısticamente).3. Aplicar mutacion (si corresponde, probabilısticamente).

1Notese que para que esto funcione puede ser necesario normalizar la funcion antes de hacer este calculo


4. Reproducir.5. Repetir hasta completar una nueva generacion de N individuos.

Otra tecnica consiste en efectuar torneos:

1. Elegir dos grupos de n individuos aleatoriamente desde la poblacion.2. Seleccionar al mejor elemento del primer grupo (padre), y al mejor elemento

del segundo (madre).3. Aplicar crossover (si corresponde, probabilısticamente).4. Aplicar mutacion (si corresponde, probabilısticamente).5. Los dos nuevos individuos reemplazan a los peores de cada uno de los grupos.

Esta ultima tecnica es generalmente preferida por razones de eficiencia.


Condición de Término

Hasta el momento hemos visto que para hacer evolucionar una poblacion esnecesario:

• Generar una poblacion inicial.• Seleccionar individuos para producir nuevas generaciones.

¿Cuando nos detenemos?

Depende de lo que queramos, pero en general cuando el mejor individuo de lapoblacion tiene una calidad aceptable.


Resumen

En resumen, antes un problema con programacion genetica, es necesario:

1. Definir el conjunto de terminales.2. Definir el conjunto de funciones.3. Definir la funcion de calidad.4. Definir parametros tales como tamano de la poblacion, tamano maximo de un

individuo, probabilidad de cruza, metodo de seleccion y criterio de terminacion.


Ejemplo

Supongamos que se quiere obtener una funcion matematica que se ajuste alconjunto de 10 ejemplos:

Entrada Salida

0 0

0.1 0.005

0.2 0.02

0.3 0.045

0.4 0.08

0.5 0.125

0.6 0.18

0.7 0.245

0.8 0.32

0.9 0.405

Conjunto de terminales: una variable (para la entrada), y los terminales −5 . . .+5

Conjunto de funciones: +, -, *, %.

Funcion de calidad: Error cuadratico medio sobre los 10 ejemplos.


Otros parametros:

Tamano Poblacion 600

Prob. cruza 90 %

Prob. mutacion 5 %

Seleccion Torneo, tamano 4

Criterio terminacion ninguno

Maximo de generaciones 100

Maximo prof. arbol despues de cruza 200

Maxima prof. mutacion 4

Alg. inicializacion grow


Resultados

Las funciones de mejor calidad en las generaciones 0, 1, 2 y 3 se muetran acontinuacion:

f0(x) =x

3

f1(x) =x

6− 3x

f2(x) =x

x(x− 4)− 1 + 4x −

9(x+1)5x +x

6−3x

f3(x) =x2

2(calidad 0!)

Las generaciones posteriores muestran siempre individuos de calidad 0, pero sutamano crece.


Programación Genéticajabaier.sitios.ing.uc.cl/iic2622/gp.pdfProgramación Genética Programaci´on...

Documents

Transcript of Programación Genéticajabaier.sitios.ing.uc.cl/iic2622/gp.pdfProgramación Genética Programaci´on...