遗传算法小生境技术
xt+1tik=xik+ ik
xt+1jk=xt
(1) jk+ jk其中, a (Ntt
k xik)xik>xtjkt
ik= a (xt
tt, jk=a (xik xtjk),a= ik Mk)
xik<xjkexp( a0t/T);a0为预定系数;t为当前进化代数;T为最大进
化代数;Nk为取值范围的上限;Mk为xik取值范围的下限。 其次,引入非均匀变异算子[6],重点搜索原个体附近的微小区域,增强算法的局部寻优能力,并使交叉量随进化代数的增加而变化。假设变异个体为X,变异点为xi,取值范围[Nk, Mk],变异结果为
xt
+txt+1
k
k
k= (t,Nk x)ifrandom(0,1)=0 xtk
(t,xt
k Mk)ifrandom(0,1)=0 (2) 其中, (t,y)表示[0, y]范围内符合非均匀变异的一个随机数,
按下式定义: (t,y)=y (1 r(1 t/T)b);r为[0, 1]范围内的符合均匀分布的一个随机数;T为最大进化代数;b为一个系统参数,决定了随机数扰动对进化代数t的依赖程度。
3.3 交叉概率和变异概率
对于交叉概率(Pc)和变异概率(Pm)的自适应计算,当Pc过大时,虽然产生新个体的速度快,但容易破坏较优个体的模型。当Pc过小,由于减少了种群的多样性,使算法出现早熟现象。同样Pm过小不易产生新个体,Pm过大,算法就变成随机搜索问题,而且影响收敛速度。为此,在进化过程中根据不同个体各自的适应度自适应的调整交叉概率和变异概率,计算方法如下:
k1(fmax f')P=
f'≥fc fmax f
kf'<f (3)
3 k2(fmax f)P=
f≥fm f max f
kf<f
(4)
4
其中,fmax为群体中最大的适应值;f为每代群体的平均适应值;f'为要交叉的2个个体中较大的适应值;f为个体的适应值;k1,k2,k3,k4取(0, 1)区间的值。
3.4 改进的梯度算子
梯度算法的一般定义:在种群中选择一个个体X,维数为m,假设在X染色体上产生一个随机扰动 X=( x1, x2,", xm),设目标函数为f(X)。在一般的基于微分寻优的方法中都通过按梯度向量所指的方向寻找最优解,目标函数f(X)的m维梯度向量为 f(X)=
(
f f x,,",f),假如该向量方向始终指向增长方向,说明1 x2 xm
该方向是指向最大值,朝相反的方向移动得到极小值:
Xt+1=Xt G (5)
当该向量方向指向下降的方向,则该方向指向最小值,沿着该方向移动得到最小值:
Xt+1=Xt+G (6) 其中,G为移动向量,G=η f(X);η称为步长(或梯度系
数)是一个很小的正数。
使用一个大于零扰动量 X>0,这样梯度信息可以用目标函数的一阶偏微分来近似地代替:
f(X) x=f(X+ xi) f(X)
(7) i xi
对种群中每个最优个体进行梯度优化,使个体向局部最优解不断靠近,以提高计算的精确度,步骤如下:
if (fX+ X)>f(X)thenXt+1=Xt η f(X) else if f(X+ X)<f(X)thenXt+1=Xt η f(X)
else 个体X已经到达了峰
当扰动后的目标函数大于当前目标函数,梯度向量为正,应该朝该梯度向量相反的方向移动,这时 f(X)为正数,所以有Xt+1=Xt η f(X);当目标函数小于当前目标函数时,梯度向量为负,应该朝该梯度向量的方向移动,由于这时 f(X)为负数,因此有Xt+1=Xt η f(X)。
4 GANGA算法步骤
GANGA算法的具体步骤如下:
步骤1 设置进化代数,随机产生M个初始种群P(t),求出个体的适应度Fi(i=1,2,",M)。
步骤2 根据个体的适应度对其进行降序排列,记忆前N个个体(N<M)。
步骤3 选择运算。对群体P(t)进行赌盘法选择运算,得到P'(t)。
步骤4 交叉运算。按式(3)计算Pc,并对群体P'(t)按 式(1)进行算术交叉运算,得到P''(t)。
步骤5 变异算法。按式(4)计算Pm,并对群体P''(t)按 式(2)进行非均匀变异运算,得到P'''(t)。
步骤6 小生境排挤运算。将步骤5得到的M个个体和步骤2所记忆的N个个体合并在一起,得到一个含有M+N个个体的新群体;对这M+N个个体,求出每2个个体Xi和Xj之间的海明距离:

Xi Xj=
i=1,2,",M+N 1 j=i+1,i+2,",M+N
(8) 当Xi Xj<L时,比较个体Xi和Xj的适应度大小,并对其中适应度较低的个体处以罚函数:Fmin(Xi, Xj)=Penalty。
步骤7 梯度运算。按式(5)计算梯度向量,按式(6)算法对这M+N个个体进行梯度优化。
步骤8 根据这M+N个个体的新适应度对各个个体进行降序排序,记忆前N个个体。
步骤9 终止条件判断。若不满足终止条件,则:t=t+1,并将步骤8排序中的前M个个体最为新的下一代群体P(t),然后转到步骤3;若满足终止条件,则输出计算结果,算法结束。
5 试验分析
5.1 试验函数及运行参数
Shubert 函数定义如下:
F(x5
1,x2)=∑icos[(i+1)x5
1+i] ∑icos[(i+1)x2+i] (9)
i=1
i=1
s.t
10≤xi≤10(i=1,2)
这是一个多峰函数,在其定义域内共有760个局部极小
值,其中有18个点是全局最小值,理论上全局最小解为F=-186.731。
该函数有2个自变量,染色体长度为2,编码为[x1, x2]。采用小区间生成法,把解区间划分为9个小区间,每个小区间随机初始生成M/9个体。由于Shubert函数的最小值为负,适应度函数为
F(x
1 0.05f(x1,x2)
iff(x1,x2)<0
1,x2)= 1
if
f(x,x (10)
12)≥0
—187—
· 基于梯度优化的自适应小生境遗传算法席红雷,行小帅,张清泉 (山西师范大学物理与信息工程学院,临汾 041004) 摘要:针对基本遗传算法全局搜索能力差和收敛速度慢,且...
基于个体优化的自适应小生境遗传算法_专业资料。针对遗传算法在处理复杂多峰函数... 基于梯度优化的自适应小... 2人阅读 3页 2.00 基于自适应小生境遗传...
在自适应小生境的基础上,利用进化过程中相邻个体的信息产生的试探点标记的算法...基于梯度优化的自适应小生境遗传算 法[J]. 计算机工程, 2008, 34(11): 186...
基于小生境的自适应遗传算法_法学_高等教育_教育...环境中的遗传和进化过程而形成的一种全局优化概率...由于其不依赖于梯度信息或其它辅助知识,而只需要影响...
基于自适应小生境遗传算法的物流配送路径优化研究_专业资料。针对遗传算法具有早熟的缺点和小生境遗传算法比遗传算法更费时的问题,将自适应小生境技术引入遗传算法,...
F eb 2009 面向多模态函数优化的自适应小生境遗传算法陆 青 梁昌勇 杨善林 张俊岭 230009) * (合肥工 业大学 计算机网络系统研究所 合肥 摘 要 为了解决小生...
进化优化小生境遗传算法控... 1人阅读 3页 2.00元 基于小生境遗传算法的...利用进化梯度信息调整个体向更优解进化,并根据进化代数自适应调整实数编码个体的...
( 1982 -),女, 讲师, 硕士. 研究方向: 计算数学与最优化问题. 第5 期 薛凌霄等: 基于共轭梯度法的小生境混合遗传算法 · 557· s( x i , xj ) = ...
基于自适应小生境遗传算法的混合交通网络设计双层规划模型 在现有的交通网络设计...投资额以及CO的排放总量三方面因素,建立起以三者之和最小为目标的优化函数;下层...
提出了一种改进的小生境遗传算法Ζ 该算法基于自适应交叉概率算子和变异算子, ... 并在变异量的确定上引入了梯度的概念Ζ 通过在 Shubert 函数的全局最优化问题...
热门文档