不同種子的TSP/TSPTW

Question

我想問問是否可以用不同種子運行GA來生成初始解決方案並進行分析？但是，在應用遺傳算法開始時，您必須提供一些人口解決方案。 例如，您使用種子「12345」運行遺傳算法以生成初始解，然後從該初始解中填充隨機解列表，然後繼續應用遺傳算法步驟解決該問題。

然後你運行遺傳與另一個種子，例如「5678」來生成初始解，然後你從這個初始解填充隨機解的名單，並繼續應用GA措施來解決問題..

這意味着第一次運行中的填充列表可能包含第二次運行中生成的初始解決方案。

我的問題是，有什麼辦法可以使用不同種子的遺傳算法進行比較和分析嗎？如果不是，我怎樣才能比較和分析，我是否應該只針對這個問題使用不同的實例文件？

Answer 1

爲了進行隨機算法的比較，首先通常使用不同的隨機種子對其進行多次運行。您然後獲得的輸出是一個隨機變量。然後，可以通過對所得樣本進行統計假設檢驗（ANOVA或Kruskal-Wallis進行多重比較，t檢驗或Mann-Whitney U檢驗進行配對比較）來評估一種算法是否優於另一種算法。如果在這些測試中得到的p值低於你想要的閾值（通常爲0.05，但爲了更嚴格的證明你會設置這個更低，例如0.01），你會拒絕H0假設，即這些結果是相等的。就其手段而言。因此，你認爲結果是不平等的，進一步說，具有更好平均性能的算法是更好的算法選擇（如果你對平均性能感興趣 - 「更好」通常有許多維度）。

有一兩件事讓我不知道在您的評論：

如果我多次與最初的解決方案相同的種子運行遺傳算法，其結果將是完全不同的

我想你在你的代碼中犯了一些錯誤。爲了獲得完全相同的結果，您需要在算法內部進行的任何隨機決策中使用相同的隨機對象。在你的代碼中的某處，你可能使用了new Random()而不是你最初用給定的種子獲得的那個。另一個原因可能是您使用並行處理繪製隨機數的零件。你永遠不能保證你的線程總是以相同的順序執行，所以一次線程1獲得第一個隨機數，第二個線程獲得第二個，另一次線程2首先執行並得到第一個數字。