Hispanopedia Wiki
Articulo de referencia

Programación genética lineal

La "programación genética lineal" no tiene relación con la " programación lineal ". La programación genética lineal (LGP) [ 1 ] es un método particular de programación genética ...

Hispanopedia WikiContenido en espanolLectura gratuita
La "programación genética lineal" no tiene relación con la " programación lineal ".

La programación genética lineal (LGP) [ 1 ] es un método particular de programación genética en el que los programas informáticos de una población se representan como una secuencia de instrucciones basadas en registros de un lenguaje de programación imperativo o lenguaje máquina . El adjetivo "lineal" proviene del hecho de que cada programa LGP ​​es una secuencia de instrucciones y esta secuencia se ejecuta normalmente de forma secuencial. Al igual que en otros programas, el flujo de datos en LGP se puede modelar como un grafo que visualiza el posible uso múltiple del contenido de los registros y la existencia de código estructuralmente ineficaz ( intrones ), dos diferencias principales entre esta representación genética y la variante más común de programación genética basada en árboles (TGP). [ 2 ] [ 3 ] [ 4 ]

Al igual que otros métodos de programación genética, la programación genética lineal requiere la entrada de datos para ejecutar la población del programa. Luego, la salida del programa (su comportamiento) se evalúa en función de un comportamiento objetivo, utilizando una función de aptitud. Sin embargo, LGP es generalmente más eficiente que la programación genética de árboles debido a sus dos principales diferencias mencionadas anteriormente: los resultados intermedios (almacenados en registros) se pueden reutilizar y existe un algoritmo simple de eliminación de intrones [ 1 ] que se puede ejecutar para eliminar todo el código no efectivo antes de que los programas se ejecuten en los datos previstos. Estas dos diferencias a menudo resultan en soluciones compactas y ahorros computacionales sustanciales en comparación con el flujo de datos altamente restringido en árboles y el método común de ejecutar todos los nodos del árbol en TGP. Además, LGP tiene naturalmente múltiples salidas al definir múltiples registros de salida y coopera fácilmente con operaciones de flujo de control .

La programación genética lineal se ha aplicado en muchos dominios, incluyendo el modelado y control de sistemas, con considerable éxito. [ 5 ] [ 6 ] [ 7 ] [ 8 ]

La programación genética lineal no debe confundirse con los programas de árbol lineales en la programación genética de árboles, un programa compuesto por un número variable de funciones unarias y un único terminal . Cabe señalar que la programación genética de árboles lineales difiere de los algoritmos genéticos de cadenas de bits, ya que una población puede contener programas de diferentes longitudes y puede haber más de dos tipos de funciones o más de dos tipos de terminales. [ 9 ]

Ejemplos de programas LGP

Debido a que los programas LGP se representan básicamente mediante una secuencia lineal de instrucciones, son más sencillos de leer y de usar que sus contrapartes basadas en árboles. Por ejemplo, un programa simple escrito para resolver un problema de función booleana con 3 entradas (en R1, R2, R3) y una salida (en R0), podría leerse así:

R4 = R2 Y R3 R0 = R1 O R4 R0 = R3 Y R0 R4 = R2 Y R4 # Esta es una instrucción no efectiva R0 = R0 O R2

Los registros R1, R2 y R3 deben declararse como registros de entrada (solo lectura), mientras que R0 y R4 se declaran como registros de cálculo (lectura y escritura). Este programa es muy sencillo, con tan solo 5 instrucciones. Sin embargo, los operadores de mutación y cruce podrían utilizarse para aumentar la longitud del programa, así como el contenido de cada una de sus instrucciones.

Cabe destacar que una instrucción no tiene efecto o es un intrón (marcado), ya que no afecta al registro de salida R0. El reconocimiento de estas instrucciones es la base del algoritmo de eliminación de intrones, que se utiliza para analizar el código antes de su ejecución. Técnicamente, esto se logra copiando un individuo y ejecutando la eliminación de intrones una sola vez. La copia, con los intrones eliminados, se ejecuta tantas veces como lo dicte el número de casos de entrenamiento. Es importante señalar que el individuo original permanece intacto para que continúe participando en el proceso evolutivo. Solo la copia ejecutada se comprime al eliminar estos intrones "estructurales".

Otro programa sencillo, este escrito en el lenguaje LGP Slash/A parece una serie de instrucciones separadas por una barra:

input/ # Obtiene una entrada del usuario y la guarda en el registro F 0 / # Establece el registro I = 0 save/ # Guarda el contenido de F en el vector de datos D[I] (es decir, D[0] := F) input/ # Obtiene otra entrada y la guarda en F add/ # Agrega a F los datos actuales a los que apunta I (es decir, F := F + D[0]) output/. # Muestra el resultado de F

Al representar dicho código en formato de código de bytes , es decir, como una matriz de bytes, cada uno de los cuales representa una instrucción diferente, se pueden realizar operaciones de modificación simplemente cambiando un elemento de dicha matriz.

Véase también

Notas

  1. 1 2 M. Brameier, W. Banzhaf, " Programación genética lineal ", Springer, Nueva York, 2007
  2. ↑ Brameier, M.: " Sobre programación genética lineal " (Archivado el 29/06/2007 en Wayback Machine ), Dortmund, 2003
  3. ↑ W. Banzhaf, P. Nordin, R. Keller, F. Francone, Programación genética: una introducción , Morgan Kaufmann, Heidelberg/San Francisco, 1998
  4. ↑ Poli, R.; Langdon, WB; McPhee, NF (2008). Guía práctica de programación genética . Lulu.com, disponible gratuitamente en internet. ISBN 978-1-4092-0073-4.
  5. ↑ M. Brameier, W. Banzhaf, " Una comparación de la programación genética lineal y las redes neuronales en la minería de datos médicos ", IEEE Transactions on Evolutionary Computation , 5 (2001) 17-26
  6. ↑ A. Guven, Programación genética lineal para el modelado de series temporales del caudal diario , J. Earth Systems Science , 118 (2009) 137-146
  7. ↑ R. Li, BR Noack, L. Cordier, J. Boree, F. Harambat, Reducción de la resistencia aerodinámica de un modelo de automóvil mediante control de programación genética lineal , Experiments in Fluids , 58 (2017) 103
  8. ↑ P.-Y. Passagia, A. Quansah, N. Mazellier, GY Cornejo Maceda, A. Kourta, Control de pérdida por retroalimentación en tiempo real de un perfil aerodinámico a altos números de Reynolds mediante programación genética lineal , Physics of Fluids , 34 (2022) 045108
  9. ↑ Fundamentos de la programación genética .
  • Slash/A Un lenguaje de programación y una biblioteca de C++ diseñados específicamente para GP lineal
  • DigitalBiology.NET Motor de búsqueda vertical para recursos de GA/GP
  • Software de programación genética Discipulus
  • Software de programación genética MicroGP (código abierto)
  • Un proyecto de programación genética lineal de código abierto basado en un sistema de investigación de computación evolutiva (ECJ) basado en Java.