论文部分内容阅读
平衡旅行商问题(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问题是有效的,并表现出不同的特点.
The balanced traveling salesman problem (BTSP) is a variation model of the traveling salesman problem (TSP). It is another combinatorial optimization problem that can be solved in optimization problems of gas turbines (GTE) But the BTSP model can only model the optimization problem with a single trip operator and can not model and optimize the multi-task with multiple triplers at the same time.Based on this, a multi-objective balance The multiobjective balanced traveling salesman problem (MBTSP) model can be used to model multi-task multi-task optimization problems with multiple traders. It can be applied to practical problems involving multiple targets or individuals, for example, optimization with multiple GTEs. The related literatures have proved that Ito algorithm and genetic algorithm (GA) have good performance in solving combinatorial optimization problems, so hybrid ITO algorithm (HITO) and hybrid genetic algorithm are used to solve the problem of MBTSP Problem, HITO generates a graph-based probability generation model by ant colony optimization (ACO), using the drift of the Ito algorithm and Operator is used to update the graph model to obtain the optimal solution of MBTSP.For the hybrid genetic algorithm, the first genetic algorithm with greedy method is improved named genetic algorithm with greedy genetic algorithm (GAG) , And the second is to optimize the genetic algorithm with hill-climbing algorithm, which is called genetic algorithm by hill-climbing (GAHC). The last one is genetic algorithm with simulated annealing (GASA). In order to validate this Algorithm is used to test the data of different scale MBTSP problems from small scale to large scale. The results show that the hybrid algorithm is effective in solving the MBTSP problem and shows different characteristics.