我的毕设是做TSP问题，给定一个图，n个顶点，求一个哈密顿圈（不连通认为以无穷大权连通），使总的权合最小，即最小哈密顿圈。它的通俗描述是，一个旅行商(traveling salesman)从一个城市出发，经过其它城市一次且仅一次，最后回到出发城市，求一个路径，使总的行程最短。

下面这个是用GA做的，城市数n=50，种群大小gn=100，交叉概率pc=0.98，变异概率pv=0.01，结束迭代的条件是，连续10个种群的平均评价值没有增长，图中值是种群平均评价值的倒数，也就是哈密顿圈总权和。从图中看出，它很好的收敛到某个较低值。但是最优个体并不一定出现在最后的种群，为什么？这很容易理解，算法是用种群为单位计算的，但我要的结果却是一个个体，以种群为单位是为了很好的避开局部最优，但是全局最优可能会存在于较后期的某个种群，而不一定是最后一个种群，以人类的历史为比喻，最聪明的人一定是今天地球上的某个人吗？人类历史也可能停止不前，只能说总体水平在优化，但我个人认为比爱因斯坦聪明的人还没有过，但它却不在最后一个种群当中。

GA收敛得很好，但是比较慢，它竟然进化了1千多代！相比SAA对一个相同数据的计算结果图如下：

它没有优化到前者那个水平，最后只能划一条直线的原因是温度已经降得过低了，已经没有可能再优化了。它的起伏比较大，但是它的优点是收敛快，它从17000左右优化到7000左右，只迭代了100次不到，而且它只迭代一个个体，相比之下GA优化到那个水平却进化了500代左右。SAA还有改进的空间，比如温度的控制，迭代次数和温度的关系，等。而GA就要从交叉的方法等改进。

评论