Como devo testar um algoritmo genético

Question

Eu fiz uma muito poucos algoritmos genéticos; eles trabalham (eles encontrar uma solução razoável rapidamente). Mas agora eu descobri TDD . Existe uma maneira de escrever um algoritmo genético (que depende fortemente de números aleatórios) de uma forma TDD ?

Para colocar a questão de forma mais geral, Como você testar um método não-determinístico / função. Aqui está o que eu ter pensado:

1. Use uma semente específica. Que não vai ajudar se eu cometer um erro no código, em primeiro lugar, mas vai ajudar a encontrar bugs quando refatoração.

2. Use uma lista conhecida de números. Semelhante ao anterior, mas eu poderia seguir o código através de mão (o que seria muito tedioso).

3. Use um número constante. Pelo menos eu sei o que esperar. Seria bom para garantir que um dado sempre lê 6 quando RandomFloat (0,1) sempre retorna 1.

4. Tente mover o máximo de código não-determinístico fora da GA possível. que parece bobagem, que é o cerne da questão de propósito.

Os links para livros muito bons sobre o teste seria apreciada também.

Answer 1

Parece-me que a única maneira de testar a sua lógica consistente é a aplicação de de entrada consistente , ... ou deleite cada iteração como um único autómato cujo estado é testado antes e após a iteração, rodando o sistema de não-determinístico global em componentes testáveis ??com base em valores de iteração determinísticos.

Para variações / criação / herança atributo em iterações, testar esses valores sobre os limites de cada iteração e testar a produção global de todas as iterações com base na entrada conhecido / saída do sucesso iteração subtestes ...

Uma vez que o algoritmo é iterativo você pode usar indução em seu teste para garantir que ele funciona para uma iteração, n + 1 iterações para provar que irá produzir resultados corretos (independentemente do determinismo de dados) para um determinado faixa de entrada / domínio e as restrições sobre possíveis valores de entrada.

Editar Eu encontrei este estratégias para testes sistemas não-determinísticos que poderia fornecer algum insight. Pode ser útil para a análise estatística dos resultados ao vivo uma vez que o processo de TDD / desenvolvimento comprova a lógica é boa.

Answer 2

Gostaria de testar funções aleatórias, testando-lhes um número de vezes e analisar se a distribuição dos valores de retorno atende às expectativas estatísticos (isso envolve algum conhecimento estatístico).

Answer 3

Se você está falando TDD, eu diria definitivamente começar por escolher um número constante e crescente a sua suíte de testes de lá. Eu fiz TDD em alguns problemas altamente matemáticos e isso ajuda a ter alguns casos constantes que você conhece e têm trabalhado à mão para ser executado com desde o início.

W / R / T seu quarto ponto, mover o código nondeterministic fora da GA, eu acho que esta é provavelmente uma pena abordagem considerando. Se você pode decompor o algoritmo e separar as preocupações não deterministas, ele deve fazer o teste do simples peças deterministas. Contanto que você for cuidadoso sobre como você nomear as coisas que eu não acho que você está sacrificando muito aqui. A menos que eu sou mal-entendido que você, o GA ainda vai delegar a este código, mas ele vive em outro lugar.

Quanto links para livros muito bons sobre (desenvolvedor) testar meus favoritos são:

• Test Driven por Lasse Kosela
• trabalhar efetivamente com Legacy Code por Michael Feathers
• Padrões xUnit teste por Gerard Meszaros
• Next Generation Java ™ Testing: TestNG e avançados conceitos por Cédric Beust & Hani Suleiman

Answer 4

Uma maneira que eu faço para unidade testar de funções não deterministas de algoritmos GA é colocar a eleição de números aleatórios em uma função diferente da uma lógica que os usos que os números aleatórios.

Por exemplo, se você tem uma função que leva um gene (vector de algo) e leva dois pontos aleatórios do gene para fazer alguma coisa com eles (mutação ou qualquer outro), você pode colocar a geração de números aleatórios em um função, e depois passá-las, juntamente com o gene para uma outra função que contém a lógica dado que números.

Desta forma, você pode fazer TDD com a função lógica e passá-lo certos genes e determinados números, sabendo exatamente o que a lógica deve fazer no gene dado que os números e ser capaz de escrever afirma no gene modificado.

