献给同样要写作业的苦逼同学们。 代码都很简单看行内注释就足够了。 懒得看代码的同学直接run起来看提示信息即可。

遗传算法这边有两点跟基础的遗传算法有点不太一样。

• 概率计算

适应度就是目标函数。但是TSP的目标函数是越小越好的，所以不能简单地归一化目标函数作为概率。 这里我采取的办法是求出每个解与当前种群里最差的解的差值作为未归一化的概率：

# fs 是一维向量，为当前种群内的各个解的目标函数值
Pu = max(fs) - fs + 1;
P = Pu/sum(Pu);

• 动态终止迭代

这里实现的遗传算法跑的挺慢的，至少比SA要慢多了。所以除了一个迭代上限5000外，还加了一个动态终止。

当新得到的种群的最优适应度比起上一次的种群的最优适应度要小，或者最优适应度与平均适应度的比值变大（这意味着虽然最优适应度可能没有变好，但种群整体在渐渐变好）时，就会继续迭代。在一定的容忍度之内上述条件一直没有达到的话，则迭代终止。这样一来，直到整个种群的平均水准和最优水准都不进化并且维持这个状况一定时间之后，算法才结束。

Emmmm如果有帮助的话点颗星吧~