组合优化与智能计算分享 http://blog.sciencenet.cn/u/fswdong 清淡的生活,枯燥的钻研,幸福的泪水,拼搏的超脱

博文

[下载,原创]求解旅行商问题的改进遗传算法

已有 5867 次阅读 2009-8-27 08:38 |个人分类:试算工具|系统分类:科研笔记|关键词:旅行商问题,TSP,遗传算法,GA,边化简,选择策略| 遗传算法, 旅行商问题, TSP, 边化简, 选择策略

    附件程序是本人设计的遗传算法程序计算旅行商问题,随包附带了TSPLIB95中较大规模问题数据集,城市数量在1000至10000个城市之间。遗传算法中结合了本人设计的旅行商问题的初始边集化简策略以及选择性交叉、变异算子,是三年前完成的部分工作。使用Lin-kernighan作为局部搜索算法情况雄,试算结果表明,问题规模在小于2000个城市的时候,计算工具可以比同样使用Lin-kernighan的同类进化策略的遗传算法收敛时间得到明显缩短,并以很高高概率收敛于问题的全局最优解,全局最优解源自TSPLIB95。下面是当时试算的统计结果,没有加下划线的数据为30次重复运算的平均计算结果。

算法1GA使用3-Opt局部优化算法;

算法2GA使用重复N/2次且采用Quadrand 3近邻域参照优化边集初始化的链式Lin-kernighan算法;

算法3GA使用重复N/2次且采用初始边集化简的链式Lin-kernighan算法

算法4GA使用重复N/2次且采用初始边集化简的链式Lin-kernighan算法,并使用了选择性交叉和变异算子

    实验环境为Intel Core2 E6300 1.86GHz CPU1GB内存,操作系统为Windows XP

    该算法很多基础算法源自于Concorde,所以不用作商业用途,可以作为研究者交流,并不提供源代码交流,谢谢合作。

到这里点击下载:遗传算法计算工具





http://blog.sciencenet.cn/blog-253220-251676.html

上一篇:[下载,原创]求解旅行商问题的基本遗传算法
下一篇:[名家]Lov K. Grover - Grover算法的始作者

1 王汉森

发表评论 评论 (9 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-10-17 16:44

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部