智能控制进化算法遗传算法

智能控制进化算法遗传算法1第一页，共五十页，编辑于2023年，星期三8.2.1遗传学习的基本思想8.2.2遗传学习算法的理论基础8.2.3遗传学习算法的改良8.2.4遗传学习算法的应用8.2遗传学习原理与算法2第二页，共五十页，编辑于2023年，星期三1.问题的提出美国的J.Holland教授于1975年提出在遗传学的基础上利用计算机来模拟生物的进化过程，从而实现复杂问题的优化求解。模拟生物染色体的运作（复制、交叉、变异），是一种随机化搜索算法3第三页，共五十页，编辑于2023年，星期三步骤4第四页，共五十页，编辑于2023年，星期三需要解决的问题编码机制；选择机制；控制参数选择；二进制字符串的群体构成；适应度函数的计算遗传算子（交叉、变异）的定义。5第五页，共五十页，编辑于2023年，星期三2.遗传学习算法的操作算子编码机制(Encodingmechanism)适应度函数(Fitnessfunction)选择机制(Selectionmechanism)交叉算子(Crossover)变异算子(Mutation)6第六页，共五十页，编辑于2023年，星期三(1)编码机制二进制编码每一个位（0或1）－基因字符串－染色体多值编码方法实数编码7第七页，共五十页，编辑于2023年，星期三(2)适应度函数优化问题的目标函数“适应度值”的计算直接通过将目标函数经一定的线性变换映射到的［0，1］区间内的一个值。8第八页，共五十页，编辑于2023年，星期三(3)选择机制基本思想取自于自然界进化论的“适者生存”。适应度值越高的个体，生存的数量也越高。满足“优胜劣汰”自然法则。也可称为复制机制比例选择法(Proportionateselectionscheme)转轮选择法(RouletteWheelSelectionScheme)：随机方法9第九页，共五十页，编辑于2023年，星期三(4)交叉算子模拟有性繁殖现象随机地从父辈集合中选取两个个体作为双亲。设L表示一个体的字符串（染色体）长度，随机地产生(0～L)之间的一个数d，并把此点位置称为交叉点。交叉运算就是将双亲的基因链在交叉点断裂，且将在交叉点之后的基因根据交叉率的条件决定是否进行相互交换形成下一代。所谓交叉率pc是根据优化问题预先确定的一个0～1之间的值。通常取0.6～0.9。10第十页，共五十页，编辑于2023年，星期三(5)变异算子模拟基因突变现象所谓变异指的是随机地选取染色体中的某个基因（也即字符串中的某一位）进行取反运算，即将原有的“1”变为“0”和反之。变异率pm取比较小的数值，一般pm为0.001～0.2。11第十一页，共五十页，编辑于2023年，星期三3.遗传学习算法的设计举例12第十二页，共五十页，编辑于2023年，星期三(1)群体初始化群体规模N 一般情况下取N=10～200之间为宜。初始群体的构成 随机选择13第十三页，共五十页，编辑于2023年，星期三举例群体P1（随机初始化）染色体适应度值00000111000.210000111110.601101010110.611111110110.914第十四页，共五十页，编辑于2023年，星期三以

的比例分配转轮(2)选择15第十五页，共五十页，编辑于2023年，星期三选择举例

群体P2（经选择后）染色体适应度值10000111110.601101010110.611111110110.911111110110.916第十六页，共五十页，编辑于2023年，星期三群体P3（交叉运算后）染色体适应度值10000｜110110.501101010110.611111110110.911111｜111111.0(3)交叉本例中随机选取1和4号个体、2和3号个体分别形成两对进行交叉运算。当取交叉率pc=0.5时，只有个体1和4这一对双亲进行真正的交叉运算，而另一对个体2和3不进行交叉运算。17第十七页，共五十页，编辑于2023年，星期三(4)变异取pm=0.05

