En programación informática , la programación de expresión genética (GEP) es un algoritmo evolutivo que crea programas o modelos informáticos. Estos programas informáticos son estructuras complejas en forma de árbol que aprenden y se adaptan modificando su tamaño, forma y composición, de forma muy similar a un organismo vivo. Y, al igual que los organismos vivos, los programas informáticos de GEP también están codificados en cromosomas lineales simples de longitud fija. Por lo tanto, GEP es un sistema genotipo-fenotipo , que se beneficia de un genoma simple para mantener y transmitir la información genética y de un fenotipo complejo para explorar el entorno y adaptarse a él.
Los algoritmos evolutivos utilizan poblaciones de individuos, seleccionan individuos según su aptitud e introducen variación genética utilizando uno o más operadores genéticos . Su uso en sistemas computacionales artificiales se remonta a la década de 1950, donde se utilizaron para resolver problemas de optimización (por ejemplo, Box 1957 [1] y Friedman 1959 [2] ). Pero fue con la introducción de las estrategias de evolución por parte de Rechenberg en 1965 [3] que los algoritmos evolutivos ganaron popularidad. Un buen texto de introducción a los algoritmos evolutivos es el libro "An Introduction to Genetic Algorithms" de Mitchell (1996). [4]
La programación de la expresión génica [5] pertenece a la familia de algoritmos evolutivos y está estrechamente relacionada con los algoritmos genéticos y la programación genética . De los algoritmos genéticos heredó los cromosomas lineales de longitud fija; y de la programación genética heredó los árboles de análisis expresivos de tamaños y formas variados.
En la programación de la expresión génica, los cromosomas lineales funcionan como el genotipo y los árboles de análisis como el fenotipo, creando un sistema genotipo/fenotipo . Este sistema genotipo/fenotipo es multigénico , por lo que codifica múltiples árboles de análisis en cada cromosoma. Esto significa que los programas informáticos creados por GEP están compuestos de múltiples árboles de análisis. Debido a que estos árboles de análisis son el resultado de la expresión génica, en GEP se denominan árboles de expresión . Masood Nekoei, et al. utilizaron este estilo de programación de la expresión en la optimización ABC para llevar a cabo ABCEP como un método que superó a otros algoritmos evolutivos. ABCEP
El genoma de la programación de la expresión génica consiste en una cadena simbólica lineal o cromosoma de longitud fija compuesto por uno o más genes de igual tamaño. Estos genes, a pesar de su longitud fija, codifican á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 (la posición cero indica el inicio de cada gen):
012345678012345678L+a-baccd**cLabacddonde “L” representa la función logaritmo natural y “a”, “b”, “c” y “d” representan las variables y constantes utilizadas en un problema.
Como se muestra arriba, los genes de la programación de la expresión génica tienen todos el mismo tamaño. Sin embargo, estas cadenas de longitud fija codifican árboles de expresión de diferentes tamaños. Esto significa que el tamaño de las regiones codificantes varía de un gen a otro, lo que permite que la adaptación y la evolución se produzcan sin problemas.
Por ejemplo, la expresión matemática:
También se puede representar como un árbol de expresión :
donde "Q" representa la función raíz cuadrada.
Este tipo de árbol de expresión consiste en la expresión fenotípica de los genes GEP, mientras que los genes son cadenas lineales que codifican estas estructuras complejas. Para este ejemplo en particular, la cadena lineal corresponde a:
01234567Q*-+abcdque es la lectura directa del árbol de expresiones de arriba a abajo y de izquierda a derecha. Estas cadenas lineales se denominan k-expresiones (de la notación Karva).
Pasar de expresiones k a árboles de expresión también es muy sencillo. Por ejemplo, la siguiente expresión k:
01234567890Q*b**+baQbase compone de dos terminales diferentes (las variables “a” y “b”), dos funciones diferentes de dos argumentos (“*” y “+”), y una función de un argumento (“Q”). Su expresión da:
Las k-expresiones de la programación de la expresión génica corresponden a la región de los genes que se expresan. Esto significa que puede haber secuencias en los genes que no se expresen, lo que es cierto para la mayoría de los genes. La razón de estas regiones no codificantes es proporcionar un buffer de terminales para que todas las k-expresiones codificadas en los genes GEP correspondan siempre a programas o expresiones válidos.
Por lo tanto, los genes de la programación de la expresión génica se componen de dos dominios diferentes (una cabeza y una cola), cada uno con propiedades y funciones diferentes. La cabeza se utiliza principalmente para codificar las funciones y las variables elegidas para resolver el problema en cuestión, mientras que la cola, aunque también se utiliza para codificar las variables, proporciona esencialmente un reservorio de terminales para garantizar que todos los programas estén libres de errores.
Para los genes GEP la longitud de la cola viene dada por la fórmula:
donde h es la longitud de la cabeza y nmax es la aridad máxima. Por ejemplo, para un gen creado utilizando el conjunto de funciones F = {Q, +, −, ∗, /} y el conjunto de terminales T = {a, b}, nmax = 2. Y si elegimos una longitud de cabeza de 15, entonces t = 15 (2–1) + 1 = 16, lo que da una longitud de gen g de 15 + 16 = 31. La cadena generada aleatoriamente a continuación es un ejemplo de un gen de este tipo:
0123456789012345678901234567890*b+a-aQab+//+b+babbabbbababbaaaCodifica el árbol de expresión:
que, en este caso, sólo utiliza 8 de los 31 elementos que constituyen el gen.
No es difícil ver que, a pesar de su longitud fija, cada gen tiene el potencial de codificar árboles de expresión de diferentes tamaños y formas, desde el más simple compuesto por un solo nodo (cuando el primer elemento de un gen es una terminal) hasta el más grande compuesto por tantos nodos como elementos hay en el gen (cuando todos los elementos de la cabeza son funciones con máxima aridad).
Tampoco es difícil ver que es trivial implementar todo tipo de modificación genética ( mutación , inversión, inserción, recombinación , etc.) con la garantía de que toda la descendencia resultante codifique programas correctos y libres de errores.
Los cromosomas de la programación de la expresión génica suelen estar compuestos por más de un gen de igual longitud. Cada gen codifica un árbol de subexpresión (sub-ET) o subprograma. Luego, los sub-ET pueden interactuar entre sí de diferentes maneras, formando un programa más complejo. La figura muestra un ejemplo de un programa compuesto por tres sub-ET.
En el programa final, los sub-ET podrían vincularse mediante la adición o alguna otra función, ya que no hay restricciones en cuanto al tipo de función de enlace que se puede elegir. Algunos ejemplos de enlaces más complejos incluyen tomar el promedio, la mediana, el rango medio, establecer un umbral para su suma para hacer una clasificación binomial, aplicar la función sigmoidea para calcular una probabilidad, etc. Estas funciones de enlace suelen elegirse a priori para cada problema, pero también pueden desarrollarse de manera elegante y eficiente mediante el sistema celular [6] [7] de programación de la expresión génica.
En la programación de la expresión génica, los genes homeóticos controlan las interacciones de los diferentes sub-ETs o módulos del programa principal. La expresión de dichos genes da como resultado diferentes programas principales o células, es decir, determinan qué genes se expresan en cada célula y cómo interactúan entre sí los sub-ETs de cada célula. En otras palabras, los genes homeóticos determinan qué sub-ETs son invocados y con qué frecuencia en qué programa principal o célula y qué tipo de conexiones establecen entre sí.
Los genes homeóticos tienen exactamente el mismo tipo de organización estructural que los genes normales y se construyen mediante un proceso idéntico. También contienen un dominio de cabeza y un dominio de cola, con la diferencia de que las cabezas contienen ahora funciones de enlace y un tipo especial de terminales (terminales génicos) que representan a los genes normales. La expresión de los genes normales da como resultado, como es habitual, diferentes sub-ET, que en el sistema celular se denominan ADF (funciones definidas automáticamente). En cuanto a las colas, contienen solo terminales génicos, es decir, características derivadas generadas sobre la marcha por el algoritmo.
Por ejemplo, el cromosoma de la figura tiene tres genes normales y un gen homeótico y codifica un programa principal que invoca tres funciones diferentes un total de cuatro veces, vinculándolas de una manera particular.
De este ejemplo se desprende claramente que el sistema celular no sólo permite la evolución sin restricciones de las funciones de enlace, sino también la reutilización del código. Y no debería ser difícil implementar la recursión en este sistema.
Los sistemas multicelulares están compuestos por más de un gen homeótico. Cada gen homeótico de este sistema crea una combinación diferente de árboles de subexpresión o ADF, creando múltiples células o programas principales.
Por ejemplo, el programa que se muestra en la figura se creó utilizando un sistema celular con dos células y tres genes normales.
Las aplicaciones de estos sistemas multicelulares son múltiples y variadas y, al igual que los sistemas multigénicos, pueden utilizarse tanto en problemas con una sola salida como en problemas con múltiples salidas.
El dominio de cabeza/cola de los genes GEP (tanto normales como homeóticos) es el componente básico de todos los algoritmos GEP. Sin embargo, la programación de la expresión génica también explora otras organizaciones cromosómicas que son más complejas que la estructura de cabeza/cola. Básicamente, estas estructuras complejas consisten en unidades funcionales o genes con un dominio de cabeza/cola básico más uno o más dominios adicionales. Estos dominios adicionales suelen codificar constantes numéricas aleatorias que el algoritmo ajusta incansablemente para encontrar una buena solución. Por ejemplo, estas constantes numéricas pueden ser los pesos o factores en un problema de aproximación de funciones (consulte el algoritmo GEP-RNC a continuación); pueden ser los pesos y umbrales de una red neuronal (consulte el algoritmo GEP-NN a continuación); las constantes numéricas necesarias para el diseño de árboles de decisión (consulte el algoritmo GEP-DT a continuación); los pesos necesarios para la inducción polinómica; o las constantes numéricas aleatorias utilizadas para descubrir los valores de los parámetros en una tarea de optimización de parámetros.
Los pasos fundamentales del algoritmo básico de expresión genética se enumeran a continuación en pseudocódigo:
Los primeros cuatro pasos preparan todos los ingredientes necesarios para el ciclo iterativo del algoritmo (pasos 5 a 10). De estos pasos preparatorios, el crucial es la creación de la población inicial, que se crea aleatoriamente utilizando los elementos de la función y los conjuntos terminales.
Como todos los algoritmos evolutivos, la programación de la expresión genética funciona con poblaciones de individuos, que en este caso son programas informáticos. Por lo tanto, se debe crear algún tipo de población inicial para que todo comience a funcionar. Las poblaciones posteriores son descendientes, mediante selección y modificación genética, de la población inicial.
En el sistema genotipo/fenotipo de programación de la expresión genética, sólo es necesario crear los cromosomas lineales simples de los individuos sin preocuparse por la solidez estructural de los programas que codifican, ya que su expresión siempre da como resultado programas sintácticamente correctos.
Las funciones de aptitud y los entornos de selección (denominados conjuntos de datos de entrenamiento en el aprendizaje automático ) son las dos facetas de la aptitud y, por lo tanto, están estrechamente conectadas. De hecho, la aptitud de un programa depende no solo de la función de costo utilizada para medir su rendimiento, sino también de los datos de entrenamiento elegidos para evaluar la aptitud.
El entorno de selección está formado por el conjunto de registros de entrenamiento, también denominados casos de aptitud. Estos casos de aptitud pueden ser un conjunto de observaciones o mediciones relativas a algún problema y forman lo que se denomina el conjunto de datos de entrenamiento.
La calidad de los datos de entrenamiento es esencial para la evolución de buenas soluciones. Un buen conjunto de datos de entrenamiento debe ser representativo del problema en cuestión y también estar bien equilibrado; de lo contrario, el algoritmo podría quedarse estancado en algún óptimo local. Además, también es importante evitar el uso de conjuntos de datos innecesariamente grandes para el entrenamiento, ya que esto ralentizará las cosas innecesariamente. Una buena regla general es elegir suficientes registros para el entrenamiento para permitir una buena generalización en los datos de validación y dejar los registros restantes para la validación y las pruebas.
En términos generales, existen básicamente tres tipos diferentes de problemas según el tipo de predicción que se realice:
El primer tipo de problema se conoce con el nombre de regresión ; el segundo se conoce como clasificación , siendo la regresión logística un caso especial en el que, además de las clasificaciones precisas como "Sí" o "No", también se asocia una probabilidad a cada resultado; y el último está relacionado con el álgebra de Boole y la síntesis lógica .
En la regresión , la respuesta o variable dependiente es numérica (normalmente continua) y, por lo tanto, el resultado de un modelo de regresión también es continuo. Por lo tanto, es bastante sencillo evaluar la idoneidad de los modelos en evolución comparando el resultado del modelo con el valor de la respuesta en los datos de entrenamiento.
Existen varias funciones de aptitud básicas para evaluar el rendimiento del modelo, siendo la más común la que se basa en el error o residuo entre la salida del modelo y el valor real. Dichas funciones incluyen el error cuadrático medio , la raíz del error cuadrático medio , el error absoluto medio , el error cuadrático relativo, la raíz del error cuadrático relativo, el error absoluto relativo y otras.
Todas estas medidas estándar ofrecen una granularidad fina o suavidad al espacio de solución y, por lo tanto, funcionan muy bien para la mayoría de las aplicaciones. Pero algunos problemas pueden requerir una evolución más burda, como determinar si una predicción está dentro de un cierto intervalo, por ejemplo, menos del 10% del valor real. Sin embargo, incluso si uno solo está interesado en contar los aciertos (es decir, una predicción que está dentro del intervalo elegido), hacer que las poblaciones de modelos evolucionen en función solo del número de aciertos que cada programa obtiene no suele ser muy eficiente debido a la granularidad burda del panorama de aptitud . Por lo tanto, la solución suele implicar la combinación de estas medidas burdas con algún tipo de función suave, como las medidas de error estándar enumeradas anteriormente.
Las funciones de aptitud basadas en el coeficiente de correlación y el R cuadrado también son muy suaves. Para los problemas de regresión, estas funciones funcionan mejor al combinarlas con otras medidas porque, por sí mismas, solo tienden a medir la correlación , sin tener en cuenta el rango de valores de la salida del modelo. Por lo tanto, al combinarlas con funciones que funcionan para aproximar el rango de los valores objetivo, forman funciones de aptitud muy eficientes para encontrar modelos con buena correlación y buen ajuste entre los valores predichos y los reales.
El diseño de funciones de aptitud para la clasificación y la regresión logística aprovecha tres características diferentes de los modelos de clasificación. La más obvia es simplemente contar los aciertos, es decir, si un registro se clasifica correctamente se cuenta como un acierto. Esta función de aptitud es muy simple y funciona bien para problemas simples, pero para problemas más complejos o conjuntos de datos muy desequilibrados da resultados pobres.
Una forma de mejorar este tipo de función de aptitud basada en aciertos consiste en ampliar la noción de clasificaciones correctas e incorrectas. En una tarea de clasificación binaria, las clasificaciones correctas pueden ser 00 u 11. La representación "00" significa que un caso negativo (representado por "0") se clasificó correctamente, mientras que el "11" significa que un caso positivo (representado por "1") se clasificó correctamente. Las clasificaciones del tipo "00" se denominan verdaderos negativos (VN) y "11" verdaderos positivos (VP).
También hay dos tipos de clasificaciones incorrectas y se representan por 01 y 10. Se llaman falsos positivos (FP) cuando el valor real es 0 y el modelo predice un 1; y falsos negativos (FN) cuando el objetivo es 1 y el modelo predice un 0. Los recuentos de TP, TN, FP y FN generalmente se guardan en una tabla conocida como matriz de confusión .
De este modo, al contar TP, TN, FP y FN y asignar pesos diferentes a estos cuatro tipos de clasificaciones, es posible crear funciones de aptitud más fluidas y, por lo tanto, más eficientes. Algunas funciones de aptitud populares basadas en la matriz de confusión incluyen sensibilidad/especificidad , recuperación/precisión , medida F , similitud de Jaccard , coeficiente de correlación de Matthews y matriz de costo/ganancia que combina los costos y las ganancias asignadas a los cuatro tipos diferentes de clasificaciones.
Estas funciones basadas en la matriz de confusión son bastante sofisticadas y adecuadas para resolver la mayoría de los problemas de manera eficiente. Pero existe otra dimensión de los modelos de clasificación que es clave para explorar de manera más eficiente el espacio de soluciones y, por lo tanto, da como resultado el descubrimiento de mejores clasificadores. Esta nueva dimensión implica explorar la estructura del modelo en sí, que incluye no solo el dominio y el rango, sino también la distribución de la salida del modelo y el margen del clasificador.
Al explorar esta otra dimensión de los modelos de clasificación y luego combinar la información sobre el modelo con la matriz de confusión, es posible diseñar funciones de aptitud muy sofisticadas que permitan la exploración fluida del espacio de soluciones. Por ejemplo, se puede combinar alguna medida basada en la matriz de confusión con el error cuadrático medio evaluado entre los resultados del modelo en bruto y los valores reales. O combinar la medida F con el R cuadrado evaluado para el resultado del modelo en bruto y el objetivo; o la matriz de costo/ganancia con el coeficiente de correlación , y así sucesivamente. Las funciones de aptitud más exóticas que exploran la granularidad del modelo incluyen el área bajo la curva ROC y la medida de rango.
También relacionada con esta nueva dimensión de los modelos de clasificación, está la idea de asignar probabilidades a la salida del modelo, que es lo que se hace en la regresión logística . Luego también es posible usar estas probabilidades y evaluar el error cuadrático medio (o alguna otra medida similar) entre las probabilidades y los valores reales, y luego combinar esto con la matriz de confusión para crear funciones de aptitud muy eficientes para la regresión logística. Los ejemplos populares de funciones de aptitud basadas en las probabilidades incluyen la estimación de máxima verosimilitud y la pérdida de bisagra .
En lógica no existe una estructura modelo (tal como se definió anteriormente para la clasificación y la regresión logística) para explorar: el dominio y el rango de las funciones lógicas comprenden solo 0 y 1 o falso y verdadero. Por lo tanto, las funciones de aptitud disponibles para el álgebra de Boole solo pueden basarse en los aciertos o en la matriz de confusión, como se explicó en la sección anterior.
La selección por ruleta es quizás el esquema de selección más popular utilizado en computación evolutiva. Implica mapear la aptitud de cada programa a una porción de la ruleta proporcional a su aptitud. Luego, la ruleta se hace girar tantas veces como programas haya en la población para mantener constante el tamaño de la población. Por lo tanto, con la selección por ruleta, los programas se seleccionan tanto de acuerdo con la aptitud como con la suerte del sorteo, lo que significa que algunas veces se pueden perder los mejores rasgos. Sin embargo, al combinar la selección por ruleta con la clonación del mejor programa de cada generación, se garantiza que al menos los mejores rasgos no se pierdan. Esta técnica de clonación del mejor programa de la generación se conoce como elitismo simple y se utiliza en la mayoría de los esquemas de selección estocástica.
La reproducción de programas implica primero la selección y luego la reproducción de sus genomas. La modificación del genoma no es necesaria para la reproducción, pero sin ella no se producirían la adaptación y la evolución.
El operador de selección selecciona los programas que el operador de replicación copiará. Según el esquema de selección, la cantidad de copias que genera un programa puede variar: algunos programas se copian más de una vez, mientras que otros se copian solo una vez o no se copian en absoluto. Además, la selección suele configurarse de modo que el tamaño de la población permanezca constante de una generación a otra.
La replicación de genomas en la naturaleza es muy compleja y los científicos tardaron mucho tiempo en descubrir la doble hélice del ADN y proponer un mecanismo para su replicación. Pero la replicación de cadenas es trivial en los sistemas evolutivos artificiales, donde sólo se requiere una instrucción para copiar cadenas para pasar toda la información del genoma de generación en generación.
La replicación de los programas seleccionados es una pieza fundamental de todos los sistemas evolutivos artificiales, pero para que la evolución ocurra necesita ser implementada no con la precisión habitual de una instrucción de copia, sino más bien con algunos errores incluidos. De hecho, la diversidad genética se crea con operadores genéticos como mutación , recombinación , transposición , inversión y muchos otros.
En la programación de la expresión génica, la mutación es el operador genético más importante. [8] Cambia los genomas al cambiar un elemento por otro. La acumulación de muchos cambios pequeños a lo largo del tiempo puede crear una gran diversidad.
En la programación de la expresión génica, la mutación no tiene ninguna restricción, lo que significa que en cada dominio génico cualquier símbolo de dominio puede ser reemplazado por otro. Por ejemplo, en las cabezas de los genes cualquier función puede ser reemplazada por un terminal u otra función, independientemente del número de argumentos en esta nueva función; y un terminal puede ser reemplazado por una función u otro terminal.
La recombinación generalmente implica la combinación de dos cromosomas progenitores para crear dos nuevos cromosomas mediante la combinación de diferentes partes de los cromosomas progenitores. Y siempre que los cromosomas progenitores estén alineados y los fragmentos intercambiados sean homólogos (es decir, ocupen la misma posición en el cromosoma), los nuevos cromosomas creados por recombinación siempre codificarán programas sintácticamente correctos.
Se pueden implementar fácilmente distintos tipos de cruces, ya sea modificando el número de progenitores implicados (no hay razón para elegir sólo dos), el número de puntos de división o la forma en que se elige intercambiar los fragmentos, por ejemplo, de forma aleatoria o de alguna manera ordenada. Por ejemplo, la recombinación genética, que es un caso especial de recombinación, se puede realizar intercambiando genes homólogos (genes que ocupan la misma posición en el cromosoma) o intercambiando genes elegidos al azar de cualquier posición en el cromosoma.
La transposición implica la introducción de una secuencia de inserción en algún lugar de un cromosoma. En la programación de la expresión génica, las secuencias de inserción pueden aparecer en cualquier parte del cromosoma, pero solo se insertan en las cabezas de los genes. Este método garantiza que incluso las secuencias de inserción de las colas resulten en programas sin errores.
Para que la transposición funcione correctamente, debe preservar la longitud de los cromosomas y la estructura de los genes. Por lo tanto, en la programación de la expresión génica, la transposición se puede implementar utilizando dos métodos diferentes: el primero crea un cambio en el sitio de inserción, seguido de una deleción al final de la cabeza; el segundo sobrescribe la secuencia local en el sitio de destino y, por lo tanto, es más fácil de implementar. Ambos métodos se pueden implementar para operar entre cromosomas o dentro de un cromosoma o incluso dentro de un solo gen.
La inversión es un operador interesante, especialmente potente para la optimización combinatoria . [9] Consiste en invertir una pequeña secuencia dentro de un cromosoma.
En la programación de la expresión génica, se puede implementar fácilmente en todos los dominios genéticos y, en todos los casos, la descendencia producida siempre es sintácticamente correcta. Para cualquier dominio genético, se elige al azar una secuencia (que va desde al menos dos elementos hasta un tamaño igual al del dominio mismo) dentro de ese dominio y luego se invierte.
Existen otros operadores genéticos y en la programación de la expresión génica, con sus diferentes genes y dominios génicos, las posibilidades son infinitas. Por ejemplo, los operadores genéticos como la recombinación de un punto, la recombinación de dos puntos, la recombinación génica, la recombinación uniforme, la transposición génica, la transposición de raíz, la mutación específica de dominio, la inversión específica de dominio, la transposición específica de dominio, etc., se implementan fácilmente y se utilizan ampliamente.
Las constantes numéricas son elementos esenciales de los modelos matemáticos y estadísticos y por ello es importante permitir su integración en los modelos diseñados por algoritmos evolutivos.
La programación de la expresión génica resuelve este problema de forma muy elegante mediante el uso de un dominio genético adicional (el Dc) para manejar constantes numéricas aleatorias (RNC). Al combinar este dominio con un marcador de posición terminal especial para las RNC, se puede crear un sistema de gran expresividad.
Estructuralmente, el Dc viene después de la cola, tiene una longitud igual al tamaño de la cola t y está compuesto por los símbolos utilizados para representar los RNC.
Por ejemplo, a continuación se muestra un cromosoma simple compuesto por un solo gen y un tamaño de cabeza de 7 (el Dc se extiende sobre las posiciones 15-22):
01234567890123456789012+?*+?**aaa??aaa68083295donde el terminal "?" representa el marcador de posición para los RNC. Este tipo de cromosoma se expresa exactamente como se muestra arriba, dando:
Luego, los ? en el árbol de expresión se reemplazan de izquierda a derecha y de arriba a abajo por los símbolos (para simplificar, representados por números) en Dc, dando:
Los valores correspondientes a estos símbolos se guardan en una matriz. (Para simplificar, el número representado por el numeral indica el orden en la matriz). Por ejemplo, para la siguiente matriz de 10 elementos de RNC:
El árbol de expresiones anterior da:
Esta elegante estructura para manejar constantes numéricas aleatorias es el corazón de diferentes sistemas GEP, como las redes neuronales GEP y los árboles de decisión GEP.
Al igual que el algoritmo básico de expresión genética, el algoritmo GEP-RNC también es multigénico y sus cromosomas se decodifican como de costumbre expresando un gen tras otro y luego uniéndolos todos entre sí mediante el mismo tipo de proceso de enlace.
Los operadores genéticos utilizados en el sistema GEP-RNC son una extensión de los operadores genéticos del algoritmo GEP básico (ver arriba), y todos ellos pueden implementarse directamente en estos nuevos cromosomas. Por otra parte, los operadores básicos de mutación, inversión, transposición y recombinación también se utilizan en el algoritmo GEP-RNC. Además, también se utilizan operadores especiales específicos de Dc, como mutación, inversión y transposición, para ayudar a una circulación más eficiente de los RNC entre programas individuales. Además, también hay un operador de mutación especial que permite la introducción permanente de variación en el conjunto de RNC. El conjunto inicial de RNC se crea aleatoriamente al comienzo de una ejecución, lo que significa que, para cada gen en la población inicial, se genera aleatoriamente un número específico de constantes numéricas, elegidas de un cierto rango. Luego, su circulación y mutación se habilitan mediante los operadores genéticos.
Una red neuronal artificial (RNA o NN) es un dispositivo computacional que consta de muchas unidades o neuronas simples conectadas. Las conexiones entre las unidades suelen estar ponderadas por pesos de valor real. Estos pesos son el principal medio de aprendizaje en las redes neuronales y, por lo general, se utiliza un algoritmo de aprendizaje 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 se presenta en las unidades de entrada y luego se propaga en dirección hacia adelante desde las unidades de entrada a través de una o más capas de unidades ocultas hasta las unidades de salida. La activación que llega a una unidad desde otra unidad se multiplica por los pesos de los enlaces sobre los que se propaga. Luego, se suman todas las activaciones entrantes y la unidad se activa solo si el resultado entrante está por encima del umbral de la unidad.
En resumen, los componentes básicos de una red neuronal son las unidades, las conexiones entre las unidades, los pesos y los umbrales. Por lo tanto, para simular por completo una red neuronal artificial, es necesario codificar de algún modo estos componentes en un cromosoma lineal y luego poder expresarlos de una manera significativa.
En las redes neuronales GEP (GEP-NN o redes GEP), la arquitectura de la red está codificada en la estructura habitual de un dominio de cabeza/cola. [10] La cabeza contiene funciones/neuronas especiales que activan las unidades ocultas y de salida (en el contexto GEP, todas estas unidades se denominan más apropiadamente unidades funcionales) y terminales que representan las unidades de entrada. La cola, como es habitual, contiene solo terminales/unidades de entrada.
Además de la cabeza y la cola, estos genes de redes neuronales contienen dos dominios adicionales, Dw y Dt, para codificar los pesos y los umbrales de la red neuronal. Estructuralmente, Dw viene después de la cola y su longitud dw depende del tamaño de la cabeza h y de la aridad máxima n max y se evalúa mediante la fórmula:
El Dt viene después de Dw y tiene una longitud d t igual a t . Ambos dominios están compuestos por símbolos que representan los pesos y los umbrales de la red neuronal.
Para cada gen NN, los pesos y los umbrales se crean al comienzo de cada ejecución, pero su circulación y adaptación están garantizadas por los operadores genéticos habituales de mutación, transposición, inversión y recombinación. Además, también se utilizan operadores especiales para permitir un flujo constante de variación genética en el conjunto de pesos y umbrales.
Por ejemplo, a continuación se muestra una red neuronal con dos unidades de entrada ( i 1 e i 2 ), dos unidades ocultas ( h 1 y h 2 ) y una unidad de salida ( o 1 ). Tiene un total de seis conexiones con seis pesos correspondientes representados por los números 1 a 6 (para simplificar, los umbrales son todos iguales a 1 y se omiten):
Esta representación es la representación canónica de la red neuronal, pero las redes neuronales también pueden representarse mediante un árbol, que en este caso corresponde a:
donde "a" y "b" representan las dos entradas i 1 e i 2 y "D" representa una función con conectividad dos. Esta función suma todos sus argumentos ponderados y luego establece un umbral para esta activación con el fin de determinar la salida reenviada. Esta salida (cero o uno en este caso simple) depende del umbral de cada unidad, es decir, si la activación total entrante es igual o mayor que el umbral, entonces la salida es uno, cero en caso contrario.
El árbol NN anterior se puede linealizar de la siguiente manera:
0123456789012DDDabab654321donde la estructura en las posiciones 7 a 12 (Dw) codifica los pesos. Los valores de cada peso se guardan en una matriz y se recuperan según sea necesario para la expresión.
Como ejemplo más concreto, a continuación se muestra un gen de red neuronal para el problema de o exclusivo . Tiene un tamaño de cabeza de 3 y un tamaño de Dw de 6:
0123456789012DDDabab393257Su expresión da como resultado la siguiente red neuronal:
que, para el conjunto de pesos:
da:
lo cual es una solución perfecta para la función exclusiva-o.
Además de funciones booleanas simples con entradas binarias y salidas binarias, el algoritmo GEP-nets puede manejar todo tipo de funciones o neuronas (neurona lineal, neurona tanh, neurona atan, neurona logística, neurona límite, neuronas de base radial y de base triangular, todo tipo de neuronas de paso, etc.). También es interesante que el algoritmo GEP-nets puede usar todas estas neuronas juntas y dejar que la evolución decida cuáles funcionan mejor para resolver el problema en cuestión. Por lo tanto, las redes GEP se pueden usar no solo en problemas booleanos sino también en regresión logística , clasificación y regresión . En todos los casos, las redes GEP se pueden implementar no solo con sistemas multigénicos sino también con sistemas celulares, tanto unicelulares como multicelulares. Además, los problemas de clasificación multinomial también se pueden abordar de una sola vez mediante redes GEP tanto con sistemas multigénicos como con sistemas multicelulares.
Los árboles de decisión (DT) son modelos de clasificación donde se mapean una serie de preguntas y respuestas utilizando nodos y bordes dirigidos.
Los árboles de decisión tienen tres tipos de nodos: un nodo raíz, nodos internos y nodos de hoja o terminales. El nodo raíz y todos los nodos internos representan condiciones de prueba para diferentes atributos o variables en un conjunto de datos. Los nodos de hoja especifican la etiqueta de clase para todas las diferentes rutas en el árbol.
La mayoría de los algoritmos de inducción de árboles de decisión implican seleccionar un atributo para el nodo raíz y luego tomar el mismo tipo de decisión informada sobre todos los nodos de un árbol.
Los árboles de decisión también se pueden crear mediante programación de expresión genética, [11] con la ventaja de que todas las decisiones relativas al crecimiento del árbol las toma el propio algoritmo sin ningún tipo de intervención humana.
Básicamente, existen dos tipos diferentes de algoritmos DT: uno para inducir árboles de decisión con solo atributos nominales y otro para inducir árboles de decisión con atributos numéricos y nominales. Este aspecto de la inducción de árboles de decisión también se aplica a la programación de la expresión génica y existen dos algoritmos GEP para la inducción de árboles de decisión: el algoritmo de árboles de decisión evolutivos (EDT) para tratar exclusivamente con atributos nominales y el EDT-RNC (EDT con constantes numéricas aleatorias) para tratar tanto atributos nominales como numéricos.
En los árboles de decisión inducidos por programación de expresión génica, los atributos se comportan como nodos de función en el algoritmo básico de expresión génica, mientras que las etiquetas de clase se comportan como terminales. Esto significa que los nodos de atributo también tienen asociada una aridad o número de ramas específico que determinará su crecimiento y, en última instancia, el crecimiento del árbol. Las etiquetas de clase se comportan como terminales, lo que significa que para una tarea de clasificación de k clases, se utiliza un conjunto de terminales con k terminales, que representan las k clases diferentes.
Las reglas para codificar un árbol de decisión en un genoma lineal son muy similares a las reglas que se usan para codificar expresiones matemáticas (ver arriba). Por lo tanto, para la inducción del árbol de decisión, los genes también tienen una cabeza y una cola, con la cabeza que contiene atributos y terminales y la cola que contiene solo terminales. Esto nuevamente garantiza que todos los árboles de decisión diseñados por GEP sean siempre programas válidos. Además, el tamaño de la cola t también está determinado por el tamaño de la cabeza h y el número de ramas del atributo con más ramas n max y se evalúa mediante la ecuación:
Por ejemplo, considere el siguiente árbol de decisiones para decidir si jugar al aire libre:
Se puede codificar linealmente como:
01234567HOWbaabadonde “H” representa el atributo Humedad, “O” el atributo Prospectiva, “W” representa Viento, y “a” y “b” las etiquetas de clase “Sí” y “No” respectivamente. Tenga en cuenta que los bordes que conectan los nodos son propiedades de los datos, que especifican el tipo y la cantidad de ramas de cada atributo y, por lo tanto, no es necesario codificarlos.
El proceso de inducción de árboles de decisión con programación de expresión génica comienza, como es habitual, con una población inicial de cromosomas creados aleatoriamente. A continuación, los cromosomas se expresan como árboles de decisión y se evalúa su aptitud en relación con un conjunto de datos de entrenamiento. De acuerdo con su aptitud, se seleccionan para reproducirse con modificaciones. Los operadores genéticos son exactamente los mismos que se utilizan en un sistema unigénico convencional, por ejemplo, mutación, inversión, transposición y recombinación.
Los árboles de decisión con atributos nominales y numéricos también se pueden inducir fácilmente con la programación de la expresión génica utilizando el marco descrito anteriormente para tratar con constantes numéricas aleatorias. La arquitectura cromosómica incluye un dominio adicional para codificar constantes numéricas aleatorias, que se utilizan como umbrales para dividir los datos en cada nodo de ramificación. Por ejemplo, el gen que se muestra a continuación con un tamaño de cabeza de 5 (el Dc comienza en la posición 16):
012345678901234567890WOTHabababbbabba46336codifica el árbol de decisión que se muestra a continuación:
En este sistema, cada nodo de la cabeza, independientemente de su tipo (atributo numérico, atributo nominal o terminal), tiene asociada una constante numérica aleatoria, que para simplificar en el ejemplo anterior se representa con un numeral del 0 al 9. Estas constantes numéricas aleatorias están codificadas en el dominio Dc y su expresión sigue un esquema muy simple: de arriba a abajo y de izquierda a derecha, los elementos de Dc se asignan uno a uno a los elementos del árbol de decisión. Así, para la siguiente matriz de RNC:
El árbol de decisiones anterior da como resultado:
que también puede representarse de forma más colorida como un árbol de decisión convencional:
Se ha criticado a la GEP por no suponer una mejora importante respecto de otras técnicas de programación genética . En muchos experimentos, no funcionó mejor que los métodos existentes. [12]