Programación de expresiones de genes

En programación, programación de expresión de genes (PEG) es un algoritmo evolutivo que crea programas o modelos. Estos programas son complejas estructuras arbóreas que aprenden y se adaptan por el cambio de sus tamaños, formas y composición, muy parecido a un organismo vivo. Como organismos vivos, los programas de PEG eran codificados en simple cromosomas de tamaños fijos. Como, PEG es un sistema genotipo-fenotipo, beneficiado de un simple genoma para mantener y trasmitir información genética y un fenotipo complejo para explorar el ambiente y adaptarse.

Historia

Algoritmos evolutivos usa poblaciones de individuos, selecciona individuos de acuerdo a la aptitud, e introduce variación genética usando uno o más operadores genéticos. Su uso en los sistemas computacionales artificiales data de 1950 donde eran usados para resolver problemas de optimización (e.g. Box 1957[1] and Friedman 1959).[2] Pero fue con la introducción de estrategias evolutivas by Rechenberg in 1965[3] que los algoritmos evolutivos ganaron popularidad. Un buen texto sobre algoritmos evolutivos es el libro “An Introduction to Genetic Algorithms” by Mitchell (1996).[4]

Programación de expresión de genes[5] pertenece a la familia de los algoritmos evolutivos y está estrechamente relacionado con algoritmos genéticos y programación genética. De los algoritmos genéticos heredó los cromosomas lineales de tamaño fijo; y de la programación genética la expresividad de los árboles de parseo de variados tamaños y formas.

En la programación de expresión de genes los cromosomas lineales trabajan como el genotipo y los árboles de parseo como el fenotipo, creando un sistema genotipo/fenotipo. Este sistema genotipo/fenotipo es multigen, poniendo múltiples árboles de parseo codificados en cada cromosoma. Esto significa que los programas creados por PEG están compuestos por múltiples árboles de parseo. Porque estos árboles de parseo son el resultado de expresiones genéticas, en PEG son llamados árboles de expresión es.

Codificación: el genotipo

El genoma de la programación de expresión de genes consiste en una cadena linear, simbólica, cromosomas tamaño fijo compuesto de uno o más genes de igual tamaño. Estos genes, a pesar de su tamaño fijo, están codificados por árboles de expresión de diferentes tamaños y formas. Un ejemplo de un cromosoma con dos genes, cada uno de tamaño 9, es la cadena.

012345678012345678
L+a-baccd**cLabacd

donde

“L” representa la función logaritmo y “a”, “b”, “c”, y 

“d” representa la variables and constantes usadas en el problema.

Árboles de Expresión: el fenotipo

Como se ve above, los genes de programación de expresión de genes tienen todos el mismo tamaño. Como sea, estos códigos de cadenas de tamaño fijo para arboles de expresiónes de tamaños diferentes. Esto significa que las regiones de codificada varia de gen a gen, permitiendo que la adaptación y la evolución ocurran fácilmente.

Por ejemplo, la expresión matemática:

puede ser representada como un árbol de expresiones:

donde “Q” representa la función raíz cuadrada.

Este tipo de árboles de expresión consiste en la expresión del fenotipo de los genes PEG, donde los genes son cadenas lineales que codifican estas complejas estructuras. Para este ejemplo en particular, la cadena lineal corresponde a:

01234567
Q*-+abcd

el cual es la lectura directa del árbol de expresión desde arriba hacia abajo desde la izquierda hacia la derecha. Estas cadenas lineales son llamadas k-expresiones (from Karva notation).

Yendo desde k-expresiones a árboles de expresión es muy sencillo. Por ejemplo, la siguiente k-expresión:

01234567890
Q*b**+baQba

es está compuesto de dos diferentes terminales (la variable “a” y “b”), 2 funciones diferentes de 2 argumentos (“*” y “+”), y una función de un argumento (“Q”). Su expresión:

K-expresiones y genes

Las k-expresiones de PEG corresponde a la región de genes que queda expresada. Esto significa que puede haber secuencias en los genes que no son expresadas, lo cual es verdadero para la mayoría de los genes. La razón de estas regiones no codificadas es proveer un buffer de terminales para que todas las k-expresiones codificadas en genes de PEG corresponda siempre a programas válidos o expresiones.

Los genes de PEG por tanto están compuestos de 2 diferentes dominios –cabeza y una cola – cada uno con diferentes propiedades y funciones. La cabeza es usada principalmente para codificar las funciones y variables escogidas para resolver el problema, considerando la cola, mientras también se usa para codificar las variables, proporciona un depósito de términos esencialmente para asegurar que todos los programas son libres de errores.

