|
3.3 学习算子设计与改进 |
针对不同的问题,设计一套恰当的编码方案,对遗传算法的实现细节起到不可估量的作用。一般地,设计一套编码方案应满足以下三条原则。
(1)完备性:问题空间的任意一个可行解都能被编码串表示出来。
(2)健全性:所设计的任意一个编码串都能对应到问题空间的可行解中。
(3)非冗余性:编码串与可行解之间是一一对应的。
对于众多的实际问题,很难设计出能够同时满足以上三条原则的编码方案,但无论如何,任意一套编码方案必须满足完备性原则。
随着算法的广泛应用,已经提出很多编码方案,其中主要有下面几种。
1 .二进制编码
二进制编码是一种最主要的编码方法,把问题空间的可行解映射成算法可以处理的0、1组成的位串。它的优点是:编码、解码操作简单易行,使交叉、变异等操作便于实现;满足最小字符集编码原则;便于对算法从理论方面进行分析。
2 .浮点编码
染色体被编码成一个浮点数,问题空间与编码空间是一致的,通过浮点数即可反映出问题的规律。它的优点是:计算精度与编码本身无关;能处理非常规约束。
3 .格雷( Gray )编码
它是一种二进制编码的变化形式,格雷码在具备了二进制编码的全部优点的同时,还提高了自身的局部搜索能力。
由于神经网络权值的取值范围在(0,1),用遗传算法优化网络的权值,染色体编码串的长度=输入节点数×隐含层节点数+隐含层节点数×输出层节点数。对于基于数据驱动的健康状态诊断方法而言,问题本身比较复杂,用于诊断的网络模型的节点数相对较多,由此染色体位数较高。考虑到这些因素,本章采用浮点数编码方式,一方面便于直接表示权值,不丢失解码精度;另一方面降低编码负担,方便计算。
适应度函数是根据具体问题的目标函数来确定的,用于对染色体进行评价,同时选择策略也是依据适应度值进行操作的。生物体的进化过程遵循“优胜劣汰”的原则,即生物体的进化方向总是朝着个体适应度值增长的方向进行进化。这也是设计适应度函数时必须满足的条件 [16] 。
误差函数作为BP神经网络的一个重要性能指标,其值越小,表明实际输出与期望输出差距越小,即网络性能越稳定。因此,用遗传算法优化神经网络时,最为常见的适应度函数的设计形式为:
式中,y k ,k=1,2,…,N为神经网络训练得到的预测值; 为神经网络训练得到的实际结果。
为了防止进化初期随机生成的初始种群中的特殊个体统治整个群体,误导群体的发展方向,本章以线性调整原理为依据,对适应度值做如下的线性调整:
式中,f max 和 f min 分别是当代种群中最大、最小的适应度值;f 为当前个体的适应值;f′为修改后的个体适应值;β为调节系数。
由图3-1可知,当前种群中适应度的差值变大时,夹角α会变小,即个体适应度可调整的范围就会变小,也就是说种群中个体间的适应度差距降低,这样就有效防止了超正常个体统治整个群体;反之,则可调整的范围变大,从而拉开群体中个体间的差距,从而避免算法在最优解附近发生振荡现象。
图3-1 适应度调整
下面列举了几种常见的选择策略,已经MATLAB编程实现。
1 .轮盘赌选择( Roulette Wheel Selection )
任意个体被选择的概率与自身的适应度值的大小成正相关,但是又不保证适应度值大的个体一定会被选择,因为该策略是一种随机策略。
设群体大小为m,其中个体i的适应度为 f i ,则个体被选择的概率P Si 为:
2 .最优保存策略( Elitist Strategy )
该策略保证了适应度最大的个体一定被遗传到下一代,但是却牺牲了种群多样性。其基本思想是:从当前群体中选择适应度值最大的个体,直接替换掉经过交叉和变异操作后的新种群中适应度最低的个体。
3 .随机联赛选择( Stochastic Tournament )
该策略只比较适应度值的大小,且没有算术操作,其基本思想是:对种群随机地进行划分,并选择每一分块中适应度值最高的个体遗传到下一代群体中。
4 .期望值方法( Expectancy Method )
其基本思想是:按下式计算每一个体的期望选择率:
当某一个体被选中时,按下式对期望生存进行调整:
经调整后,凡是期望选择率小于等于零的个体都不参与选择操作。
针对具体的问题,酌情筛选使用的策略,可单独使用,也可混合使用。本章采用轮盘赌方法与最优保存相结合的混合策略,这样不仅克服了单一轮盘赌方法的适应度较高的个体选不中的问题,而且也能弥补以丢失样本多样性为代价的最优保存法因陷入某局部最优个体而影响算法全局搜索能力的缺陷,同时,混合后的选择策略还会提高算法的计算效率。
交叉(Crossover),指按照一定概率,从种群中随机选取两个配对个体,交换它们某些基因座上的值,从而产生新的个体。
目前,常用的几种交叉算子如下[17]。
1 .单点交叉( One-Point Crossover )
对于配对的两个个体,交叉过程仅交换彼此在编码串中随机得到的一个基因座上的值,其他位置并不改变。
2 .两点交叉与多点交叉( Multiple-Point Crossover )
两点交叉是交换配对两个体编码串中两个基因座上的值。将概念推广,多点交叉就是将用于交换的扩展到多个基因座。一般情况下不会采用多点交叉策略,因为该策略破坏优良模式的概率极大。
3 .均匀交叉( Uniform Crossover )
该策略属于多点交叉的一种变形,使用均匀分布,对每个基因座的值以相同的概率进行交换,形成新的个体。
4 .算术交叉( Arithmetic Crossover )
一种基于浮点数编码的交叉方法,通过对两个配对个体进行线性组合来产生新的个体。
设两个配对个体为 、 ,使用下式进行算术交叉,以产生两个新个体:
式中,α为一个常值参数,称为组合系数。
交叉算子作为遗传算法的核心操作,直接影响算法的性能,因此根据具体问题来设计相应的交叉算子。由上文可知,本章采用的是浮点数的编码方式,对于单点、多点的交叉不合适,受此限制,本章采用算术交叉算子,其具体操作步骤如下。
步骤 1:首先确定交叉操作的次数n c ,以交叉概率P c 来确定:
步骤2:确定要配对的个体编码串,并随机产生[0,1]的组合系数α。
步骤3:应用式(3.6)进行交叉操作,循环执行n c 次后算法结束。
变异算子(Mutation),指按照一定概率,从种群中随机选取一个个体,并随机确定一个位置进行基因突变。目前,常用的几种变异算子如下 [18] 。
1 .基本位变异( Simple Mutation )
从种群中随机选取要变异的个体,以变异概率为基准对编码串中某些基因座的值进行变异操作。
2 .均匀变异( Uniform Mutation )
通过均匀分布函数产生一组随机数,用于对个体编码的变异操作,使用该随机数替换个体编码基因座上的值。
3 .非均匀变异( Non-Uniform Mutation )
一种基于浮点数的变异方法,通过对父代基因串的随机扰动产生一个调节量。
设从种群中选择一个个体X i ,经非均匀变异后产生的新个体为 ,经随机扰动产生的调节量为ΔX i :
式中,g c 为当前进化的代数;g m 为欲进化的总代数;r为一个(0,1)间的随机数;b i 为当代种群中最大的权值;a i 为当代种群中最小的权值。
变异操作可以产生一个新的染色体编码串保证种群的多样性,是一个不能缺少的遗传步骤。受到浮点数编码方式的限制,基本位变异算子并不适合本章算法,所以这里就使用了非均匀的变异算子,其具体操作步骤如下。
步骤1:首先确定变异操作的次数n m ,以交叉概率P m 来确定:
步骤2:随机产生一个(0,1)间的数r;应用式(3.10)进行非均匀变异操作,循环执行n c 次后算法结束。