求解TSP问题的改进果蝇优化算法  

Improved fruit fly algorithm for TSP problem

作　　者：段艳明[1] 肖辉辉[1,2] 

机构地区：[1]河池学院计算机与信息工程学院,广西宜州546300 [2]江西财经大学信息管理学院,南昌330013

出　　处：《计算机工程与应用》2016年第6期144-149,共6页Computer Engineering and Applications

基　　金：广西自然科学基金(No.2013GXNSFBA019022);河池学院青年科研课题(No.2012B-N005;No.2012B-N007)

摘　　要：基于求解TSP问题,提出一种改进果蝇优化算法(GFOA),该算法结合TSP问题的特点,把果蝇优化算法的连续空间对应到离散规划,利用轮盘赌法初始化路径,并把遗传算法的交叉、变异操作应用于路径的寻优,同时利用C2Opt算子对局部最优路径进行优化,加快局部搜索能力和收敛速度。通过对13个TSPLIB标准库的TSP算例进行仿真实验,实验结果表明,提出的算法在较小规模算例中能以较少的迭代次数和运行时间快速收敛到已知最优解,在较大规模算例中能接近理论最优解,具有较快的收敛速度和较高的收敛精度。An improved Fruit Fly Optimization Algorithm（GFOA）is designed to tackle the traveling salesman problem.With the characteristics of the TSP problem, the continuous space is corresponded to the discrete, and roulette method is used to initialize the path, and the crossover and mutation operators of GA are applied to the optimization of the path. At the same time the local search ability and convergence speed are speeded up by using C2 Opt to optimize the local path.The proposed algorithm is evaluated on 10 TSP test problems. The numerical experiments show that the proposed algorithm can find the global optima solution with less iteration number and run time in smaller numerical example, and can approach to the theory optimal solution in larger numerical example. So the proposed algorithm has faster convergence speed and higher convergence precision.

关 键 词：旅行商问题(TSP) 果蝇优化算法 轮盘赌法 C2Opt算子 

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