资源描述:
《基于GA的二维迷宫解决方案设计【计算机科学专业】【毕业设计+文献综述+开题报告】》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、(20届)本科毕业论文基于GA的二维迷宫解决方案设计摘要:迷宫问题是古老又经典的问题,相关的研究已有上百年的历史。迷宫问题实际上也是一个组合优化问题。遗传算法具有自适应全局寻优、智能搜索并且收敛性好等特性,是解决迷宫问题的一种较理想的方法。论文首先分析了遗传算法的基本原理,遗传算法的特点,遗传算法的发展方向和它的主要应用领域。接着利用遗传算法的思想,针对传统的二维迷宫问题,设计染色体编码,染色体本质上是从起点到终点的一个方向组序列,难度在于如何设计适应值函数和遗传操作(包括选择,交叉,变异这三种操
2、作)。通过实验,解决了适应值函数和遗传操作相关问题,又对遗传算法遗传算子、种群规模和染色体长度等进行优化设计,提高搜索的效率,分析结果并证明解决迷宫的可行性。最后我做了一个简单的迷宫,应用遗传算法求解。关键词:遗传算法;编码;迷宫求解GA-basedsolutiondesigntwo-dimensionalmazeAbstract:Mazeisanancientclassicproblem,thestudyhistoryhashundredsofyears.Mazeactuallyacombina
3、torialoptimizationproblem.Geneticalgorithmhaveglobaloptimization,intelligentsearchandgoodconvergence,isagoodmethodtosolvemazeproblem.Papersfirstanalyzesthebasicprinciplesofgeneticalgorithms,thefeaturesofgeneticalgorithm,thedirectionofdevelopmentofgene
4、ticalgorithmanditsmainapplications.Then,usinggeneticalgorithmstheoryforthetraditionaltwo-dimensionalmazeproblem,designofchromosomecoding,chromosomesareessentiallyfromthebeginningtotheendofthesequenceinonedirection.Difficultyishowtodesignthefitnessfunc
5、tionandgeneticoperations(includingtheselection,crossover,mutationthesethreeoperations),inexperiment,solvethefitnessfunctionandtherelatedissuesingeneticoperations,andoptimizationgeneticoperators,populationsizeandchromosomelength,toimprovethesearcheffic
6、iency,theresultsprovethepossibleofsolvingthemaze.Finally,Imadeasimplemaze,theapplicationofgeneticalgorithm.Keywords:GeneticAlgorithm;maze;coding目录1.遗传算法理论11.1遗传算法的起源11.2遗传算法概念21.3遗传算法的原理21.4遗传算法的特点51.5遗传算法几个主要应用领域51.6遗传算法发展方向62.遗传算法的基本原理和实现技术92.1模式定理9
7、2.2编码技术102.2.1群体设定102.2.2适应度函数102.2.3遗传操作112.3混合遗传算法133.迷宫问题153.1迷宫问题描述153.2编码选择163.2.1群体设定163.2.2染色体编码163.2.3适应函数度183.2.4选择算子的设计193.2.5交叉算子的设计213.2.6变异算子的设计233.2.7Epoch方法233.3针对迷宫问题改进遗传算法243.4迷宫实例253.4.1种群数设定253.4.2染色图长度设定263.4.3交叉率设定27致谢31参考文献321.遗传
8、算法理论1.1遗传算法的起源当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代,生命科学与工程科学的交叉、渗透和相互促进是其中一个典型例子,也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。1967年,Holland的学生在博士论文中首次提出“遗传算法”(GeneticAlgorithms)一词。此后,Holland指导学生完成了多篇有关遗传算法研究的论文。1971年,R.B.Hollstien在他的博士论文中首次把遗传算法用于函数优化