TSPTW用遺傳算法

Question

我與遺傳算法的81個城市實施TSPTW（與時間窗口旅行商），我採用以下步驟：

mutation prob=0.03 
population size=100 
-Generate random population according to the value of population size intialized 
-Sort the generated population 
-Looping for populations and determine two parents by roulette selection, apply crossover on the parents, get child and add it to children list 
-I am saving the best solution over the algorithm 
-Sort the Children, replace worst tour in populations with best one of children 
until no good children is existing is better than worst solution in populations 
-loop (1 to population size)in all populations and Apply mutation of each worst solution with solution i , if the mutated solution is better than the worst solution of children. I insert it in populations in its place according to its fitness function and remove the worst one. 

我不能找到一個好的結果，我跑它到了特定的時間，但是我發現有時候它會陷入解決方案，無法獲得更好的結果。 我改變了

參數（人口規模= 20000，1000,100，突變 概率= 0.03,0.02，..）

我也有循環交叉測試它，並下令交叉

我想知道，我的步驟是正確的嗎？我如何正確指定種羣大小和變異概率？

Answer 1

你的算法可能太精英了。它只允許更好的解決方案進入你的人口。我認爲在某些時候它將包括所有類似的個人。沒有多樣性遺留和你的精英替代只有少量的突變可能會引入新的遺傳物質。

我會建議只使用精英主義，因爲你只讓上一代最好的個體生存下來。其餘的人都應該被新一代所取代。

或者你可以用我們發明的後代選擇方法。對於每個孩子的生存來說，它肯定比父母的更好。否則，他們會被丟棄，並選擇一對新的父母來創造一個新的孩子。你循環產生新的孩子，直到你有足夠的人口填補新的人口。然後你替換你的人口並重新開始。後代選擇遺傳算法在質量方面通常優於遺傳算法。它在HeuristicLab中實施。如果您打開VRPTW並只允許一輛車，您應該能夠對TSPTW進行建模。

另一種選擇是使用基於軌跡的算法，例如，基於禁忌搜索，如統一禁忌搜索。由於時間窗口解決方案和達到不同的局部最優解，可能需要約束鬆弛。