文献类型：期刊文献

中文题名：仿生蚊子追踪算法

英文题名：Mosquito Host-Seeking Algorithm for TSP Problem

作者：冯翔[1];张进文[1];虞慧群[1]

机构：[1]华东理工大学计算机科学与工程系,上海200237

年份：2014

卷号：37

期号：8

起止页码：1794

中文期刊名：计算机学报

外文期刊名：Chinese Journal of Computers

收录：CSTPCD;;EI(收录号：20143600063126);Scopus;北大核心:【北大核心2011】；CSCD:【CSCD2013_2014】；

基金：国家自然科学基金(60905043;61073107;61173048);上海市教育委员会科研创新项目;中央高校基本科研业务费;大学生创新项目资助~~

语种：中文

中文关键词：仿生算法;旅行商问题;蚊子追踪算法;分布并行算法

外文关键词：bio-inspired algorithm; traveling salesman problem （TSP） ; mosquito host-seeking algorithm （MHSA） ; distributed and parallel algorithm

摘要：旅行商问题(Traveling Salesman Problem,TSP)是NP完全问题中最为著名的问题,它易于陈述而难于求解,至今尚未找到准确有效的求解大规模TSP问题的方法.文中提出了能求出TSP有效近似最优解的新的蚊子追踪(Mosquito Host-Seeking,MHS)算法,证明了蚊子的目标追踪行为和MHS数学模型的一致性、蚊子追踪算法的收敛性,并通过理论证明确定了MHS算法中各参数的选择范围.蚊子追踪算法是一个全新的仿生算法.文中以TSP问题为载体,详细提出了蚊子追踪算法的动机、生物学模型、数学模型、算法、理论基础(数学证明)及大量实验结果.从理论和实验两方面证明了蚊子追踪算法能够求出TSP问题理论上的优化解.
Traveling salesman problem （TSP） is probably the best known combinatorial optimization problems （COP） and is NP complete.The TSP is easily formulated but difficultly solved.In this paper,we propose a novel mosquito host seeking algorithm （MHSA） as a new branch of biology inspired algorithms for solving TSP problems.The MHS algorithm is inspired by host seeking behavior of mosquitoes.We expatiate the mathematical model,algorithm,motivation,biological model and experimental results of MHS algorithm in detail.The MHS algorithm can work out the theoretical optimum solution,which is important and exciting.The theoretical analysis and experimental results have verified this key point of the proposed algorithm.