Realizar operaciones de cruce en AST en programación genética

8

Entonces, en general, cuando realiza un cruce en GA, voltea directamente una sección aleatoria en el "genoma", con la sección correspondiente en el otro padre, y la muta en función de la tasa de mutación.

Considere las siguientes secuencias:

0100 1000 0001 1011

0010 0110 1101 1111

Un crossover sin ninguna mutación podría tener este aspecto:

0100 0110 1101 1011

0010 1000 0001 1111

En ese caso, los bloques 2 y 3 se intercambiaron y los bloques 1 y 4 se mantuvieron sin cambios.

Sin embargo, no estoy seguro de cómo funcionaría en GP con árboles de sintaxis abstracta, porque no hay garantía de que el punto en el árbol abstracto al que hace referencia en el primer padre sea compatible con la sección del segundo padre, por ejemplo una sección puede tener un tipo devuelto de booleano, mientras que la otra tiene un tipo devuelto de cadena, como en el siguiente ejemplo:

    p1
   /  \
  b    i
 /\   /\
b  f i  s

    p2
   /  \
  s    b
 /\   /\
i  n s  i

si intentara cruzar la rama 1 del padre 1 que tiene un tipo de retorno b, con la rama 1 del padre 2 que tiene un tipo de retorno de s, crearía un error de sintaxis si se ejecutara, así que, ¿cómo realizaría correctamente un cruce en un AST, se apreciarían ejemplos específicos?

    
pregunta Jordan LaPrise 29.04.2016 - 19:34

1 respuesta

5

Una primera observación es que la GA canónica se basa en una representación de longitud fija (un número fijo de genes en < em> loci en el cromosoma).

Los operadores de GA de crossovers son similares a la reproducción sexual biológica: el material genético tanto de la madre como del padre se combina de tal manera que los genes en el niño se encuentran (aproximadamente) en la misma posición que en sus padres.

Es bastante diferente del tradicional cruce de GP basado en árboles, que puede mover un subárbol a una posición totalmente diferente en la estructura del árbol.

Esta forma de cruce puede ocurrir ya que el GP estándar asume una "limitación" conocida como closure :

  

todas las variables, constantes, argumentos para funciones y valores devueltos por funciones deben ser del mismo tipo de datos.

Una representación basada en AST es una forma de programación genética tipificada (fuertemente) e introduce algunas restricciones en los puntos de cruce posibles.

Cada nodo de AST está asociado con un tipo y, antes de realizar el cruce, debe crear una lista de puntos de cruce compatibles:

       p1[1]                          p2[1]
      /     \                        /     \
  [2]b       i[5]                [2]s       b[5]
  /  \       /  \                /  \       /  \
[3]b [4]f [6]i  [7]s           [3]i [4]n [6]s  [7]i


b(p1): [2, 3]      b(p2): [5]
f(p1): [4]         f(p2): []
i(p1): [5, 6]      i(p2): [3, 7]
s(p1): [7]         s(p2): [2, 6]
n(p1): []          n(p2): [4]

Ahora:

  1. seleccione un punto de cruce aleatorio [P] de p1
  2. intercambia el subárbol [P] con uno compatible de p2

por ejemplo

  1. la selección aleatoria para p1 es [5]
  2. los subárboles compatibles de p2 tienen raíz en [3] y [7] . La selección aleatoria es [7] .

El resultado del cruce es:

    p1                p2
   /  \              /  \
  b    i            s    b
 /\                / \  / \
b  f              b   fs   i 
                          / \
                         i   s

Los niños no tienen la misma forma, pero es bastante estándar en GP.

Este es un enfoque muy básico. Con el tiempo tienes que considerar varios otros aspectos:

  • a menudo los puntos de cruce no se seleccionan con probabilidad uniforme :

      

    los conjuntos primitivos GP típicos conducen a árboles con un factor de ramificación promedio   (el número de hijos de cada nodo) de al menos dos, por lo que la mayoría de los nodos serán hojas. En consecuencia, la selección uniforme de los puntos de cruce conduce a operaciones de cruce que intercambian frecuentemente solo cantidades muy pequeñas de material genético (es decir, subárboles pequeños); de hecho, muchos cruces pueden reducirse a simplemente intercambiar dos hojas.

         

    Para contrarrestar esto, Koza (1992) sugirió el enfoque ampliamente utilizado para elegir funciones el 90% del tiempo y deja el 10% del tiempo.

    (de Guía de campo para la programación genética por Riccardo Poli, William Langdon, Nicholas McPhee, John Koza )

    Las listas simples de puntos de cruce compatibles no podrían ser suficientes.

  • es posible que tenga que usar operadores especiales para reducir el tamaño del árbol (por ejemplo, Hoist Mutation, Shrink mutation)

  • En algunos contextos, es posible que desee un operador de cruce que tiende a preservar la posición del material genético ( homólogo ).

    Por ejemplo, con un punto de cruce homólogo usted tiene que analizar los dos árboles primarios de los nodos raíz y seleccionar el punto de cruce solo de las partes de los dos árboles en la región común.

      

    La región común está relacionada con la homología, en el sentido de que   región común representa el resultado de un proceso de coincidencia entre padres   arboles Dentro de la región común entre dos árboles progenitores, la transferencia de   Los primitivos homólogos pueden suceder como lo hace en una cadena genética de bits lineales   algoritmo

    ("Una guía de campo para la programación genética")

    El cruce homólogo presenta detalles de implementación interesantes (debe coordinarse con la lista de puntos de cruce compatibles con el tipo).

  • La representación basada en AST puede introducir diversas formas de "sesgo estructural" que deben reconocer los operadores de cruce / mutación.

Por último, pero no menos importante, hay otras representaciones adecuadas para implementar la Programación Genética Tipificada (incluso no basada en árboles). Las representaciones lineales pueden ser la mejor opción para ciertos lenguajes de programación (es bastante sencillo realizar crossover homólogo cuando se usan representaciones lineales y los operadores homólogos se usan ampliamente en GP lineal).

Dos maravillosos recursos gratuitos para más detalles son:

respondido por el manlio 30.04.2016 - 13:15

Lea otras preguntas en las etiquetas