Para genes de PEG el largo de las colas es dado por la fórmula:

donde h es el largo de la cabeza y nmax es la aridad máxima. Por ejemplo, para un gene creado usando el conjunto de funciones F = {Q, +, −, *, /} y el conjunto de terminales T = {a,

b}, nmax = 2. Si escogemos el largo de una cabeza
es de 15, entonces t = 15 (2 − 1) + 1 = 16, donde el largo del gen 

g de 15 + 16 = 31. La cadena generada aleatoriamente abajo es un es un ejemplo de estos genes:

0123456789012345678901234567890
*b+a-aQab+//+b+babbabbbababbaaa

Se codifica el árbol de expresión:

en este caso, solo se usa 8 de los 31 elementos que constituye el gen.

No es difícil ver esto, a pesar de su tamaño fijo, cada gen tiene

el potencial para codificar por árboles de expresión de diferentes tamaños y formas, 

con un único nodo (donde el primer elemento de un

gen es un terminal) y el más grande compuesto de tantos nodos como    

los elementos en el gen (donde todos los elementos en la cabeza son funciones con máxima aridad).

No es difícil de ver que es trivial implementar todo tipo de modificaciones genéticas ([[mutación ( algoritmos genéticos)|mutación]], inversión, inserción, [[crossover (algoritmos genéticos)|recombinación]], y así) con la garantía que todos las descendencias resultantes ponen código correcto, programas libres de errores.

Multigenético cromosomas

Los cromosomas de PEG están usualmente compuestos de más de un gen de igual tamaño. Cada código por un árbol

de sub-expresión (sub-ET) o sub-programa. Entonces el sub-ETs puede interactuar ellas 

en diferentes maneras, formando un programa más complejo. La figura muestra un programa compuesto de tres sub-ETs.

[[Image:Expresión d 3 genes de PEG, 1st k-expression

  • Qb+*-bbba.png|thumb|Expression of GEP genes as sub-ETs. a) A

three-genic chromosome with the tails shown in bold. b) The sub-ETs encoded by each gene.]]

En el programa final el sub-AEs puede ser enlazado por adición o otra función, Como no hay restricciones para la función de enlace. Algunos ejemplos de enlaces más complejos incluye

el promedio, la mediana, clasificación binomial, aplicando la función sigma para 

calcular la probabilidad y más. Estas funciones son usualmente escogidas antes para cada problema, pero ellas pueden estar evolucionando elegantemente

y eficientemente por el cellular system[6][7] of 

gene expression programming.

Celdas y reutilización de código

En PES, homeotic genes controlan las interacciones de los diferentes sub-AEs o módulos del programa principal. La expresión de esos genes resultantes en diferentes programas o celdas, eso es, ellos

determinan cuales genes son expresados en cada celda y como el sub-AEs de
cada celda interactúa con otro. En otras palabras, genes homéoticos 

determinan cual sub-AEs se llama y que a menudo en el programa o celda y que tipo de conexiones ellos establecen con otra

Genes Homéoticos y el sistema celular

Genes homéoticos tienen exactamente el mismo tipo de organización estructural de genes normales y son construidos igualmente. Ellos también contienen un dominio cabeza y uno cola, con la diferencia que las cabezas contienen funciones de enlace y un tipo especial de terminales – genes terminales – que representan genes normales. La expresión de los genes normales resultan como es usual en diferentes sub-AEs, los cuales en sistemas celulares son llamados FDAs (funciones definidas automáticamente). Para las colas, contienen solo genes terminales, así es, derivado de característica generadas en el aire por el algoritmo.

Por ejemplo, el cromosoma en al figura tiene 3 genes normales y un

gen homeotico y codifica un programa que invoca 3 funciones 

diferentes 4 veces, enlazándolas en un camino en particular.

[[Image:Expression of a unicellular GEP system with three ADFs.png|thumb|Expression of a unicellular system with three ADFs. a) The chromosome composed of three conventional genes and one homeotic gene (shown in bold). b) The ADFs encoded by each conventional gene. c) The main program or cell.]]

De este ejemplo queda claro que el sistema celular no solo permite la evolución de las funciones sino también el reutilización de código. Y no debe ser difícil de implementar [[Recursión (computer Science)|recursion]] en el sistema.

