智能控制基础：6遗传算法

遗传算法第四章遗传算法 遗传算法简介4.14.10 基本遗传算法4.2 遗传算法的数学理论基础4.3 遗传算法的应用4.46.1遗传算法简介6.1.1遗传算法的产生与发展产生1967年，Holland的学生J.D.Bagley在博士论文中首次提出“遗传算法(Genetic

Algorithms)”一词；1968年，Holland提出了“模式定理（SchemaTheorem）”，一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，标志遗传算法的诞生；6.1遗传算法简介6.1.1遗传算法的产生与发展发展1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会(ISGA，InternationalSocietyofGeneticAlgorithms)；1989年，Holland的学生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”，对遗传算法及其应用作了全面而系统的论述；1992年，Michalewicz出版了很有影响力的著作《Geneticalgorithms+DataStructures=EvolutionPrograms》；1997年，《IEEETransactionsonEvolutionaryComputation》创刊，做为具有系统优化、适应和学习的高性能计算和建模方法，遗传算法研究逐渐成熟。6.1遗传算法简介6.1.2

生物遗传学的基本知识遗传（heredity）：亲体系把生物信息交给子代，子代按照所得信息而发育、分化，因而子代和父代具有相同或相似的性状，保证物种的稳定性；变异（variation）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；选择是指具有精选的能力，它决定生物进化的方向。遗传因子（gene）：DNA或RNA长链结构中占有一定位置的基本遗传单位，也称为基因；种瓜得瓜，种豆得豆适者生存，优胜劣汰6.1遗传算法简介6.1.3遗传算法的思路与特点遗传算法的思路6.1遗传算法简介6.1.3遗传算法的思路与特点遗传算法的特点是对参数的编码进行操作，而非对参数本身。特别是对一些无数值概念或者很难有数值概念而只有代码概念的优化问题，编码处理方式更显示出独特的优越性；是从许多点开始并行操作，而非局限于一点；通过目标函数来计算适应度，从而对问题依赖小；寻优规则是由概率决定的，而非确定性的；6.1遗传算法简介6.1.3遗传算法的思路与特点遗传算法的特点是在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索；对寻优的函数基本无限制；具有并行计算的特点，因而可通过大规模并行计算来提高计算速度；更适合大规模复杂问题的优化；计算简单，功能强。6.1遗传算法简介6.1.4遗传算法的基本操作选择交叉或基因重组变异选择是用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。基因重组是结合来自父代交配种群中的信息产生新的个体。交叉之后子代经历的变异，实际上是子代基因按小概率扰动产生的变化6.1遗传算法简介6.1.4遗传算法的基本操作简单实例产生初始种群计算适应度0001100000010111100100000001011001110100101010101011100101101001011011110000000110011101000001010011（8）（5）（2）（10）（7）（12）（5）（19）（10）（14）6.1遗传算法简介6.1.4遗传算法的基本操作简单实例选择个体染色体适应度选择概率累积概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488＋5＋2＋10＋7＋12＋5＋19＋10＋140.08695758＋5＋2＋10＋7＋12＋5＋19＋10＋140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521746.1遗传算法简介6.1.4遗传算法的基本操作简单实例选择个体染色体适应度选择概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000006.1遗传算法简介6.1.4遗传算法的基本操作简单实例选择个体染色体适应度选择概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000000.0702210.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641淘汰！淘汰！选择在0～1之间产生一个随机数：6.1遗传算法简介6.1.4遗传算法的基本操作简单实例交叉0001100000111001011011000000011001110100101010101011100101101001011011110000000110011101000001010011000110000011100101101100000001100111010010101010101110010110100101101110011101001100000001000101001100011110100000010110111100001011010110111100001001110100000110011101001100000001101010100010100100116.1遗传算法简介6.1.4遗传算法的基本操作简单实例变异00011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100110001111010000001011011110000101101011011110000100101010000011001110100110000000110101010001010010011000110000011100101101100000001100111010010101010101110010110100101101111000000011001110100000101001100011110100000010110111100001011010110111100001001110100000110011101001100000001101010100010100100116.1.4遗传算法的基本操作简单实例至下一代，适应度计算→选择→交叉→变异，直至满足终止条件6.1遗传算法简介6.2基本遗传算法6.2.1简单函数优化实例问题的提出一元函数求最大值：6.2基本遗传算法6.2.1简单函数优化实例问题的提出用微分法求取f(x)的最大值：解有无穷多个：6.2基本遗传算法6.2.1简单函数优化实例问题的提出当i为奇数时xi对应局部极大值点，i为偶数时xi对应局部极小值。x19即为区间[-1,2]内的最大值点：函数最大值f(x19)比f(1.85)=3.85稍大6.2基本遗传算法6.2.1简单函数优化实例编码表现型：x

