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 de máquina . El adjetivo "lineal" se deriva del hecho de que cada programa LGP es una secuencia de instrucciones y la secuencia de instrucciones normalmente se ejecuta de forma secuencial. Al igual que en otros programas, el flujo de datos en LGP se puede modelar como un gráfico que visualizará el posible uso múltiple de los contenidos de los registros y la existencia de código estructuralmente no efectivo ( intrones ), que son dos diferencias principales de esta representación genética con respecto a 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 juzga contra algún 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 diferencias principales 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 dan como resultado 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 de árbol en TGP. Además, LGP naturalmente tiene múltiples salidas al definir múltiples registros de salida y coopera fácilmente con las operaciones de flujo de control .
La programación genética lineal se ha aplicado en muchos dominios, incluido el modelado de sistemas y el control de sistemas, con considerable éxito. [5] [6] [7] [8]
La programación genética lineal no debe confundirse con los programas de árboles lineales en la programación genética de árboles, programa compuesto por un número variable de funciones unarias y un único terminal . Nótese 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]
Debido a que los programas LGP se representan básicamente mediante una secuencia lineal de instrucciones, son más sencillos de leer y de utilizar 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 R1, R2, R3 deben declararse como registros de entrada (sólo lectura), mientras que R0 y R4 se declaran como registros de cálculo (lectura-escritura). Este programa es muy simple, ya que tiene sólo 5 instrucciones. Pero los operadores de mutación y cruce podrían funcionar para aumentar la longitud del programa, así como el contenido de cada una de sus instrucciones.
Tenga en cuenta que una instrucción no es efectiva o es un intrón (marcado), ya que no afecta al registro de salida R0. El reconocimiento de esas instrucciones es la base del algoritmo de eliminación de intrones que se utiliza para analizar el código antes de la ejecución. Técnicamente, esto sucede copiando un individuo y luego ejecutando la eliminación de intrones una vez. La copia con los intrones eliminados se ejecuta tantas veces como lo dicte la cantidad de casos de entrenamiento. Cabe destacar que el individuo original se deja intacto, para continuar participando en el proceso evolutivo. Es solo la copia que se ejecuta la que se comprime al eliminar estos intrones "estructurales".
Otro programa simple, este escrito en 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, la guarda en F
add/ # agrega a F los datos actuales apuntados por I (es decir, F := F + D[0])
output/. # genera el resultado de F Al representar dicho código en formato de bytecode , es decir, como una matriz de bytes, cada uno de los cuales representa una instrucción diferente, se pueden realizar operaciones de mutación simplemente cambiando un elemento de dicha matriz.