智能控制理论讲稿,第4章,遗传算法

《智能控制理论讲稿,第4章,遗传算法》由会员分享，可在线阅读，更多相关《智能控制理论讲稿,第4章,遗传算法（20页珍藏版）》请在金锄头文库上搜索。

1、第四章 遗传算法遗传算法 （ Genetic Aegorithwrs,GA） 是一种基于自然选择和基因遗传学原理的优化搜索方法，在其创立过程中，有两个研究目的：1 抽象和严谨地解释自然界的适应过程；2 将自然生物总结的重要机理运用到工程系统、计算机系统及人工系统的设计中。该方法具有全局导优能力，应用十分广泛。一 遗传算法的概念遗传算法是美国密执安大学 John.H.Holland 教授根据生物进化模型而提出的一种优化算法。 自然选择学说是进化论的中心内容。 据此，生物发展进化主要有三个原因：遗传、变异和选择。1. 遗传：是指子代总是和亲代相似，遗传性是一切生物所共同的特性，它使得生物将其特性、

2、性状传给后代。遗传是生物进化的基础2. 变异：是指子代和亲代有某些不相似的地方，即子代永远不会和亲代完全一样，它也是一切生物所具有的共同特性，是生物个体之间相互区别的基础。引起便宜的主要原因是生活环境的影响、器官的使用的不同及杂交。生物的变异性为生物进化和发展创造条件。3. 选择：是指具有精选的能力，它决定生物进化的方向，在进化过程中，有的要保留、有饿要被淘汰，自然选择是指生物在自然界中（生存环境） ，适者生存、不适者被淘汰的过程。通过不断地自然选择，有利于生存的变异就会遗传下去，逐步积累，是变异越来越大，逐步产生新的生物种。具体地说，选择是通过遗传和变异起作用的， 即变异为选择提供资料， 遗

3、传巩固和积累了选择的资料。 而选择则能控制变异和遗传的方向， 使变异和遗传朝着适应环境的方向发展。这样，生物就在遗传、变异、选择三者的结合作用下，从简单到复杂、从低级到高级不断向前发展。进化论的自然选择过程蕴涵着一种搜索和优化的思想。遗传算法正是吸取了自然生物系统“适者生存，优胜劣汰”的进化原理，从而使它能够在一个复杂空间中进行鲁棒搜索， 为解决许多用传统方法难以解决的优化问题提供了新途径，新方法。二、遗传算法的特点遗传算法是基于自然选择和基因遗传学原理的搜索算法，它将生物进化原理引入待优化参数形成的编码串群体中， 按照一定的重配值函数及一系列遗传操作， 对每个个体进行筛选， 从而使适配值高的

4、个体被保留下来， 组成新的群体。 在新群体中包含了上一代的大量信息（遗传） ，以及新的优于上一代的个体（变异） 。这样周而复始，群体中的每个个体适应度不断提高，直至满足一定的极限条件，此时，群体中适配值最高的个体即为待优化参数的最优解。与常规优化解相比，如解析法、枚举法、动态规划法等，异端算法有如下特点：1. 字群体寻优， 不是从一点开始， 而是从许多点开始并行操作，因而可以防止搜索过程收敛于局部最优解， 即全局优化搜索。2. 遗传算法通过目标函数（适应函数）来计算适配值，即选择优秀种群，而不需要其它推导和附属信息，因而对问题的依赖性较小，求解的鲁棒性好。3. 遗传算法对待寻优的适应函数基本无

5、限制，即不要求连续，也不要求可微，即可以是函数（数学解析式） ， 也可以是隐函数（映射矩阵，神经网络系） ，因而应用广泛。4. 遗传算法在解空间进行高效启发式搜索，而非盲目穷举或随机搜索，只要“基因”位置选择恰当，遗传操作合适，其搜索效率很高。5. 遗传算法具有并行计算的特点，可以用大规模并行计算来提高计算速度，且计算简单，功能强。6. 遗传算法的寻优规则是由概率决定的，而非确定性的。7. 遗传算法更适合大规模交杂问题的优化求解。8. 遗传算法是对参数的编码群体进行操作，而非参数本身，因而很容易与多智能体（ Multi-Agent ）相对应，所易于解决智能网络求解问题。三、基本操作美国密执安大

