genetic-algorithm - 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.

我找不到好的结果，我运行它到特定的高时间，但我发现有时它会卡在解决方案上，无法获得更好的结果。我改变了

parameters(population size=20000 ,1000,100, mutation probability=0.03,0.02,..)

我还用循环交叉和有序交叉测试了它

我想知道，我的步骤是否正确？如何正确指定种群大小和突变概率？

Answer 1

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

我建议仅使用精英主义，因为您只让上一代中最优秀的个体生存下来。其余的个体应该全部被新一代取代。

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

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