一种利用混合优化算子求解旅行商问题的方法  

A Method of Mixed Optimization Operator to Solve the Traveling Salesman Problems

作　　者：贾玉福 陶懿 丰霄 JIA Yu-fu;TAO Yi;FENG Xiao(School of Information Management and Statistics,Hubei University of Economics,Wuhan 430205,China)

机构地区：[1]湖北经济学院信息管理与统计学院,湖北武汉430205

出　　处：《软件导刊》2019年第3期62-64,共3页Software Guide

基　　金：湖北省教育厅科技处研究计划项目(B2013033);湖北经济学院青年基金项目(XJ201316)

摘　　要：利用遗传算法、社会群体优化算法和模拟退火算法等仿生类整体探索算法求解旅行商问题(TSP),往往需要局部优化算子促进算法收敛。目前大多采用单一的n-opt算子而没有考虑利用其它算子或算子组合对旅行商路线进行优化。为此定义了P_Swap、FP_Swap和L_Swap等3个算子,在TSPLIB数据集中选取18个实例,分别利用各个算子及组合对旅行商路线问题进行优化。对比分析结果显示,P_Swap算子的优化能力与2-opt算子相当,3个算子组合的优化能力明显强于2-opt算子,组合优化算法求得的最优解优于目前已知的大部分算法。solving the Traveling Salesman Problem(TSP)with global exploratory bionic algorithms such as genetic algorithm,social group algorithm and simulated annealing algorithm,local optimization operators are often needed to promote the convergence of the algorithm.At present,most of the local optimization operators use a single n-opt operator,without considering the effectiveness of using other operators or combinations of operators to optimize the traveling salesman routes.In this paper,three operators,P_Swap,FP_Swap and L_Swap,are defined.Eighteen cases are selected from TSPLIB data set to compare and analyze the results of traveling salesman route optimization using each operator and its combination.The results show that the optimization ability of P_Swap operator is similar to that of 2-opt operator,and the optimization ability of the combination of three operators is obviously stronger than that of 2-opt operator.The optimal solution obtained by the combinatorial optimization algorithm is better than most of the known algorithms.

关 键 词：旅行商问题 n-opt算子 组合优化 全局探索能力 随机扰动 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]