Programación de expresiones de genes

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.

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.

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:

${\displaystyle {\sqrt {(a-b)(c+d)}}\,}$

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:

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:

${\displaystyle t=h(n_{\max }-1)+1}$

donde h es el largo de la cabeza y n_max 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.

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.

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

gen homeotico y codifica un programa que invoca 3 funciones 

Gen homeotico en este sistema pone diferentes combinaciones of 

solo una salida y con múltiples salidas.

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.

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 individuos, los cuales en este caso son programas. 

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

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

conjunto de datos de entrenamiento.

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

y multinomiales;

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

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

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

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

de una generación a otra.

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

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

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

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

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

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, 

cualquier posición en el cromosoma.

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

programas error-libre.

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

un cromosoma.

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

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.

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:

${\displaystyle d_{w}=hn_{\max }}$

EL Dt viene después de Dw y tiene tamaño d_t 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 (i₁ and i₂), 2 unidades ocultas (h₁ and h₂), and one output unit (o₁). 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 i₁

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 (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 n_max y es evaluado por la ecuación:

${\displaystyle t=h(n_{\max }-1)+1\,}$

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:

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

convencional:

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]

• Ferreira, C. (2006). Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence. Springer-Verlag. ISBN 3-540-32796-7.
• Ferreira, C. (2002). Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence. Portugal: Angra do Heroismo. ISBN 972-95890-5-4.

• Artificial intelligence
• Decision trees
• Evolutionary algorithms
• Genetic algorithms
• Genetic programming
• GeneXproTools
• Machine learning
• Neural networks

• GEP home page, maintained by the inventor of gene expression programming.
• GeneXproTools, commercial GEP software.