Comment tester un algorithme génétique ?

Question

J'ai réalisé un certain nombre d'algorithmes génétiques ; ils fonctionnent (ils trouvent rapidement une solution raisonnable). Mais j'ai maintenant découvert TDD . Existe-t-il un moyen d'écrire un algorithme génétique (qui s'appuie fortement sur des nombres aléatoires) de manière TDD ?

Pour poser la question de manière plus générale, comment tester une méthode/fonction non déterministe. Voici ce à quoi j'ai pensé :

1. Utilisez une graine spécifique. Ce qui ne m'aidera pas si je fais une erreur dans le code en premier lieu, mais aidera à trouver des bugs lors de la refactorisation.

2. Utilisez une liste de numéros connus. Similaire à ce qui précède, mais je pourrais suivre le code à la main (ce qui serait très fastidieux).

3. Utilisez un nombre constant. Au moins, je sais à quoi m'attendre. Il serait bon de s'assurer qu'un dé indique toujours 6 lorsque RandomFloat(0,1) renvoie toujours 1.

4. Essayez de déplacer autant de code non déterministe que possible hors de l'AG, ce qui semble idiot puisque c'est le cœur de son objectif.

Des liens vers de très bons livres sur les tests seraient également appréciés.

Answer 1

Il me semble que la seule façon de tester son logique cohérente est d'appliquer contribution constante , ... ou traiter chaque itération comme un automate unique dont l'état est testé avant et après cette itération, transformant le système global non déterministe en composants testables basés sur des valeurs d'itération déterministes.

Pour les variations/la reproduction/l'héritage d'attributs dans les itérations, testez ces valeurs aux limites de chaque itération et testez la sortie globale de toutes les itérations sur la base des entrées/sorties connues des itérations-sous-tests réussies ...

Comme l'algorithme est itératif, vous pouvez utiliser induction dans vos tests pour vous assurer qu'il fonctionne pour 1 itération, n+1 itérations pour prouver qu'il produira des résultats corrects (indépendamment du déterminisme des données) pour une plage/un domaine d'entrée donné et les contraintes sur les valeurs possibles en entrée.

Modifier J'ai trouvé ceci stratégies pour tester les systèmes non déterministes qui pourrait fournir un aperçu. Il pourrait être utile pour l'analyse statistique des résultats en direct, une fois que le processus de TDD/développement aura prouvé que la logique est saine.

Answer 2

Je testerais des fonctions aléatoires en les testant un certain nombre de fois et en analysant si la distribution des valeurs de retour correspond aux attentes statistiques (cela implique quelques connaissances statistiques).

Answer 3

Si vous parlez de TDD, je dirais qu'il faut absolument commencer par choisir un nombre constant et développer votre suite de tests à partir de là. J'ai fait du TDD sur quelques problèmes hautement mathématiques et il est utile d'avoir quelques cas constants que vous connaissez et que vous avez élaborés à la main pour les utiliser dès le début.

En ce qui concerne votre quatrième point, déplacer le code non déterministe hors de l'AG, je pense que c'est probablement une approche qui mérite d'être considérée. Si vous pouvez décomposer l'algorithme et séparer les préoccupations non déterministes, cela devrait rendre les tests des parties déterministes plus simples. Tant que vous faites attention à la façon dont vous nommez les choses, je ne pense pas que vous sacrifiez grand chose ici. A moins que je ne comprenne mal, l'AG continuera à déléguer à ce code, mais il vit ailleurs.

En ce qui concerne les liens vers de très bons livres sur les tests (de développeurs), mes préférés sont les suivants :

• Pilotage par les tests par Lasse Kosela
• Travailler efficacement avec le code hérité par Michael Feathers
• Patrons de test XUnit par Gerard Meszaros
• La nouvelle génération de tests Java™ : TestNG et concepts avancés par Cédric Beust & Hani Suleiman

Answer 4

Vous pourriez écrire un réseau neuronal redondant pour analyser les résultats de votre algorithme et faire en sorte que la sortie soit classée en fonction des résultats attendus. :)

Décomposez votre méthode autant que possible. Ensuite, vous pouvez également avoir un test unitaire autour de la partie aléatoire pour vérifier la gamme de valeurs. Faites même exécuter le test plusieurs fois pour voir si le résultat change.

Answer 5

J'ai écrit une application didactique C# TDD Genetic Algorithm : http://code.google.com/p/evo-lisa-clone/

Prenons la méthode de résultat aléatoire la plus simple de l'application : PointGenetics.Create, qui crée un point aléatoire, compte tenu des limites. Pour cette méthode, j'ai utilisé 5 tests, et aucun d'entre eux ne repose sur une graine spécifique :

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

Le test d'aléa est simple : pour une grande limite (nombreuses possibilités), deux points générés consécutifs ne doivent pas être égaux. Les autres tests vérifient d'autres contraintes.