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

Hybrid Algorithms for Multi-Objective Balanced Traveling Salesman Problem

平衡旅行商问题(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问题是有效的,并表现出不同的特点.

Balanced traveling salesman problem（BTSP）,a variant of traveling salesman problem（TSP）,is another combination optimization problem,which can be applied in many fields such as the optimization problem for gas turbine engines（GTE）.BTSP can only model optimization problems with the single traveling salesman and task,but can＇t model and optimize the problem with multiple salesmen and tasks at the same time.Therefore,this paper firstly provides a multi-objective balanced traveling salesman problem（MBTSP）model,which can model the optimization problems with multiple salesmen and tasks.Specifically it can be applied to the real-world problems with multiple objectives or individuals,for example,the optimization for multiple GTE.Some literatures have proved that ITO algorithm and genetic algorithms can show better performance in solving combination optimization problems,therefore,the paper utilizes the hybrid ITO algorithm（HITO）and hybrid genetic algorithm（GA）to solve MBTSP.For HITO,it utilizes ant colony optimization（ACO）to produce a probabilistic generative model based on graph,and then uses the drift and volatility operators to update the model,and obtains optimum solution.For the hybrid GA,the first is improved by greedy method called GAG,the second GA is optimized by incorporating hill-climbing named GAHC,and the final one is GASA.In order to effectively test the algorithms,the paper makes extensive experiments using small scale to large scale MBTSP data.The experiments show that the algorithms are effective and reveal the different characteristics in solving MBTSP problem.