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

来源：计算机研究与发展杂志2017年第8期北京时间：

作者：董学士,董文永,王豫峰,

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

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