CAJ | 학술논문

重新定义表示青蛙移动距离和位置的数据结构及运算符意义,提出混合蛙跳算法(shuffled frog leaping algorithm,SFLA)求解旅行商问题(traveling salesman problem,TSP)基于交换序的实现方法.把具有极强局部搜索能力的幂律极值动力学优化(power law extremal optimization,T-EO)融合于SFLA,并针对TSP对T-EO过程进行设计和改进.改进后的T-EO采用新颖的组元适应度计算方法,通过定义边置换增益能量,结合模拟退火控制过程,并采取幂律定律用概率的方式选取2-opt置换产生邻域解.为避免每个族群最优解的趋同性,提出最优样本差异控制策略.通过求解TSPLIB数据库中的实例,证明该改进算法有效.
중신정의표시청와이동거리화위치적수거결구급운산부의의,제출혼합와도산법(shuffled frog leaping algorithm,SFLA)구해여행상문제(traveling salesman problem,TSP)기우교환서적실현방법.파구유겁강국부수색능력적멱률겁치동역학우화(power law extremal optimization,T-EO)융합우SFLA,병침대TSP대T-EO과정진행설계화개진.개진후적T-EO채용신영적조원괄응도계산방법,통과정의변치환증익능량,결합모의퇴화공제과정,병채취멱률정률용개솔적방식선취2-opt치환산생린역해.위피면매개족군최우해적추동성,제출최우양본차이공제책략.통과구해TSPLIB수거고중적실례,증명해개진산법유효.
A novel shuffled frog-leaping algorithm (SFLA) was proposed for solving traveling salesman problem (TSP) based on the technique of exchanging order. The data structure of moving distance and position of frog and the local information exchange strategy for the SFLA were redefined. In order to improve the local search ability, the power law extremal optimization (τ-EO) was incorporated into the SFLA. The fitness for the component of a solution was carefully designed. Simulated annealing (SA) and the 2-opt move technique were used to generate neighboring solutions in the improved τ-EO. In the shuffling process of the SFLA, a diversity control scheme was presented for the local best solution in each memeplex. Experimental results show that the performance of the proposed algorrthm to solve TSP is satisfatory.