求解tsp问题的人工鱼群算法

《求解tsp问题的人工鱼群算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、求解TSP问题的人工鱼群算法摘要：人工鱼群算法在函数优化问题中取得了较好的应用，但在组合优化问题中的应用相对较少。因此，文中用人工鱼群算法来求解TSP问题，并与标准粒子群算法和基本遗传算法进行了比较分析。通过仿真实验对公认的TSP测试数据中算例Oliver30进行测试并与目前已知最优解进行了对比，结果表明，人工鱼群算法解决TSP问题时可以收敛到已知最优解，并且解的质量要优于标准粒子群算法和基本遗传算法。关键词：旅行商问题；人工鱼群算法；聚群行为；觅食行为；追尾行为中图分类号：TP18文献标识码：A文章编

2、号：1009-3044（2014）19-4527-03ArtificialFishSwarmAlgorithmforsolvingTSPCHENGChun-ying1，LIHai-feng2，BAOChun-hua1（1.CollegeofComputerScienceandTechnology，InnerMongoliaUniversityforNationalities，Tongliao028043，China；2.InnerMongoliaCoalIndustryTechnicalschool，T

3、ongliao028021，China）Abstract：Artificialfishswarmalgorithmiswellappliedinfunctionoptimizationproblems，butitisrelativelylessusedincombinatorialoptimization5problem。Inthispaper，usingartificialfishswarmalgorithmtosolveTSPproblem，andwiththestandardparticleswa

4、rmoptimizationalgorithmandanalyzedthebasicgeneticalgorithm.ThispapercomparestheexperimentalsimulationofrecognizedOliver30TSPtestdataofanexampletestandtheknownoptimalsolution，andthequalityofthesolutionisbetterthanthestandardparticleswarmalgorithmandthebas

5、icgeneticalgorithm.Keywords：travelingsalesmanproblem；artificialfishswarmalgorithm；theswarmingbehavior；thepreyingbehavior；thefollowingbehaviorTSP（TravelingSalesmanProblem）问题，即旅行商问题，是经典的组合优化问题。在许多工程应用问题中，如物流配送、网络布线和电路板钻孔等，都可以归结为TSP求解问题。目前，对于解决TSP问题人们提出了很多有

6、价值的方法，如模拟退火算法[1]、遗传算法[2]、蚁群算法[3]和粒子群算法[4]等智能算法。而人工鱼群算法（ArtificialFishSwarmAlgorithm，5AFSA）[5-6]是李晓磊等人于2002年在对动物群体智能行为研究的基础上提出的一种新型仿生优化算法，该算法主要利用鱼群的三大基本行为分别为觅食、聚群和追尾行为，采用自上而下的寻优模式从构造个体的底层行为开始，通过鱼群中个体的局部寻优，达到全局最优值在群体中突现出来的目的。人工鱼群算法主要应用还集中在解决函数优化问题，在组合优化问题中

7、的应用较少，尤其是TSP问题中的应用少之又少。为此本文利用人工鱼群算法来解决TSP问题，并与标准粒子群算法和基本遗传算法进行了比较分析。1旅行商问题TSP问题，即旅行商问题，是经典的组合优化问题之一。旅行商问题的基本描述是：假设有一个旅行商人要访问[n]个城市，他必须选择要走的路径，选择路径的限制条件是每个城市只能访问一次，而且最后要回到原来出发的城市。路径的选择目标是要求求出的路径为所有路径之中的最短路径。简单说，旅行商问题就是需要寻找这样的一条旅行线路：从某个城市开始，经过每个城市一次且仅一次，最终

8、回到出发城市，使得旅游的路经总长度为最短。TSP问题的数学模型[7]可描述为：[minf（X）][s.t.g（X）≥0，X∈D]（1）公式（1）5中，[f（X）]为目标函数，[g（X）]为约束函数，[X]为决策变量，[D]表示有限个点组成的集合。通常，一个组合优化问题可用三个参数[（D，F，f）]来表示，其中[D]表示决策变量的定义域，[F={XX∈D，g（X）≥0}]，[f]表示目标函数，满足的可行解[X′]称为问题的最优解。2人工鱼群算