El operador de recombinación de bordes ( ERO ) es un operador que crea una ruta que es similar a un conjunto de rutas existentes (padres) al observar los bordes en lugar de los vértices. La principal aplicación de esto es para el cruce en algoritmos genéticos cuando se necesita un genotipo con secuencias de genes que no se repiten, como para el problema del viajante de comercio . Fue descrito por Darrell Whitley y otros en 1989. [1]
Algoritmo
ERO se basa en una matriz de adyacencia , que enumera los vecinos de cada nodo en cualquier padre.
Por ejemplo, en un problema de vendedor ambulante 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 los que ruedan. alrededor del final de la cuerda.
Por lo tanto;
... -> [A] <-> [B] <-> [C] <-> [E] <-> [F] <-> [D] <- ...
... se convierte en la siguiente matriz de adyacencia tomando cada nodo por turno y enumerando sus vecinos conectados;
A: BDB: CAC: SERD: FAE: CFALIMENTADOS
Con la misma operación realizada en el segundo padre (CABDEF), se produce lo siguiente:
A: CBMALOC: FAD: SERE: DFF: EC
Seguido de hacer una unión de estas dos listas e ignorar cualquier duplicado. Esto es tan simple como tomar los elementos de cada lista y agregarlos para generar una lista de puntos finales de enlaces ú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 matriz de adyacencia , que almacena los enlaces para una red descrita por todos los enlaces en los padres. Tenga en cuenta que aquí se pueden emplear más de dos padres para proporcionar enlaces más diversos. Sin embargo, este enfoque puede resultar en rutas subóptimas.
Luego, para crear una ruta K , se emplea el siguiente algoritmo: [2]
el algoritmo ero es dejar que K sea la lista vacía sea N el primer nodo de un padre aleatorio. while length ( K )hacer K : = K , N (agregar N a K ) Eliminar N de todas las listas de vecinos si la lista de vecinos de ' N no está vacía, entonces deje que N * sea el vecino de N con la menor cantidad de vecinos en su lista (o uno aleatorio, si hubiera múltiples); de lo contrario, deje que N * sea un nodo elegido al azar que no está en K N : = N *
Para recorrer el ejemplo, seleccionamos aleatoriamente un nodo de 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 aleatoriamente D.
- 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.
Comparación con otros operadores
La recombinación de bordes generalmente se considera una buena opción para problemas como el problema del vendedor ambulante. En un estudio de 1999 en la Universidad del País Vasco , la recombinación de bordes proporcionó mejores resultados que todos los demás operadores de cruce, incluido el cruce parcialmente mapeado y el cruce de ciclo . [3]
Referencias
- ^ Whitley, Darrell; Timothy Starkweather; D'Ann Fuquay (1989). "Problemas de programación y vendedor ambulante: el operador de recombinación de borde genético". Congreso Internacional de Algoritmos Genéticos . págs. 133–140. ISBN 1-55860-066-3.
- ^ Darrell Whitley, Timothy Starkweather y Daniel Shaner: El vendedor ambulante y la programación de secuencias: Soluciones de calidad utilizando la recombinación de bordes genéticos en L. Davis (ed.): Manual de algoritmos genéticos . Van Nostrand Reinhold, Nueva York 1991
- ^ P. Larrañaga et al: Algoritmos genéticos para el problema del viajante: una revisión de representaciones y operadores . Revisión de inteligencia artificial, volumen 13, número 2, abril de 1999, p. 129-170