P4给出了第2个个体和第4个个体中分别有一个基因发生变异后的情况。群体P4(变异运算后)染色体适应度值10000110110.501101110110.711111110110.901111111110.918第十八页，共五十页，编辑于2023年，星期三(5)终止准则判断方法有两类：19第十九页，共五十页，编辑于2023年，星期三8.2.1遗传学习的基本思想8.2.2遗传学习算法的理论基础8.2.3遗传学习算法的改良8.2.4遗传学习算法的应用8.2遗传学习原理与算法20第二十页，共五十页，编辑于2023年，星期三8.2.2理论基础有多种理论分析遗传算法的收敛性，例如Holland提出的模板理论(Schematheory)Goldberg提出的建筑块假设(Buildingblockhypothesis)。它们通过计算有用相似性，检查包含在群体中的各种模板的增长速率来表明遗传学习的能力。这里主要介绍模板定理21第二十一页，共五十页，编辑于2023年，星期三1.模板的基本概念模板表示那些在某些基因位置上具有相同性质、而在另一些位置上是不影响子集特征的染色体集合。例如：模板**000表示最后三个位置的值必须为“0”的一组染色体构成的子集。在二进制编码前提下，“*”可以是“0”、也可以是“1”。22第二十二页，共五十页，编辑于2023年，星期三模板的阶o(S)模板的阶o(S)模板的定义长度δ(S)模板中含有0或1的个数。如S=**111，则模板S的阶o(S)=3。模板中有确定值数码之间的最大距离。如：S=**111，则模板S的长度δ(S)=2。S=1*00*，则模板S的长度δ(S)=3。两个定义23第二十三页，共五十页，编辑于2023年，星期三2.模板定理假设一个L长的染色体。如果用二进制编码，则有2L个模板。对于有N个个体构成的群体总的模板数NS满足： 。NS的实际大小取决于群体中染色体的分散性。模板理论可以说明在进化计算中特定字符串在下一代中繁殖的情况。24第二十四页，共五十页，编辑于2023年，星期三（1）选择算子假设模板S在t时刻在群体中有n(S,t)个特定字符串（即同一字符串在群体中的占有数目）。由比例选择法可知

其中：

f(S):

模板S内所有子集的目标函数平均值； f(P):群体内的平均目标函数值.当f(S)>

f(P)时，该模板的数目会增加25第二十五页，共五十页，编辑于2023年，星期三（2）交叉算子交叉算子运算后，模板S中保留特定字符串的概率

选择、交叉算子运算后，在下一代中模板S的特定字符串数目满足：

具有较好的目标函数和较短定义长度的模板，其字符串的增长率最快。26第二十六页，共五十页，编辑于2023年，星期三（3）变异算子在变异运算后字符串仍然属于S模板的概率为

因为，变异率pm通常是非常小27第二十七页，共五十页，编辑于2023年，星期三定理8-1:模板定理

这一定理表明了随着遗传学习的进行，优秀品质的字符串个体在群体中占有的数目会越来越多，最终得到平均适应度高、定义长度短和阶次小的模板。这种模板又可称为建筑块。28第二十八页，共五十页，编辑于2023年，星期三8.2.1遗传学习的基本思想8.2.2遗传学习算法的理论基础8.2.3遗传学习算法的改良8.2.4遗传学习算法的应用8.2遗传学习原理与算法29第二十九页，共五十页，编辑于2023年，星期三8.2.3遗传学习算法的改良目前已经提出的改进方案有：编码机制——灰度编码和动态编码；选择机制——优选策略、基于次序的选择、稳定状态选择及随机余数法的比例选择；交叉机制——两点或多点交叉、均匀交叉；控制参数——动态自适应参数控制技术；算法策略——分布式遗传学习算法和并行遗传学习－算法。30第三十页，共五十页，编辑于2023年，星期三1.编码机制的改进灰度编码技术保证连续变量编码后的相邻Hamming距离为1。 0000080011110009101121100101111301001101114011012010151110131101610101410017001015000131第三十一页，共五十页，编辑于2023年，星期三2.选择机制的改进解决早熟问题。有两个途径：一是采用全量程适应度函数定标；二是采用改进的选择方案。32第三十二页，共五十页，编辑于2023年，星期三全量程适应度函数定标线性变换

