仿生蚊子追踪算法.pdf

《仿生蚊子追踪算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第37卷第8期计算机学报Vo1．37No．82014年8月CHINESEJOURNALOFCOMPUTERSAug．2014仿生蚊子追踪算法冯翔张进文虞慧群(华东理工大学计算机科学与工程系上海200237)摘要旅行商问题(TravelingSalesmanProblem，TSP)是NP完全问题中最为著名的问题，它易于陈述而难于求解，至今尚未找到准确有效的求解大规模TSP问题的方法．文中提出了能求出TSP有效近似最优解的新的蚊子追踪(MosquitoHost—Seeking，MHS)算法，证明了蚊子的目标追踪行为和MHS数学模型的一致性、蚊子追踪算法的

2、收敛性，并通过理论证明确定了MHS算法中各参数的选择范围．蚊子追踪算法是一个全新的仿生算法．文中以TSP问题为载体，详细提出了蚊子追踪算法的动机、生物学模型、数学模型、算法、理论基础(数学证明)及大量实验结果．从理论和实验两方面证明了蚊子追踪算法能够求出TSP问题理论上的优化解．关键词仿生算法；旅行商问题；蚊子追踪算法；分布并行算法中图法分类号TP393DOI号10．3724／SP．J．1016．2014．01794MosquitoHost·SeekingAlgorithmforTSPProblemFENGXiangZHANGJin-WenYUHui

3、—Qun(DepartmentofComputerScienceandEngineering，EastChinaUniversityofTechnologyandScience，Shanghai200237)AbstractTravelingsalesmanproblem(TSP)isprobablythebestknowncombinatorialoptimi—zationproblems(COP)andiSNP—complete．TheTSPiSeasilyformulatedbutdifficultlysolved．Inthispaper，we

4、proposeanovelmosquitohost—seekingalgorithm(MHSA)asanewbranchofbiology—inspiredalgorithmsforsolvingTSPproblems．TheMHSalgorithmisinspiredbyhost—seekingbehaviorofmosquitoes．Weexpatiatethemathematicalmodel，algorithm，motivation，biologicalmode1andexperimentalresultsofMHSalgorithminde

5、tail．TheMHSalgorithmcanworkoutthetheoretiealoptimumsolution，whichiSimportantandexciting．Thetheoreticalanalysisandexperimentalresultshaveverifiedthiskeypointoftheproposedalgorithm．Keywordsbio—inspiredalgorithm；travelingsalesmanproblem(TSP)；mosquitohost—seekingalgorithm(MHSA)；dis

6、tributedandparallelalgorithm果将会在两者的交叉领域中取得”[1]．在信息科学领1引F域，尤其在计算机科学领域，受自然界法则启发，模拟智能体实施智能行为的原理而来的理论、方法和南加州大学的Leonard教授在《Science》上发技术越来越成为研究热点]．智能体包括人、动物表的论文“MolecularComputationofSolutionsto等具有智能行为能力的所有物体．智能体本身也可CombinatorialProblems”中指出：“自然(生物学和以由许多智能体组成，如蚊子群．物理)和计算(计算机科学)是相关的，重

7、要的学术成图灵提出了图灵机(也就是计算设备)的概念，收稿日期：2012—11—06；最终修改稿收到日期：2014—03—02．本课题得到国家自然科学基金(60905043，61073107，61173048)、上海市教育委员会科研创新项目、中央高校基本科研业务费、大学生创新项目资助．冯翔，女，1977年生，博士，教授，博士生导师，中国计算机学会(CCF)会员，主要研究领域为分布并行计算、人工智能、网络通信．E-mail：xfer~g@ecust．edu．cn．张进文，男，1991年生，硕士研究生，主要研究方向为分布并行计算、网络通信．虞慧群，男，19

8、67年生，博士，教授，博士生导师，主要研究领域为软件工程、可信计算和形式化方法．8期冯翔等：仿生蚊子追踪算法