用遗传算法解决TSPTW问题

Question

用遗传算法解决TSPTW问题

3

我正在使用遗传算法实现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等），并尝试了循环交叉和顺序交叉。我想知道，我的步骤是否正确？如何正确指定种群大小和变异概率？

- Yasmin

1

你的突变是错误的。突变可能发生在任何一个孩子身上，而不仅仅是最差的那个（如果我对你最后一步的理解是正确的话）。虽然如此，这可能并不是你问题的根源，因此并不是一个答案。 - NWS

我已经在种群中添加了更好的后代，因此当对种群进行变异时，它也包括一些更好的后代。 - Yasmin

重新审视你所采取的步骤，我怀疑你在如何交叉和生成新种群方面感到困惑。你是否阅读过以下文章：http://en.wikipedia.org/wiki/Genetic_algorithm 以及 http://en.wikipedia.org/wiki/Selection_%28genetic_algorithm%29 和 http://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29？ - NWS

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andreas · Accepted Answer

你的算法可能过于精英主义化，只允许更好的解决方案进入你的种群。我认为在某个阶段它将由所有类似的个体组成。没有多样性留下来，而你的精英主义替换只能引入很少的突变来引入新的基因材料。

我建议只在前代中让最优秀的个体存活，其他个体都应该被新一代取代。

或者你可以采用我们发明的后代选择方法。对于每个孩子要生存下来，它必须比其父母中更好的那个更好。否则他们将被丢弃并选择一对新的父母来产生新的孩子。你循环产生新的孩子，直到你有足够的孩子来填满一个新的种群。然后你替换你的种群并重新开始。后代选择遗传算法通常在其能够实现的质量方面优于遗传算法。它在HeuristicLab中实现。如果你打开一个VRPTW并只允许一辆车，你应该能够模拟TSPTW。

另一个选择是采用基于轨迹的算法，例如基于禁忌搜索的统一禁忌搜索。由于时间窗口解决方案和到达不同的局部最优解，可能需要进行约束放松。