作为实数，可以视为遗传算法的表现型形式基因型：二进制编码（串长取决于求解精度）串长与精度之间的关系：若要求求解精度到6位小数，区间长度为2-(-1)＝3，即需将区间分为3/0.000001=3×106等份。所以编码的二进制串长应为22位。6.2基本遗传算法6.2.1简单函数优化实例产生随机种群产生的方式：随机产生的结果：长度为22的二进制串产生的数量：种群的大小（规模）指种群中个体数目，如30，50…11110100111000010110001100110011101010101110……6.2.1简单函数优化实例计算适应度6.2基本遗传算法不同的问题有不同的适应度计算方法本例：直接用目标函数作为适应度函数①将某个体转化为[-1,2]区间的实数：

s=<1000101110110101000111>→x=0.637197②计算x的函数值（适应度）：

f(x)=xsin(10πx)+2.0=2.5863456.2.1简单函数优化实例计算适应度第一步，将一个二进制串（b21b20…b0）转化为10进制数：

第二步，x’对应的区间[-1,2]内的实数：6.2基本遗传算法二进制与十进制之间的转换：(0000000000000000000000)→-1(1111111111111111111111)→26.2基本遗传算法6.2.1简单函数优化实例遗传操作选择：轮盘赌选择法；交叉：单点交叉；变异：小概率变异模拟结果

设置的参数：种群大小50；交叉概率0.75；变异概率0.05；最大迭代数200。得到的最佳个体：

smax=<1111001100111011111100>;xmax=1.8506;f(xmax)=3.8503;6.2基本遗传算法6.2.1简单函数优化实例模拟结果进化的过程世代数自变量适应度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.85036.2基本遗传算法6.2.2编码编码方式二进制编码：

优点在于编码、解码操作简单，交叉、变异等遗传操作便于实现，而且便于利用模式定理进行理论分析等。

6.2基本遗传算法6.2.2编码编码方式二进制编码：

缺点在于不便于反映所求问题的特定知识，对于一些连续函数的优化问题等由于遗传算法的随机特性而使其局部搜索能力较差，对于一些高维、高精度的连续函数优化问题，二进制编码存在着连续函数离散化的映射误差，个体编码串较短时，可能达不到精度要求，而个体编码串的长度较长时，虽然能提高精度，但会使算法的搜索空间急剧扩大，会造成遗传算法的性能降低。6.2基本遗传算法6.2.2编码编码方式浮点数编码：指个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等于决策变量的个数。优点：适合于在遗传算法中表示范围较大的数适合于精度要求较高的遗传算法便于较大空间的遗传搜索改善了遗传算法的计算复杂性，提高了运算效率便于遗传算法与经典优化方法的混合使用便于设计针对问题的专门知识的知识型遗传算子便于处理复杂的决策变量约束条件6.2基本遗传算法6.2.3种群设定种群规模种群规模的确定受遗传操作中选择操作的影响很大，种群规模越大，种群中个体的多样性越高，算法陷入局解的危险就越小。从种群多样性出发，种群规模应比较大。种群规模太大会带来若干弊病：1、从计算效率着眼，种群越大，其适应度评估次数增加，计算量也增加，从而影响算法效能；2、种群中个体生存下来的概率大多采用和适应度成比例的方法。种群中个体非常多时，少量适应度很高的个体会被选择而生存下来，但大多数个体却被淘汰，这会影响配对库的形成，从而影响交叉操作。6.2基本遗传算法6.2.3种群设定种群规模规模太小会使遗传算法的搜索空间分布范围有限，因而搜索有可能停止在未成熟阶段，引起未成熟收敛现象。要避免未成熟收敛现象，必须保持种群的多样性，即种群规模不能太小。6.2基本遗传算法6.2.4适应度函数及其尺度变换适应度函数的重要性适应度函数的选取直接影响遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目标函数变换而成的，对目标函数值域的某种映射变换称为适应度的尺度变换（fitnessscaling）。6.2基本遗传算法6.2.4适应度函数及其尺度变换几种常见的适应度函数直接转换若目标函数为最大化问题：Fit(f(x))=f(x)

若目标函数为最小化问题：Fit(f(x))=-f(x)存在两个问题：1、可能不满足常用的轮盘赌选择中概率非负的要求；2、某些待求解的函数在函数值分布上相差很大，由此得到的平均适应度可能不利于体现种群的平均性能，影响算法的性能。6.2基本遗传算法6.2.3适应度函数及其尺度变换几种常见的适应度函数界限构造法若目标函数为最大化问题：若目标函数为最小化问题：6.2基本遗传算法6.2.3适应度函数及其尺度变换适应度函数的作用适应度函数设计不当有可能出现欺骗问题：（1）进化初期，个别超常个体控制选择过程，影响算法全局优化特性；（2）进化末期，个体差异太小导致进化缓慢，可能获得某个局部最优解。6.2基本遗传算法6.2.3适应度函数及其尺度变换适应度函数的线性变换法

f’=α

*f+β系数的确定满足以下条件：①f’avg=favg②f’max=cmultf’avg

cmult

