Melhor estrutura de dados para o algoritmo genético em C ++?

Question

Eu preciso implementar um algoritmo genético personalizado para o meu problema (projeto de faculdade), ea primeira versão tinha que codificado como uma matriz de curta duração (bits por cromossomo tamanho da população x).

Essa foi uma má concepção, desde que eu estou declarando um curto mas apenas usando o "0" valores e "1" ... mas era apenas um protótipo e funcionou como se pretendia, e agora é hora de eu desenvolver uma versão nova e melhorada. Desempenho é importante aqui, mas a simplicidade também é apreciado.

Eu pesquisei ao redor e veio com:

para o cromossomo: - classe String (como "0100100010") - matriz de bool - vetorial (vetores parece ser otimizado para bool) - bitset (soa o mais natural)

e para a população: - C Array [] - Vector - Queue

Estou inclinado a escolher vector para cromossomo e matriz para pop, mas eu gostaria que a opinião de qualquer pessoa com experiência no assunto.

Agradecemos antecipadamente!

Answer 1

Eu estou supondo que você quer acesso aleatório para a população e para os genes. Você diz que o desempenho é importante, que eu interpreto como a velocidade de execução. Então você é provavelmente melhor fora de usar um vector<> para os cromossomos e uma vector<char> para os genes. A razão para vector<char> é que bitset<> e vector<bool> são optimizados para o consumo de memória, e são, portanto, lento. vector<char> vai lhe dar maior velocidade ao custo de memória x8 (assumindo char = byte em seu sistema). Então se você quiser velocidade, ir com vector<char>. Se o consumo de memória é fundamental, então use vector<bool> ou bitset<>. bitset<> parece ser uma escolha natural aqui, no entanto, ter em mente que ele é templated sobre o número de bits, o que significa que a) o número de genes deve ser fixo e conhecido em tempo de compilação (que eu acho que é um grande não -no), e b) se você usar tamanhos diferentes, você acaba com um tamanho da cópia por bitset de cada um dos métodos bitset que você usa (embora inlining pode negar isso), ou seja, o código bloat. No geral, eu acho que vector<bool> é melhor para você, se você não quer vector<char>.

Se você estiver preocupado com a estética do vector<char> você poderia typedef char gene; e depois usar vector<gene>, que parece mais natural.

A string é como um vector<char> mas mais pesado.

Answer 2

Especificamente para responder sua pergunta. Eu não estou exatamente certo o que você está sugestão. Você fala sobre matriz e classe string. Você está falando sobre as classes de contêiner STL onde você pode ter uma fila, bitset, vetor, lista ligada etc. Gostaria de sugerir um vector para você população (coisa mais próxima de uma matriz C existe) e um bitset para você cromossomo se você estiver preocupados com a capacidade de memória. Então como você já estiver usando um vetor de sua representaion sequência de seu DNA. ( "10110110")

Para idéias e uma boa ferramenta para dabble. Recomendamos que você baixar e inicialmente usar esta biblioteca. Ele funciona com os principais compiladores. Funciona em variantes do UNIX. Tem todo o código-fonte.

Todo o material quadro é feito para você e você vai aprender muito. Mais tarde, você pode escrever seu próprio código a partir do zero ou herdar a partir dessas classes. Você também pode usá-los no código comercial, se quiser.

Porque eles são objetos que podem ser alteradas representaion do seu DNA facilmente de inteiros para reais às estruturas de árvores para matrizes de bits etc etc.

Não é cura sempre aprendendo envolvidos, mas que vale a pena.

Eu usá-lo para gerar milhares de redes neurais, em seguida, eliminá-las com uma função de aptidão simples, em seguida, executá-los de verdade.

Galib

http://lancet.mit.edu/ga/

Answer 3

Assumindo que você quer código por você mesmo (se você quiser uma biblioteca externa kingchris parece ter um bom lá) ele realmente depende de que tipo de manipulação que você precisa fazer. Para obter o máximo retorno para seus investimentos em termos de memória, você pode usar qualquer tipo inteiro e set / manipular bits individuais via bitmasks etc. Agora, esta abordagem provavelmente não ideal em termos de facilidade de uso ... O exemplo a seqüência acima trabalho seria ok, porém novamente não é significativamente diferente do que os shorts, aqui você está agora apenas representando quer '0' ou '1' com um valor de 8 bits em oposição ao valor de 16 bits. Além disso, mais uma vez dependendo da manipulação, o caso corda vai provavelmente revelar unwieldly. Então, se você poderia dar mais algumas informações sobre o algoritmo que talvez pudesse dar mais feedback. Eu gosto dos bits individuais como parte de um inteiro (um bitset), mas se você não está acostumado a máscaras, turnos, e todas essas coisas boas não pode ser bom para você.

Answer 4

Eu sugiro escrever uma classe para cada membro da população, que simplifica as coisas consideravelmente, desde que você pode manter todas as funções relevantes seu membro no mesmo lugar muito bem embrulhado com os dados reais.

Se você precisa de um "conjunto de bools" Eu sugiro usar um int ou vários ints (em seguida, usar máscara e mordeu operações sábias para o acesso (modificar / FLIP) cada bit) dependendo do número de seus cromossomos.

Eu normalmente usado algum tipo de classe de coleção para a população, pois apenas uma matriz de membros da população não permite que você adicione simplesmente à sua população. Eu sugeriria implementar algum tipo de lista dinâmica (se você estiver familiarizado com ArrayList então isso é um bom exemplo).

Eu tive grande sucesso com algoritmos genéticos com a receita acima. Se você preparar sua classe membro corretamente pode coisas realmente simplificar e permite que você se concentrar em algoritmos de codificação melhor genéticas em vez de se preocupar com suas estruturas de dados.