人工神经网络与智能算法.ppt

《人工神经网络与智能算法.ppt》由会员分享，可在线阅读，更多相关《人工神经网络与智能算法.ppt（75页珍藏版）》请在三一办公上搜索。

1、智能算法（Intelligent Algorithm）,2,主要内容,人工神经网络（Artificial Neural Network，ANN）模拟退火（Simulated Annealing，SA）遗传算法（Genetic Algorithm，GA）,3,人工神经网络参考文献,陈念贻，钦佩，陈瑞亮，陆文聪，模式识别方法在化学化工中的应用，科学出版社，北京，2000。从爽，面向MATLAB工具箱的神经网络理论与应用，中国科学技术出版社，合肥，1998。焦李成，神经网络计算，西安电子科技大学出版社，西安，1993。王永骥，涂健，神经元网络控制，机械工业出版社，北京，1998。Bishop,C.(

2、1995).Neural Networks for Pattern Recognition.Oxford:University Press.Carling,A.(1992).Introducing Neural Networks.Wilmslow,UK:Sigma Press.Fausett,L.(1994).Fundamentals of Neural Networks.New York:Prentice HallHaykin,S.(1994).Neural Networks:A Comprehensive Foundation.New York:Macmillan Publishing.P

3、atterson,D.(1996).Artificial Neural Networks.Singapore:Prentice Hall.,4,生物神经元及神经网络,神经元对信息的接受和传递都是通过突触来进行的。单个神经元可以从别的细胞接受多个输入。由于输入分布于不同的部位，对神经元影响的比例(权重)是不相同的。另外，各突触输入抵达神经元的先后时间也不一祥。因此，一个神经元接受的信息，在时间和空间上常呈现出一种复杂多变的形式，需要神经元对它们进行积累和整合加工，从而决定其输出的时机和强度。正是神经元这种整合作用，才使得亿万个神经元在神经系统中有条不紊、夜以继日地处理各种复杂的信息，执行着生物中

4、枢神经系统的各种信息处理功能。多个神经元以突触联接形成了一个神经网络。,5,一、人工神经网络,什么是人工神经网络？它就是在对大脑的生理研究的基础上，用模拟生物神经元的某些基本功能元件（即人工神经元），按各种不同的联结方式组织起来的一个网络。其目的在于模拟大脑的某些机理与机制，实现某个方面的功能，可以用在模仿视觉、模式识别、函数逼近、模式识别、分类和数据压缩等领域，是近年来人工智能计算的一个重要学科分支。人工神经网络有多种形式，其中反向传播人工神经网络(Back-Propagation Artificial Network,简称BP网络)是一种广泛使用的神经网络模型，它充分体现了人工神经网络的特

5、点。BP网络是一种对非线性可微分函数进行权值训练的多层网络，在人工神经网络的实际应用中，8090的人工神经网络模型是采用BP网络或它的变化形式。,6,1.1 BP神经网络,神经元的结构神经元是人工神经网络的基本处理单元，它一般为多输入/单输出的非线性元件。神经元输出除受输入信号的影响外，还受神经元内部其它因素的制约，因此在人工神经元的建模中，常常加一额外输入信号，称为偏差(bais)，并取值为1。,输入分量,权值分量,神经元的输出,偏差权值,激活函数,输入分量通过与它相乘的权值分量相连，求和后与偏差权值共同构成激活函数的输入。,7,偏差,神经元的输出为：,偏差b被简单地加在,上，作为激活函数的

6、一个输入分量。,偏差的重要作用，它使得激活函数的图形可以左右移动，这样可增加网络解决问题的能力。,8,激活函数,激活函数具有模拟生物神经元的非线性特性。,Sigmoid函数：,双曲正切tanh函数：,Sigmoid函数和双曲正切tanh函数都是单调上升函数，其极值分别为0、1和1、1，且都是可微的。,9,激活函数的一阶导数,在BP神经网络训练算法中，要用到激活函数的一阶导数。,Sigmoid函数的导数：,双曲正切tanh函数的导数：,由此可以看出，由于激活函数的特点，用神经网络计算时，需对输入和输出的值进行调整。,激活函数是采用Sigmoid函数时，输入和输出的值应在0,1之间；激活函数是双曲