Outra maneira, para teste com a geração de números aleatórios é externalização que a geração de outra classe, que pode ser acedido através de um contexto ou carregado a partir de um valor de configuração, e usando um diferente para execuções de teste. Haveria duas implementações dessa classe, uma para produção que gera números aleatórios reais, e outro para testes, que teriam maneiras de aceitar os números que mais tarde ele irá gerar. Em seguida, no teste que você poderia estabelecer que determinados números que a classe irá fornecer ao código testado.

Answer 5

Você poderia escrever uma rede neural redundante para analisar os resultados de seu algoritmo e ter a saída classificados de acordo com os resultados esperados. :)

Quebre seu baixo método, tanto quanto sua lata. Em seguida, você também pode ter um teste de unidade em torno de apenas a parte aleatória para verificar o intervalo de valores. Mesmo têm o teste algumas vezes para ver se as mudanças de resultados.

Answer 6

Todas as suas funções devem ser completamente determinista. Isso significa que nenhuma das funções que você está testando deve gerar o número aleatório dentro da própria função. Você vai querer passar isso como um parâmetro. Dessa forma, quando o programa está a tomar decisões com base em seus números aleatórios, você pode passar em números representativos para testar a saída esperada para esse número. A única coisa que não deve ser determinista é o seu gerador de números aleatórios real, que você realmente não precisa se preocupar muito sobre porque você não deveria estar escrevendo isso sozinho. Você deve ser capaz de simplesmente assumir que funciona, desde que a sua uma biblioteca estabelecida.

Isso é para os testes de unidade. Para os testes de integração, se você estiver fazendo isso, você pode olhar para zombando de sua geração de números aleatórios, substituindo-o por um algoritmo que irá retornar números conhecidos 0..n para cada número aleatório que você precisa gerar.

Answer 7

Eu escrevi uma aplicação didáctica C # TDD Algoritmo Genético: http://code.google.com/p/evo-lisa-clone/

Vamos tomar o mais simples método de resultado aleatório na aplicação: PointGenetics.Create, o que cria um ponto aleatório, dados os limites. Por este método que eu usei 5 testes, e nenhum deles se baseia em uma semente específica:

http: / /code.google.com/p/evo-lisa-clone/source/browse/trunk/EvoLisaClone/EvoLisaCloneTest/PointGeneticsTest.cs

O teste de aleatoriedade é simples: para uma grande fronteira (muitas possibilidades), dois pontos gerados consecutivos não deve ser igual. Os testes restantes verificar outras restrições.

Answer 8

Bem, a parte mais testável é a função de fitness - onde toda a sua lógica será. isso pode ser, em alguns casos bastante complexos (que você pode estar executando todos os tipos de simulações com base em parâmetros de entrada) Então você quer ter certeza de todas as coisas que trabalha com um monte de testes de unidade, e este trabalho pode seguir qualquer metodologia.

Com relação ao testar o GA parâmetros (taxa de mutação, a estratégia de cross-over, o que for), se você está implementando essas coisas se você pode certamente testá-lo (você pode voltar a ter testes de unidade em torno lógica mutação etc.), mas você ganhou 't ser capaz de testar o 'ajuste fino' do GA.

Em outras palavras, você não será capaz de testar se GA realmente executa de forma diferente da bondade das soluções encontradas.

Answer 9

Um teste que o algoritmo dá-lhe o mesmo resultado para a mesma entrada poderia ajudá-lo, mas às vezes você vai fazer alterações que mudam o resultado escolhendo comportamento do algoritmo.

Gostaria de aproveitar ao máximo esforço para ter um teste que garante que o algoritmo dá-lhe um resultado correto. Se o algoritmo dá-lhe um resultado correto para um número de sementes estáticas e valores aleatórios o algoritmo funciona ou não é quebrado através das alterações feitas.

Outra chance em TDD é a possibilidade de avaliar o algoritmo. Se você pode verificar automaticamente o quão bom resultado é que você pode adicionar testes que mostram que uma mudança não reduziu as qualidades de seus resultados ou aumento de seu tempo de cálculo razoável.

Se você quiser testar o seu algoritmo com muitas sementes de base que você talvez querem ter a processos de teste de um terno que executa um teste rápido para iniciar após cada economizar para garantir que você não tenha quebrado nada e um terno que se estende por uma mais tempo para uma avaliação mais tarde

Answer 10

Eu altamente sugiro olhar em usar objetos mock para seus casos de teste de unidade ( http: // en. wikipedia.org/wiki/Mock_object ). Você pode usá-los para zombar de objetos que fazem suposições aleatórias, a fim de causar-lhe obter resultados esperados vez.