遗传算法毕业设计提纲

1、目录 TOC o 1-5 h z HYPERLINK l bookmark7 o Current Document 1遗传算法介绍2 HYPERLINK l bookmark10 o Current Document 1.1遗传算法的产生和发展2 HYPERLINK l bookmark13 o Current Document 1.2遗传算法的基本求解步骤3 HYPERLINK l bookmark16 o Current Document 1.2.1 编码3 HYPERLINK l bookmark19 o Current Document 1.2.2初始化：3 HYPERLINK l b

2、ookmark22 o Current Document 1.2.3估计适应度：4 HYPERLINK l bookmark25 o Current Document 1.2.4再生（选择）：4 HYPERLINK l bookmark28 o Current Document 交叉：4 HYPERLINK l bookmark31 o Current Document 变异：4 HYPERLINK l bookmark34 o Current Document 重复：4 HYPERLINK l bookmark37 o Current Document 2遗传算法的应用例子5 HYPERLI

3、NK l bookmark40 o Current Document 2.1编码5 HYPERLINK l bookmark43 o Current Document 2.2初始化5 HYPERLINK l bookmark46 o Current Document 2.3计算适应度62.4再生（选择）6 HYPERLINK l bookmark52 o Current Document 2.5交叉6 HYPERLINK l bookmark55 o Current Document 2.6变异7 HYPERLINK l bookmark58 o Current Document 3遗传算法解

4、决TSP的例子8 HYPERLINK l bookmark61 o Current Document 3.1 TSP问题描述8 HYPERLINK l bookmark64 o Current Document 3.2遗传算法用于TSP问题9 HYPERLINK l bookmark67 o Current Document 3.2.1编码表示9 HYPERLINK l bookmark70 o Current Document 3.2.2初始化群体和适应度函数及其终止条件的设定9 HYPERLINK l bookmark73 o Current Document 3.2.3选择算子10 HY

5、PERLINK l bookmark76 o Current Document 3.2.4交叉算子10 HYPERLINK l bookmark79 o Current Document 3.2.5变异算子11 HYPERLINK l bookmark82 o Current Document 3.2.6 TSP问题的总结111遗传算法介绍遗传算法(genetic algorithms, GA)是一种模拟自然选择和遗传机制的寻 优方法，它是建立在达尔文的生物进化论和孟德尔的遗传学说基础上的算法。 基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选 择，适应值高的基因结构就保存

6、下来。遗传算法就是模仿了生物的遗传、进化原 理，并引用了随机统计原理而形成的。1.1遗传算法的产生和发展50年代末60年代初，生物学家Fraser试图通过计算的方法来模拟生物 界遗传与选择的进化过程，这便是GA的雏形。受此启发，Holland教授认识 到自然遗传可以转化为人工遗传算法。1967年Bagley在其博士论文中首次提 出了遗传算法这一术语。1975年，Holland出版了自然与人工系统中的适 应性行为。该书系统地阐述了遗传算法的基本理论和方法，提出了遗传算法的 基本定理-模式定理，从而奠定了遗传算法的理论基础。20世纪80年代初， Holland教授实现了第一个基于遗传算法的机器学习

7、系统一分类器系统 (Classifier System简称CS)，开创了基于遗传算法的机器学习的新概念。l992 年，JohnR. Koza出版了专著遗传编程，提出了遗传编程的概念，并成功地 把遗传编程的方法应用于人工智能、机器学习、符号处理等方面。随着遗传算法 的不断发展，关于遗传算法的国际学术活动越来越多，遗传算法已成为一个多 学科、多领域的重要研究方向。国外遗传算法的发展现状1991年DWhitey在他的论文中提出了基于领域交叉的交叉算子，这个算子 是特别针对用序号表示基因的个体的交叉，并将其应用到了 TSP问题中，通过实 验对其进行了验证。D.H.Ackley等提出了随即迭代遗传爬山法

