计算机研究与发展

作者：董学士,董文永,蔡永乐,

关键词：混合算法, 遗传算法, 着色瓶颈旅行商问题, 着色旅行商问题, 瓶颈旅行商问题,

基于着色旅行商问题(coloredtravelingsalesmanproblem,CTSP)，给出了一种适用性更加宽泛的组合优化问题模型：着色瓶颈旅行商问题(coloredbottlenecktravelingsalesmanproblem,CBTSP).CBTSP可建模含有部分重合工作区域的规划问题，譬如有合作任务和单独任务的人员与车辆的路线规划，此类问题由于目标函数与旅行商问题不一样，因此不能够用CTSP模型来建模.由于CBTSP属于NP难问题，对于规模大的此类问题，自然启发式算法是个合适的选择.基于此，提出了一种自然启发式算法求解CBTSP，该算法是基于伊藤过程的粒子群算法(particleswarmoptimization,PSO)、模拟退火算法(simulatedannealing,SA)和遗传算法(geneticalgorithm,GA)的混合算法(PSGA).PSGA首先用二重染色体编码来构建问题的解，然后运用遗传算法的交叉操作进行更新，其中交叉长度由伊藤过程的活动强度来控制，而活动强度由粒子半径和环境温度来决定.为了充分验证算法的有效性，使用小尺度到大尺度不同规模的数据进行实验，通过广泛的实验与分析表明:PSGA求解CBTSP问题的求解质量要优于对比算法.

来源：2018年第11期

《计算机研究与发展》期刊编辑部

查看计算机研究与发展杂志2018年第11期