Abstract: 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 C2Opt 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.

Key words: Traveling Salesman Problem（TSP）, fruit fly optimization algorithm, roulette method, C2Opt operation

摘要： 基于求解TSP问题，提出一种改进果蝇优化算法（GFOA），该算法结合TSP问题的特点，把果蝇优化算法的连续空间对应到离散规划，利用轮盘赌法初始化路径，并把遗传算法的交叉、变异操作应用于路径的寻优，同时利用C2Opt算子对局部最优路径进行优化，加快局部搜索能力和收敛速度。通过对13个TSPLIB 标准库的TSP算例进行仿真实验，实验结果表明，提出的算法在较小规模算例中能以较少的迭代次数和运行时间快速收敛到已知最优解，在较大规模算例中能接近理论最优解，具有较快的收敛速度和较高的收敛精度。

关键词: 旅行商问题（TSP）, 果蝇优化算法, 轮盘赌法, C2Opt算子