改进混合蛙跳算法求解旅行商问题.doc

,杨烨,李霞(深圳大学信息工程学院,广东深圳518060摘要:以旅行商问题(TSP为例,引入调整序思想设计了局部搜索策略,同时在全局信息交换过程中加入变异操作,提出一种改进混合蛙跳算法求解TSP问题。实验结果表明,与遗传算法和粒子群优化算法相比较,改进混合蛙跳算法在求解TSP问题上具有更好的搜索性能和顽健性。关键词:混合蛙跳算法;旅行商问题;局部搜索;全局信息交换中图分类号:TP18文献标识码:A文章编号:1000-436X(200907-0130-06Modifiedshuffledfrog-leapingalgorithmtosolvetravelingsalesmanproblemLUOXue-hui,YANGYe,LIXia(CollegeofInformationEngineering,ShenzhenUniversity,Shenzhen518060,ChinaAbstract:Modifiedshuffledfrog-leapingalgorithmtosolveTSPwasproposed,whichpresentedtheconceptofadjustmentsequencetodesignthestrategyoflocalsearching,,:shuffledfrog-leapingalgorithm;travelingsalesmanproblem;localsearch;globalinformationexchange1引言混合蛙跳算法是2000年由MuzaffarEusuff和KevinLansey提出的一种基于群智能的亚启发式计算优化算法,用于解决离散组合优化问题[1]。作为一种新型的仿生物学智能优化算法,SFLA结合了基于模因(meme进化的模因演算法(MA,memeticalgorithm和基于群体行为的粒子群算法(PSO,particleswarmoptimization2种群智能优化算法的优点。该算法具有概念简单,调整的参数少,计算速度快,全局搜索寻优能力强,易于实现的特点[2]。混合蛙跳算法主要应用于解决多目标优化问题,例如水资源分配、桥墩维修、车间作业流程安排等工程实际应用问题[3~5]。著名的旅行商问题[6](TSP,travelingsalesmanproblem是一类典型组合优化问题,求得一条遍历所有城市的最短回路,属于NP难问题。对TSP问题一般分为两大类的研究:一类着重于研究算法解决大规模实际问题[7],如文献[7]中解决的TSP问题城市规模最大达到316228个,侧重点在于算法能快速地有效求得可行解;另一类则是利用TSP问题来验证优化算法解决离散组合优化问题的有效性。几十年来,出现了很多近似优化算法用于求解TSP问题,基本分为2类:①与问题本身特征相关的局部启发式搜索算法,如2-Opt、3-Opt和Lin-Kernighan(LK[8]等。这类优化算法多数充分收稿日期:2008-08-02;修回日期:2008-11-20基金项目:国家自然科学基金资助项目(60772148FoundationItem:TheNationalNaturalScienceFoundationofChina(600772148第7期罗雪晖等:改进混合蛙跳算法求解旅行商问题·131·利用问题本身特征的相关信息有效寻找问题的局部最优解,但是这些算法过分依赖于问题本身特征,当问题的规模扩大后,问题本身特征的相关信息更复杂,大大增加算法计算量,使得算法搜索时间过长。②独立于问题的经典智能优化算法,如蚁群算法、遗传算法、模拟退火法、粒子群算法、免疫算法等。此类算法大多数是模拟生物进化算法,不依赖于问题本身特征,具有较强的全局搜索能力。近年来,许多学者将局部启发式搜索算法和智能优化算法相结合产生新型混合算法应用于求解TSP问题。文献[8]提出了一种求解TSP问题的混合遗传算法,该算法结合了基于领域的LK算法和采用了交叉逆转算子;文献[9]介绍了求解TSP问题的蚁群算法,在算法中引入局部信息激素、信息激素更新策略与变参数策略等;文献[10]提出了基于改进粒子群优化算法求解旅行商问题,文中引入了