(Computer School, Wuhan University, Wuhan 430072)
出版日期: 2018-11-01基金资助:国家自然科学基金项目(61672024,61170305)Hybrid Algorithm for Colored Bottleneck Traveling Salesman Problem
Dong Xueshi, Dong Wenyong, Cai Yongle(武汉大学计算机学院 武汉 430072) (dxs_cs@163.com)
Online: 2018-11-01摘要/Abstract
摘要： 基于着色旅行商问题(colored traveling salesman problem, CTSP)，给出了一种适用性更加宽泛的组合优化问题模型：着色瓶颈旅行商问题(colored bottleneck traveling salesman problem, CBTSP).CBTSP可建模含有部分重合工作区域的规划问题，譬如有合作任务和单独任务的人员与车辆的路线规划，此类问题由于目标函数与旅行商问题不一样，因此不能够用CTSP模型来建模.由于CBTSP属于NP难问题，对于规模大的此类问题，自然启发式算法是个合适的选择.基于此，提出了一种自然启发式算法求解CBTSP，该算法是基于伊藤过程的粒子群算法(particle swarm optimization, PSO)、模拟退火算法(simulated annealing, SA)和遗传算法(genetic algorithm, GA)的混合算法(PSGA).PSGA首先用二重染色体编码来构建问题的解，然后运用遗传算法的交叉操作进行更新，其中交叉长度由伊藤过程的活动强度来控制，而活动强度由粒子半径和环境温度来决定.为了充分验证算法的有效性，使用小尺度到大尺度不同规模的数据进行实验，通过广泛的实验与分析表明:PSGA求解CBTSP问题的求解质量要优于对比算法.
参考文献
相关文章 15
| [1] | 丁旭阳, 谢盈, 张小松. 基于边缘计算的进化多目标优化图像隐写算法[J]. 计算机研究与发展, 2020, 57(11): 2260-2270. |
| [2] | 董学士,董文永,王豫峰,. 混合算法求解多目标平衡旅行商问题[J]. 计算机研究与发展, 2017, 54(8): 1751-1762. |
| [3] | 吕亚丽,武佳杰,梁吉业,钱宇华. 基于超结构的BN随机搜索学习算法[J]. 计算机研究与发展, 2017, 54(11): 2558-2566. |
| [4] | 张大坤,宋国治,林华洲,任淑霞. 二次改进遗传算法与3D NoC低功耗映射[J]. 计算机研究与发展, 2016, 53(4): 921-931. |
| [5] | 尤枫,赵瑞莲,吕珊珊. 基于输出域的测试用例自动生成方法研究[J]. 计算机研究与发展, 2016, 53(3): 541-549. |
| [6] | 姜火文,曾国荪,胡克坤. 一种遗传算法实现的图聚类匿名隐私保护方法[J]. 计算机研究与发展, 2016, 53(10): 2354-2364. |
| [7] | 田中大,高宪文,李树江,王艳红. 遗传算法优化回声状态网络的网络流量预测[J]. 计算机研究与发展, 2015, 52(5): 1137-1145. |
| [8] | 王相海,丛志环,方玲玲,宋传鸣. 混合种群多样性自适应遗传操作的HMM训练模型[J]. 计算机研究与发展, 2014, 51(8): 1833-1844. |
| [9] | 徐雨明 朱宁波 欧阳艾嘉 李肯立. 异构系统中DAG任务调度的双螺旋结构遗传算法[J]. 计算机研究与发展, 2014, 51(6): 1240-1252. |
| [10] | 张英杰,龚中汉. 基于阈值统计学习的差分进化引力搜索算法[J]. 计算机研究与发展, 2014, 51(10): 2187-2194. |
| [11] | 冯 翔 马美怡 施 尹 虞慧群. 基于社会群体搜索算法的机器人路径规划[J]. 计算机研究与发展, 2013, 50(12): 2543-2553. |
| [12] | 马 超 邓 超 熊 尧 吴 军. 一种基于混合遗传和粒子群的智能优化算法[J]. , 2013, 50(11): 2278-2286. |
| [13] | 胡新平 贺玉芝 倪巍伟 张 勇. 基于赌轮选择遗传算法的数据隐藏发布方法[J]. , 2012, 49(11): 2432-2439. |
| [14] | 王显志, 王忠杰, 徐晓飞, 刘英,. 面向多需求可满足性折中的服务组合方法[J]. , 2011, 48(4): 627-637. |
| [15] | 朱 夏 李小平 王 茜. 基于总空闲时间增量的无等待流水调度混合遗传算法[J]. , 2011, 48(3): 455-463. |
PDF全文下载地址:
https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=3805
