Como representar um caminho para um algoritmo genético?

Question

I pretende utilizar um GA para determinar o caminho óptimo de A a B, que satisfaçam certas condições (comprimento, o número de voltas, etc.)

Um exemplo de um caminho é: Up 4, Left 8, Down 3, Direita 3, para baixo 1, Esquerda 10, até 4, Left 1, até 3

O problema é que eu realmente não sei uma boa maneira de representar a informação como esta em um bom caminho para o uso em um GA, especialmente porque os caminhos têm um comprimento variável.

Alguém tem uma boa idéia de como fazer algo assim?

Answer 1

Eu não sei exatamente o que o seu problema representação é, então eu suspeito que você tem esta pergunta de um mal-entendido de corda cromossomo de um GA. Teoricamente falando, a seqüência de cromossomos não tem que ser recombinados explicitamente em limites inteiro se você tomar a etapa extra de demarcar seus genes individuais, que lhe permitem recombinar em uma base gene-por-gene. Isto resolve o problema de um gene de comprimento variável, tal como o "percurso". Recombinação de genes de comprimento variável é apenas uma questão de adicionar uma outra variante ao método de mutação, especificamente "usar este elemento ou bombardear este elemento" em adição ao "elemento de utilização de um elemento ou de B" padrão se o gene é quebrável em discreta elementos, como o seu caminho é.

Answer 2

Parece que você realmente querem estar usando algo parecido com o A * algoritmo de otimização , que é comumente usado (com bons resultados) para o caminho-finding. Você pode especificar qualquer função heurística que você gosta, a fim de obter a solução apropriada.

Answer 3

Gostaria de usar U, D, L, R ....

Assim, "Up 4, Left 8, Down 3, Direita 3, para baixo 1, Esquerda 10, Up 4, Left 1, Up 3" seria:

UUUULLLLLLLLDDDRRRDLLLLLLLLLLUUUULUUU

Seria muito mais fácil para se reproduzir cordas assim.

Para A (15 caracteres) e B (3 caracteres), a minha função de reprodução entre A e B seria:

• Escolha de um comprimento desejado aleatório (len) entre 1 e MAX (LEN (A), LEN (B)) {entre 1 e 15}
• Escolha um ponto (s) de divisão aleatório entre 1 e Len.
• Escolha se você quer A ou B para ir primeiro aleatoriamente.
• Siga as primeiras s personagens o único a ir em primeiro lugar, e os últimos caracteres (LEN-s) do outro.

Answer 4

GA pode lidar com cromossomas com comprimento variável. Actual individual pode ser muito complexo. por exemplo, ele pode conter um número de bits de comprimento fixo, cadeia de caracteres (comprimento não fixo), e talvez algum conjunto de pares de números complexos conjugados. Além disso conjugadas números complexos pares deve sempre preservar algumas condições. Isso pode ser feito, mas o indivíduo mais complexo fica, operações genéticas mais complexas se (por exemplo cross over, mutação). Provavelmente função da aptidão levaria mais algumas linhas de código. Mas ainda é possível.

Talvez como sugerido que você poderia escolheu o número codificado representação caminho, mas ainda pode ser feito com o seu exemplo codificado como Osama ALASSIRY sugeriu:. UUUULLLLLLLLDDDRRRDLLLLLLLLLLUUUULUUU
Por mais de cruz:

• operador deixar mutação ler lenght1 atual de determinado indivíduo,
• gerar dois aleatório números x1, y1, tanto x1, y1 =
• fazer o mesmo para o indivíduo 2, agora você tem dois pares (x1, y1) e (x2, y2),
• copiar do indivíduo 1 que está entre x1 e y1, e insira-o indivíduo 2 entre os valores X2 e Y2. Nova versão do Individual 2 pode mudar seu comprimento como número de genes entre X1Y1 e x2y2 pode ser diferente, mas isso é ok,
• o que estava na versão original do indivíduo 2 entre x2y2 deve ser inserido nova versão do indivíduo 1 entre X1Y1 (seu comprimento também vai mudar),

Para deixar claro:
pai A: UUUULLLLLLLLDDDRRRDLLLLLLLLLLUUUULUUU
pai B: DRRRRLULUDDDR
você gerar pares aleatórios Paíra (4,18), pairB (0,5) supondo que você contar genes de 0 você trocar seguintes cadeias:
UUUU LLLLLLLLDDDRRRD LLLLLLLLLLUUUULUUU
DRRRRL ULUDDDR
Então, depois de cruz sobre você começa
UUUU DRRRRL LLLLLLLLLLUUUULUUU
LLLLLLLLDDDRRRD ULUDDDR
Agora você só fez mais de cruz. você pode usar também um ponto de corte, ou pontos multiplicam.

Quanto à mutação:

• gerar número entre 0 e comprimento do indivíduo,
• gerar número entre 1-4 e actualizam-gene. (Se foi gerado um alterá-lo para L, 2-D, L-3, 4-R)

você fez mutação. Você também pode mutação mais de um gene.

Mas como eu disse, existem outras possibilidades.

Answer 5

Para mim, isso soa bastante semelhante ao problema do caixeiro Viajando , isso página conter algum informação útil?