计算的准则是希望换算后的适应度最大值应该是群体平均适应度值的某一小的倍数，通常取1.5或2。σ-截断法

其中：群体的平均适应度值；

σ：群体适应度的标准方差；

c

：一个小的常数，通常取1～3。33第三十三页，共五十页，编辑于2023年，星期三选择方法的改进基于次序的选择法竞争选择随机余数技术优选策略局部替代法稳定状态法选择育种法34第三十四页，共五十页，编辑于2023年，星期三3.交叉机制的改进两点交叉或多点交叉均匀交叉（是否交叉由概率决定）父辈字符串分别为A、B：

A=10110011011101B=11011000010101交叉后的子代为：

A'=11110011010101B'=1001100001110135第三十五页，共五十页，编辑于2023年，星期三倒置变换对于字长为10的字符串个体A=100｜1101｜010 随机选取两点4和8。将4与8之间的字符串进行倒置，即第7位变换到第4位、第6位变换到第5位...，生成新的个体A'

A'=100｜1011｜01036第三十六页，共五十页，编辑于2023年，星期三4.控制参数 经验性结论增大群体规模会增加群体中个体的发散性，减少GA算法过早收敛于局部最优的可能性。但也增加了算法的计算时间。小规模群体的GA搜索问题可以选择相对较大的交叉率和变异率，而群体规模比较大时，可以选择较小的交叉率和变异率。37第三十七页，共五十页，编辑于2023年，星期三5.算法策略动态自适应策略 根据性能指标和搜索的阶段，自适应调整控制参数，对于遗传算法的收敛，尤其对高精度最优解的搜索有着重要的作用。分布式GA算法和并行GA算法策略分布式GA算法是一个群整体分解为几个弱相关的子体分别进行进化计算，并行GA算法是对传统的串行计算方法用并行计算手段来实现。38第三十八页，共五十页，编辑于2023年，星期三GA的优点GA算法的突出优点在于能够根据交互的环境中的相应情况和进化算子在没有任何最优解先验知识条件下寻找到最优解。它不同于梯度下降法那样只对一点进行优化计算而是通过对群体中的所有个体进行遗传操作达到优化的目的，因此避免了单点优化算法可能出现的局部最优问题。从而使得GA算法可以处理复杂的、高维的、多目标的优化问题。这些都是传统优化方法无法比拟的。39第三十九页，共五十页，编辑于2023年，星期三8.2.1遗传学习的基本思想8.2.2遗传学习算法的理论基础8.2.3遗传学习算法的改良8.2.4遗传学习算法的应用8.2遗传学习原理与算法40第四十页，共五十页，编辑于2023年，星期三8.2.4遗传学习算法的应用遗传学习算法能够解决许多传统的优化方法难以解决的众多问题，已经在工程优化设计、机器学习、自适应控制、鲁棒控制器设计、PID控制、模糊逻辑控制器优化、最优控制、系统辨识、故障诊断、神经网络控制等领域得到应用和发展。41第四十一页，共五十页，编辑于2023年，星期三1.非线性系统的神经网络辨识42第四十二页，共五十页，编辑于2023年，星期三举例考虑非线性系统选择神经网络结构为输入矢量为[y(k),y(k-1),u(k)]输出矢量为y(k+1)。43第四十三页，共五十页，编辑于2023年，星期三GA设计用一个16位字长的编码来表示一个权系数，神经网络结构共需要16×[(1+3)×6+(6+1)×1]=496 位长的字符串。群体规模N=60，pc=0.7,pm=0.01。44第四十四页，共五十页，编辑于2023年，星期三