求解多旅行商问题的改进分组遗传算法

发布时间：2018-11-18 08:06

【摘要】：该文针对总路径长度最小的多旅行商问题,提出一种改进分组遗传算法。在该算法中,设计了一种有序分组编码,采用新编码方式的个体与多旅行商问题有效解之间具有一一对应的关系。为了减少算法的运行时间,根据编码的特点构造了一种快速交叉算子。同时,结合贪婪算法和2-opt算法设计了一种新的局部搜索算子,以提高算法的收敛精度。实验结果分析表明,所提算法能够有效地解决多旅行商问题,具有可靠的全局收敛性,较高的计算效率。
[Abstract]:In this paper, an improved grouping genetic algorithm is proposed for multi-traveller problem with minimal total path length. In this algorithm, an ordered block coding is designed, in which there is a one-to-one correspondence between the efficient solution of the multi-traveller problem and the individual using the new coding method. In order to reduce the running time of the algorithm, a fast crossover operator is constructed according to the characteristics of coding. At the same time, a new local search operator is designed with greedy algorithm and 2-opt algorithm to improve the convergence accuracy of the algorithm. The experimental results show that the proposed algorithm can solve the multi-traveling salesman problem effectively and has reliable global convergence and high computational efficiency.
【作者单位】： 大连海事大学交通运输管理学院;
【基金】：国家科技支撑计划(2014BAH24F04) 国家自然科学基金(71271034)~~
【分类号】：TP18

【参考文献】

相关期刊论文 前4条

1 王军强;郭银洲;崔福东;张承武;孙树栋;;基于多样性增强的自适应遗传算法的开放式车间调度优化[J];计算机集成制造系统;2014年10期

2 谢秉磊;李颖;刘敏;;带临时补充点的融雪剂撒布车辆路径问题[J];系统工程理论与实践;2014年06期

3 刘明;张培勇;;求解多旅行商问题的新混合遗传算法:以应急物资配送为例[J];系统管理学报;2014年02期

4 韩丽霞;王宇平;兰绍江;;基于有序划分编码的图着色算法[J];电子学报;2010年01期

【共引文献】

相关期刊论文 前10条

1 李凯;;一种基于改进遗传算法的图着色算法[J];计算机与现代化;2017年02期

2 徐小平;朱秋秋;王峰;;求解圆排列问题的粒子群蚁群优化算法[J];系统仿真学报;2017年02期

3 张淑丽;刘胜辉;沙晨明;;求解柔性作业车间调度的岛屿模型遗传算法[J];哈尔滨理工大学学报;2016年05期

4 王勇臻;陈燕;于莹莹;;求解多旅行商问题的改进分组遗传算法[J];电子与信息学报;2017年01期

5 江唯;何非;童一飞;李东波;;基于混合算法的环形轨道RGV系统调度优化研究[J];计算机工程与应用;2016年22期

6 徐小平;朱秋秋;邰会强;;利用粒子群优化算法求解圆排列问题[J];计算机系统应用;2016年02期

7 代冀阳;殷林飞;杨保建;王村松;;基于GA的多智能机器人合作的物流配送系统研究[J];计算机应用与软件;2015年12期

8 刘婷;张立毅;张晋斌;;改进分布估计算法求解多用户检测问题[J];信号处理;2015年11期

9 张文俊;朱诗兵;李长青;王雪;;一种基于图N重着色理论的信道冲突模型[J];科学技术与工程;2013年27期

10 刘智s，

本文编号：2339411