第7章-智能最优化算法

第7章智能最优化算法随着仿生学、遗传学和人工智能科学的发展，从20世纪70年代以来，科学家相继将遗传学、神经网络科学的原理和方法应用到最优化领域，形成了一系列新的最优化方法，如遗传算法、神经网络算法、蚁群算法等。这些算法不需要构造精确的数学搜索方向，不需要进行繁杂的一维搜索，而是通过大量简单的信息传播和演变方法，得到问题的最优解。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局最优化概率搜索算法。7.1遗传算法7.1.1生物的遗传与进化生物从其亲代继承特性或形状的现象称为遗传；生物在其延续生存的过程中,逐渐适应生存环境，使其品质不断得到改良，这种生命现象称进化。•构成生物的基本结构和功能单元是细胞•细胞中含有一种微小的丝状化合物称染色体•染色体主要由一种叫做核糖核酸(简称DNA)的物质构成•DNA按一定规则排列的长连称基因•基因是遗传的基本单位另外，在进行细胞复制时，也可能产生某些差错，从而使DNA发生某种变异，产生新的染色体。可见，同源染色体之间的复制、交叉或变异会使基因或染色体发生各种各样的变化，从而，使生物呈现新的性状，产生新的物种。细胞在分裂时，遗传物质DNA通过复制转移到新的细胞中，新细胞就继承了旧细胞的基因。有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉而重组，即在两个染色体的某一相同位置处DNA被切断，然后分别交叉组合形成两个新的染色体。7.1.2基本遗传算法X可以看作由n个遗传基因组成的染色体，也称个体。最简单的等位基因由0和1这两个整数组成，相应的染色体或个体就是一个二进制符号串。12,TnXxxLx12nX:X,XLX在遗传算法中，将设计变量用符号串表示。由m个个体组成一个群体，记作()Pt这种编码所形成的符号串称个体的基因型，与之对应的值称个体的表现型。把其中每一个看作一个遗传基因，它的所有可能的取值称等位基因。iX（1）遗传编码遗传算法的运行不直接对设计变量本身进行操作，而是对表示可行解的个体编码进行选择、交叉和变异等遗传运算。在遗传算法中把原问题的可行解转化为个体符号串的方法称编码。现有的编码方法可以分为三类，它们是二进制编码、浮点数编码和符号编码。二进制编码所用的符号集是由0和1组成的二值符号集，它所构成的个体基因型是一个二进制符号串。符号串的长度与所要求的求解精度有关。minmax,UUl2l假设某一参数的取值范围是，若用长度为的二进制符号串来表示，总共能够产生个编码。编码精度为21maxminlUU（7-1）这里介绍常用的二进制编码方法。1221:lllXbbbbb假设某一个体的编码是：(7-2)11221maxminminliiliUUxUb则对应的解码公式为(7-3)就表示一个个体，称个体的基因型，对应的十进制数175就是个体的表现型，编码精度为01023,x例如，对于变量10210240010101111:X若采用10位二进制编码时，可代表个不同的个体。如()FX()fX(,)Xr在研究生物的遗传和进化现象时，生物学家使用适应度这个术语来度量物种对生存环境的适应程度。，一般由目标函数或惩罚函数（2）个体适应度在遗传算法中使用适应度这个概念来度量群体中个体的优劣程度。适应度较高的个体遗传到下一代的概率较大，反之则较小。度量个体适应度的函数称适应度函数，一般由目标函数或惩罚函数转换而来。()FX()fX(,)kXr以目标函数为例，常用的转换关系如下：max()fX对于极大化问题：000minminmin(),()(),()fXCiffXCFXiffXC(7-4)minC式中为一适当小的正数。min()fX对于极小化问题：0maxmaxmax(),()(),()CfXiffXCFXiffXC(7-5)maxC为一较大的正数。式中，生物的进化是以集团为主体进行的。与此对应，遗传算法的运算对象也是由M个个体所组成的集合，称群体。第t代群体记作P（t），遗传算法的运算就是群体的反复演变过程。（3）遗传运算遗传算法将染色体中基因的复制、交叉和变异归结为各自的运算规则或遗传算子，并反复将这些遗传算子作用于群体P（t），对其进行选择、交叉和变异运算，以求得到最优的个体，即问题的最优解。生物的进化过程主要是通过染色体之间的复制、交叉和变异来完成的。1）选择运算遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作。适应度较高的个体有较大的概率遗传到下一代。112(,)MisiiiPffiM设群体的大小为M，个体i的适应度为fi，则个体i被选中的概率Pis为：目前常用比例选择运算。其基本的操作是：个体被选中并遗传到下一代的概率与它的适应度的大小成正比。每个概率值组成一个区间，全部概率值之和为1。2）交叉运算交配重组是生物遗传进化过程中的一个重要环节。模仿这一过程，遗传算法使用交叉运算，即在两个相互配对的个体间按某种方式交换其部分基因，从而形成两个新生的个体。运算前需对群体中的个体进行随机配对，然后以不同的方式确定配对个体交叉点的位置，并在这些位置上进行部分基因的交换，形成不同的交叉运算方法。目前最常用的是单点交叉运算。产生一个0到1之间的随机数，依据概率值所出现的区间来决定对应的个体被选中的次数，此法亦称轮盘法。11000000010001010011父个体1父个体211000100010001000011子个体1子个体2交叉运算交叉点交叉点单点交叉又称简单交叉，它是在个体编码串中随机地设置一个交叉点，并在该交叉点上相互交换两个配对个体的基因，如下所示：3）变异运算生物的遗传和进化过程中，在细胞的分裂和复制环节上可能产生一些差错，从而导致生物的某些基因发生某种变异，产生出新的染色体，表现出新的生物性状。模仿这一过程，遗传算法采用变异运算，将个体编码串中的某些基因座上的基因值用它的不同等位基因来替换，从而产生新的个体。有很多变异运算方法，最简单的是基本位变异。基本位变异操作是在个体编码串中依变异概率Ps随机指定某一位或某几位基因座上的基因值作变异运算，如下所示：11000100011100011001变异运算编码，构成初始群体P(t)计算P(t)中各个体的适应度图7-1遗传算法的运算流程图给定T、置t=0t=t+1得到新的群体p(t+1)变异运算交叉运算选择运算Y取最大适应度的个体解码输出终止tT遗传算法的运算流程图如下：N2212max()fXxx例用遗传算法求如下函数的全局最大值s.t.xi∈{1,2,…,7}(i=1,2)由此开始的遗传算法求解过程如表所示。解，由于变量的取值上限为7下限为0，故对1x2x和均采用3位二进制编码。0.230.210.420.14(16)53509834适应度f(x1,x2)(15)7,27,17,73,5变量x1,x2(14)子代群体P（1）(13)111010111001111111011101变异结果(12)6254变异点(11)111011101001111101011001交叉结果(10)54交叉点(9)3-41-2配对情况(8)111001101011111001011101选择结果(7)2011选择次数(6)0.350.170.240.24(5)50253434适应度f(x1,x2)(4)7,13,45,33,5变量x1,x2(3)111001011100101011011101初始群体P(0)(2)4321个体编号i(1)/iiff/iiff需要说明的是，表中第②、8、⑨、11栏的数据是应该随机产生的，这里特意选择了一些较好的数据以便尽快得到较好的结果。实际运算中一般需求经过多次进化才能得到这样的最优结果。从表中可以看出，群体经过一代进化后，其适应度的最大值和平均值都得到了明显的改进。实际上已经找到了最佳的个体“111111”以及对应的最优解：X＝[7,7]T,f(X)=987.2神经网络算法7.2.1人工神经元与神经网络人的大脑中有100多亿个神经细胞。一个神经细胞主要由细胞体、树突、轴突和突触组成。树突伸向四方，其作用是收集四周神经细胞的信息。突触是两个神经细胞之间起连接作用的部分。树突将收集到的信息经过轴突输出，传给其他细胞。突触有兴奋性和抑止性两种状态。兴奋性突触在脉冲的刺激下能使下一个神经细胞产生兴奋性膜电位，很多细胞通过各自的突触对某一个神经细胞发生作用，使其膜电位发生变化，当膜电位的累加值超过某一阈值时，就会使该细胞产生一个新的脉冲。一个神经细胞周围大约有100~1000个其他细胞，神经细胞的信息就是这样从一个细胞传递给另外一个细胞的，从一个神经网络传到另一个神经网络。1943年，美国心理学家W.McCllochhe和数学家W.pitts根据生物神经元的基本特性，提出MP神经元模型，开创了人工神经元研究的新纪元。MP神经元模型如图所示图7-2MP神经元模型wj1x2xnwj2wjnθjf()ujyjx1图7-3MP模型的激活函数ujff(uj)1其符号的正负表示产生的作用是兴奋性的或抑止性的，其数值的大小表达作用的强弱；jj表示神经元的阈值（触发值）ju代表神经元的总输入，jjy表示神经元的状态或输出。j图7-2MP神经元模型wj1x2xnwj2wjnθjf()ujyjx1其中个神经元对第个jiwij表示第神经元的作用权值，1()njjiijijjuwxyfu于是一个神经元在某时刻的状态或输出可用下面的数学表达式加以描述（7-7）()f其中称激活函数。1000,sgn(),jjjjuyuu(7-8)时，神经元的状态是总输入ju的双值函数。当激活函数取如图7-3所示的符号函数ju0jy当小于零时，表示神经元未被触发，保持原来的状态不变。这与生物神经细胞对信息的反应和传递是一致的，因此它也成为人工神经元及其所构成的神经网络最基本的数学描述。除符号函数之外，常用的激活函数还有如图7-4所示的线性函数和S型函数等。ju1jy当大于零时，表示神经元被触发产生一个新的脉冲。11,(),,jajjjajajauuyfuuuuuuu（a）线性函数0ua1-ua-1yjuj图7-4激活函数(b)S型函数11()jjjuyfue01-1yjuj目前提出的人工神经网络模型已有40多种按网络结构分为前馈型和反馈型；按网络性能分为连续型、离散型、确定型和随机型；按学习方式分为有导师型和无导师型；按突触连接性质分为一阶线性型和高阶非线性型等。人工神经网络是将上述人工神经元以某种方式组合起来的网络结构。人工神经网络通过某种学习（训练）方法模拟生物体中神经网络的某些结构与功能，从而用以解决不同的工程实际问题。目前常用的BP网络和RBF网络属前馈型神经网络，Hopfield网络属反馈型网络。BP网络由多个输入结点、多个隐含层和一个输出层组成。每层包含多个神经元（结点）。前后层之间实现全连接，层内各结点之间无连接。7.2.2BP网络BP网络是一种输入信号前向传播、误差信号反向传播的多层前馈型网络。（1）BP网络结构BP网络中，隐含层神经元的激活函数一般采用Sigmoid型的对数函数或正切函数，输出层神经元通常采用线性激活函数。图7-5所示为单隐层BP网络的结。(a)结构图隐层（n个神经元）输出层（m个神经元）x1x2x3xn1w111w1n,n1w1n,3u1unu2v1v2vnh1h2hny1y2yn1f2f11121n21212nw112w2m,nw211图7-5单隐层BP网络输入W1W2隐含层输出层线性激活函数S型激活函数(b)结构简图12Xn1×1n×1n×1u1f2fyvhm×1m×nn×1n×n1m×1(c)网络结构示意图XW1JHLYW2网络中隐含层和输出层神经元的输出为1111122211212,,,,,,njjiijinlljjljhfwxjnyfwhlm