7、正切tanh函数时，输入和输出的值范围则在1,1之间。,10,1.2 BP网络的模型结构,BP网络是一种在输入层和输出层之间具有一层或多层隐层的网络模型，而其典型的结构为有一隐层、包含输入层和输出层的三层网络模型。典型BP网络的结构示意图如下：,网络的输入模式向量为P，有r个输入神经元，对应输入模式向量的每个元素。,隐层内有s1个神经元，对应隐层输出是a1。,网络的输出为a2，有s2个神经元，而目标输出为T。,三层BP神经网络不同层神经元之间实现权重连接，而每层内各个神经元之间不连接。,11,BP网络的四个计算过程,输入模式由输入层经隐含层向输出层的“模式正向传播”过程；（神经元的激活值从输入

8、层经隐含层向输出层传播，在输出层各神经元获得网络响应。）网络实际输出与希望输出的误差信号由输出层经隐含层向输入层逐层修正连接权和阂值的“误差反向传播”过程；由“模式正向传播”过程与“误差反向传播”过程的反复交替进行的网络学习训练过程；网络全局误差趋向极小的学习收敛过程。（网络对输入模式响应的正确率也不断增加。）,12,BP网络的计算过程的简单描述（1）,模式正向传播过程,隐含层中第j个神经元的输出为：,输出层中第k个神经元的输出为：,误差反向传播过程,定义误差函数为：,神经网络学习的过程就是通过调整权值，使误差E最小，此时可利用最速下降法求权值及误差的反向传播。,13,BP网络的计算过程的简单

9、描述（2）,隐含层中第j个神经元的输出的权值变化为：,对第i个输入到隐含层中第j个神经元输出的权值变化为：,修正后的新权重调整为：,称为学习系数，值在0,1之间。,14,加快BP网络训练速度的方法,BP网络得到了广泛的应用，但也存在自身的不足与限制，主要表现在网络训练需较长时间和网络有可能达到局部最小。据此，BP网络有各种改进方法，以加快训练速度，避免陷入局部极小。主要的改进方法有：,增加动量项，以平滑权的变化，一种常用形式是：,为动量因子，值在0,1之间，n为迭代次数。,采用二阶学习算法。前面的基于函数梯度的算法属于一阶算法，缺点就是在极值点附近收敛速度慢。采用二阶算法，如牛顿法、共轭梯度法

10、等，将有较快的收敛速度。,模拟退火法。,15,1.4 BP神经网络计算（1）,网络的层数：在运用BP神经网络时，最多采用的是具有一层或两层隐层的网络。具有偏差和至少一个S型隐层的网络，可以近似任何函数，这已成为设计BP神经网络的原则。网络计算精度的提高，可以通过采用一个隐层，而增加隐层神经元数的方法来获得，这也就是通常用一隐层、包含输入层和输出层的三层BP网络模型的原因。神经元数：输入和输出的神经元数可以根据需要求解的问题和数据所表示的方式来确定。问题确定后，输入层与输出层的神经元数也就随之定了。隐层神经元数的选择有较广的范围：当隐层神经元数较少时，误差下降到一定程度后会变化很小；当隐层神经元

11、数过多时，不仅网络训练时间长，还会出现过拟合问题，降低神经网络的预测功能。通常隐层神经元数的选择原则是：在能解决问题的前提下，再加上1到2个神经元以加快误差的下降速度即可。,16,BP神经网络计算（2）,初始权值的选取 权重初始值的选取，对网络训练学习是否达到局部最小，是否能够收敛以及训练时间的长短有很大的关系。如果初始权值太大，使得加和后的值落在激活函数的饱和区，从而导致激活函数的导数非常小，在计算权值修正时，调整值接近零，网络的学习训练几乎处在停止状态。所以一般总是希望经过初始权值计算后每个神经元的输出值都接近零，这样可以保证每个神经元的权值都能在激活函数变化最大之处进行调节。一般来说，初

