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

发布时间：2018-01-14 00:33

本文关键词：混合算法求解多目标平衡旅行商问题　出处：《计算机研究与发展》2017年08期 　论文类型：期刊论文

【摘要】：平衡旅行商问题(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问题是有效的,并表现出不同的特点.
[Abstract]:Balanced traveling salesman problem. BTSPs are the changing model of traveling salesman problem (TSP), and another kind of combinatorial optimization problem. It can be applied to the optimization problem of steam turbine gas turbine engine, etc., but the BTSP model can only model the optimization problem with a single traveling salesman. Problems with multiple tasks cannot be modeled and optimized at the same time. A multiobjective balanced traveling salesman problem is proposed for the first time. The GTE model can be used to model the multi-task optimization problem with multiple traveling salesman. It can be applied to practical problems with multiple objectives or individuals, such as optimization with multiple GTE. Ito algorithm and genetic algorithm GA) have better performance in solving combinatorial optimization problems. Hybrid ITO algorithm is applied to hybrid Ito algorithm. HITO) and hybrid genetic algorithm (HITO) are used to solve the MBTSP problem. HITO uses ant colony optimization. ACO) is used to generate graph-based probabilistic model, and then Ito's drift and fluctuation operators are used to update the graph model to obtain the optimal solution of MBTSP. For hybrid genetic algorithm. The first one uses greedy method to improve genetic algorithm. Named greedy genetic algorithm algorithm with greedy initialization (gag). The second is genetic algorithm by ill-climbing genetic algorithm (algorithm). The last one is genetic algorithm with simulated annealing. In order to verify the algorithm effectively, we use the data of different scale MBTSP problem from small scale to large scale to carry on the experiment. The results show that the hybrid algorithm is effective in solving the MBTSP problem. And show different characteristics.
【作者单位】：武汉大学计算机学院;
【基金】：国家自然科学基金项目(61672024,61170305)~~
【分类号】：TP18
【正文快照】： 平衡旅行商问题(balanced traveling salesmanproblem,BTSP)是TSP的变化模型,可应用在汽轮机的优化等问题.但是BTSP模型只能对含一个旅行商单个任务的问题建模,没法同时对含多个旅行商有多个单独任务的问题进行建模和优化,基于此,本文提出了多目标的平衡旅行商问题(multi-obje

【参考文献】