Várias iterações da seleção torneio em algoritmo genético

Question

Ei, eu estou um pouco confuso sobre como várias iterações das obras de seleção torneio.

Eu sei que você começar a selecionar pares aleatórios (ou membros k) e colocar o vencedor em uma piscina de acasalamento. Você continua fazer isso até a piscina de acasalamento é preenchido.

No entanto, eu não sei o que acontece depois.

Será que basta começar acasalamento aleatoriamente aqueles na piscina de acasalamento? E reinicie o processo de seleção, escolhendo pares aleatórios da nova geração?

Graças.

Answer 1

Tradicionalmente depois dos vencedores do torneio são encontrados, eles formam a próxima geração. Todos os processos de mutação, seleção etc continuar após esta em ciclos.

Answer 2

Eu escrevi um monte desses algoritmos genéricos, ao ponto que eu fiz um quadro para evitar escrever o mesmo código novamente e novamente.

Para a piscina de acasalamento, que depende do tipo de pessoas que você está procurando, as soluções que você está procurando, e se você tem uma maneira de combinar os indivíduos de uma forma que há uma chance melhor que eles vão produzir um melhor individual.

Você pode usar o acasalamento aleatório, mas isso vai lhe dar as soluções "pior" - pior, porque você não tem idéia se eles vão produzir um indivíduo ou não melhor. Ele ainda vai ser boas soluções, e quando comecei a escrever estes algoritmos eu sempre usei acasalamento ao acaso, mas imediatamente após a obtenção de um novo indivíduo a partir de 2 antigos, eu comparei o desempenho do 3, e descartou a pior, terminando com o 2 pais às vezes (e descartando a criança de 1 segundo de idade), ou acabar com um pai e um filho.

Mas, para ser mais eficiente, e se você sabe como combinar indivíduos para que eles vão produzir uma solução melhor (e isso pode ser muito complicado), você pode usar uma função de afinidade, que leva 2 pessoas e retorna uma afinidade entre eles. A parte difícil é determinar a afinidade. Dependendo do problema, pode ser muito diferente. Por exemplo, se eu levar o problema caixeiro-viajante, eu tenho as melhores soluções quando acasalamento indivíduo com menos de similaridade. Assim, a minha função de afinidade voltou 1 -. Semelhança

Desta forma, eu poderia reduzir o número de iterações em 80% e obter soluções muito boas.

Mas tenha em mente que quanto maior é a sua piscina, mais tempo vai demorar a função de afinidade para executar - funções de afinidade pode ser O (n²), ou até mesmo O (n³), casos em que ele pode ser o gargalo de seu algoritmo. Neste caso, pode ser melhor usar o acasalamento aleatório.

Em conclusão, o acasalamento aleatório é bom - afinal, podemos dizer que funciona dessa maneira na vida real - mas se você sabe como calcular uma afinidade entre 2 indivíduos, você pode usá-lo para reduzir o número de iterações você precisará obter uma boa solução. Tenha em mente que a afinidade de computação pode ser muito complexa (e eu até acho que se computando os melhores afinidades para uma determinada piscina é NP-Completo).

Answer 3

Isto não é um bom conselho, mas ...

No entanto, eu não sei o que acontece depois.

Faça o que quiser. Você poderia transformar todos eles ... ou você pode acasalar cada par que você escolhe no torneio. Use o que funciona melhor. Seja criativo.

Como alguém neste fórum tem fora pontas:. O pequeno segredo sujo sobre gás é que é mais arte do que ciência

Além disso, para realmente obter um bom conselho, você vai precisar de uma melhor descrição do problema que você quer resolver.