8、采用了一种复杂的概率选举 机制，此机制中由m个“投票者”来共同决定新个体的值(m表示群体的大小)。 实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六 个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在 求解速度方面更有竞争力。H.Bersini和G.Seront将遗传算法与单一方法结合起来，形成了一种叫 单一操作的多亲交叉算子，该算子在根据两个母体以及一个额外的个体产生新个 体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献 还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其 余两个有更好的性能。国内遗传算法

9、的发展现状2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同 的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁 移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效 率不高的现象，提出了一种用基因块编码的并行遗传算法。该方法以粗粒度并行 遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为 新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色 体群体作为下一轮以相同方式演化的初始群体。2005年，江雷等针对并行遗传算法求解TSP问题，探讨了

10、使用弹性策略 来维持群体的多样性，使得算法跨过局部收敛的障碍，向全局最优解方向进化。1.2遗传算法的基本求解步骤1.2.1编码：确定用何种码制，然后将问题参数编码形成基因码链，每一个码链代表一个 个体，表示优化问题的一个解。1.2.2初始化：随机产生一个规模为P的初始种群，其中每个个体为一定长度的码链，该群体代表优化问题的一些可能解的集合。1.2.3估计适应度：计算种群中每个个体的适应度，适应度为群体进化时的选择提供了依据。一 般来说适应度越高，解的素质越好。适应度函数可以根据目标函数而定。1.2.4再生（选择）：根据每个个体的相对适应度，计算每个个体的再生次数，并进行再生操作， 产生新的个体

11、加人下一代群体中，一般再生的概率与其适应度成正比。1.2.5交叉：从种群中随机选择两个染色体，按一定的概率进行基因交换，交换位置的选 取是随机的。1.2.6变异：从种群中随机地选择一个染色体，按一定的变异概率P进行基因变异,GA的 搜索能力主要是由选择与交叉赋于的，变异算子则保证了算法能搜索到问题空 间的每一点，从而使算法具有全局最优性，它进一步增强7GA的能力.1.2.7重复：若发现最优解，则算法停止，否则转3 ,对产生的新一代群体进行重新评 价、选择、交叉、变异操作，如此循环往复，使群体中最优个体的适应度和平均 适应度不断提高。其流程图如下：编码,生成初始种群计算与评价种群中个体适应度物;

12、选择交叉变异2遗传算法的应用例子用遗传算法求解f(x)= x2 (0=x=31), x为整数时f(x)的最大值2.1编码在区间0,31上的整数可以用一个5位的二进制位串进行编码，x的值直接对 应二进制位串的数值，如：9对应01001，31对应11111。2.2初始化在0,31范围内按某种分布，随机产生一个规模为P的初始种群，本例中假 定初始种群取为4个二进制串，x1=01100,x2=11001,x3=01000,x4=10010。以上5 位字串称为染色体，每个分量称为基因，每个基因有两种状态0或者1。2.3计算适应度计算种群中每个个体的适应度，本题中，适应度函数可定为： fitnes(x)=

13、f(x)= %2，于是Fitness(x1)=144，Fitness(x2) =625,Fitness(x3)=64,Fitness(x4)二4002.4再生(选择)初始种群中每个个体入选种群的概率为：p(xi)=fitness(xi)/E ifitness(xi).利用上述概率，对这四个整数进行四次有放回的随机抽取，产 生四个新的整数，显然概率大的有更多的机会被抽中，四个新的整数气=01100, % =11001，% =11001，% =10010.经前四步后，具体情况如表下所示：234序号初始种群X值适应度人选种群概率期望复制数实际复制数1011001214412%0.4812110012

14、562551%2.0423010008645%0.204100102040032%1.281合计1233100%44平均308.325%112.5交叉将土(i=1，2, 3, 4)随机结合成两组，每组两个数；对每组再进行一次 随机抽样，以等概率从1，2, 3, 4中选取一个数n.假设在上述例子中恰%； =01100， % =11001分为一组，随机抽取n=3，那么将由二进制表示的%，% 从后三位开始212互换，得到两个新的二进制整数，记为气，七。同样对另外一组数作类似处理， 假设另一组抽得n=2,这样得到四个新的整数，结果为=01001， = 11100， = 11010，x=10001.具体