6、学 Holland 教授的遗传算法，具有操作简单且作用强大，两个特点，它包含基本操作：1. 复制（ Reproduction）又称繁殖2. 交叉（ Crossover）3. 变异（ Mutation）遗传算法操作过程如下：生成初始种群计算每个个体的适应度 fi 最优解？Y N 输出最优解 选择高 fi 个体复制交换变异图 2-1 GA 的基本流程由图可知，先把待寻优的参数或变量（实际问题参数集）表示成“位串（染色体串） ” （ lndividual string ）以确定初始种群，一般用二进制码串表示，每位又称为“基因” （ gene） 。通过位串，可以得到一个 x 0 ， N。第 2 步：选

7、取目标函数或算适配值 f （ x） ，计算每个位串的适应度（ fitness ） 。第 3 步：是否收敛于最优解。第 4 步：进行复制，交换，变异操作，并重新计算适应度，直至找到最优解输出（迭代） 。例 1：寻找函数 f （ x） = -x 2 + 31x + 10 , 当 x 0 ， 31 为整数时的最大值。第一步：确定初始种群编码1. 编码的目的是将寻求优化解的参数用位串来表示，在本例中，x 在 0-31 之间变化，所以用 5 位二进制位串即可，即 00000 11111。2. 选择初始种群：一般种群参数要适中，太少了可能迭代次数要增加， 甚至得不到结果； 太多了会增加计算工作量， 降低效

8、率。这里选择种群个数为 4，并随机选取个体：串号 随机生成种群 X 值 F(x) fi / fi fi/fi( 平均 ) Ri 1 2 3 4 00001 11100 01000 10011 1 28 8 19 40 94 194 238 0.071 0.166 0.343 0.420 0.284 0.664 1.372 1.080 0 1 1 2 总计 566 1 4 平均值 141.5 0.25 1 最大值 238 0.42 1.68 表 3-1 ：复制操作前的各项准备第二步：计算适应度 fi 应该说决定适应度 fi 的计算公式是一个技巧性很高，而理论上的研究又很不充分的复杂问题。 一般要

9、根据优化的目标函数来决定 （较难选择） 。本例求解 f(x) = x2 + 31x +10 的最大值，所以目标函数即为此。见上表。同时可计算出复制概率 fi / fi 、期望复制数fi/fi( 平均 ) 。其中 fi （平均）是 fi 的平均值（期望值） 。见上表。表 3-1。第三步：复制根据适者生存理论， 越能适应环境的生物品种， 越能繁衍其后代。在这里，复制的原则是：适应度 fi 越高的位串，其复制的字字及复制的数量越多，根据 Ri（平均） = fi/fi （平均）知道，根据四舍五入原则，将 Ri（平均）圆整为整数 Ri，发现串 2、 3 被复制一次，串4 被复制 2 次，串 1 被淘汰。

10、见下表：新串号 复制种群 匹配 （随机） 交叉点 新种群 X fi(1) 1 2 3 4 11100 01000 10011 10011 4 3 2 1 3 2 2 3 11111 01011 10000 10000 31 11 16 16 10 230 250 250 表 3-2 复制操作后的各项数据第四步：交换（交叉）分两步： 1. 将新复制的位串随机两亮配对；2. 随机选择交叉点，对匹配的位串进行交叉繁殖，产生一对新的位串，具体操作过程如下：设位串长为 L，在 1， L-1 内，随机选择一个整数作为交叉点，将两个配对位串从位置 K 后的所有基因（二进制位码）进行交换。生成新种群。例如：串

