operación de cruce en el algoritmo genético para TSP

Question

estoy tratando de resolver el Travelling Salesman Problem (TSP) con Genetic algorithm

Mi genoma es permutación de vértice en el gráfico (camino de vendedor).

¿Cómo debo realizar la operación de cruce sobre mis genomas?

¿Dónde puedo encontrar implementaciones de mi problema en C#?

Answer 1

Debe consultar "Solución de algoritmo genético del TSP que evita el cruce y la mutación especiales" de Gokturk Ucoluk. PDF here. Proporciona una visión general de los operadores de cruce especiales para permutaciones y propone una representación inteligente de permutaciones que funciona bien con el cruce estándar (es decir, cruzar dos permutaciones siempre produce dos permutaciones).

La idea clave es representar la permutación como su secuencia de inversión, es decir, para cada elemento de i, tienda en a[i] cuántos elementos más grandes que i están a la izquierda de i en la permutación. A diferencia de la representación directa, la única restricción en a[i] es local, es decir, a[i] no puede ser mayor que N - i. Esto significa que el cruce simple de dos secuencias de inversión válidas siempre produce dos secuencias de inversión válidas, sin necesidad de un manejo especial de los elementos que se repiten.

Answer 2

Aquí está a C# program enfoque para lo que estás buscando.

En cuanto al interés (o falta de ella) de la aplicación cruzado, todo depende de la lógica de selección particular usará su aplicación (y/o la función de evaluación en sí, si por ejemplo se incluye una evaluación de la velocidad de mejora). En muchos casos, las operaciones cruzadas "rescatarán de la tabla de cortar" algunas soluciones que son efectivas/óptimas en un área del gráfico pero que de alguna manera se "pegan" en otras. Esto no quiere decir que si el algoritmo general es lo suficientemente lento y cubre un buen porcentaje del espacio de solución, las mismas soluciones pueden no haber sido descubiertas nuevamente, pero el cruce también puede aumentar estos descubrimientos (y/o permitirte estar atrapado en otro mínimo local ;-))

No relacionado directamente pero de notable interés para quien mira GA, es el experimento original "original "ultimate" experiment in GA" en GA por el Prof. Alderman (de fama RSA), que utilizó moléculas de ADN reales [ en un programa C - es una broma] para resolver un problema gráfico relacionado, el de los gráficos hamiltonianos.

Editar: Al releer la pregunta entiendo por qué pidió que o más precisamente qué quieres un "No que no quiere cross-over" responder ;-)
Su genonme está directamente relacionado con el gráfico en sí (nada de malo con eso, a priori), pero esto trae el impedimento de que la mayoría de los desvíos cruzados no serán viables, ya que pueden tener nodos duplicados (visitar la misma ciudad dos veces o más) y faltan nodos (no visitan algunas ciudades) ... Además, los cruces viables afectarán gráficos similares, y por lo tanto, tal vez simplemente gasten incrementalmente la búsqueda, en comparación con lo que cambia iones habría descubierto ...
Hum ... Entonces quizás cross-over, en esta implementación particular no ayudará mucho al algoritmo (y de hecho tomará mucho de su CPU para crear, probar y, a menudo, descartar derivaciones cruzadas, CPU que se usaría mejor al permitir más iteraciones, y una velocidad de enfriamiento más lenta ...). ¡A no ser que! Encontrará una manera inteligente de realizar operaciones cruzadas ;-)

Answer 3

El propósito de cruzar para expandir el espacio de búsqueda evolutiva reuniendo nuevas combinaciones genómicas.

El único criterio real requerido para el proceso evolutivo es que el producto de cruce contiene porciones de ambos padres y representa un genoma válido.

Solo usted conoce las reglas de validez de su algoritmo, por lo que solo puede especificar un método de cruce que funcione (a menos que desee compartir más detalles de las reglas de validación para su estructura de genoma).

Answer 4

"Crossover" en algoritmos genéticos simplemente se refiere a una forma arbitraria de mezclar dos "secuencias genéticas", cada una de las cuales representa una solución particular a un problema (cómo una secuencia asigna a una solución depende de usted). Así, por ejemplo, supongamos que tiene una población que consta de las dos secuencias siguientes:

AAAAAAAAAA 
BBBBBBBBBB 

Una forma de recombinar estas dos secuencias de "padre" es escoger al azar un punto de cruce (por ejemplo, la posición 3), lo que resulta en estas dos secuencias de "niños":

