TUTORIAL DE PROGRAMACIN GENTICA
TUTORIAL DE PROGRAMACIN GENTICA
Torres Juan Esteban, Martnez Jos Jess, Departamento de Ingeniera
de Sistemas e Industrial, Universidad Nacional de Colombia, Bogot1.
Introduccin1.1 Algoritmos GenticosUn algoritmo gentico (AG) es una
clase de algoritmos de bsqueda estocstica, basados en los
mecanismos de seleccin natural. Combinan la supervivencia de los
mejores individuos dentro de un conjunto, los ms aptos, con un
intercambio de informacin estructurado y aleatorio, que imita los
procesos de evolucin biolgica. En cada generacin se crea un nuevo
conjunto de criaturas artificiales (estructuras de datos) que usan
las partes ms aptas de las generaciones anteriores. Los Algoritmos
Genticos son algoritmos evolutivos ya que explotan eficientemente
la informacin histrica, permitiendo especular sobre nuevos puntos
de bsqueda, dentro del espacio de soluciones, esperando un mejor
comportamiento a travs de su evolucin. Operan frecuentemente con
cadenas de caracteres de longitud fija, generalmente binaria. La
aptitud se determina ejecutando algoritmos y rutinas especficos,
usando una interpretacin de las cadenas de caracteres como el
conjunto de parmetros. La recombinacin sexual, tambin llamada
cruce, es el principal operador gentico empleado, donde la mutacin
comnmente es un operador de importancia secundaria. En los ltimos
10 aos ha habido un gran desarrollo tanto terico como de
aplicaciones de esta tcnica. La programacin gentica se ha aplicado
exitosamente a una gran cantidad de problemas complejos tales como
diseo automtico, reconocimiento de modelos, minera de datos,
control robtico, sntesis de arquitecturas en redes neuronales
artificiales , bioinformtica, msica y arte[2].
1.2 Programacin GenticaEs un retoo de los Algoritmos Genticos,
en el que los cromosomas (estructuras de datos) que sufren la
adaptacin, son en s mismos programas de computador. Se usan
operadores genticos especializados que generalizan la recombinacin
sexual y la mutacin, para los programas de computador estructurados
en rbol que estn bajo adaptacin. La Programacin Gentica, PG, tiene
las siguientes caractersticas:
Material gentico no lineal y generalmente estructurado en
rbol.
Aunque algunos Algoritmos Genticos tienen material gentico que
no es lineal, el material gentico lineal sigue siendo la regla en
los Algoritmos Genticos. Sin embargo, la PG casi siempre opera
sobre material gentico no lineal, y generalmente explcitamente en
estructura de rbol.
Material gentico de longitud variable.
La PG casi siempre opera sobre material gentico que puede variar
de tamao. Por razones prcticas, generalmente se implementan
limitaciones en el crecimiento, pero normalmente permite
crecimientos considerables a partir de la generacin original que se
produce aleatoriamente.
Material gentico ejecutable.
La PG es la evolucin directa de programas de computador. As, en
casi todos los casos el material gentico que esta evolucionando es
en cierto sentido ejecutable. Aunque ejecutable no es el trmino ms
preciso, y sobre esto hay una serie de reas grises. Generalmente
las estructuras son interpretadas por algn interpretador, a veces
en un lenguaje idntico o muy parecido a un lenguaje de computacin
existente, a veces en un lenguaje diseado para el problema a mano.
Sin embargo, en casi todos los casos hay un concepto de ejecucin
del material gentico, con el objeto de ver directamente el
comportamiento de la funcin deseada, a partir de la cual se obtiene
la aptitud.
Cruce que preserva la sintaxis.
Aunque se han reportado muchos operadores de cruce para PG, en
la mayora de los casos estn definidos de manera que preserven la
correccin sintctica del programa que es el material gentico,
definida por cualquier lenguaje que se haya escogido para su
representacin.2. Conceptos bsicos de la PG
El espacio de bsqueda en la PG es el espacio de todos los
posibles programas de computador compuestos de funciones y
terminales apropiados al dominio del problema. Las funciones pueden
ser operaciones aritmticas, operaciones de programacin, funciones
matemticas, funciones lgicas, o funciones especificas del
dominio.
La PG es un intento de tratar con uno de los aspectos centrales
en ciencias de la computacin:
Cmo pueden aprender los computadores a solucionar problemas sin
que se les programe explcitamente? En otras palabras, cmo podemos
hacer para que los computadores hagan lo que tienen que hacer, sin
necesidad de decirles exactamente como lo deben hacer?
En la aplicacin de la PG a un problema, hay cinco pasos
preparatorios importantes, definir[7]:
1. El conjunto de terminales,
2. El conjunto de funciones primitivas,
3. La medida de la aptitud,
4. Los parmetros para controlar la corrida, y
5. El mtodo para designar un resultado y el criterio para
terminar la ejecucin del programa
Paso 1. Consiste en identificar el conjunto de terminales. Los
terminales son las hojas de los rboles que corresponden a variables
o a valores constantes, se pueden ver como las entradas al
programa. El conjunto de terminales (junto con el conjunto de
funciones) son los ingredientes a partir de los cuales la PG, trata
de construir un programa de computador para solucionar total, o
parcialmente, un problema.
Paso 2. Consiste en identificar el conjunto de funciones que se
van a usar, para generar la expresin matemtica que trata de
satisfacer la muestra dada finita de datos. A cada funcin le
corresponde una aridad (nmero de parmetros) y un tipo de datos.
Cada programa de computador (rbol de anlisis gramatical) es una
composicin de funciones del conjunto de funciones F y terminales
del conjunto de terminales T.
Cada una de las funciones del conjunto de funciones debe ser
capaz de aceptar, como sus argumentos, cualquier valor y tipo de
dato que posiblemente, pueda retornar cualquier funcin del conjunto
de funciones, y cualquier valor y tipo de dato que posiblemente,
pueda tomar por cualquier terminal del conjunto de terminales. Esto
es, el conjunto de funciones y el conjunto de terminales deben
tener la propiedad de clausura.
En PG, se incuban genticamente poblaciones de cientos, o ms
programas de computador. Esta incubacin se hace usando el principio
de supervivencia darwiniana, la reproduccin del ms apto junto, una
operacin de cruce gentico apropiada para el apareamiento de
programas de computador y una operacin de mutacin gentica.
La PG comienza con una poblacin inicial de programas de
computador compuestos de funciones y terminales apropiadas al
dominio del problema. La creacin de esta poblacin inicial es, en
efecto, una bsqueda aleatoria ciega, en el espacio de bsqueda del
dominio del problema representado como programas de computador.
Paso 3. Cada programa de computador individual en la poblacin,
se mide en trminos de que tan bien se comporta en el ambiente del
problema particular. Esta medida se llama medida de aptitud. La
naturaleza de la medida de aptitud vara con el problema.
Para muchos problemas, la aptitud de un programa se mide
ponderando el error que se produce al ejecutar ese programa. El
mejor programa de computador tendr un error cercano a cero. En un
problema de control ptimo, la aptitud de un programa de computador
puede ser el tiempo (combustible o dinero) que toma llevar el
sistema al estado objetivo. Si uno esta tratando ejemplos de
reconocimiento de patrones o de clasificacin, la aptitud de un
programa particular se puede medir por una combinacin del nmero de
instancias manejadas correctamente (cierto positivo, y falso
negativo) y nmero de instancias manejadas incorrectamente (cierto
negativo, y falso positivo). Por otro lado si uno encuentra un buen
generador de nmeros aleatorios, la aptitud de un programa se puede
medir por medio de entropa, satisfaccin de la prueba de brecha,
satisfaccin de la prueba de corrida, o alguna combinacin de estos
factores. Para algunos problemas, puede ser apropiado usar una
medida de aptitud multiobjetivo, que incorpore una combinacin de
factores tales como correccin, parsimonia, o eficiencia.
En muchos casos, cada programa de la poblacin se corre para
varios casos de aptitud, de manera que su aptitud se mida como una
suma o producto de una variedad de situaciones representativas
diferentes. Estos casos de aptitud a veces representan un muestreo
de valores diferentes de una variable independiente, o un muestreo
de condiciones iniciales diferentes de un sistema. Por ejemplo, la
aptitud de un programa individual, se puede medir en trminos de la
suma del valor absoluto de las diferencias entre la salida
producida por el programa y la respuesta correcta.
Los programas de computador de la poblacin inicial, generacin 0,
generalmente tienen una aptitud excesivamente pobre. No obstante,
algunos individuos de la poblacin sern ms aptos que otros. Estas
diferencias en el comportamiento son las que se explotan y exploran
posteriormente.
La operacin reproduccin incluye la seleccin de un programa de la
poblacin actual de programas, se basa en su aptitud, permitindole
si es del caso, sobrevivir copindolo en la nueva poblacin.
La operacin cruce se usa para crear nuevos hijos programas de
computador, a partir de dos programas padres seleccionados. Los
programas padres en PG, normalmente son de diferentes tamaos y
formas. Los programas hijos se componen de subexpresiones
(subrboles, subprogramas, subrutinas, bloques) de sus padres. As,
los programas hijos normalmente son de diferentes tamaos y formas
que sus padres.
Intuitivamente, si dos programas de computador tienen alguna
efectividad en solucionar un problema, entonces alguna de sus
partes probablemente tenga algn mrito. La recombinacin de partes
escogidas aleatoriamente, de programas con alguna efectividad, a
veces produce nuevos programas de computador que son aun ms aptos
para solucionar un problema determinado, que cualquiera de sus
padres. En el siguiente numeral se justifica formalmente que en
cada generacin se encuentran mejores programas.
Paso 4. Despus de que se efectan las operaciones genticas sobre
la poblacin actual, la poblacin de hijos reemplaza la generacin
anterior, a cada individuo de la nueva poblacin se le mide su
aptitud, y el proceso se repite por muchas generaciones. En cada
etapa de este proceso altamente paralelo, controlado localmente, el
estado del proceso consistir nicamente de la poblacin actual de
individuos. La fuerza que controla este proceso consiste solo en la
aptitud observada de los individuos en su lucha con el ambiente
problema. Normalmente, los parmetros que controlan la ejecucin de
PG son: el tamao de la poblacin; el nmero de generaciones; las
probabilidades de aplicacin de los operadores genticos de cruce y
mutacin; y la estrategia de seleccin de los individuos para la
nueva generacin.
Paso 5. El mejor individuo que aparece en cualquier generacin de
una corrida, es decir el mejor hasta ahora, normalmente se designa
como el resultado producido por la corrida de PG.
La variabilidad dinmica de los programas que se desarrollan para
una solucin, es otra caracterstica de la PG. Generalmente es difcil
y no es natural, tratar de especificar o limitar con anterioridad
el tamao y la forma de una solucin eventual. Sin embargo, la
especificacin o limitacin con anterioridad, del tamao o la forma de
la solucin a un problema restringe la ventana a travs de la cual el
sistema ve el mundo y puede imposibilitar encontrar la solucin de
todo el problema.
Otra caracterstica de la PG es la ausencia, o el papel
relativamente mnimo, del preprocesamiento de entradas y el
postprocesamiento de salidas. Las entradas, resultados intermedios,
y salidas se expresan normalmente directamente en trminos de la
terminologa natural del dominio del problema. El postprocesamiento
de la salida del programa, si lo hay, se hace con una envoltura
(interface de salida).
Finalmente, otra caracterstica importante de la PG es que las
estructuras que sufren la adaptacin gentica son estructuras
activas. Es decir los cromosomas son el genotipo y tambin el
fenotipo
3. Pasos para la solucin de problemas por PG.
3.1. Solucin de problemas por PG
En resumen, la PG incuba programas de computador para la solucin
de problemas, ejecutando los siguientes pasos:
1. Generar una poblacin inicial de composiciones aleatorias de
funciones y terminales del problema (es decir, programas).
2. Ejecutar iterativamente los siguientes pasos hasta que se
satisfaga el criterio de terminacin:
a. Ejecutar cada programa de la poblacin y asignarle un valor de
aptitud, de acuerdo a su comportamiento frente al problema.
b. Crear una nueva poblacin de programas aplicando las
siguientes dos operaciones primarias, a los programas escogidos,
con una probabilidad basada en la aptitud.
i. Reproducir un programa existente copindolo en la nueva
poblacin.
ii. Crear dos programas a partir de dos programas existentes,
recombinando genticamente partes escogidas de los dos programas en
forma aleatoria, usando la operacin cruce aplicada a un punto de
cruce, escogido aleatoriamente dentro de cada programa.
iii. Crear un programa a partir de otro seleccionado
aleatoriamente, cambiando aleatoriamente un gen (funcin o
terminal). Es posible que se requiera un procedimiento de reparacin
para que se satisfaga la condicin de clausura.
3. El programa identificado con la mayor aptitud (el mejor hasta
la ltima generacin), se designa como el resultado de la corrida de
PG. Este resultado puede representar una solucin (o una solucin
aproximada) al problema.
3.2. Ejemplo del operador cruce
El cruce gentico (recombinacin sexual) opera sobre dos programas
padres y produce dos nuevos programas hijos consistentes de partes
de cada padre.
Consideremos los siguientes programas:
(+ ( * 0.234 Z) (- X 0.789)), equivalente a 0.234 Z + X -
0.789;
(* ( * Z Y) (+ Y (* 0.314 Z) ) ), equivalente a Z Y (Y + 0.314
Z))
En la figura 2 estos dos programas se presentan como rboles
rotulados con ramas ordenadas. Los nodos, del rbol corresponden a
funciones (es decir, operaciones) y las hojas, corresponden a
terminales (es decir, datos de entrada).
La operacin cruce crea nuevos hijos, figura 4, intercambiando
subrboles (es decir, sublistas, subrutinas, subprocedimientos)
entre los dos padres.
Figura 2. Programas de computador padres
Figura 3. Dos fragmentos de cruce.
Suponga que los nodos de ambos rboles se numeran en preorden
(raz, subrbol izquierdo, subrbol derecho). Suponga tambin, que se
seleccion aleatoriamente el nodo nmero 2, entre los 7 nodos del
primer rbol, como punto de cruce para el primer padre y que se
seleccion aleatoriamente el nodo nmero 5, entre los 9 nodos del
segundo rbol, como punto de cruce del segundo padre. Por lo tanto
los puntos de cruce son el * para el primer padre y el + para el
segundo padre. Los dos fragmentos del cruce son los dos subrboles
que se muestran en la figura 3.
Los hijos resultantes del cruce se muestran en la figura 4. De
esta manera, el cruce crea nuevos programas usando partes de los
programas padres existentes. Debido a que se intercambian subrboles
completos, la operacin cruce siempre produce programas sintctica y
semnticamente vlidos, como descendientes sin considerar el punto de
cruce. Debido a que los programas padres se han seleccionado para
la operacin cruce con una probabilidad basada en su aptitud, el
cruce explora regiones del espacio de bsqueda con programas que
contienen partes de programas promisorios.
Figura 4. Dos descendientes.
4. Teora del esquema para PG
En el contexto de AG con representaciones binarias, un esquema (
o plantilla de similitud) es una cadena de smbolos tomados del
alfabeto {0,1, #}. El carcter # es un smbolo comodn, por eso un
esquema puede representar varias cadenas de bits. Por ejemplo, el
esquema 1#0#1 representa cuatro cadenas: 10001, 11011, 11001 y
10011, donde el smbolo # se ha remplazado por 1 o 0. El nmero de
smbolos que no son comodines # se llama el orden O de un esquema.
La distancia entre el ms lejano de dos smbolos # se llama la
longitud caracterstica L de un esquema. Holland[4] obtuvo un
resultado vlido para AG, el teorema del esquema, que predice cmo el
nmero de instancias de un esquema en una poblacin vara de una
generacin a la siguiente. El teorema se expresa as [3][4]:
Donde es el nmero de cadenas que coinciden con el esquema H en
la generacin t. es la aptitud promedio de las cadenas que coinciden
con H. es la probabilidad de cruce, es la probabilidad de mutacin
por bit, es la aptitud promedio de las cadenas en la poblacin, es
el nmero de cadenas en la poblacin, es el nmero de bits en las
cadenas y es el valor esperado del nmero de cadenas que coinciden
con el esquema H en la generacin t+1.
El teorema del esquema de Holland para AG predice que cuando se
tienen individuos con un orden alto y una longitud caracterstica
larga el nmero de individuos que coinciden con el esquema H
aumentaran exponencialmente con el paso de las generaciones.Hasta
ahora los enfoques tericos utilizados en PG para entender el
comportamiento de los individuos de la poblacin y la dinmica de la
bsqueda con las generaciones son la teora del esquema y las cadenas
de Markov.
Las cadenas de Markov se han utilizado (Poli, Rowe, McPhee)[10]
para modelar el comportamiento de los individuos dentro de la
poblacin y su dinmica a travs del tiempo en PG. En esa disertacin
(Poli, Rowe, McPhee)[10] presentan un modelo de Markov para PG y AG
de longitud variables con cruce homologo (utilizado para mantener
la posicin del material gentico de los hijos tomado de los padres)
utilizando el modelo de Vose para AG y la reciente teora del
esquema para PG (la cual provee formulas exactas para calcular
probabilidades de reproduccin y recombinacin de un programa
especifico en un espacio de bsqueda) obteniendo un modelo terico
extensible a PG con cruce uniforme y de un punto. Aun este enfoque
esta en pleno desarrollo.
Una de las dificultades de obtener resultados tericos para PG
utilizando la idea del esquema es la definicin de esquema para PG
es mas complicada que en AG y varias definiciones se han propuesto
en la literatura como alternativas (Koza[7], OReilly &
Oppacher[2], Whigham[2]). Estas definiciones de esquemas se
componen de uno o mltiples fragmentos de rbol. Por eso, un esquema
puede estar presente mltiples veces dentro de un mismo programa.
Esto, juntamente con la variabilidad del tamao y forma del programa
para un mismo esquema, conduce a complicaciones considerables en el
cmputo de las probabilidades para la prediccin de individuos de un
esquema H.
Dada la popularidad del resultado para AG de la teora del
esquema, Koza hizo un primer ensayo para explicar por que la PG
trabaja, produciendo una teora informal mostrando que el teorema
del esquema de Holland debera trabajar para PG de forma adecuada.
La teora fue basada en la idea de la definicin del esquema como el
subespacio de todos los rboles los cuales contiene, como subrboles,
un conjunto predefinido de subrboles completos. As de acuerdo con
la definicin de Koza, un esquema H se puede representar como un
conjunto de expresiones-S, por ejemplo H={(+ 2 y),(- x y)} el cual
representa todos los programas incluyendo al menos una ocurrencia
de la expresin (+ 2 y) y al menos una ocurrencia de (- x y). Koza
no plantea una definicin de orden o de longitud caracterstica para
los esquemas de PG.
Posteriormente el trabajo de Koza fue formalizado y refinado por
OReilly quien deriv un teorema del esquema para PG en presencia de
seleccin y cruce proporcionales a la aptitud. La definicin del
esquema de OReilly define el concepto de orden y la longitud
caracterstica para esquemas de PG. En ella la definicin de orden de
un esquema es el nmero de smbolos que no son # en las expresiones o
fragmentos contenidos en el esquema; la longitud caracterstica es
el nmero de enlaces incluidos entre las expresiones y los
fragmentos de rbol en el esquema mas los enlaces conectados entre
ellos. Desafortunadamente, la definicin de longitud caracterstica
es complicada por el hecho de que los componentes de un esquema se
pueden embeber en diferentes rutas en diferentes programas. Whigham
tambien ha trabajado sobre la teora en PG, basado en gramticas
libres del contexto pero con similares problemas que OReilly.
En los ltimos aos varios autores (Poli, Langdon, McPhee) se han
dedicado a obtener una teora de esquema ms tratable para PG,
obteniendo expresiones tiles para obtener los valores esperados del
nmero de individuos relacionado con un esquema a travs de las
generaciones. Enseguida se describe las teoras del esquema con
cruce de un punto[11].
4.1. Esquemas de tamao y forma constantes en PG (Poli &
Langdon)[2,10,11]: como un esquema es un subespacio del espacio de
las posibles soluciones (ver figura 5), l tambin indica cuales reas
del espacio de bsqueda utiliza una poblacin, por eso los esquemas
serian tiles para explicar como la PG se mueve a travs de ese
espacio, es decir, como realiza la bsqueda. Por lo tanto la teora
de esquema debe incluir los efectos de la seleccin, cruce, mutacin
(operadores comunes) y debe ser de cierta forma fcil de
calcular.
La definicin de (Poli & Langdon) de esquema de PG ha sido
inspirada del modelo de Holland aplicado en AG, en el cual se
utilizan smbolos comodn (#). En la nueva definicin de esquema para
PG (Poli & Langdon) definen dos tipos de smbolos comodines: # ,
= ; donde los smbolos = indica una funcin o un terminal, mientras
que el smbolo # indica subrboles enteros, como ejemplo los
siguientes rboles son equivalentes:
Entonces un esquema H se define de una forma similar que en AG:
un esquema PG es un rbol con raz compuesto de nodos de un conjunto
F T
EMBED Equation.3 donde F y T son los conjunto de funciones y de
terminales utilizados en una corrida de PG, y el operador = es una
funcin polimrfica con tantas aridades como el nmero de aridades
diferentes de los elementos de F T, donde los terminales en T son
funciones de aridad cero.
Por ejemplo, sea el conjunto de funciones F = { +, * } y el
conjunto de terminales T = { a , b }, el esquema H = ( + ( * = a )
= ) representara cuatro programas:
Si un esquema posee rboles de tamao y forma constantes, aquel
esquema no contendr smbolos # , por lo tanto se obtendrn esquemas
de un rbol con el mismo tamao y forma. Con estas limitaciones se
definen los siguientes parmetros de forma similar como en la teora
de esquema de Holland:
El Orden O de un esquema H se define como el nmero de smbolos
diferentes de = ; la longitud N(H) seria el nmero total de nodos en
el esquema H; la longitud caracterstica L (H) es el nmero de
enlaces (aristas) en el fragmento del rbol mnimo que incluye todos
los smbolos diferentes de = dentro de un esquema H.
Por ejemplo:
De forma similar que en AG, un esquema PG con bajo orden y gran
longitud puede representar un nmero muy grande de programas, si el
orden O = 4 y la longitud N = 40, entonces se pueden obtener 2N-O =
236 = 68719476736 programas diferentes.4.2. Hiperespacio e
hiperplano[2]:
De forma similar como se trata en AG los hiperespacios e
hiperplanos se aplican en PG para comprender geomtricamente como
estn conformados los esquemas, para el modelo de Poli &
Langdon; un esquema G es un hiperespacio si el no contiene algn
nodo definido (es decir, O (G) = 0 ), un esquema H es un hiperplano
si el contiene al menos un nodo definido. Entonces el esquema G(H)
es el hiperespacio asociado con H, donde se han remplazado todos
los nodos definidos de H con smbolos comodines.
En la figura 5 se observa la interpretacin geomtrica de
hiperespacio, hiperplano y programa, donde todo el volumen
corresponde al hiperespacio G: { = ( =, =) }; si F = { -, +, * } y
el conjunto de terminales T = { x,y } ; entonces existirn 12
programas diferentes que corresponden a los doce vrtices de la
figura 5; por ejemplo, el nodo amarillo de la figura corresponder
al programa { + ( y, x ) } ( ver los ejes de coordenadas de la
figura) ; adems las aristas de los cubos indican hiperplanos de
orden O = 1, por ejemplo, la arista roja (punteada) corresponde al
esquema H1: { = ( y , x ) } y la arista azul (con guiones) equivale
a H2: { + ( = , x ) }; mientras que las caras correspondern a
hiperplanos de orden O = 2, por ejemplo, ambas caras de color verde
plido indica el esquema a H3: { = ( y , = ) }.
4.3. Mutacin de punto y cruce de un punto [11]:
El equivalente de la mutacin empleada en AG para PG, es la
mutacin punto que consiste de sustitucin de una funcin del rbol con
otra funcin de la misma aridad, o la sustitucin de un terminal con
otro terminal, lo anterior para conservar una sintaxis valida en el
nuevo rbol mutado. Y el equivalente del cruce de un punto en AG es
el operador con el mismo nombre pero aplicado en rboles (Poli &
Langdon) con tamao y forma constante; este operador se puede
sintetizar en tres pasos (igual que en AG):
Alineamiento de los rboles padres
Seleccin de una arista comn de cruce
Intercambio de subrboles para formar los hijos
El operador de cruce de un punto PG posee importantes
caractersticas que lo hacen diferente al cruce estndar; en ausencia
de mutacin el cruce de un punto conduce a la poblacin a la
convergencia (como en AG), esto es, los miembros de la poblacin
llegan a ser muy similares, y por lo tanto cada programa llega a
ser idntico con cada uno. Lo anterior se debe a que mientras una
proporcin lo suficiente grande de la poblacin tiene exactamente la
misma estructura en las partes superiores del rbol, la probabilidad
de seleccionar un punto de cruce en las partes bajas del rbol es
relativamente pequea, esto significa que mientras una estructura
comn emerge, el cruce de un punto conduce la bsqueda a un espacio
mucho ms pequeo de estructuras (partes superiores) de
aproximadamente de tamao fijo. Por eso, PG se comportara como una
bsqueda AG para una solucin parcial en un espacio de bsqueda
relativamente pequeo. Esto significa que el algoritmo converger
hacia una parte superior comn; por otra parte, el cruce en un punto
no incrementa la profundidad de los hijos mas all que el de sus
padres, y por eso no se incrementaran mas all de la profundidad
mxima de la poblacin aleatoria inicial, de forma similar sucede con
la disminucin de la profundidad. Por lo tanto la bsqueda de PG con
cruce en un punto esta limitada a un subespacio de programas
definidos por la poblacin inicial, y as, la creacin de la poblacin
inicial puede modificar significativamente su comportamiento.
Los hijos producidos por el cruce de un punto heredan la
estructura comn de las partes superiores de sus padres; as si se
cruza un programa consigo mismo se producir el mismo programa, esta
propiedad es una instancia de una propiedad general: los esquemas
PG son cercanos bajo cruce (es decir, cuando el cruce de un punto
es aplicado a dos programas del mismo esquema, el hijo producido
tambin ser del mismo esquema) conocida como respeto (respect,
Radcliffe en lgebra de AG[12]). Un operador de cruce respetuoso
hace seguro que los hijos hereden caractersticas comunes presentes
en los padres; esto tiene efecto en la reduccin del tamao del
espacio de bsqueda explorado por un AG en el tiempo; en presencia
de seleccin, esto le da a AG la habilidad de enfocar la bsqueda
hacia regiones del espacio de bsqueda que han mostrado una alta
aptitud.
Tambin el cruce de un punto hace que los clculos del modelo de
destruccin de esquemas en PG sean factibles, esto significa que es
posible estudiar en detalle sus efectos sobre diferentes clases de
esquemas y obtener un teorema del esquema.
4.4. Teorema del esquema para cruce de un punto:
Segn Poli & Langdon el teorema del esquema para un PG
generacional con seleccin proporcional a la aptitud, cruce de un
punto y mutacin de un punto es muy similar al obtenido para AG:
Donde la desigualad es debida al hecho de que se ignor la
creacin de eventos debido al cruce o mutacin, por lo tanto se
obtiene un limite inferior para el valor esperado del nmero de
individuos muestreados de un esquema H en la generacin t+1.
El trmino equivale a que es la probabilidad de que el esquema H
sea destruido cuando un programa h de H es cruzado con un programa
dado que no pertenezca al hiperespacio asociado con H. En otras
palabras, es la probabilidad de que luego del cruce de dos
programas (con diferente estructura o forma) el esquema del primer
rbol se pierda en los hijos. El termino se conoce como la
fragilidad de la forma de un esquema con respecto a las formas de
otros esquemas en la poblacin.
(2)
(3)
La ecuacin (2) es la probabilidad que pertenezca al hiperespacio
asociado con H, y la ecuacin (3) es la probabilidad que pertenezca
al esquema H.
El teorema de esquema para PG es considerablemente mas
complicado que el de AG, esto porque en PG los rboles tienen tamao
variable y forma durante la optimizacin, en la expresin esta
variabilidad de forma y tamao son cuantificada en el numerador de
(2) el cual resume las caractersticas de todos los programas en la
poblacin que tienen la misma forma y tamao en el momento en que el
esquema H se propaga. Por lo tanto, en PG la propagacin de un
esquema H depender de las caractersticas de los programas
muestreados, de los programas que tienen la misma estructura de H y
de la fragilidad de la forma del esquema H.
Segn Poli & Langdon el teorema de esquema antes nombrado
cuando se opera con cruce de un punto y mutacin de punto en las
primeras generaciones el teorema predice que la probabilidad de que
el esquema H sea destruido es muy grande, por lo tanto se dice que
el teorema en PG en las primeras etapas (generaciones) es
pesimista; mientras que cuando el nmero de generaciones es muy alto
PG con cruce de un punto tiende a comportarse como un AG, en otra
forma[2]:
La diferencia entre las expresiones del teorema del esquema para
PG y AG, es el termino que multiplica a, este ultimo esta formado
por dos partes lo que indica que en PG con cruce de un punto hay
dos competiciones; la primera sucede en las primeras generaciones
cuando hiperespacios diferentes G(H) compiten entre s; la segunda
competicin empieza cuando quedan pocos hiperespacios, es decir, se
consolidan ciertos hiperespacios en la poblacin y los hiperplanos
dentro de los pocos hiperespacios restantes empiezan a competir. En
esta fase PG tiende a comportarse ms y ms como un AG.
Poli y Langdon (5) han generado otros teoremas del esquema para
PG ms generales que el anterior, los cuales incluyen teoremas
exactos microscpicos (dependen de parmetros propios de los
individuos) y microscpicos (dependen de parmetros promedio de la
poblacin) para diferentes operadores de cruce (homologo, uniforme,
etc.)
5. Estructuras de datos y operadores en PG
Los mecanismos evolutivos se basan en 3 operadores principales:
seleccin, cruce y mutacin. Estos operadores trabajan en conjunto
con otros elementos; es as como en PG se debe contar con una
poblacin de expresiones simblicas significativas, parmetros de
control y una funcin de aptitud.
5.1. Mecanismo de codificacinEn toda actividad que necesite una
secuencia especial de pasos o tareas que llevar a cabo se tienen
algoritmos y programas de computador. La PG busca que
representaciones simples y primitivas de tareas sencillas
evolucionen en formas ms complejas y completas, que permitan
resolver el problema de mejor manera. La forma ms general de
representar estos programas es mediante funciones y parmetros. En
matemticas y lenguajes formales, una funcin es una representacin
simblica que recibe varios valores (parmetros) y les aplica varias
operaciones, luego de lo cual entrega un valor o resultado, que es
valor de la funcin.
Por ejemplo, la funcin suma a + b, o suma (a, b) simplemente
recibe dos parmetros (a y b) y despus de aplicarles el operador +
devuelve el resultado. En teora de compiladores y lenguajes
formales, los algoritmos y las funciones, se pueden visualizar y
representar por medio de rboles.
Un rbol es una estructura de datos, que se define como un
conjunto finito de nodos T tales que: a) Hay un nodo raz. B) Los
otros nodos se particionan en M conjuntos T1, T2, ..., TM. Los
conjuntos T1, T2, ..., TM son rboles y se llaman subrboles de T.
Cuando un rbol representa un programa, sus nodos internos
representan funciones u operaciones y las hojas representan
terminales o datos de entrada.
En PG los rboles se utilizan de un modo muy intuitivo y
sencillo: todo padre es una funcin u operacin, y sus hijos (los
cuales pueden ser ms de dos) son los parmetros u operandos. Claro
est que un hijo puede ser a la vez el resultado de la operacin
sobre otros elementos, es decir, un hijo puede ser tambin una
funcin. Si se tiene en cuenta que el resultado de aplicar una
funcin sobre sus parmetros devuelve un valor, entonces todo hijo
sigue de todos modos siendo un operando. Esto se comprende ms
fcilmente con un ejemplo. Supngase que se tiene el siguiente
algoritmo:
5.2. Conversin de rboles no binarios a binarios
Un caso particular de rboles es el de los rboles binarios, en
los cuales el nmero de hijos de cualquier nodo est limitado a dos
(subrbol izquierdo y subrbol derecho). En general, en las
aplicaciones se usa de esta clase de rboles debido a la forma de su
almacenamiento, que permite la relativa facilidad de implementacin
de sus operaciones y adems son estructuras muy estudiadas, por esta
razn en muchas aplicaciones se convierten rboles no binarios en
rboles binarios, como en este caso de la PG . De manera que
comenzamos con esta conversin.
Para realizar la conversin se siguen las siguientes reglas
[1]:
1. Los nodos hermanos se enlazan en forma horizontal.
2. El nodo raz se enlaza en forma vertical con el subrbol
izquierdo.
3. Para su visualizacin grfica se gira la estructura resultante
450.
Ejemplo:
Figura 11. Conversin de un rbol no binario a binario. A) Arbol
inicial. B) Arbol binario despus de aplicar las reglas 1 y 2. c)
Visualizacin del rbol binario despus del paso 3.
De manera que se pueden representar funciones de aridad mayor
que dos, como un rbol binario.
En los algoritmos que se presentan a continuacin, se supone que
las funciones solo tienen dos operadores y que el conjunto de
terminales es vlido para todas las funciones. Para casos en los
cuales el conjunto de funciones tiene ms de dos parmetros, se hace
la equivalencia a un rbol binario y cuando se selecciona una de
estas funciones, se toma el rbol binario equivalente. Para el caso
de los parmetros se debe incluir una restriccin para que la funcin
tome los parmetros de su tipo especfico.
5.3. Representacin y recorrido de rboles binariosLos rboles se
pueden representar en memoria esttica a travs de estructuras
arreglo o a travs de estructuras dinmicas. Aqu se trabajara el
manejo dinmico, el nodo de un rbol es:
Una operacin muy importante es el recorrido de los rboles
binarios. Recorrer un rbol significa visitar los nodos del rbol en
forma sistemtica, de esta manera se garantiza que se visitan todos
los nodos una sola vez.
La estructura rbol que se trabaja es la siguiente:
typedef struct tree
{
char info[20];
struct tree *izq;
struct tree *der;
}*arbol;
El campo tipo hace referencia a si el nodo sea un terminal o una
funcin.
Hay tres mtodos, recursivos, para hacer el recorrido de un
rbol:
Preorden: Raz, Subrbol Izquierdo, Subrbol Derecho.
Inorden: Subrbol Izquierdo, Raz, Subrbol Derecho.
Postorden: Subrbol Izquierdo, Subrbol Derecho, Raz.
Ejemplo:
PREORDEN: ABDHECFGIJK.
INORDEN: DHBEAFCIGKJ.
POSORDEN: HDEBFIKJGCA.
Figura 12 rbol binario del ejemplo para hacer los
recorridos.
Preorden (T)
Comienza
Crea_Pila(Tope)
p = T
Mientras ((Tope () V (p ())
Si ( p ()Entonces
Imprima *p.Info
Inser_Pila (Tope, p)
p 1)
s = *s.EnIzq
Sino
s = *s.EnDer
Fin-Si
Fin-Mientras
s = T
Crea_Pila(Tope)
Mientras ((Tope () V (s r))
q = s
Si ( s ()Entonces
Inser_Pila (Tope, s)
s = *s.EnIzq
Enlace = 0
Sino
Elim_Pila (Tope, s)
s = *s.EnDer
Enlace = 1
Fin-Si
Fin-Mientras
Genera_Subrbol(T1)
Si ( Enlace = 0)
*q.EnIzq = T1
Sino
*q.EnDer = T1
Fin-Si
n = n - 1
Fin-Mientras
Termina
5.5. Cruce de rbolesEl operador gentico ms importante en PG es
el de cruce. En cada generacin dos individuos de los ms aptos,
combinan su informacin gentica, formando dos nuevos individuos.
Estos dos cromosomas son padres de los dos nuevos individuos
formados al cruzarse entre s. Por ejemplo, si tenemos las dos
frases Me gusta dormir tarde los domingos y Mi padre habla acerca
del clima con mi novia y las cruzamos (partiendo de algunos lugares
aleatorios, denominado punto de cruce, como por ejemplo la cuarta y
sptima palabras), podramos obtener dos nuevas frases, con
significados diferentes (se deja al lector el cruce como
ejercicio). Lo importante aqu es notar cmo el cruce induce a la
variedad en una poblacin evolutiva, permitiendo con esto llegar a
soluciones, en muchas ocasiones excelentes, en otras pocas
realmente pobres. (vase el captulo 4, el Teora del Esquema para
PG).
En PG los elementos que se cruzan son programas. Una vez se
tiene una poblacin de rboles programa, se ejecutan y se mide la
aptitud de cada uno, con respecto al problema que se quiere
solucionar. Con base en esta medida de aptitud, se seleccionan los
rboles programa padres para la siguiente generacin. Hay varios
mtodos para hacerlo, que se pueden encontrar en la bibliografa de
AG, por lo que aqu no nos vamos a ocupar de ellos.
Inicialmente, se escoge aleatoriamente una pareja de individuos
para cruzar, y tambin aleatoriamente se escoge un punto en cada uno
de ellos un punto de cruce. Se hace un traslado completo de
subrboles de un rbol al otro y viceversa. Tomando la numeracin de
los nodos en preorden, se intercambian los subrboles. En las
figuras 4 y 5 vemos un ejemplo de cruce con dos programas muy
sencillos (cul sera el listado de cdigo de estos programas?). Los
nodos estn enumerados en preorden.
Los pasos para realizar el cruce de dos rboles programas en PG
son:
1. Seleccionar rboles a cruzar
2. Encontrar el nmero de nodos de cada rbol
3. Seleccionar el punto de cruce para cada rbol
4. Realizar el intercambio de subrboles por el punto de cruce
escogido en cada rbol.
Seleccionar rboles a cruzar
Se escogen de la poblacin de rboles seleccionados por su
aptitud, aleatoriamente dos rboles, T1 y T2.
Encontrar el nmero de nodos de cada rbol
Para cada rbol se cuenta el nmero de nodos que tiene con el
algoritmo Cuenta_Nodos (T,n). Se corre para T1 y T2, obteniendo
respectivamente el nmero de nodos n1 y n2.
Seleccionar el punto de cruce para cada rbol
Con base en n1, se escoge un punto de cruce c1 para T1 y con
base en n2, se escoge un punto de cruce c2 para T2. Se recorre cada
rbol hasta el punto de cruce, encontrando el apuntador a ese nodo.
Esto se hace con el algoritmo Punto_Cruce (T, c, q) que obtiene el
apuntador q que direcciona el nodo c y la variable. Ind_Enlace nos
indica porque subrbol de q.Punto_Cruce (T, c, q, Ind_Enlace)
Comienza
Crea_Pila(Tope)
p = T
n = 1
Sw = F
Mientras ( ((Tope () V (p ()) ( (-Sw))
Si ( p ()Entonces
q = p
Inser_Pila (Tope, p)
p = *p.EnIzq
Si (p ()
n = n + 1
Ind_Enlace = 1
Si (n = c)
Sw = V
Fin-si
Fin-si
Sino
Elim_Pila (Tope, p)
p = *p.EnDer
Si (p ()
n = n + 1
Ind_Enlace = 2
Si (n = c)
Sw = V
Fin-si
Fin-si
Fin-Si
Fin-Mientras
Termina
Realizar el intercambio de subrboles
Una vez se tiene el apuntador de cada punto de cruce en su
respectivo rbol, se intercambian los apuntadores, realizndose de
esta manera el cruce.
.
Cruza_rboles(T1,T2) Comienza
Cuenta_Nodos (T1,n1).
Cuenta_Nodos (T2,n2)
c1 = random(n1) +1
c2 = random(n2) +1
Punto_Cruce (T1, c1, q1, Ind_Enlace1)
Punto_Cruce (T2, c2, q2, Ind_Enlace2)
Si ( Ind_Enlace1 = 1)
*q1.EnIzq = c2
Sino
*q21.EnDer = c2
Fin-si
Si ( Ind_Enlace2 = 1)
*q2.EnIzq = c1
Sino
*q2.EnDer = c1
Fin-si
Termina
5.6. Mutacin y seleccinLos algoritmos de mutacin son
equivalentes a los utilizados en el cruce (bsqueda del nodo) con la
diferencia de que se debe cambiar el nodo objetivo por otro. Hay
que tener la precaucin de cambiar una funcin de i parmetros por una
equivalente con los mismos parmetros y tipo, o una constante o
variable por otra constante o variable.
6. Ejemplo de PG: Regresin Simblica
El problema de regresin simblica consiste en obtener una funcin
algebraica que ajuste en gran medida un conjunto de datos
experimentales. Similar a la muy conocida regresin por mnimos
cuadrados, la diferencia es que en regresin simblica no se conoce
el formato de la funcin a ajustar, por lo tanto se debe obtener la
funcin y los coeficientes ptimos que ajusten los datos
experimentales.
Desde los datos experimentales se puede reconocer las variables
dependientes e independientes del problema, en el caso de la figura
13 existe una variable dependiente (y) y dos independientes (x1 ,
x2 ); entonces el conjunto de terminales del problema PG (ver
figura 13) sern las variables independientes y los coeficientes de
la funcin a ajustar. El conjunto de funciones se puede limitar a
las funciones elementales:{+,*,/,-}. Ntese que el rbol como
programa se ejecuta cuando se evala el modelo algebraico con los
terminales como entradas.
La funcin de aptitud ser entonces un indicativo que permite
premiar a los individuos ( rboles) que se ajustan mejor a los datos
experimentales; para hallar una funcin de aptitud til se puede
utilizar el error absoluto (diferencia de valores evaluados con el
modelo supuesto y datos experimentales), el cual disminuye para los
rboles mas aptos, luego, ese error ser inversamente proporcional a
la aptitud. Por lo anterior se plantea la siguiente funcin de
aptitud:
(4)
La ecuacin (4) indica que la aptitud del i-simo rbol es igual al
inverso de la suma de errores absolutos (donde es el valor del
j-simo dato experimental evaluado en las variables independientes;
mientras que, es el valor evaluado en el i-simo rbol ); por lo
tanto si el error es pequeo la aptitud ser muy grande. Pero si el
error es cero, el valor de la funcin de aptitud tender a infinito,
entonces en la prctica se evita esto colocando en el denominador un
numero relativamente pequeo para fijar un limite superior:
(5)
Entonces la ecuacin (5) tendr como mxima aptitud el valor de 10
(para un error de cero).
Los parmetros de control de PG pueden ser fijados con valores
recomendados [7] (Probabilidad de cruce = 0.7 ; probabilidad de
mutacin 0.01; tamao de la poblacin= 100, generaciones = 500,
Criterio de seleccin = elitismo [4] ). Por lo tanto el sistema de
PG se detendr cuando se cumpla el numero de generaciones y la
solucin ser el rbol con mejor aptitud.
Durante las generaciones y gracias al operador de cruce es muy
probable que los rboles empiecen a crecer de forma desenfrenada
provocando rboles muy largos con muy poco aporte en el incremento
de la aptitud ( hinchamiento, en ingles bloat ), por lo tanto es
conveniente fijar un tamao mximo para el tamao de los rboles de la
poblacin (o incluso el cruce de un punto evita que los rboles
crezcan (ver capitulo 4)).
En la figura 14 se puede observar como vara la aptitud (del
mejor individuo) a travs de las generaciones , al final se obtiene
una aptitud de 2.53456 con la siguiente expresin como solucin:
7. Conclusiones
En este tutorial se ha expuesto la PG como aplicacin de los
principios de evolucin darwiniana al campo de la informtica,
especficamente al del diseo de programas de computador. Esta PG
esta basada en los mismo principios de los AG: se tiene una
poblacin de individuos cada cual es una posible solucin para un
problema dado, a los cuales es posible encontrarles una medida de
su comportamiento, es decir de su aptitud, y se aplica sobre ellos
un proceso evolutivo artificial mediante operadores de seleccin ,
cruce y mutacin. Al cabo de muchas generaciones se encontrar un
individuo idneo, o sea, una solucin al problema. La gran diferencia
de este tipo de programacin esta basada en el significado del cdigo
gentico de cada individuo.
Mientras que AG cada cromosoma representa una solucin que debe
ser codificada antes de poder ser evaluada , en la PG el cromosoma
en si es un programa sintcticamente valido y ejecutable en un
computador. Para lograr esto, los programas deben representarse
como una estructura adecuada para permitir las operaciones
genticas, de otro modo, rpidamente se convertiran en un montn de
cdigo inservible que de se ejecutado causaran problemas de ejecucin
en la maquina.
Tambin se expuso el teorema del esquema para PG con ciertas
limitaciones (cruce de un punto, mutacin de un punto ) que permiten
comprobar la convergencia de PG para resolver un problema, de una
forma similar como sucede en AG.
Por las propiedades robustas de la PG en solucionar problemas
difciles su utilidad en problemas de ingeniera, economa, medicina,
msica, etc, es notable.
8. Bibliografa
[1] Martnez J y Rojas S. Introduccin a la informtica Evolutiva.
Bogot, Colombia: Universidad Nacional de Colombia. Primera Edicin.
1999.[2] Langdon W.B y Poli R, Foundations of Genetic Programming .
Berlin: Springer-Verlag, 2002.
[3] Michalewicz Z, Genetic Algorithms+Data Structures=Evolution
Programs . Berlin: Springer-Verlag, 1994..
[4] Goldberg D, genetic Algorithms in search, optimization and
Machine learning. Massachusetts: Addison-Wesley,Reading, 1989.
[5] Gen M y Cheng R, Genetic Algorithms and engineering design.
New York: John Wiley & Sons, 1997.
[6] McKay B., Willis M y Barton G, Steady-state modelling of
chemical process systems using genetic programming, Comp & Chem
Eng., vol 21, no 9, pp. 981-996, 1997.
[7] Koza J, Genetic Programming, on the programming of computers
by means of natural selection. The MIT Press, 1992
[8] Poli R y Langdon W.B. Schema theory for genetic programming
with one-point crossover and point mutation. Evolutionary
Computation, 6(3): 231-252, 1998
[9] Poli R y Langdon W.B. Exact schema theorems for GP with
one-point crossover and standard crossover operating on linear
structures and their application to the study of the evolution of
size. En Genetic Programming, Proceedings of the Genetic and
Evolutionary Computation Conference (GECCO 2001), San Francisco,
California, USA, 7-11 Julio 2001. Morgan Kaufmann.
[10] Poli R, Rowe J y McPhee N. Markov chain models for GP and
variable-length GAs with homologous crossover. En Genetic
Programming, Proceedings of the Genetic and Evolutionary
Computation Conference (GECCO 2001), San Francisco, California,
USA, 7-11 Julio 2001. Morgan Kaufmann.
[11] Poli R. Exact schema theory for genetic programming and
variable-length genetic algorithms with one-point crossover.
Genetic Programming and Evolvable Machines, 2(2):123-163, junio
2001.
[12] Radcliffe N. The algebra of genetics algorithms. Annals of
Maths and Artificial Intelligence, 10:339-384, 1994.
Figura 1. Estructura general de programacin gentica
Figura 5. Espacio de bsqueda. Los cuadros indican los esquemas o
subespacios.
subespacio
Figura 6. Ejemplo de notacin de Poli & Langdon para esquemas
en PG
Figura 7. rboles de un solo esquema
Figura 8. Ejemplos de orden, y longitud caracterstica de
esquemas
Figura 9. Hiperespacio, hiperplanos, programas
Figura 10. cruce de un punto, se observa que la profundidad de
los hijos no cambia respecto a los padres, las aristas punteadas es
el resultado del alineamiento de los padres, la arista con la lnea
roja es el punto de cruce
Figura 12. Otro ejemplo del operador de cruce
Figura13. Representacin en rbol de un modelo supuesto para un
conjunto de datos experimentales. Los nodos grises son los
terminales y los nodos blancos las funciones
EMBED Word.Picture.8
Figura 14. Aptitud(ecuacin 5) para el rbol de la figura 13, para
a = 0.5 y b = -1
Figura 14. Historia de la aptitud para regresin simblica
e-mail: [email protected]
e-mail: [email protected]
125
_1125862035.unknown
_1125862047.unknown
_1125862051.unknown
_1125864295.unknown
_1128424807.unknown
_1128424876.unknown
_1128433578.unknown
_1128424833.unknown
_1128424298.unknown
_1128424797.doc
y*
x1
x2
0
3
2
0,5
2
1
1
1,5
0,6
2
3
0,5
2,5
8
0,1
5
8,5
-1
Experimentales
Modelo
supuesto
representacin
en rbol
Datos
+
b
*
+
a
X
2
X
1
b
x
x
a
y
2
1
_1125862054.unknown
_1125862055.unknown
_1125862052.unknown
_1125862049.unknown
_1125862050.unknown
_1125862048.unknown
_1125862043.unknown
_1125862045.unknown
_1125862046.unknown
_1125862044.unknown
_1125862041.unknown
_1125862042.unknown
_1125862036.unknown
_1125862031.unknown
_1125862033.unknown
_1125862034.unknown
_1125862032.unknown
_1125862029.unknown
_1125862030.unknown
_1125862027.unknown
