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,..）

我还用循环交叉对其进行了测试，并订购了交叉

我想知道，我的步骤对吗？如何正确指定种群规模和突变概率？

4

1 回答 1

2

您的算法可能过于精英化。它只允许更好的解决方案进入您的人群。我假设在某些时候它将由所有相似的个体组成。没有剩下的多样性和您的精英替代品，只有少量的突变可以引入新的遗传物质。

我建议只使用精英主义，因为你只让上一代最优秀的人生存下来。其余的人都应该被新一代所取代。

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

另一种选择是使用基于轨迹的算法，例如基于禁忌搜索，例如统一禁忌搜索。由于时间窗解决方案和获得不同的局部最优值，可能需要放松约束。

于 2013-05-30T11:27:04.867 回答