资源描述：
《基于免疫算法的tsp问题求解》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、基于免疫算法的TSP问题求解TheSolutionofTSPProblemBaseonImmuneAlgorithm学科专业：软件工程研究生：冯舒怡指导教师：路文焕副教授企业导师：崔凤梅副教授天津大学软件学院二零一五年十二月摘要随着研究领域问题的不断深入，常规的确定性算法越来越不能满足人们的需求。神经网络算法，模拟退火算法，遗传算法跟免疫算法等算法应运而生。自然界免疫系统的研究很早就开始了，六十年代科学计算研究先驱根据相关科学技术的内容和知识，特别是理论和概念在遗传学方面的积累，形成了人工智能的免疫算法，并成功地应用于某些工程科学现场，并收到了良好的效果。与过去相比，由于遗传算法比
2、传统的搜索算法使用简单，功能强大，易于并行处理的特性，被广泛应用于组合优化问题，结构设计问题，人工智能等领域。旅行商问题，也就是TSP问题（TravelingSalesmanProblem），它是数学中著名问题之一。它的问题描述为：假设一个旅行商人有N个城市需要拜访，但他对于所走路径的要求比较高，有一定的限制：首先他所走的路径要访问每个城市一次且只有一次，最后要回到原来的出发城市。当然这样的路径同样有很多条，但选择目标路径是要从所有满足条件的路径中找到一条最短的路径。本设计主要是对免疫算法展开研究讨论。首先，全面介绍了免疫算法的基本概念及实现步骤，并且对算子进行了详细的介绍；然后把
3、免疫算法跟TSP问题相结合，并对传统的免疫算法进行改进。本设计中提出了一种子代产生方法跟多种调节算子，并把各算子应用到免疫算法中，产生不同的方法，实现对TSP问题的求解。设计最后提供了对公开坐标多组城市的测试数据。关键字：免疫算法，TSP问题，选择，交叉，变异，逆转IABSTRACTWithdevelopinginthefieldofresearch,ordinaryalgorithmcannotmeetpeople’srequires.SoNeuralNetworksAlgorithm,SimulatedAnnealingAlgorithm,GeneticAlgorithmand
4、ImmuneAlgorithmcomeintobeing.Inthesixty's,theresearchpioneersinthenatureimmunesystemresearchresultswereanalyzed,withthehelpofscienceandtechnology,andtherelevantcontentandknowledge,especiallythetheoryandconceptofgenetics,theimmunealgorithmissuccessfullyappliedinsomeareasofEngineeringScience,and
5、receivedagoodeffect.Asthegeneticalgorithmhastheadvantagesofeasytouse,strongrobustnessandeasytoparallelprocessing,itiswidelyusedincombinationoptimization,structuraldesign,artificialintelligenceandotherfields.Travelingsalesmanproblem,thatis,theTSPproblem(SalesmanProblemTraveling)isoneofthefamous
6、problemsinthefieldofmathematics.SupposethereisatravelingmerchantwhowantstovisitNcities,hemustchoosethepathtogo,thepathofthelimitisonlyavisittoeachcity,andfinallytoreturntotheoriginalcity.Thepathselectionobjectiveistheminimumvalueofthepaththatisrequiredforallpaths.ThispapermainlyreferstoImmuneA
7、lgorithm.Atfirst,itgivesusanall-roundintroductionofImmuneAlgorithmthatcontainsbasicconceptandachievementsteps.ThentheauthormakesimprovementoftraditionalImmuneAlgorithm.Inthispaper,theauthorhasintroducedseveralformulas.Andthen,theauthorc
