Comparando dois algoritmos genéticos

9

Eu tenho duas implementações de um algoritmo genético que devem se comportar de forma equivalente. No entanto, devido a restrições técnicas que não podem ser resolvidas, sua saída não é exatamente a mesma, dada a mesma entrada.

Ainda assim, gostaria de mostrar que não há diferença significativa de desempenho.

Eu tenho 20 execuções com a mesma configuração para cada um dos dois algoritmos, usando sementes de números aleatórios iniciais diferentes. Para cada execução e geração do mínimo de erro de fitness do melhor indivíduo na população foi gravado. O algoritmo emprega um mecanismo de preservação de elite, de modo que a aptidão do melhor indivíduo diminui monotonicamente. Uma corrida consiste em 1000 gerações, então eu tenho 1000 valores por corrida. Não consigo obter mais dados, pois os cálculos são muito caros.

Qual teste devo empregar? Uma maneira fácil seria provavelmente comparar apenas o erro nas gerações finais (novamente, qual teste eu usaria aqui)? Mas também se pode pensar em comparar o comportamento de convergência em geral.

nisc
fonte
Apenas como um esclarecimento: não é o caso de um algoritmo genético procurar aleatoriamente uma solução, de modo que é improvável que o segmento inicial de qualquer execução produza qualquer solução que valha a pena? Além disso, o que exatamente você quer dizer com "o erro mínimo na população"? Se você quer dizer a diferença mínima entre um valor verdadeiro conhecido e qualquer solução dos 1000 valores em uma execução, essa não é uma indicação tendenciosa do resultado da execução? Afinal, na prática, você aceitaria a solução final em cada execução e rejeitaria tudo o que a precede, certo?
whuber
Por erro, eu basicamente quero dizer 1 / fitness, então estou falando sobre o valor do melhor indivíduo em uma geração. Registrei o valor de condicionamento físico do melhor indivíduo para cada geração. Então, eu tenho 1000 * 20 * 2 números, cada um correspondendo à "adequação" do melhor indivíduo em uma geração específica de uma execução específica.
nisc 18/08/10
Eu acho que a pergunta inicial foi mal colocado, eu adicionei alguns esclarecimentos ..
NISC

Respostas:

9

Testar algoritmos estocásticos pode ser bastante complicado!

Trabalho em biologia de sistemas e existem muitos simuladores estocásticos disponíveis para simular um modelo. Testar esses simuladores é complicado, pois duas realizações de um único modelo serão tipicamente diferentes.

Nos dsmts , calculamos (analiticamente) o valor e a variação esperados de um modelo específico. Em seguida, realizamos um teste de hipótese para determinar se um simulador difere da verdade. A seção 3 do guia do usuário fornece os detalhes. Essencialmente, fazemos um teste t para os valores médios e um teste qui-quadrado para variâncias.

No seu caso, você está comparando dois simuladores, portanto, você deve usar um teste t com duas amostras.

csgillespie
fonte
Como eu usaria as informações de todas as gerações?
nisc 18/08/10
A maneira mais fácil é fazer vários testes, ou seja, testar a cada geração e usar uma correção Bonferroni ou fdr.
precisa saber é o seguinte
Ao comparar em todas as gerações, eu teria que testar em um nível de significância de 1/1000 * 0,05? Isso não é um pouco duro?
nisc 18/08/10
É verdade, mas você também está fazendo muitos testes - não pode ter tudo;) Você pode classificar os valores-p, usá-los como um guia para ver onde possíveis erros podem ocorrer.
precisa saber é o seguinte
11
Em vez da correção de bonferroni, você sempre pode usar a holm bonferroni mais poderosa. Veja meu anyswer aqui: stats.stackexchange.com/questions/575/…
Henrik
4

Talvez você possa medir a diferença média entre duas execuções do mesmo algoritmo com a diferença média entre duas execuções de algoritmos diferentes. Não resolve o problema de como medir essa diferença, mas pode ser um problema mais tratável. E os valores individuais da série temporal alimentariam o cálculo da diferença em vez de serem tratados como pontos de dados individuais para serem avaliados uns contra os outros (também não acho que a diferença específica na enésima etapa seja o que você realmente deseja). faça declarações sobre).

Atualização Sobre os detalhes - bem, em quais recursos da série temporal você está interessado, além do erro final? Eu acho que você realmente tem três perguntas diferentes para resolver:

  1. O que constitui uma semelhança para você, ou seja, o que você quer dizer quando diz que não acredita que os dois métodos são diferentes?
  2. Como você o quantifica - pode ser respondido após 1 e
  3. Como você pode testar diferenças significativas entre seus dois métodos?

Tudo o que eu estava dizendo no primeiro post foi que a resposta para (1) provavelmente não considera as diferenças individuais em cada uma das 1000 gerações. E que eu recomendaria a criação de um valor escalar para cada série temporal ou pelo menos semelhança entre séries temporais. Somente então você chega à questão das estatísticas reais (que eu sei menos sobre os três pontos), mas fui aconselhado a usar um teste t emparelhado em uma pergunta semelhante que acabei de fazer, ao ter um valor escalar por elemento).

user979
fonte
parece razoável, mais detalhes?
nisc 18/08/10