1、毕业设计论文遗传算法及其应用浅析论文专业选修课期末考核（论文）遗传算法及其应用浅析 学 院： 专 业： 班 级： 学 号： 学生姓名： 指导教师： 2015年 6 月 1 日贵州大学论文（设计）诚信责任书本人郑重声明：本人所呈交的毕业论文（设计），是在导师的指导下独立进行研究所完成。毕业论文（设计）中凡引用他人已经发表或未发表的成果、数据、观点等，均已明确注明出处。特此声明。论文（设计）作者签名： 日 期： 目录第一章 绪 论 4第二章 遗传算法介绍 52.1遗传算法介绍 52.2遗传算法的产生和发展 52.3 遗传算法的基本求解步骤 62.3.1 编码： 62.3.2初始化： 62.3.3估
2、计适应度： 62.3.4再生(选择): 62.3.5 交叉: 62.3.6 变异： 62.3.7 重复： 72.4 遗传算法流程图： 7第三章 遗传算法的应用概述 83.1 TSP 问题描述 83.2 遗传算法用于TSP 问题 93.2.1 编码表示 93.2.2 初始化群体和适应度函数及其终止条件的设定 93.2.3 选择算子 103.2.4 交叉算子 103.2.5 变异算子 113.2.6 TSP问题的总结 11第四章 应用举例 1241 问题陈述 1242 详细解答过程 124.2.1 问题分析 124.2.2 实验原理与数学模型 134.2.3 MATLAB求解结果 1543 求解结
3、果验证与反思 16第五章 附录 1751 Matlab程序代码 17参考文献 22【摘要】：遗传算法（Genetic Algorithm,GA）是近年来迅速发展起来的一种全新的随机搜索与优化算法，是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。它的研究历史比较短，早期是一种试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。近年来世界范围形成的进化计算热潮，计算智能已作为人工智能研究的一个重要方向，以及后来的人工生命研究兴起，使遗传算法受到广泛的关注。 其基本思想基于Darwin的进化论和Mendel的遗传学。遗传算法的广泛使用和发展潜
4、能使得很多学者深入研究遗传算法，并出版了很多关于它的书籍。 TSP问题是古老的经典问题，有关的研究有几百年的时间。TSP旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。 本论文首先介绍了遗传算法的基本原理、遗传算法的特点，遗传算法的发展方向和主要应用领域；接着针对问题论述了遗传算法在编码表示和遗传算子（包括选择算子，交叉算子、变异算子）等方面的应用情况，简单讨论几种编码方法,最后简单介绍了TSP问题。【关键词】遗传算法；TSP；遗传算子；编码【Abstract】Genetic Algorithm (based Algorithm, GA) is developed
5、 rapidly in recent years a new kind of random search and optimization Algorithm, is a kind of reference for biological mechanism of natural selection and evolution of highly parallel, randomized, adaptive search Algorithm. Its research history is shorter, the early is an attempt to explain complex a
6、daptive process of creatures in nature system, simulation of the evolution mechanism to construct the model of artificial system. Range of evolutionary computation in the world in recent years, computational intelligence has as an important direction of artificial intelligence research, and later th
7、e artificial life research, genetic algorithm has been widely attention. Its basic idea is based on Darwins theory of evolution and Mendels genetics. The widespread use of genetic algorithm and the development potential has led many scholars in-depth study genetic algorithm, and has published many b
8、ooks about it. The TSP problem is a classic problem of ancient, studies of hundreds of years. TSP traveling salesman problem is a typical NP complete problem, genetic algorithm is an ideal method to solve the problem of NP. This paper firstly introduces the basic principle of genetic algorithm, gene
9、tic algorithm, the characteristics of the development direction of genetic algorithm and the main application field; Then in view of the problems this paper discusses the genetic algorithm (ga) said in coding and genetic operators (including selection operator, crossover operator, mutation operator)
10、 and so on, the application of simple discuss several encoding methods, finally introduces the TSP problem. 【keywoeds】Genetic Algorithm;TSP;genetic operator;coding第一章 绪 论 遗传算法(Genetic Algorithm，GA)是近年来迅速发展起来的一种全新的随机搜索与优化算法。它是由美国密执安大学JHolland教授提出的一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。它起源于达尔文的进化论，是模拟达尔文的遗传选择和自然淘
11、汰的生物进化过程的计算模型。遗传算法的研究引起了国内外学者的关注。自1985年以来，国际上已召开了多次遗传算法的学术会议和研讨会，国际遗传算法学会组织 召 开 的 ICGA(International Conference on Genetic Algorithms)会议和FOGA(Workshop on Foundation ofGenetic Algorithms)会议，为研究和应用遗传算法提供了国际交流的机会。 遗传算法的主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不以梯度信息为基础。它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛应用于组合优化、机器学习、自适应
12、控制、规划设计和人工生命等领域。作为一种全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及应用范围广等特点，使其成为21世纪智能计算核心技术之一。进入80年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的话题近年来，遗传算法已被成功地应用于经济答理、交通运输、工业设计等不同领域解决了许多问题。例如，可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等。 第二章 遗传算法介绍2.1遗传算法介绍 遗传算法（genetic algorithms，GA）是一种模拟自然选择和遗传机制的寻优方法， 它是建立在达尔文的生物进化论和孟
13、德尔的遗传学说基础上的算法。基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。遗传算法就是模仿了生物的遗传、进化原理，并引用了随机统计原理而形成的。2.2遗传算法的产生和发展 50 年代末60 年代初， 生物学家Fraser 试图通过计算的方法来模拟生物界遗传与选择的进化过程，这便是GA 的雏形。受此启发，Holland 教授认识到自然遗传可以转化为人工遗传算法。1967 年Bagley 在其博士论文中首次提出了遗传算法这一术语。1975 年，Holland 出版了自然与人工系统中的适应性行为。该书系统地阐述了遗传算法的基本理论和方法，提出了
14、遗传算法的基本定理-模式定理， 从而奠定了遗传算法的理论基础。20 世纪80 年代初，Holland 教授实现了第一个基于遗传算法的机器学习系统-分类器系统(Classifier System 简称CS)，开创了基于遗传算法的机器学习的新概念。l992 年，John RKoza 出版了专著遗传编程，提出了遗传编程的概念，并成功地把遗传编程的方法应用于人工智能、机器学习、符号处理等方面。随着遗传算法的不断发展， 关于遗传算法的国际学术活动越来越多， 遗传算法已成为一个多学科、多领域的重要研究方向。2.3 遗传算法的基本求解步骤2.3.1 编码： 确定用何种码制, 然后将问题参数编码形成基因码链，
15、每一个码链代表一个个体, 表示优化问题的一个解。2.3.2初始化： 随机产生一个规模为P的初始种群, 其中每个个体为一定长度的码链, 该群体代表优化问题的一些可能解的集合。2.3.3估计适应度： 计算种群中每个个体的适应度, 适应度为群体进化时的选择提供了依据。一般来说适应度越高, 解的素质越好。适应度函数可以根据目标函数而定。2.3.4再生(选择):根据每个个体的相对适应度, 计算每个个体的再生次数, 并进行再生操作, 产生新的个体加人下一代群体中, 一般再生的概率与其适应度成正比。2.3.5 交叉: 从种群中随机选择两个染色体, 按一定的概率进行基因交换，交换位置的选取是随机的。2.3.6
16、 变异： 从种群中随机地选择一个染色体, 按一定的变异概率P进行基因变异,GA的搜索能力主要是由选择与交叉赋于的, 变异算子则保证了算法能搜索到问题空间的每一点, 从而使算法具有全局最优性, 它进一步增强了GA的能力.2.3.7 重复： 若发现最优解, 则算法停止, 否则转3 ,对产生的新一代群体进行重新评价、选择、交叉、变异操作, 如此循环往复, 使群体中最优个体的适应度和平均适应度不断提高。其流程图如下：2.4 遗传算法流程图：第三章 遗传算法的应用概述 旅行商问题(TSP)，也称为货郎担问题，是一个较古老的问题。最早可以追溯到1759 年Euler 提出的骑士旅行问题。1948 年，由美
17、国兰德公司推动，TSP 成为近代组合优化领域的一个典型难题。应该说，TSP 是一个具有广泛应用背景和重要理论价值的组合优化难题，它已经被证明属于NP 难题。对TSP 问题的大量研究使得TSP 问题成为了一个著名的组合优化问题目前，求解TSP 问题的较为常用的方法有二叉树描述法、启发式搜索法、最近邻法、神经网络法、模拟退火法和遗传算法等。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局概率搜索算法，具有良好的全局寻优能力，成为解决问题的有效方法之一。3.1 TSP 问题描述 TSP（旅行商问题）的简单描述是：一名商人欲到n 个城市推销商品，每两个城市i 和j 之间的距离为d，
18、存在i，j 如何使商人每个城市走一遍后回到起点，且所走的路径最短。用数学符号表示为：设n 维向量表示一条路径X=(C1, C2, ,Cn)，目标函数为minF(x)= 用图语言来描述TSP，给出一个图G=(V, E)，每边eE 上有非负权值w(e)，寻找G 的Hamilon 圈C，使得C 的总权W(C)=最小。TSP 搜索空间随着城市数n 的增加而增大，所有的旅程路线组合数为(n-1)! /2。5 个城市的情形对应120/10=12 条路线，10个城市的情形3628800/20=181440 条路线，100 个城市的情形则对应有4.6663条路线。在次庞大的搜索空间中寻求最优解，对于常规方法和
19、现有的搜索而言，存在诸多的计算困难。借助遗传算法的搜索能力解决TSP 问题是很自然的想法。3.2 遗传算法用于TSP 问题3.2.1 编码表示 用遗传算法求解TSP 时，算法的编码表示是算法设计的重点，它对遗传基因的操作有一定的限制。TSP 的编码策略主要包括二进制表示、顺序表示、路径表示、矩阵表示和边表示等。由于二进制编码具有如下的特点数据冗长，并且表达能力有限，计算机无法承受如此巨大的计算量甚至根据调整不同的参数时，所运行的时间，有时会达到近几个小时，从时间效率来说，工作效率实在是低下，并达到无法忍受的程度，所以实际中很少使用。顺序表示是指将所有城市依次排列构成一个顺序表，对于一条旅程，可
20、以依次旅行经过顺序处理每个城市，每个城市在顺序表中的顺序就是一个遗传因子的表示。每次处理完一个城市，从顺序表中去掉该城市。处理完所有城市后，将每个城市的遗传因子连接起来，即成为一条旅程的基因表示（染色体编码）。路径表示是表示旅程岁应的基因编码的最自然，最简洁的表示方法。3.2.2 初始化群体和适应度函数及其终止条件的设定 根据编码方法，随机产生初始群体，直到达到所需规模为止。适应度函数，由于是求最短路径，适应度函数一般采用求函数最大值，例如取路径总长度T 的倒数，即fitness=l/T。其中， T= 适应度越小的个体，该个体的路径越短，该个体则越好。也有采用fitness=l/T2 计算适应
21、度的算法。也有的算法采用fitness=1/(T+aN)，其中N 为未遍历的城市的个数，a 为惩罚函数系数，常取城市间最长距离的两倍多，路径T 越大，适应度函数越小。迭代停止条件一般是：若某代群体中的最差个体与最好的个体适应度的差不大于某个数（根据问题规模变化），则终止算法。若最佳个体连续保持一定代数，则终止算法。若算法迭代次数达到一定代数，则终止算法。3.2.3 选择算子 选择是从一个旧种群(old population)中选择生命力强的个体位串产生新种群的过程。或者说，选择是个体根据其适值函数f 拷贝自己的过程。直观地讲，可以把适值（或目标）函数f 看作是我们期望的最大效益或好处的某种量度
22、。根据个体的适值拷贝位串意味着：具有高的适值的个体更大可能在下一代中产生一个或多个子孙。显然这个操作是模仿自然选择现象，将达尔文的适者生存理论运用于个体的选择。对于求解TSP 问题， 常用的选择机制有轮盘赌选择机制、随机遍历抽样法、局部选择法、截断选择法、锦标赛选择法等。遗传算法中一个较难解决的问题是如何较快地找到最优解并防止“早熟”收敛问题。为了保证遗传算法的全局收敛性，就要维持解群体的个体多样性。这种做法会明显改善遗传算法的行为，因为其增加了体在种群中的分布区域，但增加了计算时间。3.2.4 交叉算子 Goldberg 提出基于路径表示的部分映射交叉(partiallymapped, PM
23、X)，首先随机地在父个体中选取两杂交点，并交换相应的段再根据该段内的城市确定部分映射。在每代父个体上先填入无冲突的城市。而对有冲突的城市分别执行这些部分映射直到填人无冲突，刚可获得交叉后的两后代。由Davis 提出顺序交叉(order, OX)，它与PMX 操作非常类似。也是首先随机地在父个体中选择两杂交点，再交换杂交段，其它位置根据保持父代个体中城市的相对次序来确定。由Oliver 等提出的循环交叉(CX)，将另一个父个体作为参照以对当前父个体中的城市进行重组。先与另一父个体实现一个循环链并将对应的城市填入相应的位置，循环组成后再将另一父体的城市填入相同的位置。上述几种TSP 操作基本上考虑
24、的是城市的位置和顺序，未考虑城市间的连Grefenstette 认为遗传算法应用与TSP，其遗传操作不仅要考虑城市间的位置，而且有必要考虑城市间的关系，城市间的关系定义为边，让子个体继承父个体中边的信息设计边的遗传操作很有意义。1989 年，Whitle 等提出了一种边重组(Edge RecombinationER)交叉操作，使个体能够从父个体继承9599的边信息。ER 操作是根据继承两个父个体定义的旅程中城市间的相邻关系生成子个体。1991 年，Stark weather 等提出了一种改进的方法，在ER 操作中不再保留父个体中共同部分的序列。实验结果表明这种处理方法比随机选择的处理的性能有相
25、当的改善。3.2.5 变异算子尽管复制和交叉操作很重要,在遗传算法中是第一位的,但不能保证不会遗漏一些重要的遗传信息。在人工遗传系统中,变异是用来防止这种不可弥补的遗漏，在简单遗传算法中，变异就是某个字符串某一位的值偶然的（概率很小的）随机的改变,即在某些特定位置上简单地把1 变成0，或反之。变异是沿着个体字符空间的随机移动，当它有节制地和交叉一起使用时，它就是一种防止过度成熟而丢失重要概念的保险策略。变异本身是一种局部随机搜索，与选择/重组算子结合在一起，保证了遗传算法的有效性，使遗传算法具有局部的随机搜索能力；同时使得遗传算法保持种群的多样性，以防止出现非成熟收敛。在变异操作中，变异率不能
26、取得太大。变异算子的设计要比交叉算子的设计灵活得多。简单的倒位操作，即首先在父个体中随机地选择两截断点，然后将该两点所夹的子串中的城市进行反序。也有一种贪婪倒位变异算子，它的主要思想是：首先随机选择一个城市C，然后在除外的其他城市中选除C、cRight、cLeft 以外的距离C最近的城市，在对cRight 到之间的城市进行倒位。3.2.6 TSP问题的总结对于TSP，目前还不存在能找到完美解的方法，这个问题是NP 难的。为了进一步提高算法的全局优化能力，避免搜索过程陷入局部极小，现已提出的改进策略主要有：并行多邻域搜索、平滑优化曲面形状、熵抽样等高级技术。对于复杂优化问题，单一机制的优化算法很
27、难实现全局优化，且效率较低。多种优化机制和邻域搜索结构相混合，是能较大程度提高全局优化度和鲁棒性的有力途径，并可一定程度上放松对单一算法参数选择的苛刻性，所以混合优化策略会是一种趋势。总之，对于TSP 问题，可从问题的编码及遗传算子设计方面来改进发展遗传算法。尤其包含启发式信息，尽量让子代继承父代的优良特性。通过保持边的有用信息找到更好的算法，这是算法改进的一个趋势，同时为了防止局部收敛必须让算法达到收敛性与群体多样性的平衡。 第四章 应用举例41 问题陈述 如下图所示，寻找图中11个端点的最短路径，其中没有连接的端点表示没有路径。要求设计遗传算法对该问题求解。42 详细解答过程4.2.1 问
28、题分析 如图如示，将节点编号，依次为1.2.3.4.5.6.7.8.9.10.11，由图论知识，则可写出其带权邻接矩阵为： 0 2 8 1 500 500 500 500 500 500 500 2 0 6 500 1 500 500 500 500 500 500 8 6 0 7 500 1 500 500 500 500 500 1 500 7 0 500 500 9 500 500 500 500 500 1 500 500 0 3 500 2 500 500 500 500 500 1 500 3 0 4 500 6 500 500 500 500 500 9 500 4 0 500
29、500 1 500 500 500 500 500 2 500 500 0 7 500 9 500 500 500 500 500 6 500 7 0 1 2 500 500 500 500 500 500 1 500 1 0 4 500 500 500 500 500 500 500 9 2 4 0注：为避免计算时无穷大数吃掉小数，此处为令inf=500。 问题要求求出任意两点间的最短路径，Floyd算法采用的是在两点间尝试插入顶点，比较距离长短的方法。我思考后认为，用遗传算法很难找到一个可以统一表示最短路径的函数，但是可以对每一对点分别计算，然后加入for循环，可将相互之间的所有情况解出。
30、观察本题可发现，所有节点都是可双向行走，则可只计算i到j的路径与距离，然后将矩阵按主对角线翻折即可得到全部数据。4.2.2 实验原理与数学模型 实现原理为遗传算法原理，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使得适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。数学模型如下： 设图由非空点集合和边集合组成，其中又设的值为， 故可表示为一个三元组则求最短路径的数学模型可以描述为： 实验具体内容： 第一、编码与初始化，因采用自然编码，且产生的编码不能重复，于是我采用了randpe
31、rm函数产生不重复的随机自然数。因解题方法是使用的是计算每一对点，则我们编码时将第一个节点单独放入，合并成完整编码。 因为节点有11个，可采用一个1行11列的矩阵储存数据，同时，由于编号为数字，可直接使用数字编码表示路径的染色体。具体如下：采用等长可变染色体的方式，例如由2到9的路径，染色体编码可能为（2，5，1，8，4，6，9，3，10，7，11），超过9之后的编码，用来进行算子的运算，不具备实际意义。 第二：计算适应度，因取最短路径值，即最小值，常用方法为C-F(x)或C/F(x)（C为一常数），此处采用前一种方式。于是，可进一步计算相对适应度。 第三：选择与复制，采用轮盘赌算法，产生一个
32、随机值，比较它与累计相对适应度的关系，从而选择出优良个体进入下一代。 第四：交叉，因编码是不重复的数字，所以采用传统的交叉方法，即上一行与下一行对位交叉，会产生无效路径，于是，采用了不同的交叉方法，具体如下：（1）在表示路径的染色体Tx 和Ty中，随机选取两个基因座（不能为起点基因座）i和j, 即将i个基因座和第j个基因座之间的各个基因座定义为交叉域，并将交叉的内容分别记忆为temp1和temp2。（2）根据交叉区域中的映射关系，在个体Tx中找出所有与temp2相同的元素，在个体Ty中找出所有与temp1相同的元素，全部置为0。（3）将个体Tx、Ty进行循环左移，遇到0就删除，直到编码串中交叉区域的左端不再
