CAJ | 학술논문

为了有效解决经典的NP难问题-旅行商问题（traveling salesman problem ， TSP），提出了一种改进的果蝇算法。针对果蝇算法存在易陷入局部最优及收敛速度慢的缺点，引入了局部最优半径的概念，以此为依据判断果蝇是否处于局部最优区域；设计了带启发式规则的变异算子，对局部最优半径中选中的果蝇个体进行启发式变异，在保护最优个体的同时，也改善了种群多样性，抑制了早熟现象的产生；采用自适应步长策略，显著提高了搜索效率。对其全局收敛性进行了验证，以TSPLIB为基准与标准果蝇算法、粒子群算法进行了实验对比，对比结果验证了该算法的有效性。
위료유효해결경전적NP난문제-여행상문제（traveling salesman problem ， TSP），제출료일충개진적과승산법。침대과승산법존재역함입국부최우급수렴속도만적결점，인입료국부최우반경적개념，이차위의거판단과승시부처우국부최우구역；설계료대계발식규칙적변이산자，대국부최우반경중선중적과승개체진행계발식변이，재보호최우개체적동시，야개선료충군다양성，억제료조숙현상적산생；채용자괄응보장책략，현저제고료수색효솔。대기전국수렴성진행료험증，이TSPLIB위기준여표준과승산법、입자군산법진행료실험대비，대비결과험증료해산법적유효성。
To address a classical NP hard problem of TSP (traveling salesman problem) ,an improved fruit fly optimization algo-rithm was proposed .Aiming at standard fruit fly optimization algorithm having shortcomings of easily plunging into local optimal and low convergence-rate ,the radius of local optimum was introduced ,by which whether the fruit fly was in a local optimum area could be judged .Meanwhile ,the heuristic mutation operator was designed ,the fruit flies selected was mutated by heuristic mutation operator in the radius of local optimum ,which not only protected the optimal individual ,but also improved the diversity of the population and prevented premature .Furthermore ,the strategy of adaptive variable step size was adopted ,which increased search efficiency effectively .Finally ,the convergence of algorithm proposed was proved .Compared to the standard fruit fly opti-mization algorithm and the particle swarm optimization algorithm benchmarked on TSPLIB ,the improved fruit fly optimization algorithm was verified to be efficient .