博文
[下载,原创]求解旅行商问题的改进遗传算法
|||
附件程序是本人设计的遗传算法程序计算旅行商问题，随包附带了TSPLIB95中较大规模问题数据集，城市数量在1000至10000个城市之间。遗传算法中结合了本人设计的旅行商问题的初始边集化简策略以及选择性交叉、变异算子，是三年前完成的部分工作。使用Lin-kernighan作为局部搜索算法情况雄，试算结果表明，问题规模在小于2000个城市的时候，计算工具可以比同样使用Lin-kernighan的同类进化策略的遗传算法收敛时间得到明显缩短，并以很高高概率收敛于问题的全局最优解，全局最优解源自TSPLIB95。下面是当时试算的统计结果，没有加下划线的数据为30次重复运算的平均计算结果。
算法1：GA使用3-Opt局部优化算法；
算法2：GA使用重复N/2次且采用Quadrand 3近邻域参照优化边集初始化的链式Lin-kernighan算法；
算法3：GA使用重复N/2次且采用初始边集化简的的链式Lin-kernighan算法；
算法4：GA使用重复N/2次且采用初始边集化简的的链式Lin-kernighan算法，并使用了选择性交叉和变异算子；
实验环境为Intel Core2 E6300 1.86GHz CPU，1GB内存，操作系统为Windows XP。
该算法很多基础算法源自于Concorde，所以不用作商业用途，可以作为研究者交流，并不提供源代码交流，谢谢合作。
到这里点击下载：遗传算法计算工具
https://blog.sciencenet.cn/blog-253220-251676.html
上一篇：[下载,原创]求解旅行商问题的基本遗传算法
下一篇：[名家]Lov K. Grover - Grover算法的始作者
