operador de recombinación de borde

El operador de recombinación de aristas ( ERO ) es un operador que crea una ruta similar a un conjunto de rutas existentes (padres) al considerar las aristas en lugar de los vértices. Su principal aplicación es el cruce en algoritmos genéticos cuando se necesita un genotipo con secuencias genéticas no repetitivas, como en el problema del viajante de comercio . Fue descrito por Darrell Whitley y otros en 1989. ^{[ 1 ]}

ERO se basa en listas de adyacencia , que enumeran los vecinos de cada nodo en cualquier nodo padre.

Por ejemplo, en un problema del viajante como el que se muestra, el mapa de nodos para los padres CABDEF y ABCEFD (ver ilustración) se genera tomando el primer padre, digamos, 'ABCEFD', y registrando sus vecinos inmediatos, incluidos aquellos que se encuentran al final de la cadena.

Por lo tanto;

... -> [A] <-> [B] <-> [C] <-> [E] <-> [F] <-> [D] <- ...

...se convierte en la siguiente lista de adyacencia tomando cada nodo por turno y enumerando sus vecinos conectados;

A: BD B: AC C: SER D: FA E: CF F: ED

Al realizar la misma operación en el segundo padre (CABDEF), se obtiene lo siguiente:

A: CB MALO C: FA D: SER E: DF F: EC

A continuación, se realiza una unión de estas dos listas, ignorando cualquier duplicado. Esto es tan simple como tomar los elementos de cada lista y agregarlos para generar una lista de puntos finales de enlace únicos. En nuestro ejemplo, generando esto;

A: BCD = {B,D} ∪ {C,B} B: ACD = {A,C} ∪ {A,D} C: ABEF = {B,E} ∪ {F,A} D: ABEF = {F,A} ∪ {B,E} E: CDF = {C,F} ∪ {D,F} F: CDE = {E,D} ∪ {E,C}

El resultado es otra lista de adyacencia que almacena los enlaces de una red descrita por todos los enlaces de los padres. Cabe destacar que se pueden utilizar más de dos padres para obtener enlaces más diversos. Sin embargo, este enfoque puede generar rutas subóptimas.

Luego, para crear un camino K , se emplea el siguiente algoritmo: ^{[ 2 ]}

El algoritmo ero es sea K la lista vacía Sea N el primer nodo de un padre aleatorio. mientras length( K ) < length(Parent) hacer K := K , N (añadir N a K ) Eliminar N de todas las listas de vecinos. Si la lista de vecinos de N no está vacía, entonces sea N * el vecino de N con la menor cantidad de vecinos en su lista (o uno aleatorio, si hay varios); de lo contrario, sea N * un nodo elegido aleatoriamente que no esté en K.N := N *

Para seguir el ejemplo paso a paso, seleccionamos aleatoriamente un nodo de entre los puntos de partida principales, {A, C}.

• () -> A. Eliminamos A de todos los conjuntos vecinos y encontramos que el más pequeño de B, C y D es B={C,D}.
• AB. Los conjuntos más pequeños de C y D son C={E,F} y D={E,F}. Seleccionamos D al azar.
• ABD. Los más pequeños son E={C,F}, F={C,E}. Elegimos F.
• ABDF. C={E}, E={C}. Elegimos C.
• ABDFC. El conjunto más pequeño es E={}.
• ABDFCE. La longitud del niño ahora es la misma que la del padre, así que hemos terminado.

Tenga en cuenta que el único borde introducido en ABDFCE es AE.

La recombinación de bordes se considera generalmente una buena opción para problemas como el del viajante de comercio. En un estudio de 1999 realizado en la Universidad del País Vasco , la recombinación de bordes proporcionó mejores resultados que todos los demás operadores de cruce, incluidos el cruce parcialmente mapeado y el cruce cíclico . ^{[ 3 ]}