12、始权值取-1,1之间的随机数是较好的选择。,17,BP神经网络计算（3）,学习速率学习速率决定每一次循环训练中所产生的权值变化量。大的学习速率可能导致系统的不稳定；但小的学习速率导致较长的训练时间，可能收敛很慢，不过能保证网络的误差值不跳出误差表面的低谷而最终趋于最小误差值。所以在一般情况下，倾向于选取较小的学习速率以保证系统的稳定性。学习速率的选取范围在0.010.8之间。在一个神经网络的计算过程中，使网络经过几个不同的学习速率的训练，通过观察每一次训练后的误差平方和的下降速率来判断所选定的学习速率是否合适。如果误差平方和下降很快，则说明学习速率合适若误差平方和出现振荡现象，则说明学习速率过

13、大。对于每一个具体网络都存在一个合适的学习速率。但对于较复杂网络，在误差曲面的不同部位可能需要不同的学习速率。为了减少寻找学习速率的训练次数以及训练时间，比较合适的方法是采用变化的学习速率，使网络的训练在不同的阶段自动设置不同学习速率的大小。,18,BP神经网络计算程序BATCHNET简介,BATCHNET是一个 BP神经网络计算的DOS程序，程序由batchnet.exe和weights.exe两个可执行文件构成。batchnet为网络训练和预测程序，激活函数为Sigmoid函数，输入输出样本值范围为0,1。weights程序产生初始权值。批处理程序demo.bat,batchnet-e10

14、 d1.0e-5 demo.run,说明：-e10 表示网络每迭代10步后显示误差；d1.0e-5 表示网络训练误差；demo.run 求解问题的网络参数文件，由batchnet调用，文件名可改，但扩展名run不能变。,19,BP神经网络计算程序BATCHNET简介,网络参数文件demo.run的格式,4train.out train.err train.pat weights.wts train.wts 100 1000 9 4 2 0.15 0.075test.out test.err test.pat train.wts test.wts 166 1 9 4 2 0.15 0.075tr

15、ain.out train.err train.pat train.wts train.wts 100 1000 9 4 2 0.15 0.075test.out test.err test.pat train.wts test.wts 166 1 9 4 2 0.15 0.075,NumfOut fErr fPat fWts fWtso nPats nIter nInp nHid nOut eta alpha,Num 运行次数，本例为4；fOut 网络计算结果输出文件，输出；fErr 网络计算误差文件，输出；fPat 训练学习样本文件，输入；fWts 问题的初始权值文件，输入，由程序weig

16、hts产生；fWtso 训练后的权值文件，输出；nPats 训练样本数，本例为100；nIter 训练迭代次数，本例为1000；nInp 输入层神经元数目，本例为9；nHid 隐层神经元数目，本例为4；nOut 输出层神经元数目，本例为2；eta 学习速率，本例为0.15；alpha 动量因子，本例为0.075。,表示用BP神经网络先对100对输入输出样本进行学习训练1000次，预测166个样本一次，然后继续学习训练1000次后再进行一次预测。Batchnet如只计算一次，则不对连接权重进行更新。,20,BP神经网络计算程序BATCHNET简介,程序weights的运行:,weights in

17、t_num nInp nHid nOut ran_wts,说明：int_num 任一6位整数；nInp 输入层神经元数目；nHid 隐层神经元数目；nOut 输出层神经元数目，这3个参数同run程序中的相一致；ran_wts 初始权值取值范围，实数1.表示取值范围在-1,1之间。,Weights 123456 9 4 2 1.0,21,BP神经网络计算程序BATCHNET简介,训练样本文件fPat的格式：,说明：In_pat 样本的输入；Out_pat 对应的样本输出；Id 对应的样本标号；,In_pat Out_pat Id,0.363636 0.191667 0.7 0.75 0.6666

