正文

遗传算法小记2008-04-19 15:54:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/rickone/34323.html

分享到:

我的毕设是做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就要从交叉的方法等改进。

阅读(7637) | 评论(1)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册