15、情况如表所示:序号复制后种群复制对象交叉点n交叉后种群X值适应度1011002301001981211001131110028784311001422110102248441001031000117289合计1638平均409.52.6变异将交叉得到的四个二进制数，每个数每个二进位进行一次随机抽样，以一个 小概率P,例如1、1000将该位取反，即由1变为1，由1变为0，以概率1-P保持该位 数字不变。这样得到四个新的数记为xn+1（1 = 1，2, 3, 4），计算其函数值f（ xn+1 ）, 回到步骤（4）。对产生的新一代群体进行重新计算适应度、选择、交叉、变异操 作，如此循环往复，使群体中

16、最优个体的适应度和平均适应度不断提高。变异可 保持群体的多样性，可使遗传算法跳出局部极值点。以上的简单例子，从开始随机产生的种群到经过一次再生、交叉、变异操作 后的新种群中，我们不难看出初始种群的平均适应度为303.8,新种群的平均适 应度为409.5,最大值从初始种群的625增加到新种群的784。可见经过一次遗传 算法的操作后，问题的解向最优解的方向前进了一大步。因此经过以上多次类似 计算，问题的解最终会接近最优解。当然在应用遗传算法时，可以事先规定一个 最大允许循环次数，以使计算得到终结，而以计算过程达到的最大函数值的xn 作为所要的解，遗传算法实际上是一种搜索方式，对那些标准数学方法难以

17、奏效的问题给出了一种处理办法。3遗传算法解决TSP的例子旅行商问题(TSP),也称为货郎担问题，是一个较古老的问题。最早可以 追溯到1759年Euler提出的骑士旅行问题。1948年，由美国兰德公司推动，TSP 成为近代组合优化领域的一个典型难题。应该说，TSP是一个具有广泛应用背景 和重要理论价值的组合优化难题，它已经被证明属于NP难题。对TSP问题的大 量研究使得TSP问题成为了一个著名的组合优化问题目前，求解TSP问题的较为 常用的方法有二叉树描述法、启发式搜索法、最近邻法、神经网络法、模拟退火 法和遗传算法等。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的 一种自适应全局概率搜

18、索算法，具有良好的全局寻优能力，成为解决问题的有效 方法之一。3.1 TSP问题描述TSP (旅行商问题)的简单描述是：一名商人欲到n个城市推销商品，每两 个城市i和j之间的距离为d，存在i，j如何使商人每个城市走一遍后回到起点， 且所走的路径最短。用数学符号表示为：设n维向量表示一条路径X=(C1, C2,Cn)，目标函数为minF(x)= Z +1d(C ,C 1) + d(C1 + C )用图语言来描述TSP，给出一个图G=(V, E)，每边eEE上有非负权值w(e)， 寻找G的Hamilon圈C，使得C的总权W(C)= Zw(e)最小。TSP搜索空间随eu E (C)着城市数n的增加而

19、增大，所有的旅程路线组合数为(n-1)! /2。5个城市的情 形对应120/10=12条路线，10个城市的情形3628800/20=181440条路线，100个 城市的情形则对应有4.6663 X 10155条路线。在次庞大的搜索空间中寻求最优解， 对于常规方法和现有的搜索而言，存在诸多的计算困难。借助遗传算法的搜索能 力解决TSP问题是很自然的想法。3.2遗传算法用于TSP问题3.2.1编码表示用遗传算法求解TSP时，算法的编码表示是算法设计的重点，它对遗传基因 的操作有一定的限制。TSP的编码策略主要包括二进制表示、顺序表示、路径表 示、矩阵表示和边表示等。由于二进制编码具有如下的特点数据