18、67 0.531225 0.0898333 0.0504219 0.6844341 0 12345670.327273 0.187501 0.733333 0.75 0.8 0.531038 0.0819442 0.0504219 0.8010571 0 1234567,22,STATISTICA Neural Networks(SNN)简介,通过输入数值变量(自变量)可以用神经网络来计算输出变量(应变量)，输出变量的类型可以是数值型的，也可以是非数值型的。在SNN中，求解问题可通过两种基本方式来进行：智能问题求解器(Intelligent Problem Solver)或程序的菜单。智能问题

19、求解器引导使用者建立求解问题的神经网络。在智能问题求解器中，有基本型和高级型两种模式可供选择。基本型中，使用者只能控制设计神经网络中的几个关键点，包括问题类型(样本相互独立的标准型和变量预测值依赖先前值的时间序列)、输出和输入变量、求解器筛选优化网络的计算时间控制、在网络设置中需保存的网络情况以及需显示的结果与统计，其余的网络设计及计算由求解器自动完成。基本型供对神经网络计算了解不多者使用。高级型中，使用者能控制设计神经网络的各方面，包括网络训练、校验、测试时所用数据的分割、置信度的类型选择、选择需产生网络的类型及复杂程度等，供对神经网络计算较熟悉者使用。,23,SNN中的神经网络方法,多层网

20、络(Multilayer Perceptrons)；径向基函数网络(Radial Basis Function Networks)；概率神经网络(Probabilistic Neural Networks)；通用回归神经网络(Generalized Regression Neural Networks)；线性网络(Linear Networks)；Kohonen网络(Kohonen Networks)；神经网络的时间序列预测(Time Series Prediction)。,24,SNN菜单 命令汇总,25,SNN处理数据需要注意的两个问题,数据的前处理与后处理在处理实际问题的数据时，数据要进

21、行匀整处理，这样的处理包括计算前和计算后的处理。神经网络计算用的数据类型应该是数值型的，当有些问题的变量是多态的情况，如对与错等，这些变量在用神经网络处理时，也需将其数值化。在SNN中有Pre/post processing，可处理这些数据的变换问题，有时还可以用Options菜单中的STATISTICA Transfer，使数据直接在STATISTICA中处理。过拟合问题在用多项式拟合数据时，就会出现过拟合的情况。一个低阶多项式可能做不到很好地拟合所有的数据点，而一个高阶的则可能做到，但实际上没有反映问题的性质。,26,SNN处理过拟合的方法,神经网络计算有同样的问题，隐层神经元数太少，不能

22、很好地描述问题，神经元数过多，会出现过拟合，因较大的神经网络总能使误差减小。解决过拟合的办法之一是用交替有效法(Cross-verification)。一些训练用样本不参加神经网络的学习训练，而是独立地在训练学习过程中用来校验。当校验误差出现同训练学习误差不一样的情况，即不是随着训练学习的进行，训练误差不断减小，反而停止下降，开始升高，表明网络有过拟合数据的情况，这时应减少隐层神经元数。在SNN中智能问题求解器具有自动选择隐层神经元数的功能。,27,SNN的求解过程,在神经网络的研究和计算中，常能见到异或问题的求解与讨论。这里以异或问题的求解为例介绍SNN的求解过程，并对SNN智能问题求解器中

23、的各项选择作一说明。,异或问题两个输入变量为二进制的数，其可能的取值及期望输出如右表所示：,异或问题看起来简单，但具有复杂的特征，它不是线性可分的，即不可能有一直线使同类在线的一边，如右图所示：,28,SNN中的智能问题求解器使用步骤,Step 1：建立上述的数据文件,输入变量类型（Input or Output）,样本分组（Training、Verification、Testing）,29,Step 2：选择求解问题方式问题类型（Basic or Advanced），选择“Advanced”。,30,SNN中的智能问题求解器使用步骤,Step 3：选择问题类型（Problem Type），选

