Algorithmes d'approximation de tests unitaires

Question

Je travaille sur une bibliothèque d'algorithmes d'approximation open-source pour les graphes et les réseaux utilisant certains paquets populaires de python comme base. L'objectif principal est d'inclure des algorithmes d'approximation à jour pour les problèmes NP-Complets sur les graphes et les réseaux. La raison de ceci est 1) Je n'ai pas vu un bon paquet consolidé (moderne) qui couvre ceci et 2) ce serait un outil pédagogique agréable pour apprendre des algorithmes d'approximation sur des problèmes d'optimisation de NP-Hard.

En construisant cette bibliothèque, j'utilise des tests unitaires pour vérifier la santé mentale (comme le ferait tout bon développeur). Je suis quelque peu prudent au sujet de mes tests unitaires dans la mesure où, par leur nature même, les algorithmes d'approximation peuvent ne pas renvoyer la bonne solution. Actuellement, je résous à la main quelques petites instances, puis je m'assure que le résultat retourné correspond à cela, mais ce n'est pas souhaitable, ni évolutif au sens de l'implémentation. Quel serait le meilleur moyen d'obtenir des algorithmes d'approximation de test unitaire? Générer des instances aléatoires et s'assurer que les résultats retournés sont inférieurs à la limite garantie par l'algorithme? Cela semblerait avoir de faux positifs (le test a juste eu de la chance ce temps, pas garanti pour toutes les instances d'être en dessous de la limite).

Answer 1

Vous devez séparer deux problèmes ici. La qualité de vos algorithmes d'approximation et l'exactitude de la mise en oeuvre de ces algorithmes. Le test de la qualité d'un algorithme d'approximation ne se prête généralement pas aux méthodes de test unitaire utilisées dans le développement de logiciels. Par exemple, vous devrez générer des problèmes aléatoires représentatifs de la taille réelle des problèmes. Vous pourriez avoir besoin de faire un travail mathématique pour obtenir une limite supérieure/inférieure pour juger de la qualité de vos algorithmes pour les grandes instances insolubles. Ou utilisez des ensembles de tests de problèmes qui ont des solutions connues ou mieux connues et comparez vos résultats. Mais dans tous les cas, les tests unitaires ne vous aideraient pas beaucoup à améliorer la qualité des algorithmes d'approximation. C'est là que votre connaissance du domaine en optimisation et en mathématiques vous aidera.

L'exactitude de votre implémentation est où les tests unitaires seront vraiment utiles. Vous pouvez utiliser des problèmes de taille de jouet ici et comparer les résultats connus (résolution à la main, ou vérifié par un débogage minutieux étape par étape dans le code) avec ce que votre code génère. Avoir de petits problèmes est non seulement suffisant mais également souhaitable ici pour que les tests puissent être exécutés rapidement et puissent être exécutés plusieurs fois au cours du cycle de développement. Ces types de tests s'assurent que l'algorithme global arrive au bon résultat.Il se situe quelque part entre un test unitaire et un test d'intégration puisque vous testez une grande partie du code sous forme de boîte noire. Mais j'ai trouvé ces types de tests extrêmement utiles dans le domaine de l'optimisation. Une chose que je recommande de faire pour ce type de test est de supprimer tout caractère aléatoire dans vos algorithmes grâce à des graines fixes pour les générateurs de nombres aléatoires. Ces tests doivent toujours fonctionner de manière déterministe et donner exactement le même résultat 100% du temps. Je recommande également les tests unitaires aux modules de niveau inférieur de vos algorithmes. Isolez cette méthode qui attribue des poids aux arcs sur le graphique et vérifiez si les poids corrects sont attribués. Isolez votre fonction de calcul de la valeur de la fonction objectif et testez-la. Vous obtenez mon point.

Une autre préoccupation qui coupe ces deux tranches est la performance. Vous ne pouvez pas tester de manière fiable les performances avec des problèmes de petits jouets. Réaliser également une modification qui dégrade les performances de manière significative pour un algorithme de travail rapidement est très souhaitable. Une fois que vous disposez d'une version en cours de vos algorithmes, vous pouvez créer des problèmes de test plus importants en mesurant les performances et en les automatisant pour vos tests de performances/d'intégration. Vous pouvez les exécuter moins souvent, car ils prendront plus de temps, mais au moins vous informerons rapidement des nouveaux goulets d'étranglement des performances lors du refactoring ou des nouvelles fonctionnalités ajoutées aux algorithmes

Answer 2

La vérification de la validité des solutions produites est la première étape évidente. De plus, un angle d'attaque pourrait être regression testing en utilisant des instances pour lesquelles la solution approximative attendue est connue (obtenue par exemple en exécutant l'algorithme manuellement ou en utilisant l'implémentation du même algorithme par quelqu'un d'autre).

Il existe également des référentiels d'instances de problèmes avec des solutions (optimales) connues, telles que TSPLIB pour les problèmes de type TSP. Peut-être que cela pourrait être utile.

S'il existe des limites supérieures connues pour l'algorithme en question, la génération de nombreuses instances aléatoires et la vérification des solutions heuristiques par rapport aux limites supérieures peuvent s'avérer fructueuses. Si vous faites cela, je vous demanderais de rendre les passages reproductibles (par exemple en utilisant toujours le même générateur de nombres aléatoires et la même graine).

Une note finale: pour certains problèmes, les instances totalement aléatoires sont en moyenne assez faciles à trouver. Le TSP asymétrique avec des poids d'arc choisis de manière uniforme et indépendante en est un exemple. Je le mentionne car cela pourrait affecter votre stratégie de test.

Answer 3

Il est généralement possible de vérifier, par exemple, que votre algorithme renvoie toujours des solutions qui satisfont leurs contraintes, même si elles ne sont pas optimales. Vous devriez également mettre en place des vérifications d'assertions à chaque occasion possible - elles seront spécifiques à votre programme, mais peuvent vérifier qu'une certaine quantité est conservée, ou que quelque chose qui devrait augmenter ou, au pire, ne pas diminuer, ou optimum est vraiment un optimum local. Etant donné ces sortes de vérifications, et les contrôles sur les bornes que vous avez déjà mentionnés, je préfère exécuter des tests sur un très grand nombre de petits problèmes générés aléatoirement, avec des graines aléatoires choisies de telle sorte que si cela échoue sur le problème 102324 vous pouvez répéter cet échec pour le débogage sans passer par les problèmes 102323 avant lui. Avec un grand nombre de problèmes, vous augmentez la probabilité qu'un bogue sous-jacent provoque une erreur suffisamment flagrante pour échouer vos contrôles. Avec de petits problèmes, vous augmentez les chances que vous puissiez trouver et corriger le bug.