Múltiples programas y sistemas multicelulares

Sistemas multicelulares están compuestos más de un homeotic gene. Cada

Gen homeotico en este sistema pone diferentes combinaciones of 

Sub-árboles de expresiones, creando múltiple celdas o programas.

Por ejemplo, el programa mostrado en la figura fue creado usando un sistema celular con dos celdas y 3 genes normales.

[[Image:Expression of a multicellular GEP system with 3 ADFs and 2 main programs.png|thumb|Expression of a multicellular system with three ADFs and two main programs. a) The chromosome composed of three conventional genes and two homeotic genes (shown in bold). b) The ADFs encoded by each conventional gene. c) 2 programas diferentes expresados en 2 celdas diferentes.]]

La aplicación de estos sistemas multicelulares es múltiples y variadas and, como la multigenic systems, pueden ser usadas las dos en problemas con

solo una salida y con múltiples salidas.

Otros niveles de complejidad

El dominio cabeza\cola de genes PEG es el básico bloque construido de todos los algoritmos PEG . Como sea, PEG también explora otras organizaciones que son más complejas que la cabeza\cola. Esencialmente estas estructuras complejas consiste en unidades funcionales o genes con una cabeza\cola básico más uno o más dominios. Estos dominios extras usualmente codifican constantes aleatorias numéricas que los algoritmos implacablemente bien-melodías para encontrar una buena solución. Estas constantes numéricas pueden ser los pesos o factores en una función aproximación del problema (see the GEP-RNC algorithm below); pueden ser los pesos y pedazos de una red neuronal (see the [[gene expression programming#Neural networks|GEP-NN algorithm]] below); las constantes numéricas necesitan para el diseño de árboles de decisión (see the [[gene expression programming#Decision trees|GEP-DT algorithm]] below); los pesos se necesitan para inducción polinomial; o las contantes numéricas aleatorias usadas para descubrir los valores de los parámetros en una tarea de optimización.

Algoritmo básico de expresión de genes

Los pasos fundamentales de Algoritmo básico de expresión de genes están puestos abajo en pseudocode:

1. Select function set;
2. Select terminal set;
3. Load dataset for fitness evaluation;
4. Create chromosomes of initial population randomly;
5. For each program in population:
a) Express chromosome;
b) Execute program;
c) Evaluate fitness;
6. Verify stop condition;
7. Select programs;
8. Replicate selected programs to form the next population;
9. Modify chromosomes using genetic operators;
10. Go to step 5.

Los primeros 4 pasos todo lo necesario para el

el ciclo del algoritmo (paso 5 hasta 10). De esos 

pasos preparativos, el crucial es la creación de la población inicial, la cual es creada aleatoriamente usando los elementos de la función

y los conjuntos terminales.

Poblaciones de programas

Como todos los algoritmos evolutivos, PEG trabaja con

poblaciones de individuos, los cuales en este caso son programas. 

Por tanto algún tipo de población inicial tiene que ser creada . poblaciones de subsecuencias son descendientes, vía selection y genetic modification, de la población inicial.

En el sistema fenotipo/genotipo de PEG, es necesario para crear la línea de cromosomas lineales de los individuos sin preocuparse acerca de la estructura de los programas para los que ellos codifican, como su expresión termina en programas sintácticamente correctos.

funciones de precisión y los ambientes de selección

funciones de precisión y los ambientes de selección(llamado conjunto de datos de entrenamiento en machine learning) las 2 facetas de precisión y están por tanto

conectados. De hecho, la precisión de un programa depende no 

solo de la función costo usada para medir su comportamiento pero también en los datos de entrenamiento escogidos para evaluar precisión

El ambiente de selección o los datos de entrenamiento

La selección de ambientes consiste en el conjunto de entradas de entrenamiento, los cuales

son también llamados casos de precisión. Esos pueden ser in conjunto de 

observaciones acerca de algún problema, y forma lo

conjunto de datos de entrenamiento.

La calidad del conjunto entrenante es esencial para la evolución de buenas Soluciones. Un buen conjunto entrenante debiera ser representativo del problema

Y también bien-balanceado, por otro lado el algoritmo pudiera quedar estancado 

En algún óptimo local. Además, es importante evitar usar innecesariamente conjuntos grandes para entrenar como esto pondrá lento las cosas innecesariamente. Una buena regla es escoger suficientes entradas para entrenar para habilitar una buena generalización en los datos validados y dejar las entradas restantes para testear.

