Uma pergunta detalhada ao aplicar o algoritmo genético ao vendedor ambulante de viagem

Question

Li várias coisas sobre isso e entendo o princípio e os conceitos envolvidos, no entanto, nenhum papel menciona os detalhes de como calcular a aptidão de um cromossomo (que representa uma rota) envolvendo cidades adjacentes (no cromossomo) que não estão diretamente conectadas por uma borda (no gráfico).

Por exemplo, dado um cromossomo 1 | 3 | 2 | 8 | 4 | 5 | 6 | 7, no qual cada gene representa o índice de uma cidade no gráfico/mapa, como calculamos sua aptidão (ou seja, a soma total de distâncias percorridas) Se, digamos, não houver borda/link direto entre a cidade 2 e 8. Seguimos algum tipo de algoritmo ganancioso para calcular uma rota entre 2 e 8 e adicionar a distância dessa rota ao total?

Esse problema parece bastante comum ao aplicar o GA ao TSP. Qualquer pessoa que tenha feito isso antes, compartilhe sua experiência. Obrigado.

Answer 1

Se não houver link entre 2 e 8 no seu gráfico, qualquer cromossomo com 2 | 8 ou 8 | 2 é inválido Para o problema clássico de vendedor ambulante. Se você encontrar outra rota entre 2 e 8, provavelmente violará o requisito "Visite cada local uma vez".

Uma solução realmente desonesta, mas pragmática, é incluir arestas entre esses nós com distâncias incrivelmente altas, ou até +INF se o seu idioma o suportar. Dessa forma, sua função padrão de minimização de condicionamento físico ascará -las naturalmente.

Eu acho que a formulação original do problema inclui arestas entre todos os nós, então isso não é um problema.

Answer 2

Esse é o tipo exato de problema, métodos especializados de crossover e mutação foram aplicados para soluções baseadas em GA para problemas de TSP. Veja isso pergunta.

Answer 3

Se a cromosona não representar uma solução válida, será totalmente inapto para resolver o problema. Então, dependendo de como você pede aptidão. ou seja, se um número mais baixo representar mais aptidão (possivelmente uma boa idéia quando o condicionamento físico representa o custo total), você atribuiria um valor máximo e quebraria qualquer cálculo adicional de condicionamento físico nessa cromosona quando você chegar a uma sequência genética que é inválida.

(ou vice -versa, atribua -lhe uma aptidão zero se uma aptidão mais alta significa que uma cromosona é mais adequada para o trabalho)

No entanto, como outros apontaram, poderia ser melhor garantir que as cromosonas inválidas não ocorram. No entanto, se esse é um processo excessivamente comx, permitir -lhes e garantir que as cromosonas quebradas dificilmente se transformem em gerações sucessivas poderiam ser uma abordagem aceitável.