遗传算法毕业设计提纲

《遗传算法毕业设计提纲》由会员分享，可在线阅读，更多相关《遗传算法毕业设计提纲（11页珍藏版）》请在金锄头文库上搜索。

1、目录1遗传算法介绍21.1遗传算法的产生和发展21.2遗传算法的基本求解步骤31.2.1 编码31.2.2初始化：31.2.3估计适应度：41.2.4再生（选择）：41.2.5 交叉：41.2.6 变异：41.2.7 重复：42遗传算法的应用例子52.1编码52.2初始化52.3计算适应度62.4再生（选择）62.5交叉62.6变异73遗传算法解决TSP的例子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问题的总结111遗传算法介

2、绍遗传算法(genetic algorithms, GA)是一种模拟自然选择和遗传机制的寻 优方法，它是建立在达尔文的生物进化论和孟德尔的遗传学说基础上的算法。 基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选 择，适应值高的基因结构就保存下来。遗传算法就是模仿了生物的遗传、进化原 理，并引用了随机统计原理而形成的。1.1遗传算法的产生和发展50年代末60年代初，生物学家Fraser试图通过计算的方法来模拟生物 界遗传与选择的进化过程，这便是GA的雏形。受此启发，Holland教授认识 到自然遗传可以转化为人工遗传算法。1967年Bagley在其博士论文中首次提 出了遗传算

3、法这一术语。1975年，Holland出版了自然与人工系统中的适 应性行为。该书系统地阐述了遗传算法的基本理论和方法，提出了遗传算法的 基本定理-模式定理，从而奠定了遗传算法的理论基础。20世纪80年代初， Holland教授实现了第一个基于遗传算法的机器学习系统一分类器系统 (Classifier System简称CS)，开创了基于遗传算法的机器学习的新概念。l992 年，JohnR. Koza出版了专著遗传编程，提出了遗传编程的概念，并成功地 把遗传编程的方法应用于人工智能、机器学习、符号处理等方面。随着遗传算法 的不断发展，关于遗传算法的国际学术活动越来越多，遗传算法已成为一个多 学科、

4、多领域的重要研究方向。国外遗传算法的发展现状1991年DWhitey在他的论文中提出了基于领域交叉的交叉算子，这个算子 是特别针对用序号表示基因的个体的交叉，并将其应用到了 TSP问题中，通过实 验对其进行了验证。D.H.Ackley等提出了随即迭代遗传爬山法采用了一种复杂的概率选举 机制，此机制中由m个“投票者”来共同决定新个体的值(m表示群体的大小)。 实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六 个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在 求解速度方面更有竞争力。H.Bersini和G.Seront将遗传算法与单一方法结合起来，形

5、成了一种叫 单一操作的多亲交叉算子，该算子在根据两个母体以及一个额外的个体产生新个 体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献 还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其 余两个有更好的性能。国内遗传算法的发展现状2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同 的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁 移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效 率不高的现象，提出了一种用基因块编码的并行遗传算法。该

6、方法以粗粒度并行 遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为 新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色 体群体作为下一轮以相同方式演化的初始群体。2005年，江雷等针对并行遗传算法求解TSP问题，探讨了使用弹性策略 来维持群体的多样性，使得算法跨过局部收敛的障碍，向全局最优解方向进化。1.2遗传算法的基本求解步骤1.2.1编码：确定用何种码制，然后将问题参数编码形成基因码链，每一个码链代表一个 个体，表示优化问题的一个解。1.2.2初始化：随机产生一个规模为P的初始种群，其中每个个体为一定长度的码链，该群体代表优化问题的一些可能解的集合

7、。1.2.3估计适应度：计算种群中每个个体的适应度，适应度为群体进化时的选择提供了依据。一 般来说适应度越高，解的素质越好。适应度函数可以根据目标函数而定。1.2.4再生（选择）：根据每个个体的相对适应度，计算每个个体的再生次数，并进行再生操作， 产生新的个体加人下一代群体中，一般再生的概率与其适应度成正比。1.2.5交叉：从种群中随机选择两个染色体，按一定的概率进行基因交换，交换位置的选 取是随机的。1.2.6变异：从种群中随机地选择一个染色体，按一定的变异概率P进行基因变异,GA的 搜索能力主要是由选择与交叉赋于的，变异算子则保证了算法能搜索到问题空 间的每一点，从而使算法具有全局最优性，

8、它进一步增强7GA的能力.1.2.7重复：若发现最优解，则算法停止，否则转3 ,对产生的新一代群体进行重新评 价、选择、交叉、变异操作，如此循环往复，使群体中最优个体的适应度和平均 适应度不断提高。其流程图如下：编码,生成初始种群计算与评价种群中个体适应度物;选择交叉变异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的初始种群，本例中假 定初