Funciones de precisión

Ampliamente hablando, hay esencialmente 3 diferentes tipos de problemas basados en el tipo de precisión hecha:

1. predicciones numéricas (continuas) ;
2. predicciones categóricas o nominales, ambas binomiales
y multinomiales;
3. predicciones binarias o Booleanas.

selección y elitismo

selección Rueda de la ruleta es quizás el más popular esquema de selección

usado en computación evolutiva. Envuelve la precisión
de cada programa a un pedazo de la Rueda de la ruleta proporcional a su 

precisión. Entonces la ruleta es hilada a tantas veces como haya programas en la población para mantener el tamaño constante. Entonces, con programas de selección de Rueda de la ruleta son ambos seleccionados de acuerdo a la precisión la suerte del empate, lo que significa que alguna veces los mejores rasgos pueden perder. Como sea, por combinar selección Rueda de la ruleta con el clonado el mejor programa de cada generación, esto garantiza que al menos el mejor rasgo no se pierde. Esta técnica de duplicado de programas la mejor-de-su-generación es conocido como simple elitismo y es

usado por la mayoría de los esquemas de selección estocástica.

Reproducción con modificación

La reproducción de programas involucra primero la selección y después la reproducción de sus genomas. modificación de genes no es requerido por la reproducción, pero sin su adaptación y evolución no tiene lugar.

Replicado y selección

la selección de operadores selecciona el programa para la replicación de operadores

para copiar. Dependiendo del esquema de selección, el número de copias que un 

programa origina puede variar, con algunos programas siendo copiados más de

una vez mientras otros son copiados solo una vez o ninguna. Además, 

selección es usualmente preparado para que el tamaño de la población quede constante

de una generación a otra.

la replicación de genomas en la naturaleza es muy complicado y toma a los científicos largo tiempo descubrir DNA double helix y propone un

mecanismo para su replicación. Pero la replicación de cadenas es 

trivial en sistemas evolutivos artificiales, donde solo una instrucción para

copiar cadenas se requiere pasar toda la información en el genoma de
generación a generación.

La replicación de programas seleccionados es una pieza fundamental de todos los sistemas evolutivos artificiales, pero para que la evolución ocurra se necesita que este implementado no con la precisión usual de una instrucción de copia, pero más bien con un poco de errores. De hecho, diversidad genética es creada

con operadores genéticos Como [[Mutación (genetic 

algorithm)|mutation]], recombination, transposition, inversión, y muchos otros.

Mutación

En mutación de PEG es el operador genético más importante .[8] Cambia genomas cambiando un elemento con otro. La acumulación de muchos pequeños cambios en el tiempo puede crear gran diversidad.

En mutación PEG es totalmente unconstrained, lo cual significa que en cada dominio del gen cada símbolo puede ser reemplazado por otro. Por ejemplo, en la cabeza de los genes cualquier función puede ser reemplazada

Por un terminal o otra función, indiferente del número de  

argumentos en la nueva función; y un terminal puede ser reemplazado por una función u otro terminal.

Recombinación

Recombinación usualmente involucra 2 pares de cromosomas para crear 2 nuevos cromosomas por combinar diferentes partes de los cromosomas padres. Y tan largo como los cromosomas padres

estén alineados y el fragmento intercambiado es homólogo (ocupa
la misma posición en el cromosoma), el nuevo cromosoma creado por 

recombinación siempre codificará sintácticamente programas correctos.p

Diferentes tipos de cruzamientos son fácilmente implementados ya por cambiar el número de padres involucrados; el número de puntos; la manera en que se escoge intercambiando

los fragmentos, por ejemplo, incluso aleatoriamente o en algún orden.Por
ejemplo, recombinación de genes, que es un caso especial de recombinación, 

puede hacerse intercambiando genes homólogos o intercambiando genes escogidos aleatoriamente de

cualquier posición en el cromosoma.

Transposición

Transposition involucra la introducción de una inserción secuencia en cualquier parte del cromosoma. En PEG la secuencias pueden aparecer donde quiera en el cromosoma,

pero solo se inserta en la cabeza de los genes. Este método 

garantiza que incluso secuencias de la cola resulta en

programas error-libre.

Para que la transposición trabaje bien, se tiene que preservar el tamaño de los cromosomas y la estructura del gen. Entonces, en la transposición PEG puede

ser implementada usando 2 métodos diferentes: el primero crea un cambio 

