混合算法求解多目标平衡旅行商问题

作     者：董学士 董文永 王豫峰 Dong Xueshi;Dong Wenyong;Wang Yufeng

作者机构：武汉大学计算机学院武汉430072 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2017年第54卷第8期

页      面：1751-1762页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金项目(61672024 61170305)~~ 

主　　题：混合伊藤算法 混合遗传算法 平衡旅行商问题 多目标平衡旅行商问题 蚁群算法 

摘      要：平衡旅行商问题(balanced traveling salesman problem,BTSP)是旅行商问题(traveling salesman problem,TSP)的变化模型,是另一种组合优化问题,可在汽轮机(gas turbine engines,GTE)等的优化问题中得到应用,但BTSP模型只能对含单个旅行商一个任务的优化问题建模,不能同时对含多个旅行商多任务的问题进行建模和优化.基于此,首次提出了一种多目标平衡旅行商问题(multiobjective balanced traveling salesman problem,MBTSP)模型,可建模含多个旅行商多任务的优化问题,具体可应用在含多个目标或个体的实际问题,例如含多个GTE的优化.相关文献的研究已证实,伊藤算法和遗传算法(genetic algorithm,GA)在求解组合优化问题中具有较好的性能,因此,应用混合伊藤算法(hybrid ITO algorithm,HITO)和混合遗传算法来求解MBTSP问题.HITO通过蚁群算法(ant colony optimization,ACO)来产生基于图的概率生成模型,再用伊藤算法的漂移和波动算子对该图模型进行更新,从而得到MBTSP的最优解.对于混合遗传算法,第一个用贪心法对遗传算法进行改进,命名为贪心法遗传算法(genetic algorithm with greedy initialization,GAG),第二个用爬山算法优化遗传算法,称之为爬山法遗传算法(genetic algorithm by hill-climbing,GAHC),最后一个为模拟退火遗传算法(genetic algorithm with simulated annealing,GASA).为了有效验证该算法,使用小尺度到大尺度的不同规模MBTSP问题的数据进行实验,结果表明:混合算法在求解MBTSP问题是有效的,并表现出不同的特点.