Operação crossover em algoritmo genético para TSP

Question

Estou tentando resolver o Problema de vendedor ambulante (TSP) com Algoritmo genético. Meu genoma é uma permutação de um vértice no gráfico (caminho para o vendedor).

Como devo realizar a operação de crossover sobre meus genomas?

Onde posso encontrar implementações do meu problema em C#?

Answer 1

Você deveria verificar "Solução de algoritmo genético da TSP, evitando crossover e mutação especiais"Por Gokturk Ucoluk. Ele fornece uma visão geral dos operadores de crossover especiais para obter permutações e propõe uma representação inteligente de permutações que funcionem bem com o crossover padrão (ou seja, o cruzamento de duas permutações sempre produz duas permutações).

A visão principal é representar a permutação como sua sequência de inversão, ou seja, para cada elemento i, armazenar em a[i] Quantos elementos maiores que i estão à esquerda de i na permutação. Ao contrário da representação direta, a única restrição em a[i] é local, ou seja, a[i] não pode ser maior que N - i. Isso significa que o crossover simples de duas seqüências de inversão válidas sempre produz duas seqüências de inversão válidas - não há necessidade de manuseio especial de elementos repetidos.

Answer 2

Em vez de usar a técnica transversal padrão de GA (como descrito pela musigênese), é melhor usar encomendou cruzamento para o problema do vendedor ambulante.

A abordagem usual não funciona tão bem para o TSP, porque a função de condicionamento físico é muito sensível às posições relativas das diferentes cidades na rota evoluída, e não em suas posições absolutas. Por exemplo, se você estava visitando todas as capitais européias, a rota mais curta não depende se você visita Bratislava em 1º, 2º ou 9º. O mais importante é que você o visite imediatamente antes ou imediatamente após visitar Viena Em vez de visitar Helsinque, Atenas e 6 outras capitais no meio.

Claro, como MJV também aponta, o cruzado tradicional também apresentará duplicatas em sua rota. Se um dos pais tiver Paris na posição 2 e outro tem Paris na posição 14, o cruzamento pode resultar em uma rota evoluída que visita Paris duas vezes (e perde outra cidade) e outra rota evoluída que não a visita. O operador genético cruzado ordenado não sofre com esse problema. Preserva os elementos e modifica a ordem.

Answer 3

Aqui está um programa C# abordagem para o que você está procurando.

Com relação ao interesse (ou falta deles) de implementação cruzado, tudo depende da lógica de seleção específica que sua implementação usará (e/ou a própria função de avaliação, se, por exemplo, incluir uma avaliação da velocidade da melhoria). Em muitos casos, As operações cruzadas "resgatarão do bloco de corte" algumas soluções que são eficazes/ideais em uma área do gráfico, mas de alguma forma "preso" em outras. Isso não quer dizer que, se o algoritmo geral for lentamente o suficiente e abrange uma boa porcentagem do espaço da solução, as mesmas soluções podem não ter sido descobertas de novo, mas o cruzamento também pode aumentar essas descobertas (e/ou deixá-lo preso outro mínimo local ;-))

Não diretamente relacionado, mas de interesse digno de nota para quem olhar para Ga, é o Experiência original "Ultimate" em GA Experiência original "Ultimate" em GA pelo Prof. Alderman (da fama da RSA), que usou moléculas de DNA reais [em um programa C - apenas brincando] para resolver um problema de gráfico relacionado, o dos gráficos hamiltonianos.

Editar: Ao reler a pergunta, eu entendo por que você fez ou mais precisamente Por que você gostaria de uma resposta "não, você não quer cruzar" ;-)
Sua genonme está diretamente ligado ao gráfico por si mesmo (nada de errado com isso, a priori), mas isso traz o impedimento de que a maioria dos intervalos não será viável, pois eles podem ter nós duplicados (visite a mesma cidade duas vezes ou mais) e esteja ausente de nós (não visitando algumas cidades) ... Além disso, viável Cross-overs afetarão gráficos semelhantes e, portanto, talvez apenas gastem de forma incremental a pesquisa, em comparação com o que as mutações teriam descoberto ...
Hum ... então talvez cruzado, Nesta implementação em particular não ajudará muito o algoritmo (e, de fato mais iterações e uma taxa de resfriamento mais lenta...). A não ser que! Você encontra uma maneira inteligente de realizar operações cruzadas ;-)

Answer 4

O objetivo do crossover é expandir o espaço evolutivo de pesquisa, reunindo novas combinações genômicas.

O único critério real necessário para o processo evolutivo é que o produto do cruzamento contém partes de ambos os pais e representa um genoma válido.

Somente você conhece as regras de validade para o seu algoritmo para que apenas você possa especificar um método de crossover que funcionará (a menos que você queira compartilhar mais detalhes das regras de validação para sua estrutura de genoma).

Answer 5

Aqui está minha implementação exata do chamado método "parcialmente mapeado crossover" em um GA para TSP.

Aqui é um artigo que explica o crossover parcialmente mapeado em teoria e abaixo é o meu 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;
}

Answer 6

Quando eu estava no primeiro curso da minha universidade, estava fazendo alguns cálculos (que levaram cerca de 30 páginas) sobre o impacto de vários operadores de GA na convergência da solução. Pelo que me lembro, o crossover não é a melhor solução para TSP, uma solução mais adequada é a mutação, que é invertida da subsistência dos vértices.

exemplo:

antes deBcdefGh

após umFedcbGh

Answer 7

"Crossover" em algoritmos genéticos apenas se refere a uma maneira arbitrária de misturar duas "sequências genéticas", cada uma das quais representa uma solução específica para um problema (como uma sequência mapeia para uma solução é de sua). Assim, por exemplo, diga que você tem uma população que consiste nas duas seqüências a seguir:

AAAAAAAAAA
BBBBBBBBBB

Uma maneira de recombinar essas duas seqüências "pais" é escolher aleatoriamente um ponto de cruzamento (digamos, posição 3), resultando nessas duas sequências "crianças":

AAABBBBBBB
BBBAAAAAAA

Ou você pode escolher aleatoriamente dois pontos de cruzamento (digamos, 3 e 8), resultando nessas duas seqüências:

AAABBBBBAA
BBBAAAAABB

Para diversão e variabilidade extra, você também pode apresentar a possibilidade de mutações pontuais ocasionais:

AAABBBABAA
BBBAAAAABB

Não há realmente nenhuma regra rígida sobre como você implementa crossover em um algoritmo genético, assim como não há realmente nenhuma regras rígidas que governem a evolução no mundo biológico. O que quer que funcione, funciona.