9、始种群取为4个二进制串，x1=01100,x2=11001,x3=01000,x4=10010。以上5 位字串称为染色体，每个分量称为基因，每个基因有两种状态0或者1。2.3计算适应度计算种群中每个个体的适应度，本题中，适应度函数可定为： fitnes(x)=f(x)= %2，于是Fitness(x1)=144，Fitness(x2) =625,Fitness(x3)=64,Fitness(x4)二4002.4再生(选择)初始种群中每个个体入选种群的概率为：p(xi)=fitness(xi)/E ifitness(xi).利用上述概率，对这四个整数进行四次有放回的随机抽取，产 生四个新的整数，

10、显然概率大的有更多的机会被抽中，四个新的整数气=01100, % =11001，% =11001，% =10010.经前四步后，具体情况如表下所示：234序号初始种群X值适应度人选种群概率期望复制数实际复制数1011001214412%0.4812110012562551%2.0423010008645%0.204100102040032%1.281合计1233100%44平均308.325%112.5交叉将土(i=1，2, 3, 4)随机结合成两组，每组两个数；对每组再进行一次 随机抽样，以等概率从1，2, 3, 4中选取一个数n.假设在上述例子中恰%； =01100， % =11001分为

11、一组，随机抽取n=3，那么将由二进制表示的%，% 从后三位开始212互换，得到两个新的二进制整数，记为气，七。同样对另外一组数作类似处理， 假设另一组抽得n=2,这样得到四个新的整数，结果为=01001， = 11100， = 11010，x=10001.具体情况如表所示:序号复制后种群复制对象交叉点n交叉后种群X值适应度1011002301001981211001131110028784311001422110102248441001031000117289合计1638平均409.52.6变异将交叉得到的四个二进制数，每个数每个二进位进行一次随机抽样，以一个 小概率P,例如1、1000将该位

12、取反，即由1变为1，由1变为0，以概率1-P保持该位 数字不变。这样得到四个新的数记为xn+1（1 = 1，2, 3, 4），计算其函数值f（ xn+1 ）, 回到步骤（4）。对产生的新一代群体进行重新计算适应度、选择、交叉、变异操 作，如此循环往复，使群体中最优个体的适应度和平均适应度不断提高。变异可 保持群体的多样性，可使遗传算法跳出局部极值点。以上的简单例子，从开始随机产生的种群到经过一次再生、交叉、变异操作 后的新种群中，我们不难看出初始种群的平均适应度为303.8,新种群的平均适 应度为409.5,最大值从初始种群的625增加到新种群的784。可见经过一次遗传 算法的操作后，问题的解

13、向最优解的方向前进了一大步。因此经过以上多次类似 计算，问题的解最终会接近最优解。当然在应用遗传算法时，可以事先规定一个 最大允许循环次数，以使计算得到终结，而以计算过程达到的最大函数值的xn 作为所要的解，遗传算法实际上是一种搜索方式，对那些标准数学方法难以奏效的问题给出了一种处理办法。3遗传算法解决TSP的例子旅行商问题(TSP),也称为货郎担问题，是一个较古老的问题。最早可以 追溯到1759年Euler提出的骑士旅行问题。1948年，由美国兰德公司推动，TSP 成为近代组合优化领域的一个典型难题。应该说，TSP是一个具有广泛应用背景 和重要理论价值的组合优化难题，它已经被证明属于NP难题

14、。对TSP问题的大 量研究使得TSP问题成为了一个著名的组合优化问题目前，求解TSP问题的较为 常用的方法有二叉树描述法、启发式搜索法、最近邻法、神经网络法、模拟退火 法和遗传算法等。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的 一种自适应全局概率搜索算法，具有良好的全局寻优能力，成为解决问题的有效 方法之一。3.1 TSP问题描述TSP (旅行商问题)的简单描述是：一名商人欲到n个城市推销商品，每两 个城市i和j之间的距离为d，存在i，j如何使商人每个城市走一遍后回到起点， 且所走的路径最短。用数学符号表示为：设n维向量表示一条路径X=(C1, C2,Cn)，目标函数为minF(x

15、)= 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的增加而增大，所有的旅程路线组合数为(n-1)! /2。5个城市的情 形对应120/10=12条路线，10个城市的情形3628800/20=181440条路线，100个 城市的情形则对应有4.6663 X 10155条路线。在次庞大的搜索空间中寻求最优解， 对于常规方法和现有的搜索而言，存在诸多的计算困难。借助遗传算法的搜索能 力解决TSP问题是很自然的想法。3.2遗传算法用于TSP问题3.2.1编码表示用遗传算法求解TSP时，算法的编码