智能控制-遗传算法

1、第四章第四章 遗传算法遗传算法 遗传算法 遗传算法（genetic algorithms）是在70年代初期由美国执根（Michigan）大学的Holland教授发展起来的。1975年， Holland发表了第一本比较系统论述遗传算法的专著Adptation in Natural and Artificial Systems.本章先介绍遗传算法及一些基本性质，然后讨论遗传算法实现的技术问题，最后通过在约束批量模型的应用了解算法实现过程。v4.1遗传算法 遗传算法的特征 遗传算法 遗传算法有待研究的主要因素 遗传算法优越性与不足v4.2模板理论 从模板理论的角度说明遗传算法的收敛性 针对遗传算法的

2、三个算子独立考虑模板的变化给出三个引理 模板定理4.1遗传算法v生物进化的基本过程群体变异子群竞争婚配种群淘汰的群体遗传算法主要借鉴了生物的一些特征，其主要特征体现为：v进化发生在解的编码上。这些编码按生物学的术语称为染色体。由于对解进行了编码，优化问题的一切性质都通过编码来研究。编码和解码是遗传算法的一个主题。v自然选择规律决定哪些染色体产生超过平均数的后代。遗传算法中，通过优化问题的目标而人为地构造适应函数以达到好的染色体产生超过平均数的后代。v当染色体结合时，双亲的遗传基因的结合使得子女保持父母的特征。v当染色体结合后，随机的变异会造成子代同父代的不同。遗传算法包含以下的主要处理步骤：v

3、对优化问题的解进行编码，此处，我们称一个解的编码为一个染色体，组成编码的元素称为基因。编码的目的主要是用于优化问题解的表现形式和利于之后遗传算法中的计算。v适应函数的构造和应用。适应函数基本上依据优化问题的目标函数而定。当适应函数确定以后，自然选择规律是以适应函数值的大小决定的概率分布来确定哪些染色体适应生存，哪些被淘汰。生存下来的染色体组成种群，形成一个可以繁衍下一代的群体。v染色体的结合。双亲的遗传基因结合是通过编码之间的交配达到下一代的产生。新一代的产生是一个生殖过程，它产生了一个新解。最后是变异。新解产生的过程中可能发生基因变异，变异使某些解的编码发生变化，使解有更大的遍历性。生物遗传

4、概念在遗传算法中的对应关系 生物遗传概念 遗传算法中的作用 适者生存 在算法停止时，最优目标值的解有最大的可能被留住 个体（individual） 解 染色体(chromosome) 解的编码（字符串，向量等） 基因(gene) 解中每一分量的特征（如各分量的值） 适应性(fitness) 适应函数值 群体(population) 选定的一组解（其中解的个数为群体的规模） 种群(reproduction) 根据适应函数值选取的一组解 交配(crossover) 通过交配原则产生一组新解的过程 变异（mutation） 编码的某一个分量发生变化的过程 最优化问题的求解过程是从众多的解中选出最优的

5、解，生物进化的适者生存的规律使得最具有生存能力的染色体以最大的可能生存。这样的共同点使得遗传算法可以在优化问题中应用。例4.1 用遗传算法求解 为整数的最大值。 xxxxf,310 ,)(2 一个简单的表示解的编码是二进制编码，即0，1字符串。由于变量的最大值是31，因此可以采用5位数的二进制码。如：10000 16 11111 31 01001 9 00010 2以上的5个字符串成为染色体，每一个分量称为基因，每个基因有两种状态0或1。 模拟生物进化，首先要产生一个群体，可以随机取4个染色体组成一个群体，)01000(, )01111(, )11001(, )00000(4321xxxx群体

6、有4个个体，适应函数可以依据目标函数而定，如适应函数2)()(xxfxfitness于是 2225)(xfitness0)(1xfitness2315)(xfitness248)(xfitness定义第i个个体入选种群的概率为jjiixfitnessxfitnessxp)()()(于是，适应函数值大的染色体个体的生存概率自然较大，若群体中4个个体成为种群则极有可能竞争上的是)01000(, )01111(, )11001(, )11001(4322xxxx若他们结合，采用如下的交配方式称为简单交配)000|01()001|11()111|01()001|11(4232xxxx)001|01()