20、冗长，并且表达 能力有限，计算机无法承受如此巨大的计算量甚至根据调整不同的参数时，所运 行的时间，有时会达到近几个小时，从时间效率来说，工作效率实在是低下，并 达到无法忍受的程度，所以实际中很少使用。顺序表示是指将所有城市依次排列 构成一个顺序表，对于一条旅程，可以依次旅行经过顺序处理每个城市，每个城 市在顺序表中的顺序就是一个遗传因子的表示。每次处理完一个城市，从顺序表 中去掉该城市。处理完所有城市后，将每个城市的遗传因子连接起来，即成为一 条旅程的基因表示(染色体编码)。路径表示是表示旅程岁应的基因编码的最自 然，最简洁的表示方法。3.2.2初始化群体和适应度函数及其终止条件的设定根据编码

21、方法，随机产生初始群体，直到达到所需规模为止。适应度函数， 由于是求最短路径，适应度函数一般采用求函数最大值，例如取路径总长度T的 倒数，即fitness=l/T。其中，T= Z +1 d(C , C 1) + d(C1 + C )适应度越小的个体，该个体的路径越短，该个体则越好。也有采用fitness=l/T2 计算适应度的算法。也有的算法采用fitness=1/(T+aN)，其中N为未遍历的城市 的个数，a为惩罚函数系数，常取城市间最长距离的两倍多，路徇 越大，适应 度函数越小。迭代停止条件一般是：若某代群体中的最差个体与最好的个体适应 度的差不大于某个数(根据问题规模变化)，则终止算法。

22、若最佳个体连续保持 一定代数，则终止算法。若算法迭代次数达到一定代数，则终止算法。3.2.3选择算子选择是从一个旧种群(old population)中选择生命力强的个体位串产生新 种群的过程。或者说，选择是个体根据其适值函数f拷贝自己的过程。直观地讲， 可以把适值(或目标)函数f看作是我们期望的最大效益或好处的某种量度。根 据个体的适值拷贝位串意味着：具有高的适值的个体更大可能在下一代中产生一 个或多个子孙。显然这个操作是模仿自然选择现象，将达尔文的适者生存理论运 用于个体的选择。对于求解TSP问题，常用的选择机制有轮盘赌选择机制、随机遍历抽样法、 局部选择法、截断选择法、锦标赛选择法等。遗

23、传算法中一个较难解决的问题是 如何较快地找到最优解并防止“早熟”收敛问题。为了保证遗传算法的全局收敛 性，就要维持解群体的个体多样性。这种做法会明显改善遗传算法的行为，因为 其增加了体在种群中的分布区域，但增加了计算时间。3.2.4交叉算子Goldberg提出基于路径表示的部分映射交叉(partiallymapped, PMX)， 首先随机地在父个体中选取两杂交点，并交换相应的段再根据该段内的城市确定 部分映射。在每代父个体上先填入无冲突的城市。而对有冲突的城市分别执行这 些部分映射直到填人无冲突，刚可获得交叉后的两后代。由Davis提出顺序交叉 (order, OX)，它与PMX操作非常类似

24、。也是首先随机地在父个体中选择两杂交 点，再交换杂交段，其它位置根据保持父代个体中城市的相对次序来确定。由 Oliver等提出的循环交叉(CX)，将另一个父个体作为参照以对当前父个体中的 城市进行重组。先与另一父个体实现一个循环链.并将对应的城市填入相应的位 置，循环组成后.再将另一父体的城市填入相同的位置。上述几种TSP操作基本上考虑的是城市的位置和顺序，未考虑城市间的连 Grefenstette认为遗传算法应用与TSP，其遗传操作不仅要考虑城市间的位置， 而且有必要考虑城市间的关系，城市间的关系定义为边，让子个体继承父个体中 边的信息设计边的遗传操作很有意义。1989年，Whitle等提出了一种边重组 (Edge Recombination. ER)交叉操作，使个体能够从父个体继承95%99%的边 信息。ER操作是根据继承两个父个体定义的旅程中城市间的相邻关系生成子个 体。1991年，Stark weather等提出了一种改进的方法，在ER操作中不再保留 父个体中共同部分的序列。实验结果表明这种处理方法比随机选择的处理的性能 有相当的改善。3.2.5变异