AAABBBBBBB 
BBBAAAAAAA 

O, usted podría escoger al azar dos puntos de cruce (por ejemplo, 3 y 8), lo que resulta en estas dos secuencias:

AAABBBBBAA 
BBBAAAAABB 

Para la diversión y v adicional ariability, también se puede introducir la posibilidad de mutaciones puntuales ocasionales:

AAABBBABAA 
BBBAAAAABB 

No hay realmente ninguna regla dura y rápida con respecto a cómo se implementa la cruce en un algoritmo genético, al igual que en realidad no hay ningún reglas duras y rápidas que rigen la Evolución en el mundo biológico. Lo que sea que funcione, funciona.

Answer 5

Cuando estaba en el primer curso de mi universidad, estaba haciendo algunos cálculos (que tomaron alrededor de 30 páginas) sobre el impacto de varios operadores de GA en la convergencia de la solución. Como recuerdo, el crossover no es la mejor solución para TSP, la solución más adecuada es la mutación, que es la inversión de la subsecuencia de los vértices.

ejemplo:

antes: A BCDEF GH

después de: A FEDCB GH

Answer 6

En lugar de utilizar la técnica estándar cross-over GA (como outlined by MusiGenesis), que es mejor use ordered cross-over for the Travelling Salesman problem.

El enfoque habitual no funciona tan bien para el TSP porque la función de aptitud es muy sensible a las posiciones relativas de las diferentes ciudades en la ruta evolucionada en lugar de a sus posiciones absolutas. Por ejemplo, si visitaba todas las capitales europeas, la ruta más corta en realidad no depende de si visita Bratislava primero, segundo o noveno. Lo que es más importante es que lo visite immediately before or immediately after visiting Vienna en lugar de visitar Helsinki, Atenas y otras 6 capitales en el medio.

Por supuesto, como mjv also points out, el tradicional cruce también introducirá duplicados en su ruta. Si uno de los padres tiene a París en la posición 2 y otra a París en la posición 14, el cruce podría dar como resultado una ruta evolucionada que visita París dos veces (y pierde otra ciudad) y otra ruta desarrollada que no la visita en absoluto. El operador genético cruzado ordenado no sufre este problema. Conserva los elementos y modifica el orden.

Answer 7

Aquí está mi implementación exacta del método llamado "crossover parcialmente mapeado" en una GA para TSP.

Here es un documento que explica el crossover parcialmente mapeado en teoría y debajo está mi código.

//construct a new individual with the genes of the parents 
//method used is cross over mapping 
//note that Individual datastrucuture contains an integer array called Genes which   //contains the route. 
// 
public Individual Breed(Individual father, Individual mother) 
{ 
    int[] genes = new int[father.Genes.Length]; 
    int[] map = new int[father.Genes.Length + 1]; //create a map to map the indices 
    int crossoverPoint1 = rand.Next(1, father.Genes.Length - 2); //select 2 crossoverpoints, without the first and last nodes, cuz they are always thje same 
    int crossoverPoint2 = rand.Next(1, father.Genes.Length - 2); 
    father.Genes.CopyTo(genes, 0); //give child all genes from the father 
    for (int i = 0; i < genes.Length; i++) //create the map 
    { 
     map[genes[i]] = i; 
    } 
    //int[] genesToCopy = new int[Math.Abs(crossoverPoint1 - crossoverPoint2)]; //allocate space for the mother genes to copy 
    if (crossoverPoint1 > crossoverPoint2) //if point 1 is bigger than point 2 swap them 
    { 
     int temp = crossoverPoint1; 
     crossoverPoint1 = crossoverPoint2; 
     crossoverPoint2 = temp; 
    } 
    //Console.WriteLine("copy mother genes into father genes from {0} to {1}", crossoverPoint1, crossoverPoint2); 
    for (int i = crossoverPoint1; i <= crossoverPoint2; i++) //from index one to the 2nd 
    { 
     int value = mother.Genes[i]; 
     int t = genes[map[value]]; //swap the genes in the child 
     genes[map[value]] = genes[i]; 
     genes[i] = t; 
     t = map[genes[map[value]]]; //swap the indices in the map 
     map[genes[map[value]]] = map[genes[i]]; 
     map[genes[i]] = t; 
    } 
    Individual child = new Individual(genes); 
    return child; 
}