24、择“Standard”。,31,SNN中的智能问题求解器使用步骤,Step 4：选择输出变量（Output Variable Selection），选择XOR变量作为输出变量。,32,SNN中的智能问题求解器使用步骤,Step 5：选择输入变量（Input Variable Selection），选择变量FIRST,SECOND作为输入变量。并关闭选项“Search for an effective subset”。,33,SNN中的智能问题求解器使用步骤,Step 6：样本分组（Division of cases）。控制训练（Training）、检验（Verification）和测试（Tes

25、ting）样本的大小。,采用自定义分组样本,34,SNN中的智能问题求解器使用步骤,Step 7：选择网络类型（Type of Network）。为比较网络，几种网络都选，即线性、径向基函数(RBF)、通用回归神经网络(GRNN)、三层和四层MLP。,35,SNN中的智能问题求解器使用步骤,Step 8：控制网络隐层数目（Hidden Units）。选择“Determine network complexity automatically”自动确定网络复杂性，忽略数值选定。,36,SNN中的智能问题求解器使用步骤,Step 9：网络设计过程（Duration of Design Process

26、）。选择完全“Thorough”项。,37,SNN中的智能问题求解器使用步骤,Step 10：希望保存最佳网络和在网络确定过程中增加网络大小（Saving Networks）。选择“Keep networks”和“Increase”项。,38,SNN中的智能问题求解器使用步骤,Step 11：结果显示（Results Shown）。选择列表样本结果“Datasheet”和统计结果汇总“Overall”。SNN计算完成后，给出多种结果。,39,SNN的求解异或问题的结果,Data Set Editor给出了训练样本。,Run Data Set是训练结果，有目标值、计算值和误差。,Regressi

27、on Statistics是最优网络计算的统计结果。,Network Set Editor则是智能问题求解器所用的各种网络的计算结果。,Network Illustration则是最优网络的图示。,40,SNN的求解异或问题的结果,计算结果表明了多层网络的隐层神经元数为5时，计算的误差已达10-5，可以用来描述异或问题。是否还有描述异或问题更好的网络结构呢？隐层数为4的RBF网络，计算异或问题的误差达到10-15，比隐层神经元数为5的多层网络的计算误差要小10个数量级，完全描述了异或问题。,41,1.4 关于ANN的进一步说明,选用合适的学习训练网络样本、优化网络结构、采用适当的学习训练方法就

28、能得到包含学习训练样本范围的输入与输出关系。如果用于学习训练的样本不能充分反映体系的特性，用ANN也不能很好的描述与预测体系，所以有“垃圾进，垃圾出；金子进，金子出”之说。确定性模型的参数回归与ANN之类的非确定性模型的不同特点。,42,确定性模型与非确定性模型的比较,确定性模型的参数回归的特点：自变量与因变量之间有明确的函数关系，具有未知数值的参数，需要通过自变量与因变量的数据组样本来回归估计，而且参数个数通常较少，具有明确的物理意义。ANN之类的非确定性模型的特点：无须针对问题提出明确的自变量与因变量之间的函数关系，而函数关系用含有众多自由参数的模型回归拟合，但自由参数无明确的物理意义。因

29、此，确定性模型回归的主要目标是得到模型的参数值。而非确定性模型计算的主要目标是得到输入与输出的关系。,43,二、模拟退火法（Simulated Annealing）,人工神经网络方法是用某种目标函数的全局极小作为算法搜索和网络所要达到的目标。在学习或运行过程中，网络的误差总是按其梯度下降的方向变化。当梯度趋于零时，网络的学习或运行就停止了，所以这种算法往往会陷入局部最小而达不到全局最小。导致网络陷入局部最小的主要原因是网络误差按单方向减少，没有上升的过程。如果将误差的减少过程由“总是按梯度下降的方向变化”改为“大部分情况下按梯度下降的方向变化”，而有时按梯度上升的方向变化，这样就有可能跳出局部

