基于GA的迷宫解决方案设计文献综述

《基于GA的迷宫解决方案设计文献综述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、文献综述基于GA的迷宫解决方案设计一、前言部分遗传算法的起源当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。1967年，Holland的学生在博士论文中首次提出“遗传算法”（GeneticAlgorithms）一词。此后，Holland指导学生完成了多篇有关遗传算法研究的论文。1971年，R.B.Hollstien在他的博士论文中首次把遗传算法用于函数优化。1975年Holland出版了他

2、的著名专著《自然系统和人工系统的自适应》（AdaptationinNaturalandArtificialSystems），这是第一本系统论述遗传算法的专著，因此有人把1975年作为遗传算法的诞生年。Holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schematheory）。该理论首次确认了结构重组遗传操作对于获得并行性的重要性。同年，K.A.DeJong完成了他的博士论文《一类遗传自适应系统的行为分析》（AnAnalysisoftheBehaviorofaClassofGenet

3、icAdaptiveSystem）。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland的模式理论与他的计算实验结合起来。尽管DeJong和Hollstien一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generationgap）等新的遗传操作技术。可以认为，DeJong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1

4、985年，在美国召开了第一届遗传算法国际会议（InternationalConferenceonGeneticAlgorithms，ICGA），并且成立国际遗传算法学会（InternationalSocietyofGeneticAlgorithms，ISGA），以后每两年举行一次。1989年，Holland的学生D.E.Goldberg出版了专著《搜索、优化和机器学习中的遗传算法》（GeneticAlgorithmsinSearch,Optimization,andMachineLearning）。该书总结了遗传算法研究的主要成果，对遗传算法及其

5、应用作了全面而系统的论述。同年，美国斯坦福大学的Koza基于自然选择原则创造性地提出了用层次化的计算机程序来表达问题的遗传程序设计(geneticprogramming,GP)方法，成功地解决了许多问题。在欧洲，从1990年开始每隔一年举办一次ParallelProblemSolvingfromNature学术会议，其中遗传算法是会议主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有FoundationsofGeneticAlgorithms，该会也是从1990年开始隔年召开一次。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和

6、动向。作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂的结构并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传程序设计是借鉴生物界的自然选择和遗传机制，在遗传算法的基础上发展起来的搜索算法，它已成为进化计算的一个新分支。在标准的遗传算法中，由定长字符串(问题的可行解)组成的群体借助于复制、交叉、变异等遗传操作不断进化找到问题的最优解或次优解。遗传程序设计运用遗传算法的思想，常采用树的结构来表示计算机程序，从而解决问题。对于许多问题，包括人工智能和机器学习上的问题都可看作是需要发现一个计算

7、机程序，即对特定输入产生特定输出的程序，形式化为程序归纳，那么遗传程序设计提供了实现程序归纳的方法。把遗传算法和计算机程序结合起来的思想出现在遗传算法中，Holland把产生式语言和遗传算法结合起来实现分类系统，还有一些遗传算法应用领域的研究者将类似于遗传算法的遗传操作施加于树结构的程序上。近年来，遗传程序设计运用遗传算法的思想自动生成计算机程序解决了许多问题[1]，如预测、分类、符号回归和图像处理等，作为一种新技术，它已经与遗传算法并驾齐驱。1996年，举行了第1次遗传程序设计国际会议，该领域己引起越来越多的相关学者们的兴趣。相关争论焦点：优化

8、问题[2]是一个流行问题，我们每天都在优化问题，我们做事情都有个先后顺序，我们选择先做什么后做什么实际上就是优化问题。遗传算法就是优化算