求解旅行商问题的改进果蝇算法

为了有效解决经典的NP难问题-旅行商问题(traveling salesman problem,TSP),提出了一种改进的果蝇算法。针对果蝇算法存在易陷入局部最优及收敛速度慢的缺点,引入了局部最优半径的概念,以此为依据判断果蝇是否处于局部最优区域;设计了带启发式规则的变异算子,对局部最优半径中选中的果蝇个体进行启发式变异,在保护最优个体的同时,也改善了种群多样性,抑制了早熟现象的产生;采用自适应步长策略,显著提高了搜索效率。对其全局收敛性进行了验证,以TSPLIB为基准与标准果蝇算法、粒子群算法进行了实验对比,对比结果验证了该算法的有效性。