共轭梯度—自适应遗传算法研究

2.4.1　引言

遗传算法(Genetic Algorithm,以下简称GA)是美国密歇根大学J.Holland教授等基于生物界自然选择和自然遗传机制而提出的一种随机搜索方法[13]。它通过群体搜索策略,借助种群个体的信息交换和信息更新不断逼近最优解。遗传算法不依赖于梯度信息,尤其适用于处理传统搜索方法难以解决的复杂的非线性问题[14]。

由于GA是采用概率变迁规则来指导它搜索方向,因此不可避免地存在局部搜索能力不足的问题。事实上,GA是一种战略意义上的“定向”搜索方法,它通过一系列有效的搜索算子使问题由初始状态的混乱无序逐步向满意解的方向进化。而基于数值分析的优化方法则是一种局部的“定位”方法,它通过利用导数,梯度等信息使解点由初态快速逼近附近的一个极值点,如果最优解点就在初始点附近,则寻优过程是十分高效的。

如何有效地利用GA的“定向”特性和局部化数值方法的“定位”特性是一个十分有意义的研究方向,本节应用共轭梯度法和遗传算法的融合作一初步研究。

2.4.2　共轭梯度—自适应遗传算法

2.4.2.1　共轭梯度法

共轭梯度法是将共轭性与最速下降相结合,利用已知点的梯度信息,构造一组共轭方向,并沿这组方向搜索,求出目标函数的极值[15]。

定义1　设向量P i(I＝0,1,2,…,n－1)为H共轭,即

其中H为n阶对称正定矩阵,P i,P j为两个n维非零向量。

首先考虑R n中二次函数的极小化问题(QP)

可以证明,应用共轭梯度法,经n次一维搜索,将得到极小值[3]。

对于非QP,其共轭梯度算法步骤如下:

Step 1.首先给定初始点X 0和允许误差ξ＞0,令K＝0,P 0＝－▽f(x)＝－g 0;

Step 2.若‖▽f(x 0)‖＜ξ,则停止计算,并以x 0矢量为极值点,否则转Step 3;

Step 3.令P K＝－▽f(x k)＝－g k,进行一维搜索,即求。

若‖g K＋1‖＜ξ,则X K＋1为所求,停止计算,否则转Step 5;

Step 5.如果K＝n,重复初始点x 0＝X K＋1,g 0＝g K＋1,P 0＝－g K＋1,K＝0,返回Step 2,否则确定共轭方向:

Step 6.令K＝K＋1,返回Step 3。

通常βK的确定有3种方法:FR法、PRP法、DM法。其中3种方法确定βK的公式分别为:

对于正定二次函数,这三种算法是等价的。对于一般的目标函数,它们产生的方向有所不同。其中FR法最为常用,本节采用的就是该方法。

2.4.2.2　混合遗传算法

利用不同算法的优势互补,构造性能更优的混合遗传算法,国内外已开展了不少这方面的研究,如文献[16～18]。这里提出一种充分利用GA的“定向”特性和共轭梯度法的“定位”能力的共轭梯度—自适应遗传算法。

1)适应度函数

这里提出下直线型适应度函数:

对求极大值:

对求极小植:

这里F(x)为原函数,F max和F min分别为每一代的最大、最小值,C 0、C 1∈[0,1]为评价起、止值,它们可灵活设置。

上述适应度函数引入评价机制,能有效克服GA的早熟和随机漫游现象。

2)自适应遗传算子

交叉和变异算子是GA中极为重要的两种算子。其对搜索的成功与否将具有重要的作用。自适应方法反映了进化的不同阶段,同一阶段的不同个体,其交叉概率和变异概率有不同的特性,因而具有较好的寻优效果。这里作者提出如下的自适应函数(关于该函数的提出依据主要源于人决策过程中的非线性思维特征:将P c与P m的选取与适应度函数值紧密联系,对于大适应度值的个体赋予小的P c和P m加以保护,反之则赋予大的P c和P m使之加速演化,而保护力度随适应度的增大而增强。具体论述见作者的文献[19]):

其中:分别为待定系数。为各代平均适应值。k 4,可事先确定,令k 4＝P c,＝P m。下面具体求解各参数。

即

上两式相除:化简可得

从而

由x的定义和(2.34)式,可得

由x的定义和(2.35)式,可得k 2;再代入k 1－k 2＝,可得k 1:

将换成P m,可得到,,的相应表达式。

为简化计算,本节算例中令k 3＝＝1。不难得到

这里,分别为交叉概率和变异概率的最大、最小值,且k 4＝,＝,上述自适应函数具有P′≤0,P″≤0的特点,即越靠近最大值,P c,P m下降越迅速,这样有利于更好地保护各代的优良品种。

2.4.2.3　混合算法的提出与步骤

F(x)在极值点附近:

(H(x∗)为F(x)的Hessian矩阵)

呈现出二次函数特性,对二次函数,其共轭梯度具有“二次终结性质”,收敛速度迅速。而最速下降法在极值点附近却呈现出日益缓慢的搜索性能。因此将共轭梯度法等具有“二次终结性质”的局部搜索方法与GA相结合将优于最速下降法与GA相结合的混合算法。下面给出一般算法步骤:

Step 1.随机产生N个十进制(或二进制)字符串,构成初始群体。

Step 2.根据适应值函数(如式(2.25),(2.26)等)。求各个体适应值。

Step 3.利用最优个体保留和赌轮盘法进行复制,自适应遗传算子进行交叉、变异(注:当变异概率上限较小如0.05时,P m也可以采用定值)。

Step 4.对各代中最优的若干个个体(若20%)应用共轭梯度寻优,对最差的若干个个体利用移民法更新。

Step 5.重复2,3,4直到收敛或达到指定代数。

Step 6.选取群体中最好的串所对应的参数作为最优解或满意解。

2.4.3　算例

应用上述算法,作者进行了大量算例计算,总体效果良好。示例如下:考虑函数[18]:

该函数的全局极值发生在(－0.676256,－0.381582,－1.282868)。其全局极值为－12.765474。应用上述方法并与自适应遗传算法(加移民法)等比较,结果如表2.1所示。

表2.1　10次试验结果比较

本算例采用的是四位十进制串,从表1可以看出,加入共轭梯度后,寻优质量和效率大大提高。另外,与最速下降法加自适应GA的比较中,可以得出两者在寻优精度方面无明显差异,而共轭梯度——自适应GA具有更快的收敛速度(对上面算例,前者平均收敛代数为14.1代,后者为23.2代)。

作者还进行了上述算法与定遗传概率的共轭梯度——GA算法(P c＝0.8,P m＝0.1)的十次实验性能比较。其收敛代数分别为:28,27,4,4,16,18,8,3,18,6;37,32,19,5,31,20,20,50,50,36。平均收敛值分别为:－12.583468和－12.219456。可见共轭梯度——自适应GA在性能上优于定遗传概率的共轭梯度——GA算法。

针对遗传算法存在着局部搜索能力较差的缺陷,本节提出了一种“定位”与“定向”相结合的共轭梯度——自适应GA方法,较大地提高了问题的求解质量和效率。该方法在极值点附近的搜索性能优于另一种混合遗传算法——最速下降法加GA。如何在函数不可微情形下寻求“定位”与“定向”相结合的混合方法,将是需要进一步研究的问题。