求解TSP的改进混合蛙跳算法  

Improved shuffled frog leaping algorithm for solving TSP

作　　者：骆剑平[1] 李霞[1] 

机构地区：[1]深圳大学信息工程学院,深圳518060

出　　处：《深圳大学学报（理工版）》2010年第2期173-179,共7页Journal of Shenzhen University(Science and Engineering)

基　　金：国家自然科学基金资助项目(60772148);高等学校博士点基金资助项目(200805900001)

摘　　要：重新定义表示青蛙移动距离和位置的数据结构及运算符意义,提出混合蛙跳算法(shuffled frogleaping algorithm,SFLA)求解旅行商问题(traveling salesman problem,TSP)基于交换序的实现方法.把具有极强局部搜索能力的幂律极值动力学优化(power law extremal optim ization,τ-EO)融合于SFLA,并针对TSP对τ-EO过程进行设计和改进.改进后的τ-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.

关 键 词：人工智能 智能计算 虫群智慧 混合蛙跳算法 极值动力学优化 模拟退火 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程] TP183[自动化与计算机技术—控制科学与工程]