30、最小而达到全局最小(下图给出了梯度下降法(a)和SA方法(b)搜索途径)。,模拟退火算法的基本思想,44,模拟退火法的起源,SA算法是受金属冷却过程的启发，最早由Metropolis于1953年提出来的。它具有灵活有效，能对问题进行全局优化。金属中原子的能量与温度有关。原子能量高的时候，有能力摆脱其原来的能量状态而最后达到一个更加稳定的状态全局极小能量状态。金属固体进行退火处理时，通常先将它加热熔化，然后逐渐降低温度。在凝固点附近，若温度下降的速度足够慢，则固体物质会形成能量最低的稳定状态。其中的金属粒子都经历能量由高到低、暂时由低到高、最终趋向低能态的过程。在金属的退火过程中，能量的状态分布

31、：,P(E),P(E)系统处于具有能量E的状态的概率；kBoltzmann常数；T系统的绝对温度(Kelvin),45,模拟退火优化法,SA算法将优化问题与统计物理学中的热平衡问题进行类比，即将统计物理学处理金属固体冷却的热平衡方法用于优化问题。,目标函数能量函数优化参数的状态空间物质的微观状态 人工温度T一个初值较大的控制参数依据网络的能量来决定控制参数的调整量（称为步长）。当T较大时，目标函数值由低向高变化的可能性较大；而T减小，这种可能性也随之减小。与金属的退火过程（Annealing）非常相似。当控制参数T下降到一定程度时，目标函数将收敛于最小值。,模拟退火优化算法的基本思想,46,模

32、拟退火优化法,计算机模拟某一温度T下物质体系热平衡状态的方法：,Step 1：随机选择一个初始微观状态i作为当前状态，其相应的能量为Ei。Step 2：从状态i作随机扰动，产生一新的状态j，其相应的能量为Ej，计算能量增量E=Ei Ej。Step 3：如果E0，则接受状态j作为当前状态，即ji；若E0，计算基于Boltzmann分布函数的比值：,其中:Boltzmann分布函数,k为Boltzmann常数,取(0,1)之间的一个随机数p，若rp，则接受状态j作为当前状态，即ji；否则，保持原来的状态i。,47,模拟退火优化法,从Boltzmann分布函数的比值(即式)可看出，温度高时大，相应k

33、T也较大，接受与当前状态能差较大的新状态的概率大；降低温度，r较小，只能接受能差较小的新状态。因此不断降低温度，体系最终能达到能量最低热平衡状态。,Step 4：重复第二、三步，在大量的能量状态变化后，系统处于能量较低的平衡态。降低温度T再重复上述过程，体系又处在能量更低的平衡态。,48,SA基本算法的步骤与框图,首先进行初始化，任意给定初始态X0，取参数初值T0，计算优化目标函数E0，然后按下进行：（1）随机产生扰动态Xi，计算E=Ei E0;（2）若E0，转到(4)。否则在(0,1)之间的一个随机数p;（3）若exp(E/T)p，转(5);（4）用Xi代替X0，E0+E代替E0；（5）以某

34、种方式取Ti T0，如 Ti=T0；（6）SA计算过程是否结束，是就停止，否则就转到(1)。,49,SA算法的控制,SA算法能否达到目标函数的最小值，主要取决于控制参数的初值是否足够高和其下降得是否慢，因此注意有关控制参数的选取问题。对于参数初值T0，常用的处理方法之一是在均匀地随机抽样X0后，取的E0方差作为T0。对于降温策略Ti=T0，01，常取0.85,0.96。,SA算法的使用可以参考教材P257（FORTRAN程序）用SA拟合丙烷丝光沸石体系在303 K时的吸附平衡数据和模型。,50,三、遗传算法(Genetic Algorithm),遗传算法是一种模拟自然选择和遗传的随机搜索算法。

