單元測試近似算法

Question

我正在使用一些流行的python軟件包作爲基礎，開發圖形和網絡的開源逼近算法庫。主要目標是包含圖形和網絡上NP-Complete問題的最新近似算法。原因是1）我還沒有看到一個很好的（現代）整合包，它涵蓋了這個，2）它將是一個很好的學習NP-Hard優化問題的近似算法的教學工具。

在構建這個庫時，我使用單元測試來進行健全性檢查（就像任何適當的開發人員一樣）。我對自己的單元測試有點謹慎，因爲從本質上來說，近似算法可能不會返回正確的解決方案。目前，我正在手工解決一些小實例，然後確保返回的結果與此匹配，但這不是可取的，也不具有實現意義上的可擴展性。

單元測試近似算法的最佳方法是什麼？生成隨機實例並確保返回的結果小於算法保證的邊界？這似乎有誤報（測試只是幸運的那一次，並不保證所有實例都低於界限）。

Answer 1

你需要在這裏分離兩個問題。近似算法的質量以及這些算法的實現的正確性。

測試近似算法的質量通常不適用於軟件開發中使用的單元測試方法。例如，您需要生成代表實際問題大小的隨機問題。您可能需要進行數學工作才能獲得一些上下限來判斷無法解析的大型實例的算法質量。或者使用已知或最知名解決方案的問題測試集並比較您的結果。但是在任何情況下，單元測試對於提高近似算法的質量都無能爲力。這是你在優化和數學領域的知識將會幫助你的地方。

你的實現的正確性是單元測試真正有用的地方。您可以在此處使用玩具大小的問題，並將已知結果（通過手工解決，或通過仔細逐步調試代碼進行驗證）與代碼生成的結果進行比較。遇到小問題不僅足夠，而且在這裏也是可取的，以便測試運行速度快，並且可以在開發週期中多次運行。這些類型的測試確保整體算法達到正確的結果。由於您正在將大部分代碼作爲黑盒進行測試，因此它位於單元測試和集成測試之間。但是我發現這些類型的測試在優化領域非常有用。我建議爲這種類型的測試做的一件事是通過用於隨機數生成器的固定種子去除算法中的所有隨機性。這些測試應始終以確定性的方式運行，並在100％的時間內給出完全相同的結果。 我還建議在算法的較低級別模塊進行單元測試。隔離將權重分配給圖形上的圓弧的方法，並檢查是否分配了正確的權重。隔離你的目標函數值計算函數和單元測試。你明白我的觀點。

削減這兩個切片的另一個問題是性能。小玩具問題不能可靠地測試性能。對於快速工作的算法，也意識到實現顯着降低性能的改變是非常需要的。一旦運行算法的版本，您可以創建更大的測試問題，測量性能並將其自動化爲性能/集成測試。您可以更頻繁地運行它們，因爲它們需要更多時間，但至少會在重構或添加新算法時提前通知新引入的性能瓶頸。

Answer 2

檢查生成的解決方案的有效性是明顯的第一步。另外，一個迎角可以是regression testing，使用期望近似解是已知的實例（例如通過手動執行算法或通過使用某人的相同算法的實現來獲得）。

還存在已知（最佳）解決方案的問題實例存儲庫，例如用於TSP類問題的TSPLIB。也許這些可以用於某些用途。

如果有問題的算法存在已知的上限，那麼生成許多隨機實例並驗證啓發式解決方案對上限可能是有益的。如果你這樣做，我會敦促你讓遊戲重現（例如總是使用相同的隨機數發生器和種子）。

最後一點：對於一些問題，完全隨機的實例平均很容易找到好的近似解。具有均勻且獨立選擇的弧權重的不對稱TSP就是這樣一個例子。我提到這一點，因爲它可能會影響您的測試策略。

Answer 3

通常您可以檢查某些內容 - 例如，您的算法總是返回滿足其約束條件的解決方案，即使它們不是最優的。你也應該在每一個可能的機會上進行斷言檢查 - 這些將針對你的程序進行檢查，但是可能會檢查一些數量是否被保留，或者應該增加或者最壞的情況保持不變，或者某些假設的本地最佳確實是一個局部最優。

鑑於這些檢查以及您已經提到的邊界檢查，我傾向於對大量隨機生成的小問題運行測試，並選擇隨機種子，以便在問題出現問題時102324您可以重複該故障進行調試，而不會遇到102323之前的問題。由於存在大量問題，您可能會增加潛在錯誤導致錯誤的可能性，從而導致檢查失敗。如果出現小問題，您可以增加找到並修復錯誤的機會。