基于人工智能的路径查找优化算法

《基于人工智能的路径查找优化算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、毕业设计[论文]题目：基于人工智能的路径查找优化算法学生姓名：Weston学号：090171021XXX学部（系）：信息科学与技术学部专业年级：计算机应用技术指导教师：XXX职称或学位：XX2012年5月18日目录摘要IIABSTRACTIIIKEYWORDSIII1.前言12.概述22.1遗传算法优缺点22.2遗传算法应用领域32.3遗传算法基本流程33.传统遗传算法解决旅行商问题53.1常用概念53.2基本过程53.3关键步骤53.4总结84.改进后的遗传算法94.1编码、设计遗传算子94.2种群初始化94.3评价104.4选择复

2、制104.5交叉114.6变异124.7终结135.系统设计与实现145.1系统设计145.2系统实现175.3结果分析206.总结21参考文献22致谢2323基于人工智能的路径查找优化算法摘要旅行商是一个古老且有趣的问题它可以描述为：给定n个城市以及它们之间的距离dij（城市i到城市j的距离），求解从其中一个城市出发对每个城市访问，且仅访问一次，最后回到出发的城市，应当选取怎样的路线才能使其访问完所有的城市后回到初始的城市且走过的路程最短。旅行商问题已被证明是属优化组合领域的NP难题，而且在现实中的许多问题都可以转化为旅行商问题来加

3、以解决。解决旅行商问题最一般的方法就是枚举出所有可能的路线然后对每一条进行评估最后选取出路程最短的一条即为所求解。解决旅行商问题的各种优化算法都是通过牺牲解的精确性来换取较少的耗时，其他一些启发式的搜索算法则依赖于特定的问题域，缺乏通用性，相比较而言遗传算法是一种通用性很好的全局搜索算法。遗传算法GA(geneticalgorithm)最早由美国密歇根大学的JohnHolland提出。具有自组织、自适应、自学习和群体进化功能有很强的解决问题的能，在许多领域都得到了应用。遗传算法以其广泛的适应性渗透到研究与工程的各个领域，已有专门的遗传

4、算法国际会议，每两年召开一次，如今已开了数次，发表了数千篇论文，对其基本的理论、方法和技巧做了充分的研究。今天，遗传算法的研究已成为国际学术界跨学科的热门话题之一。关键词：人工智能；遗传算法；TSP；旅行商问题23PathsearchsystembasedonartificialintelligencealgorithmsAbstractTravelingsalesmanisanancientandinterestingitcanbedescribedasgivenncitiesandthedistancebetweenthemdij

5、(cityitocityj,thedistance),solvingtheaccessforeachcity,startingfromoneofthecityandonlyonevisitandfinallybacktothestartingcity,shouldselectwhatrouteitbacktotheinitialvisitallthecitiescityandtraveledtheshortest.Variousoptimizationalgorithmstosolvethetravelingsalesmanprobl

6、emthroughtheexpenseoftheaccuracyofthesolutioninexchangeforlesstime-consuming,otherheuristicsearchalgorithmdependsonthespecificproblemdomainlackofuniversalsothegeneticalgorithmiscomparedtoacommongoodglobalsearchalgorithm.GA(geneticalgorithm)WasfirstproposedbyJohnHollando

7、ftheUniversityofMichigan.TheGAhasself-organizing,adaptive,self-learningandgroupevolutionfunctionsotheGAhasstrongabilitytosolveproblems,nowtheGAbeenappliedinmanyfields.Today,thegeneticalgorithmresearchhasbecomeoneofthehottopicsoftheinternationalacademiccommunityinterdisc

8、iplinary.Keywords:ArtificialIntelligence;GeneticAlgorithm;TSP1.231.前言现代社会虽然交通发达，两地之间有时甚至可以转瞬既至，但路径问题仍是当今算法界中比较