Algoritmos de aproximação de testes unitários

Question

Estou trabalhando em uma biblioteca de algoritmos de aproximação de código aberto para gráficos e redes usando alguns pacotes python populares como base.O objetivo principal é abranger algoritmos de aproximação atualizados para problemas NP-Completos em grafos e redes.A razão para isso é 1) não vi um pacote consolidado legal (moderno) que cubra isso e 2) seria uma boa ferramenta pedagógica para aprender sobre algoritmos de aproximação em problemas de otimização NP-Hard.

Ao construir esta biblioteca, estou usando testes de unidade para verificação de integridade (como qualquer desenvolvedor adequado faria).Sou um tanto cauteloso em relação aos meus testes unitários, pois, por sua própria natureza, os algoritmos de aproximação podem não retornar a solução correta.Atualmente estou resolvendo algumas pequenas instâncias manualmente e garantindo que o resultado retornado corresponda a isso, mas isso não é desejável, nem escalonável no sentido de implementação.

Qual seria a melhor maneira de algoritmos de aproximação de teste unitário?Gerar instâncias aleatórias e garantir que os resultados retornados sejam menores que o limite garantido pelo algoritmo?Isso parece ter falsos positivos (o teste teve sorte daquela vez, não é garantido que todas as instâncias estejam abaixo do limite).

Answer 1

Você precisa separar duas preocupações aqui.A qualidade dos seus algoritmos de aproximação e a correção da implementação desses algoritmos.

Testar a qualidade de um algoritmo de aproximação geralmente não se presta aos métodos de teste unitário usados ​​no desenvolvimento de software.Por exemplo, você precisaria gerar problemas aleatórios que representassem o tamanho real dos problemas.Talvez seja necessário fazer um trabalho matemático para obter um limite superior/inferior para julgar a qualidade de seus algoritmos para grandes instâncias insolúveis.Ou use conjuntos de testes de problemas que tenham soluções conhecidas ou mais conhecidas e compare seus resultados.Mas, em qualquer caso, o teste unitário não ajudaria muito a melhorar a qualidade dos algoritmos de aproximação.É aqui que seu conhecimento de domínio em otimização e matemática ajudará.

A correção da sua implementação é onde os testes unitários serão realmente úteis.Você pode usar problemas do tamanho de um brinquedo aqui e comparar resultados conhecidos (resolvidos manualmente ou verificados por meio de depuração cuidadosa passo a passo no código) com o que seu código gera.Ter pequenos problemas não é apenas suficiente, mas também desejável aqui, para que os testes sejam executados rapidamente e possam ser executados muitas vezes durante o ciclo de desenvolvimento.Esses tipos de testes garantem que o algoritmo geral chegue ao resultado correto.Está em algum lugar entre um teste de unidade e um teste de integração, já que você está testando uma grande parte do código como uma caixa preta.Mas descobri que esses tipos de testes são extremamente úteis no domínio da otimização.Uma coisa que recomendo fazer para esse tipo de teste é remover toda a aleatoriedade dos seus algoritmos por meio de sementes fixas para geradores de números aleatórios.Esses testes devem sempre ser executados de forma determinística e fornecer exatamente o mesmo resultado 100% das vezes.Também recomendo testes unitários nos módulos de nível inferior dos seus algoritmos.Isole o método que atribui pesos aos arcos do gráfico e verifique se os pesos corretos foram atribuídos.Isole sua função de cálculo do valor da função objetivo e teste-a na unidade.Você entendeu.

Uma outra preocupação que corta essas duas fatias é o desempenho.Você não pode testar o desempenho de forma confiável com pequenos problemas de brinquedos.Também é muito desejável perceber rapidamente uma mudança que degrada significativamente o desempenho de um algoritmo em funcionamento.Depois de ter uma versão em execução de seus algoritmos, você poderá criar problemas de teste maiores onde medir o desempenho e automatizá-lo para serem seus testes de desempenho/integração.Você pode executá-los com menos frequência, pois eles levarão mais tempo, mas pelo menos irão notificá-lo antecipadamente sobre gargalos de desempenho recentemente introduzidos durante a refatoração ou novas adições de recursos aos algoritmos

Answer 2

Verificar a validade das soluções produzidas é o primeiro passo óbvio.

Além disso, um ângulo de ataque poderia ser teste de regressão usando instâncias para as quais a solução aproximada esperada é conhecida (por exemploobtido executando o algoritmo manualmente ou usando a implementação do mesmo algoritmo por outra pessoa).

Também existem repositórios de instâncias de problemas com soluções conhecidas (ótimas), como TSPLIB para problemas do tipo TSP.Talvez estes pudessem ser usados ​​de alguma forma.

Se houver limites superiores conhecidos para o algoritmo em questão, gerar muitas instâncias aleatórias e verificar as soluções heurísticas em relação aos limites superiores pode ser frutífero.Se você fizer isso, recomendo que você torne as execuções reproduzíveis (por exemplo,usando sempre o mesmo gerador de números aleatórios e semente).

Uma nota final:para alguns problemas, instâncias totalmente aleatórias são, em média, muito fáceis de encontrar boas soluções aproximadas.O TSP assimétrico com pesos de arco escolhidos de maneira uniforme e independente é um exemplo.Estou mencionando isso porque pode afetar sua estratégia de teste.

Answer 3

Geralmente, há algo que você pode verificar - por exemplo, se seu algoritmo sempre retorna soluções que satisfaçam suas restrições, mesmo que não sejam ideais. Você também deve colocar verificações de asserção em todas as oportunidades possíveis - elas serão específicas para seu programa, mas podem verificar se alguma quantidade é conservada, ou se algo que deveria aumentar ou, na pior das hipóteses, permanecer o mesmo não diminui, ou que algum suposto local o ótimo é realmente um ótimo local.

Dados esses tipos de verificações e as verificações de limites que você já mencionou, sou a favor da execução de testes em um número muito grande de pequenos problemas gerados aleatoriamente, com sementes aleatórias escolhidas de forma que se falhar no problema 102324 você pode repetir essa falha para depuração sem passar pelos 102323 problemas anteriores. Com um grande número de problemas, você aumenta a chance de que um bug subjacente cause um erro óbvio o suficiente para falhar em suas verificações. Com pequenos problemas, você aumenta a chance de encontrar e corrigir o bug.