=1.0~2.06.2基本遗传算法6.2.4遗传操作——选择个体选择概率的常用分配方法按比例的适应度分配某个体i，其适应度为fi，则其被选取的概率Pi为：个体ff2P12.56.250.1821.01.000.0333.09.000.2641.21.440.0452.14.410.1360.80.640.0272.56.250.1881.31.690.0590.90.810.02101.83.240.096.2基本遗传算法6.2.4遗传操作——选择个体选择概率的常用分配方法基于排序的适应度分配适应值仅仅取决于个体在种群中的序位，而不是实际的目标值。排序方法克服了比例适应度计算的尺度问题，当选择压力太小的情况下，以及选择导致搜索带迅速变窄而产生的过早收敛。6.2基本遗传算法6.2.4遗传操作——选择常用选择方法轮盘赌选择法个体1234567891011适应度2.01.81.61.41.21.00.80.60.40.20.1选择概率0.180.160.150.130.110.090.070.060.030.020.0累计概率0.180.340.490.620.730.820.890.950.981.001.000.810.320.966.2基本遗传算法6.2.4遗传操作——选择常用选择方法最佳个体保存法（elitistmodel）该方法的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中。优点：某进化过程中某一代的最优解可不被交叉和变异操作所破坏缺点：局部最优个体的遗传基因会急速增加而使进化有可能限于局部解，也就是全局搜索能力差，更适合单峰性质的搜索空间搜索，而不是多峰性质的空间搜索，一般与其他选择方法配合使用6.2.4遗传操作——选择常用选择方法截断选择法锦标赛选择法6.2基本遗传算法个体按适应度排列，只有优秀个体能够成为父个体，参数为截断阀值（被选作父个体的百分比）。随机从种群中挑选一定数目个体，其中最好的个体作为父个体，此过程重复进行完成个体的选择。6.2基本遗传算法6.2.4遗传操作——交叉/基因重组单点交叉多点交叉偶数点交叉6.2基本遗传算法6.2.4遗传操作——交叉/基因重组二进制交叉均匀交叉6.2基本遗传算法6.2.4遗传操作——变异二进制变异对种群中基因链码随机挑选c个基因位置并对其对应的基因值以变异概率取反。6.3遗传算法的理论基础6.3.1

模式理论模式在二进制编码的串中，模式是基于三个字符集（0，1，*）的字符串，符号*代表任意字符，即0或1。如模式*1*描述了一个四个元的子集{010，011，110，111}。将种群中的个体即基因串中的相似样板称为模式，模式表示基因串中某些特征位相同的结构，因此模式可以解释为相同的构形6.3遗传算法的理论基础6.3.1

模式理论模式模式阶模式H中确定性位置的个数称为模式H的模式阶，记作O(H)，如O(011*1*)=4。

模式阶用来反映不同模式间确定性的差异，模式阶越高，模式的确定性就越高，所匹配的样本个数就越少。6.3遗传算法的理论基础6.3.1

模式理论定义距模式H中第一个确定位置和最后一个确定位置之间的距离称为模式的定义距，记作δ(H)，如δ(011*1**)=4。阶数相同的模式会有不同的性质，定义距就反映了这种性质的差异。6.3遗传算法的理论基础6.3.1

模式理论模式定理（复制对模式的影响）在给定时间步t,一个特定模式H有

m个代表串包含在种群A(t)中，记为m=m(H,t)，每个串根据它的适应值进行选择和复制，一个串Ai

选择概率为6.3遗传算法的理论基础6.3.1

模式理论模式定理（复制对模式的影响）当采用非重叠的n

个串的种群替代种群A(t)，可以得到：其中f(H)是在时间t

表示模式H

的串的平均适应度。这表明，一个特定的模式按照其平均适应度值与种群的平均适应度值之间的比率生长。一个代表串被选择复制的数量6.3遗传算法的理论基础6.3.1模式理论模式定理（复制对模式的影响）假设从t=0开始，某一特定模式适应度值保持在种群平均适应度以上一个cf（c为一常数），则模式的选择生长方程为上式表明，在种群平均值以上(以下)的模式将按指数增长(衰减)的方式被复制。在一定程度上这种复制算子在种群中并行地采样，许多不同的模式按照相同的规则增长或衰减。仅靠复制过程无助于检测搜索空间中新的区域，因而需要采取交叉操作6.3遗传算法的理论基础6.3.1模式理论模式定理（交叉对模式的影响）考虑交叉操作，模式H

被破坏的概率为δ(H)/(l-1)，模式H

生存概率为1-δ(H)/(l-1)，若交叉操作发生的概率为pc，因此对于模式H

的生存概率计算为：同时考虑选择、交叉操作对模式的影响，可得子代模式的估计：A=0111000H1=*1****0H2=***10**该式表明，模式增长或衰减依赖于两个因素．一个因素是模式的适应值是在平均适应值之上还是在平均适应值之下，另一个因素是模式具有相对长还是相对短的定义距。那些既在种群平均适应度值之上同时又