en el sitio de inserción, seguido de un borrado en el final de la cabeza; el segundo sobrescribe la secuencia local en el sitio y además es más fácil de implementar.

Inversión

Inversión es un operador interesante, especialmente poderoso por su optimización combinatoria.[9] Consiste en invertir una secuencia pequeña sin

un cromosoma.

En PEG puede ser fácilmente implementado en todo el dominio

y, en todos los casos, la descendencia producida es siempre 

sintácticamente correcta. por cualquier dominio, una secuencia es escogida aleatoriamente sin ese dominio y después invertida.

El algoritmo GEP-RNC

Constantes numéricas son elementos esenciales de matemática y modelos estadísticos y además es importante permitir su integración en el modelo designado por los algoritmos evolutivos.

PEG resuelve este problema elegantemente a través el uso de un dominio extra – the Dc – para manejar constantes numéricas

aleatorias . Combinando este dominio con un terminal especial 

por el RNCs, un sistema expresivo es creado.

Estructuralmente, el Dc viene después de la cola, tiene un tamaño igual al de la cola t, y está compuesto de los símbolos usados para representar

el RNCs.

El RNCs se le conoce para la modificación genética

Por ejemplo, abajo se muestra un simple cromosoma compuesto de un solo gen y una cabeza de tamaño 7 (the Dc stretches over positions 15–22):

01234567890123456789012