7、000|11()001|01()111|11(4321yyyy即交换第二个位置以后的基因，得到 和 。若 的第一个基因发生变异，则变成 。321,yyy4y4y)11001(4ySTEP1 选择问题的一个编码；给出一个有N个染色体的初始群体pop(1),t:=1STEP3 若停止规则满足，则算法停止；否则，计算概率并以此概率分布从pop（t）中随机选一些染色体构成一个种群 newpop(t+1)=popj(t)|j=1,2, N ；【注】 newpop(t+1)集中可能重复pop（t）中的一个元素，如例4.1中的 就选取两次。STEP4 通过交配，交配概率为Pc，得到一个有N个染色体的cors

8、spop(t+1);STEP5 以一个较小的概率p，使得一个染色体的一个基因发生变异，形成 mutpop(t+1);t:=t+1,一个新的群体pop(t)= mutpop(t);返回STEP2。STEP2 对群体pop(t)中的每一个染色体popi(t)计算它的适应函数 )(tpopfitnessfii遗传算法NiffpNjiii,2,1,1(4.1)例4.2 用遗传算法求. 1 , 0,1)(max2xxxf 由于对连续变量求解，要解决的一个问题是如何编码。假设对解的误差要求是1/16，则可以采用4位二进制编码。对应关系为16842)(dcbaabcd表4.2 遗传算法中的一步计算X值 旧群

9、体 适应函 概率 new 交配位 cross 是否 mut x值 pop(t) 数值f 分布p pop pop 变异 pop1/16 0001 0.996 0.318 0001 00|01 0000 N 0000 0 1/4 0100 0.938 0.299 0100 01|00 0101 Y 1101 13/163/16 0011 0.965 0.308 0001 000|1 0001 N 0001 1/16 7/8 1110 0.234 0.075 0011 001|1 0011 N 0011 3/16 平均值=0.7833，交配概率p=1，变异概率pm=0.02简单遗传算法可以理解为：v

10、求解的问题是极大目标函数的优化问题；v采用01二进制编码；vpop（t）中的染色体个数是一个常数；v初始群体随机选取v适应函数为目标函数；v按轮盘赌方法选取染色体个数同pop（t）相同的种群；v常规交配方法：一对染色体按随机位交换后的基因；v染色体中的每一个基因都以相同的概率变异。有待研究的主要因素有待研究的主要因素v解的编码和解码。v初始群体的选取和计算中群体的大小。v适应函数的确定。v三个算子。遗传算法的三个算子是：种群选取、交配和变异或称突变。遗传算法的优越性可以简单地归结为遗传算法的优越性可以简单地归结为v遗传算法适合数值求解那些多参数、多变量、多目标和在多区域但连通性较差的NPhar

11、d优化问题。v遗传算法在求解很多组合优化问题时，不需要有很强的技巧和对问题有非常深入的了解。v遗传算法同求解问题的其他启发式算法有较好的兼容性。遗传算法的不足遗传算法的不足（1）编码不规范及编码存在表示的不准确性。（2）单一的遗传算法编码不能全面地将优化问题的约束表示出来。（3）是否能保证收敛到最优解4.2模板理论简单遗传算法的主要特征有：v群体和种群的维数相等，且不随代数的变化而变化；v适应函数直接选用目标函数；v种群中的个体通过轮盘赌的方式选取；v种群中的一对个体采用随机交配位的方式产生一对子代；v每一个基因有相同的变异概率。v染色体称为向量v一个给定的向量结构，包括关心的分量位置和值，称

12、为该向量的一个模板。 如1010001和1111010 110表示基因不同或我们不关心这个位置的取值， 称H= 110为一个模板v0，1的位置称为模板位置，位置称为非模板位置。v模板长度：从第一个模板位置到最后一个模板位置的所有分量个数减1。 如H= 110的长度为4，记为 。)(Hv模板的阶数：模板位置对应的确定分量个数。如H= 110的阶数为3，记为 。)(H若染色体Y在H的模板位置上对应的分量相同，则称Y具有H模板。记G（t）是第t代群体，即第t代染色体集合)2 . 4(, | )()(,(HYtGYtGHT具有模板其中t称为遗传的第t代。T（H,G（t）为模板H所包含的G（t）中的所有

13、染色体集合。 引理4.1 在生殖过程中，若每一个个体被选入种群newpop(t+1)的概率为（4.1），且种群的规模与群体相同，则模板H所包含的染色体在t+1时刻的期望数为)3 . 4(, ),(),() 1,(1tHNtHftHE其中N(H,t)为t时刻T(H,pop(t)所包含的染色体数，)4.4()()()(,()(),()(:)(,(:tpopYYtpopHTYYtpopYfitnesstpopHTYfitnesstHf证明证明 H模板的每一个染色体被选中的平均概率为)(,(:)(,()(tpopHTYYtpopHTYfitness而群体中每一个个体被选的平均概率为)(:)()(tpo

14、pYYtpopYfitness所以，（4.3）成立。 引理4.2 若在t时刻，模板H的长度为 ，采用简单交配方法，即随机选一个交配位，交换位后基因，交配的概率是 ，则在t+1时刻模板H保留下来的概率为)(Hcp)5 . 4(),(1 (1)(1) 1,(tHpnHptHpci其中，p（H，t）表示t时刻模板H出现的概率。证明证明 模板H发生变化的可能是由交配产生的。由于采用交配位后的基因交换，因此选择第一个模板位到最后一个模板位中的任何一个位置为交配位都可能产生模板变化，所以，模板发生改变的最大概率是 。假设交配的双方有相同的模板，则交配后模板不变。一方不具有同H相同的概率为 。于是使模板H改

15、变的最大概率为1)(nHpc),(1tHp,),(1(1)(tHpnHpc在交配的过程中，会出现交配的双方不具有H模板，但交配后却具有H模板，故有.),(1(1)(1)1,(1tHpnHptHpc 引理4.3 假设模板H在t时刻存在的概率为p(H,t)，经过简单变异，则有)6.4(,)(1)1,(2HptHpm其中， 为每个基因变异概率， 为H的阶 mp)(H 定理4.1 （模板定理）假设群体在t时刻有相同模板H的染色体个数为N(H,t),经过满足引理4.1的种群选取、满足引理4.2的以概率 的交配和满足引理4.3以概率 的变异，则在t+1时刻，群体中具有H模板的染色体数的期望值为cpmp)7

16、 . 4(),(),()(),(1 (1)(1) 1,(tHNtHfHptHpnHptHEmc如果)8 . 4(,)(),(1 (1)(1),(1HptHpnHptHfmc则从概率意义来说，每代中具有H模板的染色体个数将随代数t的增加而增加。 证明证明 遗传算法每一代的遗传由种群选取、交配和变异三个算子组成。三个事件的综合效果，使新一代群体中具有模板H的染色体数的期望值由引理4.1、引理4.2和引理4.3得到112(,1)(,1)(,1)(,1)()1(1(, )11() (, )(, )()1(1(, )1() (, )(, ).cmcmE H tE H tp H tp H tpHp H t

17、npHf H t N H tpHp H tnpHf H t N H t例4.4 用遗传算法求解 。观察模板 ， 和 的变化情况。2310max xzxx为整数11H 102H013H表4.3 遗传算法第一步数值结果No. 群体 x 适应函数f(x) 概率分布 随机模拟 选取出现次数414)()(iifif 1 01101 13 169 0.14 0.58 1 2 11000 24 576 0.49 1.97 2 3 01000 8 64 0.06 0.22 0 4 10011 19 361 0.31 1.23 1合计 1170 1.00 4.00 4.0 平均 293 0.25 1.00 1.

18、0最大 576 0.49 1.97 2.020. 32293469),(),() 1,(1111tHNtHftHE种群中具有H1模板的染色体期望值为97. 1) 1,(,18. 2) 1,(3121tHEtHE模板特性（生殖前）模板 群体 具有同模 板染色体H1 1 2，4 469 1.6H2 1 0 2，3 320 1.09H3 1 0 2 576 1.97),(),()(tHTitHTif)(),()()(),()(tpopitHTitpopiftHTif表4.4（a） 遗传算法第二步数值结果 种群体 匹配（随机选） 交配位（随机选） 新群体 x值 f(x) 0110|1 2 4 01100 12 144 1100|0 1 4 11001 25 625 11|000 4 2 11011 27 729 10|011 3 2 10000 16 256 合计 1754 平均 439 最大 729表4.4（b） 模板特性（种群）模板 理论期望数