第9章遗传算法的实现技术.ppt
《第9章遗传算法的实现技术.ppt》由会员分享,可在线阅读,更多相关《第9章遗传算法的实现技术.ppt(49页珍藏版)》请在三一文库上搜索。
1、第9章 遗传算法的实现技术 80年代以后,遗传算法得到了广泛的使用,在实践过程中,人们对遗传算法的实施提出了许多改进。本节分别予以介绍。 9.1 编码方法 编码的重要性 编码是应用遗传算法时要解决的首要问题,也是设计遗传算法的一个关键步骤。 编码方法除了决定个体的染色体排列形式之外,它还决定了个体从搜索空间 的基因型变换到解空间的表现型时的解码方法; 编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。 由此可见,编码方法在很大程度上决定了如何进行群体的遗传进化运算以及 遗传进化运算的效率。,编码原则 针对一个具体应用问题,如何设计一种完美的编码方案一直是遗传算法的应 用难点之一,也是遗传
2、算法的一个重要研究方向。可以说目前还没有一套既严密 又完整的指导理论及评价准则能够帮助我们设计编码方案。作为参考,De Jong 曾提出了两条操作性较强的实用编码原则(又称为编码规则): 编码原则一(有意义积木块编码原则):应使用能易于产生与所求问题相关的且 具有低阶、短定义长度模式的编码方案。 编码原则二(最小字符集编码原则):应使用能使问题得到自然表示或描述的具 有最小编码字符集的编码方案。 由于遗传算法应用的广泛性,迄今为止人们已经提出了许多种不同的编码方法。 总的来说,这些编码方法可以分为三大类: 二进制编码方法 浮点数编码方法 符号编码方法,9.1.1 二进制编码方法 二进制编码方法
3、是遗传算法中最常用的一种编码方法,它使用的编码符号集 是由二进制符号0和1所组成的二值符号集0,1,它所构成的个体基因型是一个 二进制编码符号串。 (1) 编码 假设某一参数的取值范围是umax, umin,我们用长度为l的二进制编码符号串 来表示该参数,则它总共能够产生 2l种不同的编码,参数编码时的对应关系如 下: 00000000000000000 umin 00000000000000011 umin + 1111111111111111=2l1 umax 二进制编码的编码精度为:,(2) 解码 假设某一个体的编码是: x: bl bl-1 bl-2b2b1 则对应的解码公式为:,例如
4、,对于 x 0, 1023 ,若用 10 位长的二进制编码表示该参数的话, 则下述符号串: x:0010101111 就可表示一个个体, 它所对应的参数值是 x175。 编码精度为 = 1。,(3) 二进制编码方法的优点: . 编码、解码操作简单易行; . 交叉、变异等遗传操作便于实现; . 符合最小字符集编码原则(使用能使问题得到自然表示或描述的具有最小 编码字符集的编码方案。); . 便于利用模式定理对算法进行理论分析。,9.1.2 格雷码编码方法 格雷码编码方法是二进制编码方法的一种变形。 (1) 格雷码编码: 其连续的两个整数所对应的编码值之间仅仅只有一个码位是不相同的, 其余码位都完
5、全相同。如图所示。 (2) 优点: 便于提高遗传算法的局部搜索能力; 交叉、变异等遗传操作便于实现; 符合最小字符集编码原则; 便于利用模式定理对算法进行理论分析。,4,9.1.3 浮点数编码方法 (1) 二进制编码的缺点 二进制编码存在着连续函数离散化时的映射误差。 个体编码串的长度较短时,可能达不到精度要求; 个体编码串的长度较长时,虽然能提高编码精度,但却会使遗传算法的搜索 空间急剧扩大。 二进制编码不便于反映所求问题的特定知识,这样也就不便于开发针对问题专 门知识的遗传运算算子,人们在一些经典优化算法的研究中所总结出的一些 宝贵经验也就无法在这里加以利用,也不便于处理非平凡约束条件。
6、(2) 浮点数编码方法 个体的每个基因值用某一范围内的一个浮点数来表示; 个体的编码长度等于其决策变量的个数。 因为这种编码方法使用的是决策变量的真实值,所以浮点数编码方法也叫做 真值编码方法。,例如,如果一个优化问题含有5个变量xi(i1,2,5),每个变量都有其对应的上 下限Uimin , Uimax,则:,表示一个体的基因型, 其对应的表现型是:x: 5.80,6.90,3.50,3.80,5.00T。 (3) 注意事项: 在浮点数编码方法中: 必须保证基因值在给定的区间限制范围内;遗传算法中所使用的交叉、变异 等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限 制范围内
7、。 当用多个字节来表示一个基因值时,交叉运算必须在两个基因的分界字节处进 行,而不能在某个基因的中间字节分隔处进行。,(4) 浮点数编码方法的优点: 适合于在遗传算法中表示范围较大的数; 适合于精度要求较高的遗传算法; 便于较大空间的遗传搜索; 改善了遗传算法的计算复杂性,提高了运算效率; 便于遗传算法与经典优化方法的混合使用; 便于设计针对问题的专门知识的知识型遗传算子; 便于处理复杂的决策变量约束条件。,9.1.4 符号编码方法 (1) 编码方法 个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。 这个符号集可以是一个字母表,如 A, B, C, D, ; 也可以是一个
8、数宇序号表,如 1, 2, 3, 4, 5, ; 还可以是一个代码表,如 Al, A2, A3, A4, A5, 等等。 例如 :对于旅行商问题,假设有n个城市分别记为 C1, C2, , Cn ,将各个城市的 代号按其被访问的顺序连接在一起,就可构成一个表示旅行路线的个体,如: X: C1, C2, , Cn 若将各个城市按其代号的下标进行编号,则这个个体也可表示为: X:1,2, ,n 旅行商问题(Traveling Salesman Problem,简称TSP)可描述为; 已知n个城市之间的相互距离。现有一推销员必须遍访这n个城市,并且每个城市 只能访问一次,最后又必须返回出发城市。如何
9、安排他对这些城市的访问次序,可 使其旅行路线的总长度最短? ,(2) 符号编码的主要优点: 符合有意义积木块编码原则。 便于在遗传算法中利用所求解问题的专门知识。 便于遗传算法与相关近似算法之间的混合使用。 但对于使用符号编码方法的遗传算法,一般需要认真设计交叉、变异等遗传运 算的操作方法,以满足问题的各种约束要求,这样才能提高算法的搜索性能。 9.1.5 多参数级联编码方法 9.1.5 多参数交叉编码方法,9.2 适应度函数 在研究自然界生物的遗传和进化现象时,生物学家使用适应度这个术语来度量 某个物种对于其生存环境的适应程度。 与此相类似,遗传算法中也使用适应度这个概念来度量群体中各个个体
10、在优化 计算中有可能达到或接近于或有助于找到最优解的优良程度。 度量个体适应度的函数称为适应度函数。 9.2.1 目标函数与适应度函数 遗传算法的一个特点是它仅使用所求问题的目标函数值就可以得到下一步的 有关搜索信息。 最优化问题可分为两大类,一类为求目标函数的全局最大值,另一类为求目标函 数的全局最小值。对于这两类优化问题,第二章中已经介绍过由解空间中某一点的 目标函数值 f(x) 到搜索空间中对应个体的适应度函数值F(x)的转换方法: 对于求最大值的问题,作下述转换:, 对于求最小值问题,变换如下:,9.2.2 适应度尺度变换 (1) 适应度尺度变换的原因 在遗传算法中,各个个体被遗传到下
11、一代群体中的概率是由该个体的适应度来 确定的,应用实践表明,仅使用以上两式来计算个体适应度时,有些遗传算法 会收敛得很快,也有些遗传算法会收敛得很慢。 在遗传算法运行的初期阶段 群体中可能会有少数几个个体的适应度相对其他个体来说非常高。若按照常 用的比例选择算子来确定个体的遗传数量时,则这几个相对较好的个体将在下 一代群体中占有很高的比例,在极端情况下或当群体现模较小时,新的群体甚 至完全由这样的少数几个个体所组成。这时产生新个体作用较大的交叉算子就 起不了什么作用,因为相同的两个个体不论在何处进行交叉操作都永远不会产 生出新的个体,如下所示:,这样就会使群体的多样性降低,容易导致遗传算法发生
12、早熟现象(或称早期收 敛),使遗传算法所求到的解停留在某一局部最优点上。 因此,我们希望在遗传算法运行的初期阶段,算法能够对一些适应度较高的个 体进行控制,降低其适应度与其他个体适应度之间的差异程度,从而限制其复 制数量,以维护群体的多样性。 在遗传算法运行的后期阶段 群体中所有个体的平均适应度可能会接近于群体中最佳个体的适应度。也就 是说,大部分个体的适应度和最佳个体的适应度差异不大,它们之间无竞争力, 都会有以相接近的概率被遗传到下一代的可能性,从而使得进化过程无竞争性 可言,只是一种随机的选择过程。这将导致无法对某些重点区域进行重点搜索, 从而影响遗传算法的运行效率。 因此,我们希望在遗
13、传算法运行的后期阶段,算法能够对个体的适应度进行 适当的放大,扩大最佳个体适应度与其他个体适应度之间的差异程度,以提高 个体之间的竞争性。,(2) 适应度尺度变换定义 在遗传算法运行的不同阶段,有时需要对个体的适应度进行适当的扩大或缩小。 这种对个体适应度所做的扩大或缩小变换就称为适应度尺度变换。 (3) 适应度尺度变换方法 目前常用的个体适应度尺度变换方法主要有三种:线性尺度变换、乘幂尺度变 换和指数尺度变换。 . 线性尺度变换。 线性尺度变换的公式如下: F = aF + b 式中 F原适应度; F变换后的新适应度; a,b系数。 系数a,b直接影响到这个尺度变换的大小,所以对其选取有一定
14、的要求,一般 希望它们满足下面两个条件:,条件1:尺度变换后全部个体的新适应度的平均值 Favg 要等于其原适应度平均值Favg 即: Favg = Favg 这条要求是为了保证群体中适应度接近于平均适应度的个体能够有期待的数 量被遗传到下一代群体中。 条件2:尺度变换后群体中新的最大适应度 Fmax 要等于其原平均适应度 Favg 的指定 倍数。即: Fmax = CFavg 式中,C为最佳个体的期望复制数量,对于群体规模大小为50 100个个体的 情况,一般取 C = 1.2 2。 这条要求是为了保证群体中最好的个体能够期望复制C倍到新一代群体中。 如下图所示。,最小适应度为负时的处理:
15、在遗传算法执行的后期,个别劣质个体的适应度远远小于群体平均适应度及最 大适应度,并且后两者比较接近。这时按上述方法缩放适应度会使低适应度变成 负值,如图所示。这将会给后面的处理过程带来不便,必须避免这种情况的发生, 解决这个问题的方法是:把原最小适应度Fmin映射为Fmin= 0,并且保持原平均适 应度 Favg与新的平均适应度 Favg 相等。,综上所述,参数a, b的计算方法如下: (1) 计算适应度非负判别式:,若不等式满足,则执行(2), 否则执行(3)。 (2) 正常情况下的缩放:,(3) 负适应度时的缩放:,. 乘幂尺度变换 乘幂尺度变换的公式为: F = Fk 即新的适应度是原有
16、适应度的某个指定乘幂。幂指数k与所求解的问题有关, 并且在算法的执行过程中需要不断对其进行修正才能使尺度变换满足一定的伸 缩要求。 . 指数尺度变换 指数尺度变换的公式为: Fexp(-F) 即新的适应度是原有适应度的某个指数。式中系数决定了选择的强制性, 越小,原有适应度较高的个体的新适应度就越与其他个体的新适应度相差较 大,亦即越增加了选择该个体的强制性。,9.2.3 约束条件的处理方法 实际应用中的优化问题一般都含有一定的约束条件,它们的描述形式各种各样。 在遗传算法的应用中,必须对这些约束条件进行处理,而目前还未找到一种能够 处理各种约束条件的一般化方法。所以对约束条件进行处理时,只能
17、是针对具体 应用问题及约束条件的特征,再考虑遗传算法中遗传算子的运行能力,选用不同 的处理方法。 在构造遗传算法时,处理约束条件的常用方法主要有如下三种: 搜索空间限定法 罚函数法 可行解变换法 (1) 搜索空间限定法 基本思想 对遗传算法的搜索空间的大小加以限制,使得搜索空间中表示一个个体的点与解空间中表示一个可行解的点有一一对应的关系。此时的搜索空间与解空间的对应关系如图所示。,对一些比较简单的约束条件(如axb之类) 在个体染色体的编码方法上着手,就能够达到这种搜索空间与解空间之间的对 应的要求。 用这种处理方法能够在遗传算法中设置最小的搜索空间,所以它能够提高遗传 算法的搜索效率。 但
18、需要注意的是:除了在编码方法上想办法之外,也必须保证经过交叉、变异 等遗传其子作用之后所产生出的新个体在解空间中也要有确 定的对应解,而不会产生无效解。 处理方法 方法一:用编码方法来保证总是能够产生出在解空间中有对应可行解的染色体。 这个实现方法要求我们设计出一种比较好的个体编码方案。 如前面我们讲到的二进制编码方案即可实现上述要求。 方法二:用程序来保证直到产生出在解空间中有对应可行解的染色体之前,一 直进行交叉运算和变异运算。 虽然这个实现方法对编码方法的要求不高,但它有可能需要反复地进 行交叉运算和变异运算才能产生出一个满足约束条件的可行解,这样 就有可能会降低遗传算法的运行效率。,(
19、2) 罚函数法 基本思想 对在解空间中无对应可行解的个体,计算其适应度时,处以一个罚函数,从 而降低该个体适应度,使该个体被遗传到下一代群体中的机会减少。即用下式 来对个体的适应度进行调整:,式中,F(X)为原适应度; F(x)为考虑了罚函数之后的新适应度; P(x)为罚函数。 惩罚函数 设有优化问题的目标函数:,max F(x1,x2,xn) S.t. Hi(x1,x2,xn) i=1,2,m,max,式中 惩罚函数; 惩罚系数。 . 最简单的惩罚函数形式是平方法,即:,.也有人建议采用松紧法。在遗传算法初期,惩罚轻一些;到了后期,则惩 罚重一些。具体的新目标函数F为:,加入罚函数后,原来的
20、问题变为下述一个新的目标函数:,其中: K系数,可取 1/m; t当前的迭代代次; T终止迭代次数; 系数,1左右; f个体适应度的平均值; di违背约束i的程度,视问题的不同而定义。 难点 如何确定合理的罚函数是这种处理方法的难点之所在,因为这时既要考虑如 何度量解对约束条件不满足的程度,又要考虑遗传算法在计算效率上的要求。 罚函数的强度太小的话,部分个体仍有可能破坏约束条件,所以保证不了遗 传运算所得到的个体一定是满足约束条件的一个可行解; 罚函数的强度太大的话,又有可能使个体的适应度差异不大,降低了个体之 间的竞争力,从而影响遗传算法的运行效率。,(3) 可行解变换法 基本思想 在由个体
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法 实现 技术
链接地址:https://www.31doc.com/p-2968041.html