cromosoma es expresado exactamente como se muestra [[gene expression programming#Expression trees: the phenotype|above]], giving:

Entonces el ?’s en el árbol de expresión es reemplazada de izquierda a derecha y de arriba a abajo por los símbolos en el Dc, dando:

Los valores que corresponden a esos símbolos se mantienen en el array. (Por simplicidad, el número representado por el numerador indica el orden en

el array.) Por ejemplo, para los siguientes 10 elementos de RNCs:
C = {0.611, 1.184, 2.449, 2.98, 0.496, 2.286, 0.93, 2.305, 2.737,

0.755}

El árbol de expresión brinda:

Esta estructura para manejar constantes numéricas aleatorias es el

corazón de diferentes sistemas PEG , como [[PEG 
  1. redes neuronales|GEP redes neuronales]] and GEP decisión trees.

Como la basic gene expression algorithm, el algoritmo GEP-RNC es también multigenetico y sus cromosomas son decodificados usualmente para expresar un gen atrás de otro y después enlazándolos todos juntos pro el mismo tipo de proceso de enlazado.

Los operadores genéticos usados en el ssitema GEP-RNC son una extensión para los

operadores genéticos del algoritmo básico de PEG (ver [[gene expression 

programming#Reproduction with modification|above]]), y todos pueden ser

directamente implementado en esos nuevos cromosomas. Por otro lado 

, los operadores básicos de mutación, inversión, transposición, y recombinación también son usados en el algoritmo GEP-RNC. Además, operadores especiales de Dc-específico como mutación, inversión, y transposición, son usados para ayudar en una circulación eficiente de el RNCs evitando programas individuales. Incluyendo, existe una operador de mutación especial que permite la introducción permanente de variaciones en el conjunto de RNCs. El conjunto inicial de RNCs creado aleatoriamente al principio de una corrida, lo que significa, para cada gen en la población inicial , un número específico de constantes numéricas, escogidos de cierto rango, son generados aleatoriamente. Entonces la circulación y la mutación es habilitados por los operadores genéticos.

Redes neuronales

en redes neuronales artificiales (ANN o NN) es un componente computacional que consiste de muchas unidades simples conectadas o neuronas. las conexiones

entre las unidades son usualmente con peso asociados a valores reales. Estos 

pesos el significado primario de aprendizaje en redes neuronales y un algoritmo de aprendizaje es usualmente usado para ajustarlos.

Estructuralmente, una red neuronal tiene tres clases diferentes de unidades: unidades de entrada, unidades ocultas y unidades de salida. Un patrón de activación esta presentado en las unidades de entrada y después esparce en adelante desde las unidades de entrada a través de una o más capas de unidades ocultas para las unidades de salida. La activación entrante dentro una unidad a otra es multiplicada por el peso en los enlaces de los cuales se esparce.Todas las activaciones entrantes son añadidas juntas y la unidad se convierte en activada solo si los resultados están por debajo del umbral de las unidades.

En resumen, los componentes básicos de una red neuronal son las unidades, las conexiones entre ellas, los pesos y los umbrales. Entonces, para simular completamente una red neuronal artificial tiene de alguna manera codificar estos componentes en un cromosoma linear y después ser capaz de expresarlos en una manera con sentido.

En redes neuronales PEG (GEP-NN o GEP nets), la arquitectura de la red es

codificada la estructura usual de dominio cabeza\cola.[10] la cabeza contiene funciones\neuronas especiales
que activan las ocultas y las de salida ,
los terminales representan las unidades de entrada. La cola 

contiene solo unidades terminales/entrada.

Además de la cabeza y la cola, esas redes neuronales genéticas contienen 2 dominios adicionales, Dw y Dt, para codificar los pesos y los umbrales de las redes. Estructuralmente, el Dw viene después de la cola y su

tamaño dw depende del tamaño de la cabeza h y
la aridad máxima nmax y es evaluado por la 

formula:

EL Dt viene después de Dw y tiene tamaño dt igual a t. Ambos dominios están compuestos de símbolos representando el peso y los umbrales.

Por cada gen NN, los pesos los umbrales son creados al principio de cada corrida, pero su circulación y adaptación son garantizados por el operador genético usual de [[PEG

  1. Mutation|mutation]], [[gene expression

programming#Transposition|transposition]], [[gene expression programming#Inversion|inversion]], and [[gene expression programming#Recombination|recombination]]. Además, operadores especiales son también usados para permitir un flujo constante de variaciones genéticas en

el conjunto de pesos y umbrales.

Por ejemplo, abajo se muestra una red neuronal con 2 unidades de entrada (i1 and i2), 2 unidades ocultas (h1 and h2), and one output unit (o1). Tiene un total de 6 conexiones con 6 pesos correspondientes representados por los números 1-6:

Esta representación es la canónica, pero las redes neuronales pueden ser también representad por un árbol, el cual, en este caso, corresponde a:

donde “a” y “b” representa las 2 entradas i1

y i2 y “D” representa una función con 

conectividad 2. Esta función añade todos sus argumentos con peso y después

los umbrales, para determinar la salida. 

Esta salida (0 o 1 en este caso) depende del umbral de cada unidad, eso es, si el activación entrante total es mayor o igual que el umbral, entonces la salida es 1, 0 en otro caso.

El NN-árbol de abajo puede ser linealizado como:

0123456789012
DDDabab654321

donde la estructura en la línea 7–12 (Dw) codifica los pesos. Los valores de cada peso son dejados en un array y se devuelve como sea necesario para la expresión.

Un ejemplo más concreto, se muestra un gen de red neuronal por el exclusive-or problema. Tiene cabeza de tamaño 3 y Dw de tamaño 6:

0123456789012
DDDabab393257

La expresión resultante en la red neuronal siguiente:

el cual, por el conjunto de pesos:

W = {−1.978, 0.514, −0.465, 1.22,

−1.686, −1.797, 0.197, 1.606, 0, 1.753}

es dado:

el cual es una solución perfecta para la función exclusive-o.

Además de funciones simples booleanas con entrada binarias y salidas binarias, el algoritmo GEP-nets puede manejar todo tipo de funciones o neuronas También es interesante que el algoritmo GEP-nets puede usar todas esas neuronas juntas y dejar que la evolución decida cual trabaja mejor para resolver el problema. Entonces, GEP-nets puede ser usado no solo en problemas boleanos pero también en logistic regression, [[Statistical classification|classification]], and regression.

En todas las casos, GEP-nets puede ser implementado no solo con [[PEG 
  1. Multigenic chromosomes|multigenic systems]] pero

también cellular systems, ambos unicelular y multicelular. Mas aún, problemas de clasificación multinomiales también puede ser parado en uno ir por GEP-nets ambos con sistemas multigenes y sistemas multicelular.

Árboles de decisión

Árboles de decisión (DT) son modelos de clasificación donde una serie de preguntas y respuestas son mapeados usando nodos y aristas dirigidas.

Árboles de decisión tiene tres tipos de nodos: nodo raíz, nodos internos, y hojas o nodos terminales. El nodo raíz y todos los nodos internos representan condiciones para diferentes atributos o variables y un conjunto de datos. Nodos hojas especifican la etiqueta de la clase por todos los diferentes caminos en el árbol.

Mayoría de los algoritmos inductivos de árboles de decisión se involucra seleccionando un atributo para el nodo raíz y después hace el mismo tipo de decisión informada acerca

de todos los nodos en el árbol.

Árboles de decisión pueden ser creados por PEG ,[11] con la ventaja que todas las decisiones acerca del crecimiento de los árboles son hechos por el algoritmo en sí mismo sin ningún tipo de entrada humana.

Hay básicamente 2 tipos diferentes de algoritmos AD: uno para árboles de decisión inducidos con solo atributos nominales y otro para árboles de decisión inducidos con ambos atributos nominales y numéricos. Este aspecto de árboles de decisión inducidos también lleva a PEG y hay 2 algoritmos PEG para árboles de decisión inducidos: algoritmo (EDT) para manejar exclusivamente con atributos nominales y EDT-RNC (EDT con constantes numéricas aleatorias) para manejar ambos nominales y numéricos.

En árboles de decisión inducidos por PEG, el atributo se comporta como nodos función en el [[PEG

  1. The basic gene expression algorithm|basic gene expression

algorithm]], Considerando las etiquetas de la clases se comportan como terminales. Esto significa que los atributos de los nodos tienen también asociados con ellos una aridad especifica o el número de ramas que determinaran su crecimiento y, últimamente, el

crecimiento del árbol. La etiquetas de la clases se comportan como terminales , lo que significa 

que por una k-tarea de clasificación de una clase, un terminal seteado con k terminales es usado, representando el k clases diferentes.

Las reglas para codificar un árbol de decisión en un genoma linear son muy similares a las reglas usadas para codificar expresiones matemáticas (ver [[PEG

#K-expressions and genes|above]]). Entonces, para 

árboles de decisión inducidos los genes también tienen cabeza y cola, con la cabeza conteniendo atributos y terminales y la cola conteniendo solo terminales. Esto nuevamente asegura que todos los árboles de decisión de PEG son siempre programas válidos. Además, el tamaño de la cola t es también determinado por el tamaño de la cabeza h y el número de ramas del Atributo con más ramas nmax y es evaluado por la ecuación:

Por ejemplo, considere el árbol de decisión para decidir donde jugar:

Puede ser codificado linearmente:

01234567
HOWbaaba

donde “H” representa el atributo humedad, “O” el atributo Outlook, “W” representa Windy, y “a” y “b” las etiquetas "Yes" y "No" respectivamente.Notar que la conexiones entre los nodos son propiedades de

los datos, especificando el tipo y número de ramas de cada atributo,
y por tanto no tienen q ser codificadas.

El proceso de inducción de árboles de decisión con PEG empieza con la población inicial de cromosomas creados aleatoriamente Los cromosomas son expresados como árboles de decisión y su precisión evaluada contra el conjunto de entrenamiento. De acuerdo a la precisión

son seleccionados para reproducir con modificación. los operadores 

genéticos son exactamente los mismo que son usados en un sistema convencional por ejemplo, mutation, inversion, [[gene expression programming#Transposition|transposition]], y [[gene expression programming#Recombination|recombination]].

For ejemplo, el gen abajo con tamaño de cabeza 5 (el Dc empieza en la posición

16):
012345678901234567890
WOTHabababbbabba46336

codifica

el árbol de decisión mostrado abajo:

En este sistema, cada nodo en la cabeza, tipo (numérico, nominal o terminal), está asociado con

constante numérica aleatoria, con la simplicidad en el ejemplo 

abajo es representado por 0–9. Estas constantes numéricas aleatorias son codificadas en el dominio Dc su expresión sigue un simple esquema

de arriba a abajo y de izquierda a derecha, los elementos en Dc

son asignados uno por uno a los elementos en el árbol de decisión. Para el siguiente array de RNCs:

C = {62, 51, 68, 83, 86, 41, 43, 44, 9, 67}

el árbol de decisión de abajo resulta en:

[[File:GEP decisión tree with numérica and nominal attributes,

k-expression WOTHababab.png]]

puede ser representado más colorido como un árbol de decisión

convencional:

La crítica

PEG ha sido criticado por no ser una mejora sobre otros genetic programming técnicas.en muchos experimentos, no es mejor que métodos existentes.[12]

Software

Commercial applications

GeneXproTools
GeneXproTools is a predictive analytics suite

developed by Gepsoft. GeneXproTools modeling frameworks include logistic regression, classification,

regression, time series prediction, and 

logic synthesis. GeneXproTools implements the basic [[gene expression programming#The basic gene expression algorithm|gene expression algorithm]] and the GEP-RNC algorithm, both used in all the modeling frameworks

of GeneXproTools.

Open source libraries

GEP4J – GEP for Java Project

Created by Jason Thomas, GEP4J is an open-source implementation of gene expression programming in Java. It implements different GEP algorithms, including evolving [[gene expression programming#Decision trees|decision trees]] (with nominal, numérica, o mixed attributes) and automatically defined functions. GEP4J is hosted at Google Code.

[http://code.google.com/p/pygep/ PyGEP – Gene Expression Programming

for Python]: Created by Ryan O'Neil with the goal to create a simple library suitable for the academic study of gene expression programming in Python, aiming for ease of use and rapid implementation. It implements standard [[gene expression programming#Multigenic chromosomes|multigenic chromosomes]] and the genetic operators mutation, crossover, and transposition. PyGEP is hosted at Google Code.

jGEP – Java GEP toolkit

Created by Matthew Sottile to rapidly build [[Java (programming language)|Java]] prototype codes that use GEP, which can then be written

in a language such as C o Fortran for
real speed. jGEP is hosted at SourceForge.

Further reading

Véase también

Referencias

  1. Box, G. E. P., 1957. Evolutionary operation: A method for increasing industrial productivity. Applied Statistics, 6, 81–101.
  2. Friedman, G. J., 1959. Digital simulation of an evolutionary process. General Systems Yearbook, 4, 171–184.
  3. Rechenberg, Ingo (1973). Evolutionsstrategie. Stuttgart: Holzmann-Froboog. ISBN 3-7728-0373-3.
  4. Mitchell, Melanie (1996). An Introduction to Genetic Algorithms. Cambridge, MA: MIT Press.
  5. Ferreira, C. (2001). «Gene Expression Programming: A New Adaptive Algorithm for Solving Problems». Complex Systems, Vol. 13, issue 2: 87–129.
  6. {{cite web|last=Ferreira|first=C.|title=Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence|url=http://www.gene-expression-programming.com/GepBook/Introduction.htm%7Cpublisher=Angra do Heroísmo |location=Portugal|year=2002|isbn=972-95890-5-4}}
  7. {{cite web|last=Ferreira|first=C.|year=2006|title=Automatically Defined Functions in Gene Expression Programming|url= http://www.gene-expression-programming.com/webpapers/Ferreira-GSP2006.pdf%7Cpublisher= In N. Nedjah, L. de M. Mourelle, A. Abraham, eds., Genetic Systems Programming: Theory and Experiences, Studies in Computational Intelligence, Vol. 13, pp. 21–56, Springer-Verlag}}
  8. {{cite web|last=Ferreira|first=C.|year=2002|title=Mutation, Transposition, and Recombination: An Analysis of the Evolutionary Dynamics|url= http://www.gene-expression-programming.com/webpapers/ferreira-fea02.pdf%7Cpublisher= In H. J. Caulfield, S.-H. Chen, H.-D. Cheng, R. Duro, V. Honavar, E. E. Kerre, M. Lu, M. G. Romay, T. K. Shih, D. Ventura, P. P. Wang, Y. Yang, eds., Proceedings of the 6th Joint Conference on Information Sciences, 4th International Workshop on Frontiers in Evolutionary Algorithms, pages 614–617, Research Triangle Park, North Carolina, USA}}
  9. {{cite web|last=Ferreira|first=C.|year=2002|title=Combinatorial Optimization by Gene Expression Programming: Inversion Revisited|url= http://www.gene-expression-programming.com/webpapers/Ferreira-ASAI02.pdf%7Cpublisher= In J. M. Santos and A. Zapico, eds., Proceedings of the Argentine Symposium on Artificial Intelligence, pages 160–174, Santa Fe, Argentina}}
  10. {{cite web|last=Ferreira|first=C.|year=2006|title=Designing Neural Networks Using Gene Expression Programming|url= http://www.gene-expression-programming.com/webpapers/Ferreira-ASCT2006.pdf%7Cpublisher= In A. Abraham, B. de Baets, M. Köppen, and B. Nickolay, eds., Applied Soft Computing Technologies: The Challenge of Complexity, pages 517–536, Springer-Verlag}}
  11. Ferreira, C. (2006). Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence. Springer-Verlag. ISBN 3-540-32796-7.
  12. Oltean, M.; Grosan, C. (2003), «A comparison of several linear genetic programming techniques», Complex Systems 14 (4): 285--314.

Enlaces externos

Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.