求解旅行商问题的离散花授粉算法

摘要

针对原始花授粉算法（ FPA）无法用于求解组合优化问题，提出一种离散的花授粉算法，并将其应用于求解旅行商问题（ TSP）。通过重新定义花朵、全局搜索与局部搜索等概念；并对莱维飞行用一种新的方法进行分段，有效避免算法过早陷入局部最优，增强算法的全局搜索能力。最后通过对10个国际通用的TSP数据（ TSPLIB）进行测试，并将实验结果与离散粒子群算法（ DPSO）、混合离散粒子群算法（ HDPSO）、离散布谷鸟搜索（ DCS）算法、带有遗传模拟退火的蚁群粒子群（ GSA-ACS-PSOT）算法的实验结果进行对比。实验数据显示，该算法在求解旅行商问题中，能较快、较准确地找到最优解，在相同实验条件下，比其他算法求解偏差百分比明显降低。研究结果表明，本文提出的算法具有较好的求解性能。%In view of the standard Flower Pollination Algorithm ( FPA) can not be used to solve combinatorial optimization prob-lem, a Discrete Flower Pollination Algorithm(DFPA) was proposed and then applied to Traveling Salesman Problem (TSP).By redefining the concept of flowers , global search and local search , etc., and Levy flight will be segmented by a new method , ef-fectively avoiding premature falling into local optimum and enhancing the global search ability of the algorithm .Finally the per-formance of the proposed is tested against by some typical instances in the internationally commonly used library of TSP ( TSPLIB) and compared with Discrete Particle Swarm Optimization (DPSO), Hybrid Discrete Particle Swarm Optimization(HDPSO), Dis-crete Cuckoo Search ( DCS) , Genetic Simulated Annealing Ant Colony System with Particle Swarm Optimisation Technique ( GSA-ACS-PSOT) .The results of the tests show that DFPA can quickly , accurately find the optimal solution .Under the same experi-mental conditions , the algorithm reduces the error rate than any other algorithm .The results show that the proposed algorithm has better solving performance .