1、 本科 毕业 设计 (论文 ) （二零 届） 基于 GA 的 二维 迷宫解决方案设计 所在学院 专业班级 计算机科学与技术 学生姓名 学号 指导教师 职称 完成日期 年 月 摘要： 迷宫问题是古老又经典的问题，相关的研究已有上百年的历史。迷宫问题实际上也是一个组合优化问题。 遗传算法具有自适应全 局寻优、智能搜索并且收敛性好等特性， 是解决迷宫问题的一种较理想的方法。论文首先分析了遗传算法的基本原理，遗传算法的特点，遗传算法的发展方向和它的主要应用领域。接着利用遗传算法的思想，针对传统的二维迷宫问题，设计染色体编码，染色体本质上是从起点到终点的一个方向组序列，难度在于如何设计适应值函数和遗传操
2、作（包括选择，交叉，变异这三种操作）。通过实验，解决了适应值函数和遗传操作相关问题，又 对遗传算法遗传算子、种群规模和染色体长度等进行优化设计， 提高搜索的效率， 分析 结果并证明解决迷宫的可行性。最后我做了一个简单的迷 宫，应用遗传算法求解。 关键词： 遗传算法；编码；迷宫求解 GA-based solution design two-dimensional maze Abstract: Maze is an ancient classic problem, the study history has hundreds of years. Maze actually a combinator
3、ial optimization problem. Genetic algorithm have global optimization, intelligent search and good convergence , is a good method to solve maze problem . Papers first analyzes the basic principles of genetic algorithms, the features of genetic algorithm, the direction of development of genetic algori
4、thm and its main applications. Then, using genetic algorithms theory for the traditional two-dimensional maze problem, design of chromosome coding, chromosomes are essentially from the beginning to the end of the sequence in one direction. Difficulty is how to design the fitness function and genetic
5、 operations (including the selection, crossover, mutation these three operations), in experiment， solve the fitness function and the related issues in genetic operations, and optimization genetic operators, population size and chromosome length , to improve the search efficiency, the results prove t
6、he possible of solving the maze. Finally, I made a simple maze, the application of genetic algorithm. Key words: Genetic Algorithm;maze;coding 目 录 1. 遗传算法理论 . 1 1.1 遗传算法的起源 . 1 1.2 遗传算法概念 . 2 1.3 遗传算法的原理 . 2 1.4 遗传算法的特点 . 5 1.5 遗传算法几个主要应用领域 . 5 1.6 遗传算法发展方向 . 6 2. 遗传算法的基本原理和实现技术 . 9 2.1 模式定理 . 9 2.2
7、 编码技术 . 10 2.2.1 群体设定 . 10 2.2.2 适应度函数 . 10 2.2.3 遗传操作 . 11 2.3 混合遗传算法 . 13 3. 迷宫问题 . 15 3.1 迷宫问题描述 . 15 3.2 编码选择 . 16 3.2.1 群体设定 . 16 3.2.2 染色体编码 . 16 3.2.3 适应函数度 . 18 3.2.4 选择算子的设计 . 19 3.2.5 交叉算子的设计 . 21 3.2.6 变异算子的设计 . 23 3.2.7 Epoch方法 . 23 3.3 针对迷宫问题改进遗传算法 . 24 3.4 迷宫实例 . 25 3.4.1 种群数设定 . 25 3.
8、4.2 染色图长度设定 . 26 3.4.3 交叉率设定 . 27 致谢 . 错误 !未定义书签。 参考文献 . 31 1 1. 遗传算法理论 1.1 遗传算法的起源 当前科学技术正进入多学科互相交叉、互相渗透、 互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。 1967 年， Holland 的学生在博士论文中首次提出“遗传算法”（ Genetic Algorithms）一词。此后， Holland 指导学生完成了多篇有关遗传算法研究的论文。 1971 年， R.B.Holls
9、tien 在他的博士论文中首次把遗传算法用于函数优化。 1975 年 Holland 出版了他的著名专著自然系统和人工系统的自适应（ Adaptation in Natural and Artificial Systems），这是第一本系统论述遗传算法的专著，因此有人把 1975 年作为遗传算法的诞生年。 Holland 在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（ schema theory）。该理论首次确认了结构重组遗传操作对于获得并行性的重要性。同年， K.A.De Jong 完成了他的博士论文一类遗传自适应系统的行为分析（ An
10、Analysis of the Behavior of a Class of Genetic Adaptive System）。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把 Holland 的模式理论与他的计算实验结合起来。尽管 De Jong 和 Hollstien 一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（ generation gap）等新的遗传操作技术。可以认为， De Jong 的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。 遗传算法 (Genet
11、ic Algorithm, GA)是近三十年来迅速发展起来的一种全新的随机搜索与优化算法 ,其基本思想是基于 Darwin 的进化论和 Mendel 的遗传学说。该算法由密执安大学教授 Holland及其学生于 1975 年创建。此后，遗传算法的研究引起了国内外学者的关注。自 1985 年以来 .国际上已召开了多次遗传算法的学术会议和研讨会 .国际遗传算法学会组织召开的 ICGA( International Conference on Genetic Algorithms)会议和 FOGA( Workshop on Foundation of Genetic Algorithms)会议。为研
12、究和应用遗传算法提供了国际交流的机会。 遗传程序设计是借鉴生物界的自然选择和遗传机制，在遗传算法的基础上发展起来的搜索算法，它已成为进化计算的一个新分支 1。在标准的遗传算法中，由定长字符串 (问题的可行解 )组成的群体借助于复制、交叉、变异等遗传操作不断进化找到问题的最优解或次优解。遗传程序设计运用遗传算法的思想，常采用树的结构来表示计算机程序，从而解决问题 2。对于许多问题，包括人工智能和机器学习上的问题都可看作是需要发现 一个计算机程序，即对特定输入产生特定输出的程2 序，形式化为程序归纳，那么遗传程序设计提供了实现程序归纳的方法。 1.2 遗传算法概念 遗传算法简称 GA(Geneti
13、c Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理 3,4、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。 遗传算法的基本思想是基于 Darwin 进化论和 Mendel 的遗传学说的。 Darwin 进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个
14、体特征方能保留下来。 Mendel 遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境 的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法，故而在这个算法中要用到各种进化和遗传学的概念。 1.3 遗传算法的原理 遗传算法 GA 把“问题的解 ”表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把
15、这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体 ”群。这样，“一代一代 ”地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。 在遗传算法里，优化问题的解被称为个体，它表示为一个参数列表，叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字串，不过也有其他的表示方法适用，这一过程称为编码。 一开始，算法随机生成一定数量的个体，有时候操作者也可以对这个随机产生过程进行干预，播下已经部分优化的种子。在每一代中，每一个个体都被评价，并通过计算适应度函数得到一个适应度数值。种群中
16、的“个体”被按照适应度排序，适应度高的在前面 。这里的“高”是相对于初始的种群的“低适应度 ”来说的。 下一步是产生下一代个体并组成种群。这个过程是通过选择和交叉完成的，其中繁殖包括交叉(crossover)和变异 (mutation)。选择则是根据新个体的适应度进行的，适应度越高，被选择的机会越高，而适应度低的，被选择的机会就低。初始的数据可以通过这样的选择过程组成一个相对优化的3 群体。之后，被选择的个体进入交配过程。一般的遗传算法都有一个交配概率，范围一般是 0.1-0.99，这个交配概率反映两个被选中的个体进行交配的概率。例如，交配概率为 0.8， 则 80%的“夫妻”会生育后代。每两
17、个个体通过交配产生两个新个体，代替原来的“老”个体，而没交配的个体则保持不变。交配父母的染色体相互交换，从而产生两个新的染色体，第一个个体前半段是父亲的染色体，后半段是母亲的，第二个个体则正好相反。不过这里的半段并不是真正的一半，这个位置叫做交配点，也是随机产生的，可以是染色体的任意位置。再下一步是突变，通过突变产生新的“子”个体。一般遗传算法都有一个固定的突变常数，通常是 0.01 或者更小，这代表变异发生的概率。根据这个概率，新个体的染色体随机的突变，通常就是改变染色体的一 个字节（ 0 变到 1，或者 1变到 0）。 经过这一系列的过程（选择、交配和突变），产生的新一代个体不同于初始的一
18、代，并“一代一代”向增加整体适应度的方向发展，因为最好的个体总是更多的被选择去产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复：每个“个体”被评价，计算出适应度，两个个体交配，然后突变，产生第三代。周而复始，直到终止条件满足为止。 遗传算法关键问题 （ 1）串的编码方式 这本质问题是编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体” 串。串长度及编码形式对算法收敛影响极大 （ 2）适应函数的确定 适应度函数 (fitness function)也称对象函数 (object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可
19、以把问题的模型函数作为对象函数；但有时需要另行构造。 （ 3）遗传算法自身参数设定 遗传算法自身参数有 3 个，即群体大小 n、交叉概率 Pc 和变异概率 Pm。群体大小 n 太小时难以求出最优解，太大则增长收敛时间。一般 n 50-300。交叉概率 Pc 太小时难以向前搜索，太大则容易 破坏“高适应值”的结构。一般取 Pc=0.3-0.99。变异概率 Pm 太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取 Pm 0.0001-0.01。 遗传算法基本操作 （ 1）初始化 选择一个群体，即选择一个串或个体的集合 bi， i=1， 2， .n。这个初始的群体也就是问题假设解的
20、集合。一般取 n 50-300。通常以随机方法产生串或个体的集合 bi,i 1， 2， .n。问题的最优解将通过这些初始假设解进化而求出。 4 （ 2）选择 根据适者生存原则选择下一代的 个体。在选择时，以适应度为选择原则。适应度选择原则体现了适者生存，不适应者淘汰的自然法则。给出目标函数 f，则 f(bi)称为个体 bi 的适应度。适应度较高的个体，繁殖下一代的数目较多。适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。 （ 3）交叉 对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，
21、按交叉概率 P 交叉。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合， 也即产生新的个体。交叉时，可实行单点交叉或多点交叉。 例如有个体 S1=10010111011 S2=01011111011 选择它们的左边 3 位进行交叉操作，则有 S1=01010111011 S2=10011111011 一般而言，交叉概率 P 取值为 0.3 0.99。 （ 4）变异 根据生物遗传中基因变异的原理，以变异概率 Pm 对某些个体的某些“位”执行变异。在变异时，对执行变异的串的“对应位”求反，即把 1 变为 0，把 0 变为 1。变异概率 Pm 与生物变异极小的情况一致，所以
22、， Pm 的取值 较小，一般取 0.0001-0.01。 例如有个体 S 101011。对其的第 1， 4 位置的基因进行变异，则有 s=001111 单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质 . （ 5）全局最优收敛 当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新 一代群体取代上一代群体，并返回到第 2 步即选择操作处继续循环执行。 5 1.
23、4 遗传算法的特点 （ 1）遗传算法从问题解的中集开始嫂索，而不是从单个解开始。 这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的，容易误入局部最优解。遗传算法从“串集”开始搜索，覆盖面大，利于全局择优。 （ 2）遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。 由于遗传算法使用“适应值”这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需“ 适应值”和串编码等通用信息，故几乎可处理任何问题。 （ 3）遗传算法有极强的容错能力。 遗传算法的初始串集本身就带有大量与最优解甚远的信息，通过选择、交叉、变异操作能迅速排除与最优解相差极大的串
24、，这是一个强烈的滤波过程，并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。 （ 4）遗传算法最优迫近。 遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的 覆盖。 1.5 遗传算法几个主要应用领域 虽然在各种应用领域中，算法的具体实施细节有各自的特点，但遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域。遗传算法主要应用于以下几个主要领域： （ 1）函数优化 函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用例子。很多人
25、工构造的各种各样复杂形式的测试函数，有连续函数也有离散函数，有单峰函数也有多峰函数等 5，利用这些函数来评价遗传算法的性能。对于非线性、多目标的函数优化问题，用其他算法 通常较难求解，但使用遗传算法却很方便并可以得到较好的结果。 （ 2）组合优化 随着问题规模的扩大，组合优化问题的搜索空间急剧增大，甚者有时无法求到精确最优解 6。对于这类复杂问题，使用遗传算法求解可行解就显得更加有实际价值。这类问题包括旅行商问题、背包问题、装箱问题和图形划分等。 （ 3）机器人学 机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于人工自适应系统的研究。所以，机器人学理所当然地成为遗传算法的一个
26、重要应用领域。例如，遗传算法已经在移动6 机器人路径 规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方而得到研究和应用 7。 （ 4）图像处理 图像处理是计算机视觉中的一个重要研究领域 8。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在一次误差，从而影响图像的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武之地。目前已在模式识别 (包括汉字识别 )、图像恢复、图像边缘特征提取等方而得到了应用。 （ 5）遗传编程 1989 年，美国 Standford 大学的 Koza 教授发展了遗传
27、编程的概念，其基本思想是 :采用树型结构表示计算机程序，运用遗传算法的思想，通过自动生成计算机程序来解决问题。虽然遗传编程的理论尚未成热，应用也有一些限制，但它已成功地应用于人工智能、机器学习等领域。目前公开的遗传编程实验系统有十多个。 （ 6）机器学习 学习能力是高级自适应系统所具备的能力之一，基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用 9,10。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属 度函数，从而更好地改进了模糊系统的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络结构优化设计；分类器系统也在学习式多机器人路径规
28、划系统中得到了成功的应用。 （ 7）数据挖掘 数据挖掘是近几年出现的数据库技术，它能够从大型数据库中提取隐含的、先前未知的、有潜在应用价值的知识和规则。许多数据挖掘问题可看成是搜索问题，数据库看作是搜索空间，挖掘算法看作是搜索策略。因此，应用遗传算法在数据库中进行搜索，对随机产生的一组规则进行进化 .直到数据库能被该组规则覆盖，从而挖掘 出隐含在数据库中的规则。 Sunil 已成功地开发了一个基于遗传算法的数据挖掘下具。利用该工具对两个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法之一。 1.6 遗传算法发展方向 遗传算法发展方向其实就是和其他方法结合优化问题，单方面改进遗传算法的各种算子不能取得明显进展。遗传算法以其基本思想简单、便于实现和并行搜索的优点赢得了众多学者和各种工程人员的青睐，是目前应用最广的优化搜索算法之一 11。但遗传算法存在收敛速度慢和易于陷入局部最优的问题，在需要优化的 参数较多时，更凸现了遗传算法的不足。遗传算法如何提高遗传算法
