1、第五章第五章 进化算法进化算法 5.四四5.5.5.5.5.5.6. .5.5.5. .6. .6. .5. .实数编码遗传算法求函数极大值实数编码遗传算法求函数极大值求解该问题遗传算法的构造过程：求解该问题遗传算法的构造过程：（1 1）确定决策变量和约束条件；）确定决策变量和约束条件；（2 2）建立优化模型；）建立优化模型；（3 3）确定编码方法：用）确定编码方法：用2 2个实数分别表示两个个实数分别表示两个决策变量，分别将的定义域离散化为从离散点决策变量，分别将的定义域离散化为从离散点-2.0482.048到离散点到离散点2.048的的SizeSize个实数。个实数。（4 4）确定个体评价
2、方法：）确定个体评价方法： 个体的适应度直接取为对应的目标函数值，个体的适应度直接取为对应的目标函数值，即即 选个体适应度的倒数作为目标函数选个体适应度的倒数作为目标函数 ),()(21xxfxF)(1)(xFxJ（5 5）设计遗传算子：）设计遗传算子：选择运算使用比例选择算子，选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变交叉运算使用单点交叉算子，变异运算使用基本位变异算子。异算子。（6）确定遗传算法的运行参数：群体大小）确定遗传算法的运行参数：群体大小M=500M=500，终，终止进化代数止进化代数G=200G=200，交叉概率，交叉概率P Pc c=0.90=0
3、.90，采用自适应变，采用自适应变异概率异概率即变异概率与适应度有关，适应度越小，变异概率越即变异概率与适应度有关，适应度越小，变异概率越大。大。 0.01/SizeSize:1:1-0.10mP 上 述 六 个 步 骤 构 成 了 用 于 求 函 数上 述 六 个 步 骤 构 成 了 用 于 求 函 数RosenbrockRosenbrock极大值的优化计算的实数编码遗传极大值的优化计算的实数编码遗传算法。算法。 十进制编码求函数十进制编码求函数RosenbrockRosenbrock极大值。仿极大值。仿真程序见真程序见chap10_2.mchap10_2.m。 仿真程序经过仿真程序经过20
4、0200步迭代，最佳样本为步迭代，最佳样本为即当即当 ， 时，函数具时，函数具有极大值，极大值为有极大值，极大值为3880.33880.3。2.044- -2.0438 BestS2.0438 1x2.044 2x 5.7 5.7 遗传算法在神经网络设计中的应用遗传算法在神经网络设计中的应用 神经网络存在如局部极小问题、结构设计问题、神经网络存在如局部极小问题、结构设计问题、实时性差问题等。将实时性差问题等。将GA与与ANN常用常用3种结合方式。种结合方式。 (1)(1)网络权值的进化。网络权值的进化。进化过程中，网络层进化过程中，网络层数、节点数及连接方式等固定不变。因此，遗传算数、节点数及
5、连接方式等固定不变。因此，遗传算法只被用作训练神经网络的一种学习算法。法只被用作训练神经网络的一种学习算法。 (2)(2)网络结构的进化。网络结构的进化。用于神经网络的拓扑用于神经网络的拓扑结构设计结构设计。网络的网络的连接方式编码连接方式编码有两种策略：将有两种策略：将网网络的所有连接方式络的所有连接方式都明确地表示出来称为都明确地表示出来称为直接编码直接编码，只表示连接方式中的一些重要特征称为只表示连接方式中的一些重要特征称为间接编码间接编码。 在进化中，需要在进化中，需要ANN学习算法学习算法(如如BP)来训练网络的来训练网络的权值以评估每种权值以评估每种网络结构的适应度网络结构的适应度
6、。该方法编码长。该方法编码长度较小，但度较小，但每一代种群每一代种群个体个体都要进行一次完整的网都要进行一次完整的网络训练络训练，计算开销大。通常父代网络和子代网络在，计算开销大。通常父代网络和子代网络在结构上的差别很小，无须从头训练。因此，可用同结构上的差别很小，无须从头训练。因此，可用同时进化网络的结构和权值，得到的网络一般隐节点时进化网络的结构和权值，得到的网络一般隐节点较多。较多。 (3)(3)学习规则的进化。学习规则的进化。网络确定后学习算法也就确网络确定后学习算法也就确定了。但学习算法中尚有一些定了。但学习算法中尚有一些参数需要优化参数需要优化，而使，而使用者往往没有如何合理设置参
7、数的知识和经验。在用者往往没有如何合理设置参数的知识和经验。在这种情况下，可这种情况下，可应用遗传算法来进化学习规则中的应用遗传算法来进化学习规则中的参数参数以及神经网络的评价函数。以及神经网络的评价函数。 5.7.1 5.7.1 遗传算法权值优化遗传算法权值优化 将神经网络中所有将神经网络中所有权值编码成二进制码串权值编码成二进制码串或或实数实数码串表示的个体码串表示的个体，随机生成这些码串的初始群体，随机生成这些码串的初始群体，即可进行遗传算法优化计算。每一代计算后，即可进行遗传算法优化计算。每一代计算后，将码将码串解码为权值串解码为权值构成新的神经网络，通过对所有训练构成新的神经网络，通
8、过对所有训练样本进行计算得到神经网络输出的均方误差从而确样本进行计算得到神经网络输出的均方误差从而确定每个个体的适应度。经过若干代计算，神经网络定每个个体的适应度。经过若干代计算，神经网络将进化到误差全局最小。具体过程如下：将进化到误差全局最小。具体过程如下： (1)采用某种方案对每个采用某种方案对每个权值进行编码权值进行编码，随机产，随机产生一组权值编码；生一组权值编码； (2)计算神经网络的计算神经网络的误差函数误差函数，确定其适应度的，确定其适应度的函数值，函数值，误差值越大，适配值越小误差值越大，适配值越小； (3)选择若干适配值大的个体直接遗传给下一代选择若干适配值大的个体直接遗传给
9、下一代，其余按适配值确定的概率遗传其余按适配值确定的概率遗传； (4)利用交叉、变异等操作处理当前种群，产生利用交叉、变异等操作处理当前种群，产生下一代种群；下一代种群； (5)重复重复(2)(4)，直到取得满意解。，直到取得满意解。 若网络的权值在某一预先确定的范围内变化，则若网络的权值在某一预先确定的范围内变化，则各权值的各权值的二进制码串与权值之间二进制码串与权值之间有以下对应关系有以下对应关系 式中，式中，Binreplace(t)由由l位字符串表示的二进制整位字符串表示的二进制整数数,Wmax(i,j)，Wmin(i,j为各权值的取值范围。二进为各权值的取值范围。二进制编码优点制编码
10、优点:简单通用简单通用;缺点缺点:不直观、精度有限。不直观、精度有限。 实数编码实数编码优点优点：表达直观，不会出现因精度不高而：表达直观，不会出现因精度不高而导致训练失败的情况；导致训练失败的情况；缺点缺点：不能利用已有的遗传：不能利用已有的遗传操作算子，需要设计专门的遗传算子。操作算子，需要设计专门的遗传算子。 5.7. 5.7.2 2 神经网络的结构优化神经网络的结构优化 将神经网络的将神经网络的结构模式编码成码串表示的个体结构模式编码成码串表示的个体，因此遗传算法搜索的空间较小，但对于遗传算法选因此遗传算法搜索的空间较小，但对于遗传算法选择的每个神经网络，都必须用传统方法进行训练以择的
11、每个神经网络，都必须用传统方法进行训练以确定网络的权值。也有人将以上两种方法结合起来，确定网络的权值。也有人将以上两种方法结合起来，用遗传算法同时优化神经网络的权值和结构用遗传算法同时优化神经网络的权值和结构。网络。网络结构优化步骤如下：结构优化步骤如下： (1)随机产生随机产生n个结构个结构，对，对每个结构进行编码每个结构进行编码，每，每个编码个体表示一个网络结构；个编码个体表示一个网络结构； (2)用多种不同的初始权值对种群中的结构进行用多种不同的初始权值对种群中的结构进行训练；训练； (3)根据训练结果或其他策略根据训练结果或其他策略确定每个个体的适应确定每个个体的适应度度； (4)选择
12、若干选择若干适应度高的个体直接进入下一代适应度高的个体直接进入下一代，其，其余按适配值确定的余按适配值确定的概率遗传概率遗传； (5)对当前种群进行交叉和变异等遗传操作，产生对当前种群进行交叉和变异等遗传操作，产生下一代种群；下一代种群； (6)重复重复(1)(5)，直到当前种群中的某个个体对，直到当前种群中的某个个体对应的网络结构满足要求。应的网络结构满足要求。 根据编码涉及的结构信息的多少，分为直接编码根据编码涉及的结构信息的多少，分为直接编码和间接编码两种方案。和间接编码两种方案。 1 1直接编码直接编码 将网络结构的每个连接编码成二进制串。方法是将网络结构的每个连接编码成二进制串。方法
13、是 首先首先设置一个网络节点数的上限设置一个网络节点数的上限N,将网络的结构表示成将网络的结构表示成一个一个NN的矩阵的矩阵C=(cij)，其中，其中N为网络的节点数，为网络的节点数，cij表示节点表示节点i与节点与节点j之间是否有连接，之间是否有连接，有连接时有连接时cij的值为的值为连接权值连接权值，无连接时无连接时cij的值为的值为0。图给出解决。图给出解决XOR问题问题的的BP网络的一种可能的结构，节点中的数为神经元编网络的一种可能的结构，节点中的数为神经元编号。由于同层的神经元之间不存在连接，对应矩阵中的号。由于同层的神经元之间不存在连接，对应矩阵中的下三角元素均为下三角元素均为0。
14、 对主对角线以上的各元素进行二进制编码，权值范对主对角线以上的各元素进行二进制编码，权值范围为围为-34，编码时可在每个权值上加，编码时可在每个权值上加3，将所有权，将所有权值平移到正值范围内，然后将各列串联起来转置为值平移到正值范围内，然后将各列串联起来转置为一行，即为一个直接编码的基因串一行，即为一个直接编码的基因串 110 010 101 111 010 100 001 100 C13 C23 C14 C24 C15 C25 C35 C45 可以看出，各元素连接的次序是使可以看出，各元素连接的次序是使同一节点的连接同一节点的连接权所对应的字符串连在一起权所对应的字符串连在一起。 2 2间
15、接编码间接编码 只编码有关结构的最重要的特性，如隐层数，只编码有关结构的最重要的特性，如隐层数，每层的节点数，层与层之间的连接数等参数每层的节点数，层与层之间的连接数等参数，而有，而有关各连接的细节留到进化规则中考虑。这种编码方关各连接的细节留到进化规则中考虑。这种编码方案可以显著案可以显著缩短字符串长度缩短字符串长度，但无疑会导致，但无疑会导致进化规进化规则复杂化则复杂化。 由于由于N N是网络节点的上限值，其中很多节点和连是网络节点的上限值，其中很多节点和连接权值是多余的。因此，训练后会有很多的接权值是多余的。因此，训练后会有很多的cijcij为为0 0或绝对值很小。在计算网络的误差时，对于绝对值或绝对值很小。在计算网络的误差时，对于绝对值很小的权值可认为连接不存在，当算法收敛后，可很小的权值可认为连接不存在，当算法收敛后，可通过删除小权值简化网络结构。这样得到的结构很通过删除小权值简化网络结构。这样得到的结构很可能是可能是多隐层网络多隐层网络。