35、它最初由Holland在1975年提出的，研究自然系统的适应过程和设计具有自适应性能的软件。遗传算法的基本形式是用染色体来表示参数空间的编码，用适应度函数来评价染色体群体的优劣，通过遗传操作产生新的染色体，并用概率来控制遗传操作。遗传算法是一种非线性方法，它具有简洁、灵活、高效和全局优化的特性，在过程控制、系统诊断、非线性拟合与优化、人工智能等工程和研究领域都得到了广泛的应用。,51,遗传算法基础,遗传算法是一种迭代算法，它在每一次迭代时都拥有一组解(父代染色体群体)，这组解答最初是随机生成的。在每次迭代时，首先保持解，然后染色体群体经过遗传操作(选择、杂交、变异等)，生成新的组解(子代染色体

36、群体)。每个解都由一个目标函数来评价，而且这一过程不断重复，直至达到某种形式上的收敛。新的一组解不但可以有选择地保留一些先前迭代中目标函数值高的解，而且可以包括一些经由其它解结合而得的新的解，其子代的数值可以与其父代的情况有相当大的差别。,52,符号串表示和遗传操作的设计,遗传算法的术语借鉴于自然遗传学,遗传物质的主要载体是染色体。在遗传算法中，染色体(个体)由一串数据或数组构成，用来作为问题解的代码。染色体由决定其特性的基因构成，而基因又可以有称为等位基因的不同取值。目标函数称为适应度函数，而一组染色体称为群体。遗传算法的一次迭代称为一代。遗传算法成功的关键在于符号串表示和遗传操作的设计。,

37、53,染色体,解空间中的每一点都对应一个用由基因表示的染色体。例如：要确定适应度函数f(x,y)的最大值，搜寻空间变量x和y为整数，其变化范围是0-15。这样对应于搜寻空间任何点可由两基因的染色体来表示：,点（2,6）用二进制数有如下的染色体：,54,交叉,在两父代的染色体的随机长度位置上，用交叉概率进行后部交换，产生两子代，如下所示：,上面的交叉操作称为单点交叉。一般地可以进行多点交叉，如下所示：,55,变异,与交叉不同，变异涉及到一染色体个体的一个或多个基因位的翻转，产生新的基因组合，以通过交叉来获得子代染色体。下面的任一方法都可以用来进行变异操作：随机选择的基因位数值可以被随机产生的数值

38、替代，这种替代对二进制和非二进制染色体都适用；在二进制染色体中，可以对随机选择的基因位进行触发，即10或01。可以以概率Pm随机选择个体进行变异操作。变异操作的主要优点是使染色体群体中出现各种基因，这样遗传算法有在参数解空间找出各种可能的解，避免解的丢失。,56,有效性检验,对于不同的优化问题，有时需要增加检验，确保新子代的染色体表示的是参数解空间中的有效点。如考虑由四个基因组成的染色体，每个基因有三个可能的二进制值A=01，B=10，C=11。二进制染色体表示组合BACA是：,如对最后的基因位进行变异操作，产生了如下所示的无效染色体，因基因值00没有定义。,同样，交叉也可能产生有缺陷的染色体

39、操作。克服这些问题的方法是采用结构操作，交叉或变异操作针对基因，而不是针对基因位。这样，交叉操作点总能与基因边界相一致，变异操作对整个基因组随机选择新值，确保产生有效染色体。如此做的缺点是染色体群体的差异性会受到影响。,57,基本的遗传算法框图,初始染色体群体随机产生；用适应度函数来评价染色体个体；根据适应度产生繁殖的染色体个体，适应度好的染色体个体其被选择来繁殖的可能性大；通过染色体对的交叉和变异操作，产生各自的子代繁殖染色体。,58,基本的遗传算法,在遗传算法中，是依据适应度来选择个体进行繁殖的，最适合的染色体繁殖的可能性也最大。选择不仅决定由那些个体来繁殖，而且还要确定繁殖子代的数目。因