11、 1 11100 K=3，交换得 11111 串 4 10011 10000 串 2 01000 K=2，交换得 01011 串 3 10011 10000 总计 740 平均值 185 最大值 250 并计算适应度 fi 。见表 3-2。第五步：变异尽管复制和交叉操作是第一位的，很重要，但不能保证不会遗漏一些重要的遗传信息。 可用变异来防止这种不可弥补的遗漏， 应注意的是，生物体中某一个或几个基因的变化，其概率是很小的，应在千分之几。所谓变异操作就是将位串中的某一位把 1 变成 0，或反之。例如：在本例中随机生成的种群如下：编号 位串 可以看到， 无论如何交叉， 位置 4 上都不可能出现 1

12、， 若优化的结果要求误差是 1， 仅用交叉操作是做不到的。1 2 3 4 01101 11001 00101 11100 虽然变异操作在遗传算法中的作用是第二位的，但却是必须的，以保证位串的多样性（物种基因多样性） ，可提高搜索效率。在本例中，选取变异的概率为千分之一，既 0.001，种群中共有 4串， 20 位，所以期望的变异位串位数为：20 0.001= 0.02 （位）故此例无变异情况。第六步：迭代经复制、交叉、变异操作后得到的新一代种群，对此再进行第二步操作计算适应度 fi ，按事先确定的评判规则来估计是否已得到最优解，其评判规则如下：方程(k+1) k (k+1) k k E(f i

13、 ,f i )= max( f i )-max( f i ) / max( f i ) f （平均）时， H的数量增加；反之减少。种群 A（ t ）中的任一模式 H在复制中都将上述规律变化， 这种模式的增减在复制中是并行进行的， 即遗传算法中隐含的并行机制就在于此。 上式即是复制操作对模式 H数量影响的定量描述。进一步分析模式数量的增减规律，可设：f （ H） - f （平均） = cf （平均） ， c 0 （常数）所以 m（ H， t+1） = m（ H， t ） （ 1+c）从原始种群开始（ t= 0 ） ，则有：m （ H， t+1 ） = m（ H， 0） （ 1+c）可见模式数量的

14、增减将呈指数形式。结论： 虽然复制过程能按适者生存的原则， 成功地以并行方式控制着模式数量以指数形式增减， 但由于复制只是将某些高适配度的个体全盘复制， 或淘汰某些低适配度的个体， 而决不会产生新的模式结构，因而对性能的改进是有限的。2. 交叉对模式的影响交叉是位串之间的有组织的而又是随机的信息交换， 它能创造新的模式结构， 但又能最低限度地破坏复制过程所选择的高适应度的模式。用一个例子来考查一下交叉过程中模式遭破坏或生存的情况 （即概率） ，以及交叉操作对模式的影响与什么量有关。例如：位串 A= 010110， L= 6 所包含的其中的两个模式：H1=*1*0 H2=*11* 由于交换（叉）

15、点的选择是等概率的。所以选 K=3，即：A= 010110 H1= *1*0 H2= *11* 由于 H1的确定位在分隔符两侧， 而 H2的确定位在分隔符一侧 （右边） ，所以，当 A与 A交叉时，除非 A的确定位与模式 H1的确定位相同，否则交叉后 H1将遭到破坏，即交叉后的下一代不可能是 H1的成员，或者说， 下一代中不能隐含 H1模式。而 H2的确定位均在交叉之列，不论 A为何串，都将传入下一代。例如： A = 101001 与 A交叉后的下一代位串： A1= 010001 A2= 101110 显然， A1， A2均不是 H1（被破坏了）的样本，但却是 H2（存活了）的样本。如果交叉的位置 K= 4， H2也可能遭到破坏，但由于交叉选择是等概率的，而：H1 在位置 2， 3， 4， 5 交叉都遭破坏；H2 在位置 4 交叉将遭破坏所以说 H1比 H2遭破坏的概率大多了， 即 H2的 “生命力” 强于 H1。显然，交叉操作对模式 H的影响取决 （ H） ，即（ H1） = 6-2 =4 （ H2） = 5-4 =1 而交叉点 L-1 = 6-1 =5 个可能位置上随机选取，所以 H1 被破坏的概率 Pd = （ H1） /L-1 = 4/5 H1 存活的概率 Ps =1 Pd = 1/5 类似地： H2 被破坏的概率