40、此选择的方法对遗传算法的有效性有着重要的作用。GA算法的使用可以参考教材P262（FORTRAN程序）Genetic Algorithm and Direct Search Toolbox in MATLAB v2006a,59,Genetic Algorithm Toolbox in MATLAB,Calling the Function ga at the Command Line,x fval=ga(fitnessfun,nvars,options),fitnessfun is a handle to the fitness function.nvars is the number of

41、 independent variables for the fitness function.options is a structure containing options for the genetic algorithm.If you do not pass in this argument,ga uses its default options.Step,x Point at which the final value is attainedfval Final value of the fitness function,Using the Genetic Algorithm To

42、ol,gatool,60,GATool GUI of MATLAB,目标函数,变量数,约束条件,图形显示,执行计算,计算结果,计算选项,61,Ex1:Unconstrained Minimization Using GA,Function：,The function has two local minima：one at x=0,where the function value is-1,the other at x=21,where the function value is-1-1/e.Since the latter value is smaller,the global minimum

43、 occurs at x=21.,62,Result of local minimum,function y=two_min(x)if x=20 y=-exp(-(x/20).2);else y=-exp(-1)+(x-20)*(x-22);end,63,How to explore points near the global minimum,One way to make the genetic algorithm explore a wider range of points that is,to increase the diversity of the populations is

44、to increase the Initial range.,64,Range of individuals in each generation,a much wider range of individuals.By the second generation there are individuals greater than 21,and by generation 12,the algorithm finds a best individual that is approximately equal to 21.,all individuals are between-2 and 2

45、.5.While this range is larger than the default Initial range of 0;1,due to mutation,it is not large enough to explore points near the global minimum at x=21.,65,Ex2:Constrained Minimization Using GA,minimize a simple fitness function of two variables x1 and x2,min f(x)=100*(x12-x2)2+(1-x1)2;x,the fo

46、llowing two nonlinear constraints and bounds are satisfied,x1*x2+x1-x2+1.5=0,(nonlinear constraint)10-x1*x2=0,(nonlinear constraint)0=x1=1,and(bound)0=x2=13(bound),66,Define of objective function and constrains,function c,ceq=simple_constraint(x)c=1.5+x(1)*x(2)+x(1)-x(2);-x(1)*x(2)+10;ceq=;,function

47、 y=simple_fitness(x)y=100*(x(1)2-x(2)2+(1-x(1)2;,0=x1=10=x2=13,67,Result of Ex2,68,M-file Generated by GATool,function X,FVAL,REASON,OUTPUT,POPULATION,SCORES=cm_ga%Fitness functionfitnessFunction=simple_fitness;%Number of Variablesnvars=2;%Linear inequality constraintsAineq=;Bineq=;%Linear equality

48、constraintsAeq=;Beq=;%BoundsLB=0 0;UB=1 13;%Nonlinear constraintsnonlconFunction=simple_constraint;%Start with default optionsoptions=gaoptimset;%Modify some parametersoptions=gaoptimset(options,PopulationSize,100);options=gaoptimset(options,MutationFcn,mutationgaussian 1 1);options=gaoptimset(optio

49、ns,Display,off);%Run GAX,FVAL,REASON,OUTPUT,POPULATION,SCORES=ga(fitnessFunction,nvars,Aineq,Bineq,Aeq,Beq,LB,UB,nonlconFunction,options);,69,M-file by user,function c,ceq=simple_constraint(x)c=1.5+x(1)*x(2)+x(1)-x(2);-x(1)*x(2)+10;ceq=;,function y=simple_fitness(x)y=100*(x(1)2-x(2)2+(1-x(1)2;,Objec

50、tiveFunction=simple_fitness;nvars=2;%Number of variablesLB=0 0;%Lower boundUB=1 13;%Upper boundConstraintFunction=simple_constraint;x,fval=ga(ObjectiveFunction,nvars,LB,UB,.ConstraintFunction),x=0.8122 12.3122fval=1.3578e+004,70,Conventional structure of a GA applied to the experomental design,71,Ap