适应性权重遗传算法

2024-08-02

适应性权重遗传算法(精选8篇)

适应性权重遗传算法 篇1

0 引言

合理地进行发电机机端电压设定、电容器投切以及变压器分接头调节,达到降低电网线损,提高电压质量以及电压稳定等目标,此优化问题为多目标无功优化。它的难点是离散和连续控制变量共存,且优化模型较复杂,优化的目标是多目标,业内针对此问题的求解做了大量研究工作。

针对于无功优化存在的离散控制变量,文献[1]提出了一种内点分支定界法来求解,采用内点法寻优,结合广度优先遍历的分支定界法对离散变量进行归整处理,以找到更合理的最优解;文献[2]提出在牛顿最优潮流中用正曲率二次罚函数来处理离散变量;文献[3]对罚函数处理离散变量的原理以及如何与原对偶内点法直接结合进行了详细论述,给出了一种求解含离散控制变量的大规模电力系统无功优化的新算法;以上方法不足是很难以较大概率收敛到全局最优解。而模拟退火法[4]、Tabu搜索法[5]以及遗传算法(GA)[6,7,8]等现代优化技术以其随机寻优的策略,从原理上能保证以更大的概率收敛到全局最优解,而且易于处理离散控制变量,其中尤以遗传算法用于无功优化备受关注。文献[6]详细阐述了GA在电力系统无功优化中的应用,计算实例表明,GA以其收敛性好、全局寻优能力强等优点成为了无功优化求解的一种较好方法;文献[7]采用并行遗传算法提高优化求解效率;文献[8]将GA与内点法结合来求解无功优化,发挥了各自的优势。在多目标无功优化建模以及求解方面也做了一定工作,文献[9]将表征电压稳定的负荷裕度作为优化目标引入,构造了全面的多目标优化模型,包括线损、电压质量和电压安全性。文献[10]提出了多目标优化模型,并用预测-校正原内点法来求解。多目标无功优化的研究虽取得了一定成果,但为了更好地解决此问题还需更深入地研究与探讨。

本文研究了基于适应性权重遗传算法的多目标无功优化问题。首先,针对机端电压设定、电容器投切以及变压器分接头调节等多种手段的调控顺序做了研究;然后,引入了适应性权重的遗传算法来求解,对控制变量的编码以及选择、交叉、变异、保留等基本操作了探讨;对多目标优化各个目标权重的设定问题,结合遗传算法特点,给出了随着代数进化,适应性确定权重的策略;最终,仿真算例验证了本文所提求解算法以及思路的合理性。

1 多目标无功优化模型

式中:F为多目标,优化目标可表示为min(F1,F2,F3),分别表示降低线损、提高电压稳定性和改善电压质量,其中,F1=Ploss(.)为线损;M(.)为连续潮流计算得到的表征电网静态电压稳定性的负荷裕度,F2=-M(.);(Vi(.)-Ve)2表征为节点i的电压质量;F3即为电网所有节点的电压质量和;Vg为发电机节点(包括PV节点和平衡节点)设定的机端电压幅值;c为投切电容器的等效电纳;b为调节变压器的分接头变比;Vg、c、b三者为控制变量;f(.)为潮流等式约束;θ为所有节点电压的相角;Vl为负荷节点电压幅值;和Vl分别是负荷节点电压的上、下限,给定为1.05和0.95;和Vg分别为发电机节点电压的上、下限,给定为1.1和0.9;QG是发电机的无功输出;QG和QG分别为发电机无功的上、下限;和cj分别是可供投切电容器等效电纳的上、下限;bt和bt分别是可供调节变压器变比的上、下限。

求解综合优化模型(1)的难点:1)从优化目标,等式以及不等式约束,还有控制变量等来看,优化模型(1)从数学上来说是复杂优化问题,能否基于电力系统物理问题实际,来简化此模型求解;2)电容器投切c和变压器分接头调节b都为离散控制变量,而机端电压设定Vg为连续控制变量,此优化为离散和连续控制变量混合的优化,需合适的求解算法;3)这是一多目标优化问题,如何来合理地确定各目标权重。

2 连续与离散变量的协调调控

为了满足无功分层分区、就地平衡的原则,应优先动作变电站内的离散控制设备:投切电容器和调整变压器分接头,在此基础上再进行连续控制设备的调节,即发电机机端电压的设定(无功输出)。

当危及系统安全的故障发生时,由于离散控制设备单台可调节容量较小、响应动作时间慢,要使系统快速恢复到安全,更多地依赖响应速度快、可调节容量大的发电机来调节。所以,从提高系统安全性角度来讲,在正常情况下也应该优先动作离散控制设备,为发电机响应安全事件留出较大的调节裕度。

综合上述两个原因,离散控制设备应优先于连续控制设备动作。进一步,提出如下的离散控制变量优化和连续控制变量优化交叉迭代求解的思路:

1)将连续控制变量:发电机机端电压设置为额定电压值1,即Vg(0)=1;设定优化迭代次数k=1;

2)将Vg(k-1)代入优化模型(1),只考虑离散变量:电容器c(k)和变压器变比为控制变量b(k),定义此模型为离散变量优化模型(1.1);求解优化模型(1.1),得到第k次迭代的离散控制变量优化解c(k)、b(k);

3)将c(k)、b(k)代入优化模型(1),只有连续变量Vg:机端电压为控制变量,定义此模型为连续变量优化模型(1.2),求解此优化模型,得到连续控制变量Vg(k);

4)如果k>1,且满足max(|Vg(k)-Vg(k-1)|)<εc,max(|c(k)-c(k-1|)<εc,max(|b(k)-b(k-1)|<εb则退出迭代,优化解为Vg(k),c(k),b(k);否则当k>1,且上述任意max(.)<ε中有不成立的,则继续下一步;

5)优化迭代次数k=k+1,转向步骤2)。

3 基于适应性权重遗传算法的求解

遗传算法宜处理优化模型较复杂,且控制变量含离散变量的优化问题的求解,更可能从全局角度寻优。

3.1 控制变量的编码

采用二进制编码,设整数变量区间为[a,b],区间长度为b-a,将此区间分为b-a等份:

这样编码的二进制串长至少需要k位。

k位二进制串(bk-1bk-2…b0)转化为[a,b]区间内对应的整数分为如下两步:

1)将此二进制串代表的二进制数化为10进制数:

2)i’对应的区间[a,b]内的整数i:

3.1.1 机端电压的编码方案

求解连续变量优化模型(1.2),对其中的控制变量Vg进行编码。和Vg分别为1.1和0.9,且设可调节的步长为0.01,则有(1.1-0.9)/0.01=20,24<20-0<25,所以对于一台发电机机端电压二进制的编码位数为5位,当有n台发电机机端电压可调时,则编码位数为5×n。机端电压编码方案如下:

Vn,4Vn,3Vn,2Vn,1V n,0|Vn-1,4Vn-1,3Vn-1,0||V1,4 V1,3 V1,2 V1,1 V1,0其中的(Vn,4Vn,3Vn,2Vn,1Vn,0)代表一台发电机机端电压的二进制编码,且V=0或1,通过式(3)、(4)将二进制编码还原为发电机机端电压设定值:

则有发电机机端电压为:

Vg=0.9+i×0.01

此发电机机端电压编码方案同时也隐含了机端电压不等式约束。

3.1.2 电容器投切的编码方案

求解离散变量优化模型(1.1),对其中的控制变量之一电容器投切进行编码。设节点ij(j=1,2,…,n)处配置电容器,在节点ij处的单位电容器组等效电纳为ce,j,电容器组的容量范围为,如此,得到待投切电容器组数的整数范围区间。一般假设zc,j=0。

由式(2)有:

则在ij节点电容器编码所需的二进制串长度为kj(j=1,2,…,n)。

在n个节点处投切电容器组数的编码方案为:

,其中c是0、1的二进制数。由式(3)、(4)可从左至右依次求得ij节点处投切的电容器组数zj(j=n,n-1,…,1),再结合单位电容器组等效电纳为ce,j,即可得到投切的电容器电纳值cj。此电容器编码方案同时也隐含了电容器的不等式约束。

3.1.3 变压器变比的编码方案

求解离散变量优化模型(1.1),对其中的控制变量之一变压器变比进行编码。与式(2)电容器投切编码思路类似,可得到变压器分接头档位的编码方案为:

其中:b是0、1的二进制数。由式(3)、(4)可从左至右依次求得各个可调节变压器分接头档位zt(t=n,n-1,…,1),再结合档位变比步长be,t,即可得到各个变压器的变比bt。此变压器档位编码方案同时也隐含了变压器变比不等式约束bt≤bt≤。

3.1.4 电容器投切和变压器变比的综合编码方案

离散变量优化模型(1.1)含有电容器和变压器分接头两类离散控制变量,所以综合式(2)、(3)的编码方案得到求解优化模型(1.1)的电容器投切和变压器分接头调节的综合编码方案:

可简写为:

BnBn-1…B1‖CnCn-1…C1

3.2 适应度函数

由第2节可知:优化模型(1)的求解可分解为离散控制优化模型(1.1)、连续变量优化模型(1.2)的分别求解,并且交叉迭代直至收敛。无论优化模型(1.1)还是(1.2),都是一多目标优化,将最小化3个目标F1、F2、F3添加负号,变为最大化3个目标,分别定义为ZF1、ZF2和ZF3:

ZF1(Vg,c,b)=max(-F1)ZF2(Vg,c,b)=max(-F2)ZF2(Vg,c,b)=max(-F2)

对于遗传进化的每一代种群个体,二进制编码解码得到控制变量Vg,c,b,潮流计算后可求得优化目标:线损F1,电压质量F3;以当前潮流计算结果为基态点,定义系统基态负荷为L0,设定负荷变化方向和响应负荷变化的发电计划模式,利用连续潮流计算得到电压崩溃点,定义系统崩溃点负荷为L*,优化目标F2为负荷裕度M,则M=L*-L0。对应进化种群中每个个体的各个优化目标值得到。

更为关键的是如何确定多目标优化中各个目标的权重系数。本文采用文献[11]提出的适应性权重遗传算法来求解多目标优化,利用遗传算法的特点与优势,随着代数进化,不断改变权重系数,给出适应性确定权重的策略。

遗传进化中,每代产生一定数目个体组成种群P。当前种群所有个体优化目标ZF1的最大值和最小值分别为:

式中:Vg,j,cj,bj是种群中任意个体j的编码方案所对应的机端电压设定值、电容器投切量、变压器变比。

类似可得到zF2max、zF2min以及zF3max、zF3min。

在当前代,每个目标的适应性权重用下式表示:

对于种群P给定个体j对应的Vg,j,cj,bj,有:

ZF1=F1(Vg,j,cj,bj)ZF2=F2(Vg,j,cj,bj)ZF3=F3(Vg,j,cj,bj)

适应性权重的多目标优化的目标函数:

在文献[11]中已有论述,如此适应性确定多目标权重的方法,可将多目标优化常见的产生式求解思路和启发式决策思路的优点集于一体,在进化过程中根据当前种群一些有用的信息对目标偏好进行持续的细化,适应性调整权重以获得朝正向理想点的搜索压力,不同于传统的固定权重的多目标优化。

不等式约束通过适应性罚函数给出,如:

约束式(6)可统一计作gi(Vg,c,b)≤bi,i=1,2,…,M。对于个体Vg,j,cj,bj,适应性罚函数为:

式中:

∆bi(Vg,j,c j,b j)是个体Vg,j,cj,bj对第i个约束的违背值;∆bimax是当前种群中所有个体对约束i的最大违背值;ε是一个小正数,用来避免罚函数中出现被零除的情况。

综合式(5)、(7),对于个体Vg,j,cj,bj,带有罚函数的适应度函数为:

3.3 其它基本操作策略和有关参数的设置

1)选择操作:它模拟了生物进化过程中自然选择的规律,此操作决定适应度函数值越大的个体被选中的机会越多,从而使得优良特性得以遗传,体现了自然界中适者生存的道理。本文采用较成熟的轮盘赌方法。

2)交叉操作:它是将两个染色体重新组合的操作。此操作可产生新的个体,交叉体现了自然界中交换信息的思想。本文采用多点交叉方法,且离散控制变量综合编码的S编码和C编码各自分别进行交叉操作。

3)变异操作:它模拟了生物进化过程中偶然的基因突变现象,变异能增加群体中个体多样性。本文采用一点按位变异操作,以给定的变异率随机选择一个已经进行选择操作的染色体作为父本,再随机选择该个体的某二进制位进行“0”变“1”,“1”变“0”的操作,形成一个新的染色体。

4)保留操作:此操作能保证遗传优化以更大的概率收敛到全局最优解。完成选择,交叉以及变异操作后,根据给定的保留率,将上一代中若干最优(或次最优)个体直接复制到本代,随机替换本种群中某些个体,以保证本代的最优(或次最优)个体至少不会比上一代差。

把适应性权重遗传算法用于多目标无功优化求解前,需设定遗传算法参数,如种群的规模、选择率、交叉率、变异率以及保留率等,它们的设定对优化最终结果是有影响的。

这其中以交叉率以及变异率的设定更为重要,本文采用一种自适应的交叉率和变异率的设定,使优化能以较快的速度、更大的概率趋于全局收敛。在遗传进化初期,交叉率应设定较大,变异率应较小,以确保计算过程的平稳进行。在进化后期,种群体中的染色体已趋于稳定,可能收敛于局部最优解,此时交叉率发生概率可降低,而变异率应设定大一些,以便有机会跳出局部最优解。自适应的交叉率和变异率的计算公式为:

式中:k为遗传进化代数;∆u为第k-1次进化代时种群中所包含染色体的适应度函数最大值和最小值之差;Pc(0)、Pc(k)、Pm(0)、Pm(k)分别表示交叉率、变异率的初始值和第k次进化代时的数值,初始值取Pc(0)=0.9,mP(0)=0.001;Pc,min、Pm,max分别为交叉率的最小值和变异率的最大值,可分别取0.6,0.1。Nc、Nm为给定常数,用于模拟交叉率、变异率随适应度函数分散情况而变化的快慢程度,可取Nc=Nm=20。式(9)、(10)表示交叉率和变异率随种群中染色体适应度函数值分散程度而变化,分散程度变小,交叉率变小,而变异率变大。

而种群规模大小、选择率、保留率等的设定结合如下具体的仿真算例给出。

4 仿真算例

4.1 IEEE30节点算例

采用IEEE30节点标准算例进行本文所提求解算法以及思路的仿真验证,标准算例数据参见文献[12]。C++语言编写了此研究相关的算法程序。

表1给出了优化前的网络线损、电压质量以及负荷裕度目标值。

采用连续变量优化模型和离散变量优化模型分别求解,两模型交叉迭代优化,直至收敛,得到最优控制解。表2列出了连续控制变量和离散控制变量编码方案。

经过多次运算,得到遗传算法寻优性能较优的参数设定值,其中种群规模大小为60,而选择率设定为0.6,保留率设定为0.05~0.1,变异率和交叉率如前所述,自适应给定。表3给出遗传算法算例计算时间耗费、以及迭代次数等信息。

经过5次离散变量和连续变量的迭代优化,收敛得到最优解,表4给出控制变量的最优解结果。

优化后各优化目标值和优化前表1各目标值相比,有了较大改善,见表5。

而图1的(a)、(b)、(c)分别是优化过程中,随着迭代次数的增加,目标逼近最优值的过程。

4.2 IEEE118节点算例

为了对本文所提求解思路的优缺点有更全面的了解,再进一步应用IEEE118节点进行仿真与验证。IEEE118节点系统参数见文献[13],其中,发电机54台,可调变压器9台,可投切电容器14台,它们为控制变量。限于篇幅,如表6~8只是给出优化计算部分结果:如控制变量编码、控制变量优化解、优化目标解,同时表9给出IEEE118节点遗传优化的时间耗费。

表6中各发电机、变压器编码相同,而电容器由于上、下限,以及单位调节容量不同,各电容器编码各异,限于篇幅表中只列出部分电容器的编码。连续变量、离散变量编码总长度分别合计为270、104,是IEEE30节点相应编码长度的9倍、4.16倍。

表7中除了列出全部变压器变比的优化解,限于篇幅,只列出了部分发电机机端电压设定、电容器投切的优化解。

从表8可看出,经过本文所提遗传算法的优化,线损、电压质量以及负荷裕度三个优化目标值较优化前有较好效果。

遗传算法交叉率、变异率自适应确定,而其余参数,如种群规模、选择率、保留率等同IEEE30节点的设置。从表9可看出,随着系统规模的扩大,控制变量增加,相应地遗传进化每一代个体的编码长度也加长,则交叉操作、解码以及求解适应度函数的潮流计算、连续潮流计算等时间耗费都会增加。

4.3 算例总结

从以上两个算例对比可看出,遗传算法固然具有多点随机搜索的全局寻优能力,但代价是计算效率较低,且随着电网规模的增大,此不足更明显。日后的研究将集中于提高优化算法效率:如遗传算法中离散变量和连续变量并行优化;如连续变量优化可考虑采用效率更高的内点法,而遗传算法只用于离散变量优化等。

5 结论

本文提出了基于适应性权重遗传算法求解多目标无功优化的思路。研究得到离散控制变量和连续控制变量协调调控的顺序,将原优化模型分解为离散变量优化模型、连续变量优化模型,两个模型分别求解并交叉迭代,直至得到优化解。提出了用遗传算法来求解,并研究了求解此优化问题的遗传算法编码、以及选择、交叉、变异、保留等操作的策略,给出了遗传进化过程中多目标权重自适应确定的方法,用C++语言编写了求解算法程序,IEEE30节点、IEEE118节点仿真算例验证了本文所提求解算法和思想用于多目标无功优化的合理性。

摘要:研究一种多目标无功优化问题的求解方法。基于无功分层分区平衡以及保证紧急情况下电网安全的原则,给出了在电网正常情况下优先投切电容器、调节变压器分接头,然后设定机端电压的优化调控顺序,进一步提出将优化问题分解为连续变量优化和离散变量优化问题,并分别求解,迭代直至收敛的求解思路。鉴于多目标无功优化模型的复杂性,以及连续、离散控制变量并存,采用遗传算法求解,重点研究了控制变量的编码方案以及选择、交叉、变异以及保留操作策略。针对于多目标无功优化各个目标权重难以确定问题,又进一步引入了适应性权重遗传算法,随着遗传代数的进化算法能自适应地给出各个目标权重。仿真算例验证了文中所提的多目标无功优化求解方法的合理性。

关键词:多目标无功优化,电容器投切,变压器分接头调节,机端电压设定,适应性权重遗传算法

适应性权重遗传算法 篇2

空中目标识别是现代防空作战的重要研究内容.本文利用不同类型目标产生的`多类型传感器的数据信息对目标进行识别.为了训练神经网络目标识别分类器,将遗传算法和BP算法相结合,提出了一种新的自适应遗传BP算法,利用这种神经网络来确定指标的权值.仿真试验结果表明,基于自适应遗传BP算法神经网络的识别是一种简单、可靠的目标识别方法,具有很好的目标识别效果.

作 者:马峰 李富荣 张安 MA Feng LI Fu-rong ZHANG An 作者单位:马峰,MA Feng(西北工业大学电子信息学院・陕西西安・710072;92635部队・山东青岛・266041)

李富荣,LI Fu-rong(海军航空工程学院青岛分院・山东青岛・266041)

张安,ZHANG An(西北工业大学电子信息学院・陕西西安・710072)

适应性权重遗传算法 篇3

粒子群优化PSO是由Kennedy和Eberhart等人提出的一类模拟群体智能行为的优化算法。其思想来源于对鸟群捕食行为的研究,与遗传算法和蚁群算法相比,PSO容易实现并且可调整参数较少,因此被广泛应用。

文献[1,2,3]指出,目前PSO的研究主要集中在三个方面:一是算法的改进研究;二是算法的性能分析;三是算法的应用研究。而算法的性能分析主要针对参数不同取值组合对算法性能的影响。惯性权值是粒子群算法最重要的可调整参数之一。文献[4]指出较大的权值有利于提高算法的全局搜索能力,而较小的权值会增强算法的局部搜索能力。为了找到一种能在全局搜索和局部搜索之间取得最佳平衡的惯性权值选取方法,研究人员进行了大量的研究工作,先后提出了线性递减权值(LDIW)策略、模糊惯性权值(FIW)策略和随机惯性权值(RIW) 策略。而已有的搜索策略都是将粒子群看作一个整体来调整惯性权重,没有考虑到不同适应度的粒子需要不同的惯性权重,忽视了问题复杂度和群体规模等重要因素。本文分析了PSO算法中的惯性权重与种群规模、粒子适应度以及搜索空间维度的关系,把粒子惯性权重定义为这三者的函数,并结合动态管理种群的策略提出了改进的粒子群算法。新算法在每次迭代后根据当算法搜索状态更新每个粒子的惯性权重,实现了自适应调整全局搜索与局部搜索能力。通过与LDIW、 FIW 、RIW等调整算法在常用多峰测试函数上的实验结果证明,新算法具有较强的全局寻优能力与较高的搜索效率。

1 经典粒子群算法

PSO算法是一种进化计算技术,源于对鸟群捕食的行为的模拟。搜索空间中每个粒子代表一个可能解,粒子在解空间中移动的过程就是搜寻最优值的过程。所有的粒子都有一个表示当前在解空间中位置的属性Xi=(xi1xi2,… ,xin),根据粒子当前位置会产生一个粒子适应度以反映粒子位置即解的优劣。每个粒子还有一个速度向量Vi=(vi1,vi2,…,vin)决定其运动的方向和运动的快慢。首先粒子群初始化为一群随机粒子(随机解),然后通过迭代来寻找最优解。在每一轮的迭代中,粒子通过速度更新当前位置,并通过适应值函数计算出其适应度,然后根据式(1)更新其当前速度:

Vi=ωVi+crand()×(Pbesti-xi)+

crand()×(Gbest-xi) (1)

接着用式(2)更新粒子位置Xi:

Xi=Xi+Vi (2)

其中Pbesti表示粒子i的个体最优值,即粒子i目前为止在搜索空间中到过的最佳点,Gbest表示整个粒子群的全局最优值,即整个粒子群到目前为止在搜索空间中到过的最佳点。C1 和C2是两个正常数,称为学习因子。 rand() 表示0 到1之间的随机数。另外,ω称为惯性因子,ω值较大,全局寻优能力强,收敛较慢;反之局部寻优能力较强,收敛较快。

2 惯性权重调整策略

惯性权重ω是PSO算法中调整全局搜索与局部搜索的最重要参数。文献[4]指出,较大的惯性权重有利于全局探索,但效率较低;较小的惯性权重能够加速算法的收敛,但是容易陷入局部最优。如何设置合理的惯性权重,是避免陷入局部最优并高效搜索的关键。在实际问题背景下,惯性权重如何设置,要同时分析众多因素和当前搜索状态。其中,粒子适应度、种群规模以及搜索空间维度是表征当前搜索状态的重要参数。下面分别定性分析这三者与惯性权重的关系。

粒子适应度是反应粒子当前位置优劣的一个参数。对于某个具有较高适应度的粒子Pi,在Pi所在局部区域可能存在能够更新全局最优的点Px,即Px所表示的解优于全局最优。为使全局最优能够迅速更新,迅速找到Px,应当应减小粒子Pi惯性权重以增强其局部寻优能力;而对于适应度较低的粒子,当前位置较差,所在区域存在优于全局较优解的概率较低,为了跳出当前的区域,应当增大惯性权重,增强全局搜索能力。

种群规模是决定粒子对搜索空间覆盖程度关键因素。种群规模较大时,种群多样性较高,粒子所在区域覆盖全局最优解的概率较大,则应该减小惯性权重,提高局部搜索能力,实现快速收敛于全局较优;种群规模较小时,尤其对于多峰函数,粒子通常不能有效覆盖整个搜索空间,则应该增大惯性权重,提高全局搜索能力,避免陷入局部最优。

由文献[5]可知,当搜索空间维度较大并且问题较复杂时,PSO常常收敛过早,很容易陷入局部最优。如何根据不同复杂程度的问题背景,在搜索效率和寻优能力之间寻求较好平衡极为重要。对于具有高维度搜索空间的复杂问题,应该减小惯性权值以提高全局搜索能力,避免过早收敛陷入局部最优。相反,当搜索空间维度较少时,应该增大惯性权值实现快速收敛以提高搜索效率。

由以上分析可知,粒子适应度、种群规模以及搜索空间维度与惯性权重有密切关系,可根据这些参数的值实现自适应调整惯性权重。式(3)将惯性权重定义为粒子适应度、种群规模以及搜索空间维度三者的函数:

ωi=1aFi/(D×i=1i=nFi)-exp(-n/b)+1(3)

其中ωi表示第i个粒子惯性权重,Fi表示第i个粒子适应度,D表示搜索空间维度,n表示粒子数目,ab为经验参数。算法在每次迭代后通过式(3)更新所有粒子的惯性权重,从而实现了对局部搜索和全局搜索的能力自适应调整。

3 动态管理种群策略

在PSO算法的某一次迭代中,如果有部分粒子位置不佳,致使其Pbesti连续多次没有更新,这些粒子当前所在位置较差,并不能为Gbest的更新作出贡献,为提高算法搜索效率,可以把这些粒子删除。相反,如果Gbest连续多次没有被更新,此时粒子群体可能陷入局部最优,需要增加粒子来增加启发信息,加快Gbest的更新。因此,提出动态种群管理策略,具体描述如下:

1) 当Gbest连续s次没有改变,说明现有种群需要新的粒子来提供启发信息,则动态添加一个粒子,并用个体最优Pbesti更新最频繁的两个粒子的位置组合成初始位置,以全部粒子的平均速度作为初始速度;

2) 当Gbest连续s次改变,说明现有种群启发信息已经充足,为提高算法运行效率,则动态删除Pbesti更新最不频繁的粒子。

4动态管理种群的自适应惯性权重粒子群算法描述

根据上述分析,提出动态管理种群的自适应惯性权重粒子群算法—DSAPSO,算法描述如下:

DSAPSO (D, MAX,MIN,K, Pn,s)

输入:求解空间维度D,粒子数目上限MAX,粒子数目下限MIN,初始粒子数目Pn,粒子动态管理敏感指数s

输出:问题的解。

步骤:

(1) 随机生成Pn个粒子的初始位置及初始速度;

(2) 计算粒子适应度Fi,更新个体最优Pi及全局最优Pg;根据式(3)计算粒子惯性权重ωi;

(3) 根据粒子适应度更新个体最优Pi及全局最优Pg;

(4) 根据式(1)更新粒子速度,根据式(2)更新粒子位置;

(5) 动态管理种群:

① 当Gbest连续s次改变,且Pn>MIN,则动态删除Pbesti更新最不频繁的粒子。

② 当Gbest连续s次没有改变,且Pn<MAX,则增加一个粒子,用Pbesti更新最频繁的两个粒子的位置组合成初始位置,以全部粒子的平均速度作为初始速度。

③ 当Gbest连续s次没有改变,且Pn=MAX,则删除Pbesti更新最不频繁非全局最优粒子,然后动态添加一个新的粒子,并用Pbesti频繁被更新的两个粒子的位置组合成初始位置,以全部粒子的平均速度作为初始速度。

(6) 若达到结束条件则结束,否则返回(2)。

算法整体采用动态管理种群策略,并在每一次迭代中计算式(3),分别更新每个粒子的惯性权重。

5 实验结果以及分析

5.1 实验环境以及实验参数设置

在实验中,取粒子群规模MAX为30,MIN为5,其他算法粒子数目固定为30;设置c1=c2=2 。实验选取了六个不同特点的常用测试函数,如表1所示。其中,Sphere为简单的单峰函数, 在原点达到极小值;Rosenbrock为非凸的病态函数,在xi=1时达到极小值;Griewank在xi=0时达到全局极小值,当xikπ i(i=1,2,…,n,k=1,2,…,n)时,达到局部极小值;Schaffer’f6的全局极大值在(0,0),它的全局最优点被次优点所包围;Rast rigrin为多峰函数, 当xi=0时达到全局极小值,在其周围存在多个局部极小点;其中,维数是各个函数求值的空间维度D,目标值是算法结束条件,即算法搜索到的解所必须达到的值。

5.2 实验方案

采用本文提出的DSAPSO算法与下面三种惯性权重调整算法进行比较:惯性权重线性下降的标准粒子群算法LWPSO (文献[5]) 、随机惯性权重粒子群算法RWPSO(文献[6])以及带压缩因子的粒子群算法CFPSO(文献[7])。对于四种不同算法,采用两种方案进行试验:方案一是固定迭代次数为1000次,计算每种算法运行结果的平均值;方案二是确定每个函数的优化目标值,计算每种算法的评价迭代次数,超过5000次记为无穷大。每种方案独立运行10次计算结果平均值。

5.3 实验结果汇总

表2统计了固定迭代次数为1000次时,四种算法求解的平均值和最差的一次求解结果。表3统计了四种算法搜索到表1中对每个函数预订的目标值时,迭代的次数和所用的时间(单位:秒),如果迭代次数超过5000,则将次数和时间都计为无穷大。图1记录DASPSO算法在Sphere函数上求解时,PSO粒子数目随迭代次数的变化。

5.4 实验结果分析

从表2中可以看出,本文提出的DASPSO算法,由于惯性权重选择较为恰当,全局寻优能力较强,在五个函数上求解普遍优于其他算法,而且最差解与平均解相差不大,较为稳定。RWPSO 算法采用随机策略,增加种群多样性,在对多峰函数优化上算法取得不错的结果;但对单峰Sphere函数效果较差,其主要原因算法在后期仍然采用随机惯性赋值策略,没有增强局部搜索能力,很难收敛到较优解。表2比较了四种算法的全局寻优能力与收敛速度。可以看出,DASPSO算法迭代次数与所用时间远少于其他算法。这是由于在迭代过程中,动态删除部分无效粒子并不断补充新粒子,粒子数目一直少于其他算法,但每个粒子都非常活跃,全局最优更新非常快。图1记录了在Sphere函数上搜索时粒子数目的变化折线图,可以看出,在搜索过程中粒子数目很少达到30,较少的粒子减少了计算粒子适应度以及粒子移动等时间开销,极大地提高了搜索效率。

6 结 语

惯性权重是决定PSO算法全局寻优与局部寻优的重要参数。本文提出了根据搜索状态在一种每次迭代后自适应调整惯性权重,进而更好地平衡全局搜索和局部开发的改进PSO算法。改进的算法采用了动态管理种群策略,极大地提高了搜索效率。新算法与LDIW、 FIW 、RIW等调整算法在常用多峰测试函数上的实验结果证明,新算法具有较强的全局寻优能力与较高的搜索效率。

摘要:为较好平衡粒子群算法中全局搜索能力与局部搜索能力,分析了PSO(Particle Swarm Optimization)算法中的惯性权重与种群规模、粒子适应度以及搜索空间维度的关系,并把粒子惯性权重定义为这三者的函数。通过在每次迭代后更新每个粒子的惯性权重,实现了自适应调整全局搜索能力与局部搜索能力,并结合动态管理种群的策略提出了改进的粒子群算法。通过在多个常用测试函数上与已有惯性权重调整算法测试比较,证明新算法具有较强的全局寻优能力与较高的搜索效率。

关键词:粒子群算法,自适应惯性权重,种群规模,搜索空间维度,粒子适应度,动态管理种群

参考文献

[1]Angeline P J.Using selection to improve particle swarm optimization[C]//IEEE International Conference on Evolutionary Computation.Anchorage,Alaska,USA,2007:84-89.

[2]Jacques Roget,Jacob SVesterstr.A Diversity guided Particle Swarm Op-timizer,the ARPSO[R].Technical Report No.2002202,2008:65-69.

[3]Shi Y,Eberhart R.A modified particle swarm optimizer[C]//IEEEWorld Conf on Computational Intelligence.Piscataway:IEEE,2005:69-73.

[4]Zhang L P,Yu H J,Hu S X.A new approach to improve particle swarmoptimization[C]//Lecture Notes in Computer Science.Chicago:Springer2Verlag,2006:134-139.

[5]盛跃宾,陈定昌,等.有等式约束优化问题的粒子群优化算法[J].计算机工程与设计,2006,27(13):25-29.

[6]刘洪波,王秀坤,谭国真.粒子群优化算法的收敛性分析及其混沌改进算法[J].控制与决策,2006,21(6):636-640.

[7]韩江洪,李正荣,魏振春.一种自适应粒子群优化算法及其仿真研究[J].系统仿真学报,2006,18(10):2969-2971.

适应性权重遗传算法 篇4

基于群体智能理论的计算技术的研究成为了近几年研究的热点, 蚁群算法、粒子群优化算法、混合蛙跳算法等等都是基于群体协作的搜索算法。粒子群优化算法[1,2] (particle swarm optimization, PSO) 是由Kennedy和Eberhart于1995年提出的一种全局优化算法。相对于其他算法而言, PSO算法原理比较简单, 需要调节的参数较少, 容易实现, 而且PSO算法中的粒子具有记忆功能, 可以保留局部最优和全局最优信息, 协同搜索最优解。不过PSO算法也存在着缺点, 由于它收敛速度快, 容易陷入局部最优, 在进化后期, 由于种群多样性的减少, 搜索精度逐渐降低。

针对以上PSO算法的缺点, 研究人员提出了各种改进的方法。Shi等[3]将惯性权重引入了速度的更新公式中;Van den Bergh等[4]提出了合作粒子群算法, 引入多种群等等。在本文中, 通过借鉴遗传算法[5]的特点及合理平衡算法的搜索能力, 提出了一种新的改进的混合粒子群算法, 即基于交叉和自适应权重的混合粒子群优化算法。

1 基本粒子群优化算法

PSO算法是源于鸟的捕食行为, 将每个待优化问题的解都看成是空间中的一只鸟, 并抽象成一个粒子, 每个粒子有一个初始的位置和速度, 并有一个由被优化的函数 (即适应度函数) 决定的适应值, 粒子的优劣由此适应值决定。

PSO算法是通过迭代找到最优解, 但它具有自己独特的搜索方式。首先, 随机初始化一群粒子, 粒子们知道自己目前所处的位置以及目前自己发现的最好位置, 此外粒子还知道此时整个粒子群体中的最好位置。假设在d维搜索空间中的第i个粒子的位置和速度分别是Xi=[xi, 1, xi, 2, …, xi, d]和Vi=[vi, 1, vi, 2, …vi, d], 每一次的迭代过程中, , 粒子是通过两个最优解来更新自己, 一个是粒子本身找到的最优解, 称为个体极值pbest, Pi= (pi, 1, pi, 2, …, pi, d) ;另一个是整个种群目前的最优解, 称为全局最优解gbest, Pg= (pg, 1, pg, 2, …, pg, d) 。粒子根据下面两个公式[3]更新自己的速度和新的位置。

其中, w为惯性权重因子, c1和c2为学习因子, 一般c1等于c2, 通常取值为2。

基本粒子群优化算法基本流程如下:

步骤一:随机初始化所有粒子, 粒子的种群规模设为N, 初始化粒子的位置和速度。

步骤二:对种群中的所有粒子进行评价, 将当前各个粒子的位置和适应值存在各粒子的pbest中, 将整个pbest中适应值最优个体的位置和适应值存于gbest中。

步骤三:利用上面的公式 (1) 和公式 (2) 更新粒子的速度和位置。

步骤四:根据适应度函数评价种群中的所有粒子。

步骤五:对于每个粒子, 将其适应值与经历过的最好位置pbest的适应值进行比较, 如果当前的适应值更优, 则将当前粒子的位置和适应值作为当前的最好位置pbest保存。

步骤六:将每个粒子的适应值和全局经历的最好位置gbest的适应值进行比较, 如果当前的适应值更优, 则将当前粒子的位置和适应值作为全局的最好位置gbest保存。

步骤七:如果达到终止条件, 则停止算法, 输出结果, 否则返回步骤三继续进行搜索。

2 改进的粒子群优化算法

2.1 交叉因子

在粒子群优化算法中, 整个搜索的过程是跟随当前的最优解的过程, 所以算法可以更快的收敛于最优解, 然而过快的收敛却使算法容易陷入“局部极值”。再者, 由于粒子群优化算法不同于遗传算法、差分进化算法[6]等群体进化算法有交叉和变异操作来作用于个体, 以产生一个新的种群, 从而维持种群的多样性。粒子群优化算法在种群多样性降低的情况下搜索精度也会降低。为了解决上述问题, 借鉴遗传算法中的交叉的思想, 在算法的每一次迭代过程中, 按照一定的交叉概率选取指定数量的粒子, 将选取的粒子随机两两进行交叉, 产生相同数目的子代粒子, 用新产生的子代粒子替换其父代粒子, 从而产生新一的种群。

子代粒子的位置可以由下面公式得出:

child (x) =p*parent1 (x) + (1-p) *parent2 (x)

或child (x) = (1-p) *parent1 (x) +p*parent2 (x)

p为0~1之间的随机数。

子代粒子的速度由下面公式计算得出:

undefined

或childundefined

2.2 自适应权重

粒子群算法的全局探索和局部改良能力的平衡决定了算法的搜索性能, 对于群体智能算法, 其迭代搜索过程可以归纳为社会协作、自我适应和竞争三个基本环节[7]。“自我适应”是指个体主动或者被动的调节自身的状态以便于更好的适应环境。对于粒子群算法而言, 其惯性权重部分即属于粒子的自我适应。如果惯性权重w较大, 有利于跳出局部最小点, 便于进行全局搜索;如果惯性权重w较小, 则有利于算法在当前的范围内进行局部精确搜索。Shi 和Eberhart提出了线性递减的权重[8], 但是这种方法需要反复的试验确定最佳的值, 而且如果在最初搜索阶段找不到最优值, 随着w的减小, 收敛能力增强, 易陷入局部最优。 黄轩等[9]提出了随机惯量取值策略, 然而这种方法随机性太强。本文中我们运用非线性的动态权重策略, 即自适应惯性权重。当所有粒子的适应值差异较大时将惯性权重减小, 当所有粒子的适应值趋于一致或趋于局部最优时, 将惯性权重增加。惯性权重w如下表示:

undefined

上述中wmin、wmax分别表示w设为最小值和最大值, f表示粒子当前的适应值, favg和fmin分别表示当前所有粒子的平均适应值和最小适应值。运用上述的方法来设置权重, 当粒子适应值优于平均适应值时其惯性权重较小, 对粒子起到了保护作用, 相反当适应值差于平均适应值时其惯性权重较大, 可以使粒子向较好的区域移动, 有利于向最优解靠近。

2.3 新的混合算法

经过上述方法将基本的粒子群优化算法进行改进, 称改进后的为基于交叉自适应权重混合粒子群优化算法。流程图如图1所示。

改进后的混合PSO的基本步骤如下:

步骤一:随即初始化种群, 初始化所有粒子的初始速度和位置。

步骤二:对种群中的所有粒子进行评价, 将当前各个粒子的位置和适应值存在各粒子的pbest中, 将整个pbest中适应值最优个体的位置和适应值存于gbest中。

步骤三:更新粒子的速度和位置。

步骤四:更新惯性权重w。

步骤五:对于每个粒子, 将其适应值与经历过的最好位置pbest的适应值进行比较, 如果当前的适应值更优, 则将当前粒子的位置和适应值作为当前的最好位置pbest保存。

步骤六:将每个粒子的适应值和全局经历的最好位置gbest的适应值进行比较, 如果当前的适应值更优, 则将当前粒子的位置和适应值作为全局的最好位置gbest保存。

步骤七:根据交叉概率将指定数量的粒子进行两两交叉, 产生相同数目的子代粒子, 按照上述的子代粒子的速度和位置公式计算其相应的速度和位置。

步骤八:如果达到终止条件, 则停止算法, 输出结果, 否则返回步骤三继续进行搜索。

3 实验

用Shuber函数来测试改进后的粒子群算法的寻优能力, 并与基本的粒子群算法进行比较。

undefined

该函数存在760个局部极小点, 函数的最小值为-186.7309。

在基本PSO和混合PSO算法中, 将种群大小设为30, c1和c2设为2, 在混合PSO算法中, 杂交概率设为0.9, wmax=1.0, wmin=0.4。将两种算法的迭代次数设为2000, 分别独立运行50次, 得出如表1所示的结果。

4 结束语

本文针对粒子群算法易陷入局部最优及由于种群多样性减少搜索精度不高的特点, 提出了基于交叉机制的自适应权重的混合粒子群算法。通过实验可以看出新的混合的粒子群算法较基本的粒子群算法而言具有更好的寻优能力, 未来的研究工作是深入研究新算法的机理并将其应用到实际的未曾运用到的领域。

参考文献

[1]Kennedy J, Eberhart R C.Particle swarm optimization[C]//Pro-ceedings of the IEEE International Conference on Neural Networks, 1995:1942-1948.

[2]Eberhart R, Kennedy J.Anewoptimizer using particle swarm theo-ry.Proc of the Sixth[C].International Symposium on Micro Ma-chine and Human Science, Nagoya, Japan, 1995:39-43.

[3]Shi Y, Eberhart R C.Amodified particle swarm optimizer.[C]//Proceedings of the IEEE CEC.1998:303-308.

[4]Van den Bergh F, Engelbrecht A P.A cooperative approach to par-ticle swarm optimization[J].IEEE Trans.on Evolut.Comput.2004, 8:225-239.

[5]Holland J H.Adaptation in Natural and Artificial Systems[J].AnnArbor:University of Michigan Press, 1975.

[6]Price K, Storn R, Lampinen J.Differential Evolution-A PracticalApproach to Global Optimization[J].Berlin:Springer, 2005.

[7]王凌, 刘波.微粒群优化与调度算法[M].北京:清华大学出版社, 2008:17-19.

[8]Shi Y, Eberhart R C.Empirical study of particle swarm optimization[C]//Proceedings of the IEEE Congress on Evolutionary Computa-tion, 1999:1945-1950.

适应性权重遗传算法 篇5

电力系统仿真已深入到电力系统规划、设计、运行和研究等领域, 其中负荷模型对电力系统仿真影响很大[1]。由于电力综合负荷具有时变性、分散性、多样性等特点, 建立完全精确的数学模型十分困难, 只能通过负荷分类与综合对其进行一定精确程度上的模拟, 其中对负荷特性的分类是负荷建模的基础工作。

负荷特性分类是指运用聚类算法将同一电网不同负荷中特征接近或相似的综合负荷归并为一类, 并用同一负荷模型描述该“分类”的负荷特性, 从而建立一定精度的负荷模型[2]。分类过程中要考虑分类结果的实用性与分类的准确性。对此国内外学者进行了很多研究, 取得了较多成果[3,4,5,6]。目前的负荷分类方法, 主要有基于模糊C均值、免疫网络理论及基于神经网络的聚类方法等, 其中应用最广泛的是模糊C均值聚类法 (FCM) , 而FCM算法存在计算过程中对初始条件过于敏感, 易陷入局部最优解的问题[7]。

遗传算法 (GA) 是一种有效的全局搜索方法, 具有鲁棒性高, 随机性好的特点, 是目前智能优化方法中应用最为成功的算法之一, 被广泛用于自动控制、数据挖掘、图像处理等领域[8]。在传统GA算法的基础上, 本文提出了一种自适应GA算法, 改进了交叉概率pc和遗传概率pm的取值方法, 使其随着进化过程自适应取值, 从而优化GA算法的性能, 增强其全局寻优能力, 避免pc和pm取固定值时可能出现的早熟和收敛过慢现象。将其应用于电力负荷特性分类, 解决了分类结果受初始聚类中心选择影响过大和易陷入局部最优解的问题, 仿真实例论证了该方法的有效性和准确性, 具有一定的工程实用价值。

2 自适应GA算法聚类

2.1 自适应GA算法

2.1.1 传统GA算法描述

GA算法是一种借鉴生物界自然选择和进化机制全局优化概率搜索方法, 利用遗传算子 (选择、交叉和变异算子) 促进解集合类似生物种群在自然界中自然选择、优胜劣汰、不断进化, 最终收敛于最优状态[9]。

GA算法的主要运算过程为:先把解空间的数据表示成遗传空间的基因型串结构数据;随机产生N个初始个体;求出每个个体的适应度值, 选择当前种群中的两个个体, 以一定的概率 (交叉概率pc) 进行交叉操作, 得到新一代种群的个体;在群体中随机选择一个个体, 以变异概率pm进行变异操作, 为产生新的个体提供了机会;从当前种群中选出优良个体遗传到下一代中, 依次迭代。当满足最大迭代次数或满足精度要求时, 停止迭代, 当前种群的最优个体为最优解。

2.1.2 自适应GA算法pc和pm的设计

pc和pm影响着算法的性能。pc越大, 群体引入新结构就越快, 但已获得优良基因丢失的速度也相应提高, pc太小则可能导致搜索阻滞。变异操作是保持群体多样性的手段, pm太小可能使个别基因过早丢失, pm太大则遗传算法将变成随机搜索。为避免传统GA算法中pc和pm采用固定值的不足, 本文提出的自适应GA算法, 使pc和pm随遗传进程自适应变化, 使得GA算法具有更高的鲁棒性、全局最优性和更快的收敛速度。

其中, k1~k4≤1.0, 且为常数;f为个体适应度值;f'为交叉互换双方中适应度值较大的个体的适应度值;fm ax为群体的最大适应度值;f为群体的平均适应度值。

2.2 遗传算法聚类

将遗传算法用于聚类分析的流程如图1所示。

具体实现步骤为:

(1) 编码

采用浮点法对染色体进行编码。对于样本空间Rd中样本集X={x1, x2, …, xm}, 要把样本聚类为c类。染色体结构为含有c×d个基因链的结构串S, 则S=g11g12…g1 dg21g22…g2 d…gc1gc2…gcd, 其中gij表示第i个样本的第j个数据。

(2) 适应度函数

GA算法中的适应度函数用来评价个体的适应度, 个体适应度越高, 其存活的概率就越大。以各聚类中样本与聚类中心欧氏距离之和为目标函数

其中, mj (j=1~c) 是聚类中心;xk是样本。

适应度函数fS取

fS越大表明聚类划分效果越好。

(3) 种群初始化

随机选出c个样本, 根据浮点数编码方式将这组个体编码成一个染色体。重复进行N次染色体初始化, 生成个体数为N的种群。

(4) 选择操作

用轮盘赌方法选出个体参加交叉、变异操作, 选择算子

式中, fSi (i=1~N) 表示第i个个体的适应度值; 表示所有个体适应度总和。

(5) 交叉操作

首先随机生成一个交叉点, 然后交换两个父个体中位于交叉点右侧的部分, 生成两个新的子代个体。

(6) 变异操作

本文采用单点变异, 对选中的基因进行非运算。

(7) 进化过程

对种群中染色体进行选择、交叉和变异操作, 计算出每个进化个体的适应度, 并找出其中适应度最大的个体来代替上一代种群中适应度最差的个体。

(8) 终止条件

算法终止条件一般用进化收敛程度或者控制进化代数来设定, 本文以设置进化代数来终止遗传操作。

3 适应GA算法在负荷分类中的应用

3.1 特征向量的选取

在对负荷进行聚类可以选择的特征向量有:①时间特征量。②参数特征量。③运行特征量。④动态特征量。⑤实测响应特征量。

采用负荷扰动数据的实测响应作为特征向量, 不涉及模型结构, 从而减少了模型结构确定过程中的误差, 有利于提高分类的准确性。故本文选取实测响应空间作为特征向量, 包括电压激励和有功无功响应。

3.2 样本数据的预处理

对于扰动强度不同的样本, 采取纵向伸缩的方法进行处理。在样本里选择一个接近标准扰动强度 (15%) 的样本, 在其暂态过程搜索出幅值最大数据点, 再使其他样本的暂态过程幅值最大数据点与之相等, 计算出这两者幅值的比值作为比例系数, 其他暂态数据点的幅值则按该比例系数伸缩。对于样本扰动持续时间长度不同的样本, 进行数据伸缩处理, 以使计算相关系数时各个负荷扰动数据的不同阶段能够对应[2]。

3.3 遗传操作

获取标准化处理后的样本空间后, 按照2.2节所述过程进行遗传操作。遗传操作终止后, 选取末代适应度最大的染色体解码出最终的聚类中心。然后计算各样本与所得各聚类中心的欧氏距离, 各样本被归入与其欧式距离最小的聚类中心。

4 应用实例

以某220k V变电站采集的110k V侧的负荷扰动数据为样本集合, 采用实测响应空间为特征向量, 各实测样本的直观特征值如表1所示, 采用遗传算法对负荷动特性进行聚类。

将样本分为4类, 既c取4。然后进行种群初始化, 每个个体随机选取4个样本作为聚类中心, 种群大小为100。进行选择、交叉、变异操作, k1=k2=1.0, k3=k4=0.5。根据适应度函数判断染色体优良与否, 选择优良个体进入下一代, 进化代数 (迭代次数) 取100, 运行10次。

将本文方法与FCM算法进行比较, 用FCM算法对数据进行分类时, 每次选取不同的初始聚类中心, 把样本分为4类, 进行10次运算。

不同算法得到的聚类结果如表2所示。

由表2可知, 用自适应GA算法进行分类运行结果有两种, 且绝大部分都收敛在同一解上。用FCM算法进行分类时, 当选用不同的初始聚类中心时, 聚类结果有多种, 且较发散。遗传算法具有良好的全局收敛性, 能够更加准确地收敛到全局最优解, 因此分类结果较为稳定。而FCM算法易受到初始聚类中心的影响, 从而陷入局部最优解, 所以当选取不同的初始聚类中心时, 就会出现不同的分类结果, 且发散性偏大, 因此取第2种分类结果为最终分类结果。

为检验分类结果准确性, 对第2类负荷进行参数辨识, 建立等效模型并与直接综合法 (DS) 进行比较。第2类负荷参数辨识结果见表3。

把第2类负荷各样本的电压激励分别作用于等效模型, 得到各模型响应与相应实测响应的拟合误差

其中, ym (k) 为模型响应;y (k) 为实测响应。

将其与基于实测响应空间直接综合法[10]得到的综合模型的拟合误差作比较, 如表4所示。可见, 用GA算法分类所得结果建立等效模型的拟合误差较DS法更小, 能够更好地拟合实测负荷样本, 从而证明了用GA算法对电力综合负荷进行分类精确性较高, 具有实用价值。

5 结论

在负荷建模时需要对电力负荷进行分类, 针对传统FCM算法往往存在对初始条件过于敏感和易陷入局部最优解的问题, 本文提出了一种改进的自适应遗传算法。实际算例表明, 用自适应遗传算法对电力综合负荷进行分类, 具有良好的随机性和全局性, 能够有效降低初始聚类中心选择对聚类结果的影响, 避免陷入局部最优解, 取得了更为理想的分类效果。

摘要:提出了运用一种改进的遗传算法对电力负荷特性进行分类的新方法。通过对样本进行遗传操作, 求出适应度最高的个体, 解码得到最优聚类中心, 再根据样本与各中心距离进行划分, 从而得到负荷样本的最优分类结果, 用获得分类的聚类中心对所属类别样本进行拟合以检验分类效果。改进后的遗传算法的交叉概率和变异概率随进化过程自适应变化, 在保证遗传算法良好的全局性和随机性的同时, 避免了早熟收敛和收敛过慢。实际算例表明, 用这种改进遗传算法对电力负荷特性进行分类, 能够有效避免初始条件对分类结果的过度影响, 取得了良好的分类效果。

关键词:负荷特性分类,聚类,遗传算法,自适应,实测响应空间

参考文献

[1]张红斌, 贺仁睦, 刘应梅 (Zhang Hongbin, He Renmu, Liu Yingmei) .基于KOHONEN神经网络的电力系统负荷动特性聚类与综合 (The characteristics clustering and synthesis of electric dynamic loads based on KOHO-NEN neural network) [J].中国电机工程学报 (Pro-ceeding of the CSEE) , 2003, 23 (5) :1-5, 43.

[2]林舜江, 李欣然, 刘杨华, 等 (Lin Shunjiang, Li Xin-ran, Liu Yanghua, et al.) .电力负荷动特性分类方法研究 (A classification method for aggregated load dynam-ic characteristics) [J].电力系统自动化 (Automation of Electric Power Systems) , 2005, 29 (22) :33-38.

[3]李小燕, 丁明, 徐宁舟 (Li Xiaoyan, Ding Ming, Xu Ningzhou) .面向运行规划可靠性的综合聚类负荷模型 (Integrative K-means clustering based load model for op-erational planning reliability evaluation) [J].电力系统自动化 (Automation of Electric Power Systems) , 2010, 34 (8) :56-60.

[4]顾丹珍, 艾芊, 陈陈 (Gu Danzhen, Ai Qian, Chen Chen) .一种基于免疫网络理论的负荷分类方法 (A load classification method based on artificial immune net-work) [J].电网技术 (Automation of Electric Power Sys-tems) , 2007, 31 (Suppl.1) :6-9.

[5]李培强, 李欣然, 陈辉华, 等 (Li Peiqiang, Li Xinran, Chen Huihua, et al.) .基于模糊聚类的电力负荷特性的分类和综合 (The characteristics classification and synthesis of power load based on fuzzy clustering) [J].中国电机工程学报 (Proceedings of the CSEE) , 2005, 25 (24) :73-78.

[6]杨浩, 张磊, 何潜, 等 (Yang Hao, Zhang Lei, He Qian, et al.) .基于自适应模糊C均值算法的电力负荷分类研究 (Study of power load classification based on adaptive fuzzy C means) [J].电力系统保护与控制 (Power System Protection and Control) , 2010, 38 (16) :111-115.

[7]曾博, 张建华, 丁蓝, 等 (Zeng Bo, Zhang Jianhua, Ding Lan, et al.) .改进自适应模糊C均值算法在负荷特性分类中的应用 (An improved adaptive fuzzy C-means algorithm for load characteristics classification) [J].电力系统自动化 (Automation of Electric Power Systems) , 2011, 35 (12) :42-46.

[8]舒祥波 (Shu Xiangbo) .一种自适应遗传算法的聚类分析及应用 (Analysis and application of adaptive genetic algorithm of clustering) [J].信息技术 (InformationTechnology) , 2011, (4) :190-192, 196.

[9]张伟, 廖晓峰, 吴中福 (Zhang Wei, Liao Xiaofeng, Wu Zhongfu) .一种基于遗传算法的聚类新方法 (A new algorithm for clustering analysis based on genetic algo-rithm) [J].计算机科学 (Computer Science) , 2002, 29 (6) :114-116.

用自适应遗传算法解二维装箱问题 篇6

装箱问题是一个经典的组合优化问题,属于NP难问题,有着广泛的应用。关于一维装箱问题已有许多报道,而有关二维装箱问题(2D bin-packing problem)的报道则相对较少。二维装箱问题广泛应用于服装业,航空航天和计算机的存储分配中。以往的研究主要是考虑特定形状的箱子和物体[1,2,3,4],考虑特定的旋转角度(90o的倍数)[1,2,3,4,5],并得到了较好的结果;文献[6]考虑了任意形状物体所占的矩形区域和任意的旋转角度,用多匹配的方法得到了很好的结果,但该方法受物体形状的复杂程度影响。文献[7]考虑了物体的任意形状和旋转度,并用遗传算法在1000代后得到了较好的结果,通过设定罚参数,较好地解决了物体越界问题,但物体重叠问题没有得到很好的解决,且算法中的交叉率和变异率不是自适应的。文献[7]用中轴变换得到的图形骨架计算适值来达到减少计算量的目的,但骨架的提取受到物体形状的影响。受文献[7]的启发,本文提出了一种改进的遗传算法,在200代内得到了更好的结果,且每代的计算速度较快。

1 问题描述

设二维箱子的容量为C,第i个物体所占空间为wi(i=1,2,…,n),0<i=1nwi<C。考虑向量:ai=(xi,yi,θi),则2D装箱问题等价于式(1)~式(4)。

max p(a1,a2,…,an) (1)

s.t.ai=(xi,yi,θi)i=1,2,,n(2)

(xi,yi)∈D i=1,2,…,n (3)

θi∈[0,360) i=1,2,…,n (4)

其中,p(a1,a2,…,an)为适值函数。物体旋转的角度为θi,旋转中心为(xi, yi),本文算法中旋转中心的取法如图1所示。箱子的坐标系如图1所示。当所有的物体都放入箱子中且不重叠时,适值达到最大值,记为max_fitness,该值可预先计算得到。

2 用自适应遗传算法求解

对于第i个图形,考虑三个基因(xi,yi,θi),共n对基因,采用十进制编码。计算分五步:(1)随机产生具有一定数量的种群;(2)在初始种群中随机选择个体进行变异;(3)在初始种群和变异得到的新个体中随机选择个体进行交叉;(4)让变异和交叉得到的新个体与原种群中的个体竞争,按概率选择出新的种群;(5)重复(2)~(4)若干次。

交叉、变异的自适应性

交叉率,变异率的选取直接影响到遗传算法的效果,它们的值一般是人工设定的。在生物界中,有许多生物(如真菌),当环境较好时,繁殖后代的个数会稳定在一定的范围内,繁殖的方式主要是无性繁殖。当环境恶化时,这些生物会大量繁殖,繁殖的方式改为有性繁殖以增加遗传的多样性,从而增加产生更适应于新环境的后代的概率。大量繁殖相当于交叉率增大,而有性繁殖会提高变异率。

在本文的算法中,用两个函数来模拟这一过程,使交叉率和变异率能根据具体的情况做出相应的变化:①当后代没有进化时,交叉率和变异率增加,增加到一定程度时,其增速趋于缓慢;②在交叉率和变异率增加的过程中,若后代进化了,则交叉率和变异率应减少。实验中选用函数f(x)=e-1cx(1-p)的值作为交叉率和变异率的增量,其中c为常数(实验中取c=0.025,此时函数的拐点为x=20),p为交叉率或变异率,x为没有进化的代数;选用函数f(x)=bi·x·c的值作为交叉率和变异率的减量,其中bi是当前最好结果的适值,x是当前的交叉率或变异率,c是常数(实验中取c=1/3)。由于bi的存在,函数是非线性的。考虑到交叉率一般较大,变异率一般较小,故两者的增量范围分别选择[0,1]和[0,0.35]。

2.1 选 择

在原来的种群和新产生的个体中按概率选择一个新的种群,也就是让父代和子代竞争。通过实验发现,由于个体之间适值的差异不大,在用累积概率进行随机选择个体时,很容易丢失较好的个体,每一代的最好结果适值和平均适值都不稳定 (如图2所示) 。

针对这一情况,先对每个个体间的适值差异进行放大,实验中选用了二次幂函数f(x)=(c2·(x-c1x_min))2,其中x表示待放大个体的适值,x_min表示当前群体中个体的最小适值,c1取一个接近1的数(实验中c1=0.9999),c2的作用在于将适值移到坐标轴的右边(实验中c2=1000),因为越往坐标轴的右边,幂函数的值变化越大。通过实验发现,经过处理后每一代的最好的结果和平均适值较稳定。从图2可以看出,种群中的优秀个体没有很好地保护下来。为此,仿照文献[7]的方法,对每代的最好个体无条件地保存下来。

2.2 适值函数

适值函数的选择也对遗传算法的效果有直接影响。通过对各种情况进行试验发现:(1)考虑越界和重叠的像素,这时适值函数为求最小值,收敛速度较慢;(2)考虑不越界的像素,重叠的像素只统计一次,收敛速度稍快;(3)只考虑不越界不重叠的像素,收敛速度最快。在本文的算法中采用第(3)种方法,这实际上加强了不重叠的限制,设f(a1,a2,…,an)为不越界不重叠的像素的个数,适值函数取:p(a1,a2,,an)=f(a1,a2,,an)max_fitness, p∈[0,1]。 实验结果表明,越界和重叠问题同时得到解决。

3 实 验

实验一采用文献[7]中的实验数据。实验二中,箱子的形状不变,但物体的数量和形状的复杂程度都有所增加。运行环境:CPU 1.66G,内存512M DDR2,Windows XP,MATLAB 7.0。

3.1 实验一

待装箱的物体的形状见图3(a),初始种群的个数为:50,交叉率初始值0.1,变异率初始值0.1。实验结果见图3(b),图3(c),图3(d)。平均计算时间为1.31秒/代。

从实验结果可以看出,提出的算法具有较快的收敛速度,交叉率和变异率按照预期的方法自动进行了调整(如图3所示),且物体的越界和重叠问题同时得到了较好的解决。实验中,第152代的适值达到0.9995,从第152代到第200代,适值没有改进,从图3可以看出,实验结果较好,没有明显的越界或重叠部分。

3.2 实验二

待装箱的物体的形状见图4(a),初始种群的个数为:50,交叉率初始值0.1,变异率初始值0.1。结果见图4(b),图4(c),图4(d)。平均计算时间为1.19秒/代。

从实验结果可以看出,当物体的数量和复杂程度增加时,本文提出的算法并没有受到明显的影响,仍然具有较快的收敛速度。实验中,第135代得到最优解,适值为1。

4 结 论

提出的改进遗传算法具有以下特点: (1)交叉率和变异率能根据种群的进化情况作出相应的变化,解决了人工设定这两个参数的缺陷;(2) 针对个体间适值差相对较小,新产生的优秀染色体易丢失的特点,还改进了随机选择的方法;(3)改进了适值函数,使得越界和重叠问题同时得到了解决;(4)算法无须考虑图形的具体情况及其复杂度,这与遗传算法的数学要求不高和适应性强的特点相吻合。同时。通过实验发现,本文提出的算法收敛速度较快,且该算法与箱子的具体形状及物体的具体形状无关,物体的数量和形状的复杂程度对算法的收敛速度影响不大,因此适用于任意形状的箱子和物体的2D 装箱问题。

参考文献

[1]Roy P Pargas,Rajat Jain.A parallel Stochastic Optimization Algorithm for Solving2D Bin Packing Problems.Artificial Intelligence for Appli-cations.Proceedings.,Ninth Conference on,1993:18-25.

[2] Silvano Martello,David Pisinger,Daniele Vigo.The Three-Dimentional Bin Packing Problem. Operations Research,2000,48(2):256-267.

[3] Hitoshi lima,Tetsuya Yakawa.A New Design of Genetic Algorithm for Bin Packing. Evolutionary Computation, 2003. CEC’03. The 2003 Congress on,2003,2:1044-1049。

[4]Nikhil Bansal,Andrea Lodi,Maxim Sviridenko.A Tale of Two Dimen-sional Bin Packing.Proc.of the200546thAnnual IEEE Symposium on Foundations of Computer Science,IEEE,2005.

[5]Jain S,Gea HC.Two-dimensional packing problems using genetic algo-rithms.Engeering with Computers,1998,14:206-213.

[6]Yu C,Manoochehri S.Optimal packing using the multiple mating meth-od.Engineering with Computers,2003,19(1):56-65.

改进自适应遗传算法的性能分析 篇7

为此, 该文提出一种新的改进遗传算法, 改进后的算法效果良好, 在算法的收敛速度以及全局搜索性能等方面都具备良好的效果。

1 自适应遗传算法

1.1 M.Srinivas提出的自适应遗传算法 (本文中简称AGA)

AGA的基本理论依据是:在群体适应度比较集中的情况下, 能够促使变异杂交概率Pc以及概率Pm增大;反之, 则能够促使变异杂交概率Pc以及概率Pm减小。其中, Pm和Pc的具体定义公式为:

公式中:ƒmax是指群体的最大适应度;ƒavg是指群体的适应度平均值;ƒ'是指杂交双方适应度大者的适应度;ƒ是指个体的适应度;0

这种算法可以根据每代个体适应度的改变来自适应地改变Pm和Pc, 在保护最优个体的同时, 加快了较差个体的淘汰速度。该算法在一定程度上可以改善遗传算法的性能。但该算法也存在不容易跳出局部最优解, 因为该算法是以个体为单位改变Pm和Pc, 缺乏对整体的协作精神。同时, 由于该算法对每个个体都要分别计算Pm和Pc, 这样会影响程序的执行效率, 也不利于硬件的实现。

1.2 文献[3]提出的自适应遗传算法 (本文中简称IAGA)

针对M.Srinivas所提出的算法的缺点, 文献[3]提出一种改进的自适应遗传算法。其通过判断适应度集中程度的情况, 对整个群体的Pm以及Pc进行自适应地变化调整, 同时将群体适应度的集中程度用三个变量来衡量, 即:适应度平均值、群体的最大适应度、最小适应度。文献[3]提出的算法在一定程度上可以提高算法的计算速度和收敛速度。但因为它们计算所得到的变异概率Pm及交叉概率Pc具有不良的稳定性。尤其在遇到峰值密度较高的多峰值函数时, 更容易出现得到概率较大的结果的现象。同时, 该算法在一定程度上也是缺乏对算法的整体协作能力。

2 改进自适应遗传算法 (本文中简称NIAGA)

通过上述对现有的自适应遗传算法的分析, 可以看到, 目前现有的自适应遗传算法不管在收敛速度和计算速度, 还是稳定性及整体把控能力等方面都存在一定的不足之处。为此, 本文在基于上述自适应遗传算法的基础上, 提出一种新的自适应遗传算法, 以改进其在上述所存在的不足。

2.1 与进化代数有关的杂交概率的改进介绍

杂交算子的主要目的是用来产生新个体, 同时也是为了让算法具备全局搜索的能力。因此, 当我们以种群中的个体来观察时, 如果杂交的概率偏大, 群体中的优良模式就会被破坏;而如果杂交的概率偏小时, 对于新个体的产生速度又会变得缓慢。在这里可以看出, 与个体适应度有关的杂交概率的算法是具有一定的优势的。当我们以种群整体进化的整个过程来观察时, 杂交概率应该会一个稳定但会慢慢变小, 最终会向某一个稳定值靠近的过程。当我们以新个体的产生方面来看, 在杂交操作上, 群体中所有的个体应该具有相同的地位, 也就是概率是一样的, 这样就可以使得遗传算法在搜索空间拥有每个方向的匀称性。文献[3, 4]的交叉概率算法都只注意了个体的作用, 而忽视了整个种群的进化趋势情况和各个体的变异机会。

在本文中, 为了改善目前算法所存在的不足, 设计了一种与适应度没有关系, 只同进化代数有关的概率公式:

其中, 上述式子的参数含义如下表1所示:

本公式可以达到交叉概率随着进化过程而逐渐变化, 同时能够对同一代的种群中的个体给予一样的交叉能力。这样也可以更好的实现全局搜索能力, 同时, 算法的计算速度也可以得到极大的提高。相对文献[4], 该文的算法对劣质个体的处理显得相对薄弱, 但可以通过下面的方法来进行弥补此缺陷。

2.2 自适应变异概率的改进介绍

维持种群多样性是变异算子的主要用处, 其主要是用来抑制早熟现象的出现以及产生新个体。但杂交算子则不同, 其主要是在全局搜索中起作用。因此, 就变异概率来说, 应该是在同一种群中每个个体都是随着个体本身的好坏而发生变化。同时, 变异概率的取值也是十分关键的。如果变异概率的取值偏小, 就很容易导致抑制早熟现象以及产生新个体的能力减弱。而如果变异概率取值偏大, 又容易导致遗传算法搜索过程成为随机过程的现象产生, 从而使种群中较好的模式被破坏的可能性增加。所以, 自适应变化的变异操作的设计十分重要。

变异概率设计需要满足: (1) 应该使变异概率慢慢减小, 从而能够使得群体快速集中。 (2) 较小的变异概率给优秀的个体。 (3) 较大的变异概率给劣质的个体。针对上述条件, 在本文中设计了如下的自适应变异概率公式:

在公式中, Pm (t) 指的是第t代种群中个体Xi的变异概率;Pm, min指的是预先设置的最小的变异概率;Pm, max指的是预先设置的最大的变异概率。

以上式子的计算可以实现变异概率随进化过程自适应地变化。也能够针对所有待变异个体的适应值做相应的自适应变化。

3 仿真实验及结果分析

3.1 仿真测试函数的选取

为了验证本文提出的改进的遗传算法的收敛性能以及跳出局部极值的能力, 通过选取下面的函数来进行实验测试比较AGA、IAGA、NIAGA三个算法的仿真效果。

上面所选取的函数在遗传算法性能测试方面都是很经典的函数, 它们都有全局最小值, 不过也存在有多个极值点的函数。在本实验中, 先对函数ƒ1、ƒ3和ƒ4进行求负处理, 目的是方便对这些函数求最大值。

3.2 仿真实验结果及分析

在对上面三种遗传算法进行仿真实验时, 对所用到的参数作说明:收敛时间的单位是秒;群体的规模是64;最大进化代数是180。其他参数见表2

下面的结果是将三种遗传算法进行实验仿真所取得的仿真结果。

上述结果都是在经过100次计算后取得的平均值。

从表3—表5所得仿真实验结果可以分析出, 在收敛速度上, AGA和IAGA有些时候会比较快, 不过在收敛性能方面不太稳定, 同时, 能成功收敛的次数也比较少, 尤其是在优化多峰值特征非常突出的函数ƒ1和ƒ2的情况下, 它们的这个缺陷尤其显现。但NIA-GA算法在计算速度和收敛性能方面都比较平衡, 尤其是在收敛的稳定性能方面显得更好。本文提出的改进的算法, 能够在保证一定的计算速度的前提下, 使得算法的收敛概率大大提高。

4 结束语

针对传统遗传算法的早熟和收敛速度慢等缺点, 文中提出一种改进的自适应遗传算法, 实验数据表明, 该算法具有良好的搜索能力, 具有更快的收敛速度和更可靠的稳定性, 达到了预期的效果。

参考文献

[1]Holland J H.Adaptation in Natural Artificial Systems[M].MIT Press, 1975.

[2]Masanori Suglsaka, Xinjian Fan.Adaptive Genetic Algorithm with a Cooperative Mode[C].Proceedings of IEEE International Symposiumon Industrial Electronics, 2001.

[3]王蕾, 沈庭芝, 招扬.一种改进的自适应遗传算法[J].系统工程与电子技术, 2002:24 (5) :75-78.

[4]Srinvas M, Patnaik L.M.Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms[J].IEEE Trans on Systems, Man and Cyber netics, 1994:24 (4) .

[5]欧阳森, 王建华, 耿英三, 等.一种新的改进遗传算法[J].计算机工程与应用, 2003 (11) .

[6]F Herrera, M Lozano.Adaptive Genetic Operators Based on Coevolution with Fuzzy Behaviors[J].IEEE Trans on Evolutionary Computation, 2001 (5) :149-165.

[7]李茂军, 童调生.用单亲遗传算法求解有序组合优化问题[J].系统工程与电子技术, 1998 (20) :58-61.

[8]王小平, 曹立明.遗传算法:理论、应用与软件实现[M].西安:西安交通大学出版社, 2002.

基于信息熵的自适应遗传算法研究 篇8

与传统的优化方法相比,遗传算法的主要优点在于算法的鲁棒性、全局最优性和广泛适用性(对目标函数的形式无任何要求)。然而在实际应用中,遗传算法寻优容易陷入局部极值点,即发生成熟前收敛[1,2]。之所以出现如此现象是由于在标准遗传算法中经过许多代迭代后,遗传操作中最重要的交叉操作使群体染色体具有局部相似性,父代染色体的信息交换量太小,使搜索停滞不前;另一方面,选择的变异概率太小,以至于不能驱动搜索转向其它的解空间进行搜索。要跳出局部极值点,要靠大量的变异操作,当变异概率较小时,则需要长期的进化。而作为一个稳定的生物群体,变异概率应该是很小的。所以,陷入局部极小点的遗传算法寻优有时要耗费大量的时间。因此,一个自然的改进想法就是使交叉概率和变异概率随着群体的进化过程而变化。在进化初期,群体中包含的基因模式较多,应该增加交叉概率以组合现有模式,减少变异率以保持得到的优良的基因模式;在进化后期,群体中的基因模式比较单一,没有必要进行大量的模式重组,则可以减少交叉概率;为了避免进入局部极小点则需要大量引入新模式,这就要增大变异概率。

2 自适应遗传算法

遗传算法的参数中交叉概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键所在,直接影响算法的收敛性,Pc越大,新个体产生的速度越快。然而,Pc过大时遗传模式被破坏的可能性也越大,使得具有高适应度的个体结构很快就会破坏;但是如果Pc过小,会使搜索缓慢,以至停滞不前。对于变异概率Pm,如果Pm过小时,就不易产生新的个体结构;如果Pm取值过大时,那么遗传算法就变成了纯粹的随机搜索算法。针对不同的优化问题,需要反复实验来确定Pc和Pm,这是一件繁琐的工作,而且很难找到适应于每个问题的最佳值。

M.Srinivas和L.M.Patnaik[3]提出了一种交叉概率和变异概率随个体的适应度而变化的自适应遗传算法(Adaptive Genetic Algorithm)。当种群各个体适应度趋于一致或者趋于局部最优时,使Pc和Pm增加,而当群体适应度比较分散时,使Pc和Pm减少。同时,对于适应度高于群体平均适应值的个体,对应于较低的Pc和Pm,使该解得以保护进入下一代;而低于平均适应值的个体,相对应于较高的Pc和Pm,使该解被淘汰掉。因此,自适应的Pc和Pm能够提供相对某个解的最佳Pc和Pm。自适应遗传算法在保持群体多样性的同时,保证遗传算法的收敛性。

在自适应遗传算法中,Pc和Pm按如下公式进行自适应调整:

式中,fmax为当前群体最大适应度;

为群体平均适应度;

f'为待交叉的两个体较大适应度;

f为要变异个体的适应度;

k1,k2,k3,k4(0,1)。

3 信息熵的定义

信息熵衡量一个随机系统的不确定性程度,它是一个概率矢量的多元函数。如果信息熵越大,则表明系统的不确定性程度越高,其概率分布越接近均匀分布(等概率分布);反之,如果信息熵越小,则系统的不确定性程度也越小,其分布越集中于局部。因此可用信息熵来衡量遗传算法进化群体的不确定性分布,具体地说,就是随着进化代数的增加,群体的分布是怎样变化的,包括个体的分布变化和适应度的分布变化。

定义四种信息熵:x信息熵Ex,y信息熵Ey,xy联合信息熵Exy,适应度信息熵Ef,具体的计算方法与计算步骤如下:

(1)归一化

对于遗传算法进化过程中的第G代群体PG(xi,yi,fi),i=1,2,…,N。

其中:

PG———第G代群体的组成,P0为随机产生的初始群体;

xi,yi———变量x,y的第i个值,(xmin≤xi≤xmax,ymin≤yi≤ymax);

fi———变量(xi,yi)对应的目标适应度;

N———群体规模。

分别对xi,yi,fi进行如下归一化操作:

归一化的目的则是将不同的区间范围归一化到统一的区间范围[0,1],为下一步区间划分作准备。

(2)区间划分

将归一化[0,1]区间划分成n等份,得到n个等宽小区间[vk,vk+1],k=1,2,…,n,v1=0,vn+1=1;同样将归一化的平面正方形[0,1;0,1]划分为n2个相同的小正方形[ai,ai+1;bj,bj+1],(i=1,2,…,n;j=1,2,…,n)a1=b1=0,an+1=bn+1=1。

(3)统计出现频率

分别统计xi',yi',fi'(i=1,2,…,N)在n个小区间[vk,vk+1](k=1,2,…,n)内出现的次数Cxk,Cyk,Cfk;统计平面点集(xi',yi')(i=1,2,…,N)在n2个平面小正方形[ai,ai+1;bj,bj+1],(i=1,2,…,n;j=1,2,…,n)内出现的次数Cxyij。

然后计算它们在每一划分内出现的频率,Pxk=Cxk/N,Pyk=Cyk/N,Pfk=Cfk/N,(k=1,2,…,n)和Pxyij=Cxyij/N

(4)四种信息熵的计算

4 信息熵在遗传算法中的应用

与简单遗传算法相比,自适应遗传算法的性能较好,搜索速度提高很快。然而该算法陷入局部极小点后也很难自拔。原因在于该算法使个体的交叉概率和变异概率只随着适应度大小变化而和适应度的分散程度没有关系,因而不能对适应度分散程度的变化作出反应,陷入局部极小点后就很难跳出来。这里采用信息熵来衡量群体适应度的分散程度,并由此预报成熟前收敛的发生,进而提出了一种改进的自适应遗传算法。基本思想是使交叉概率和变异概率不仅和个体的适应度有关而且和适应度的分散程度有关。

分散程度的度量采用式(4)中的适应度信息熵。信息熵与收敛程度的关系收敛判定定理[4]:若群体的适应度信息熵值出现持续增大或保持不变时,则必定发生了成熟前收敛。由此定理可知,适应度信息熵的变化可用来预报群体内成熟前收敛的发生。群体发生成熟前收敛时,有一定比例的个体具有群体内的最大适应度,而且这个比例随着进化代数逐渐增加。

AGA的实质是将整个群体按适应度分为高于平均值和低于平均值两部分。前一部分的交叉概率大而变异概率小,担负着组合优良模式的任务;后一部分的交叉概率小而变异概率大,功能是引入新的模式。然而随着进化过程的进行,当群体陷入局部极小点时,大部分个体的适应度为群体内的最大值,位于平均值以上。AGA的机制使这些个体的交叉概率和变异概率均为零,使之既不能和其他个体交换基因也不能进行变异。引入新模式的任务完全由低于平均值的极少数个体依靠变异算子来完成。若新产生的个体的适应度低于最大的适应度,尽管它包含优良的模式,但由于选择机制的作用使这些个体很难生存下来,因此这些优良模式很难保存。只有当新个体的适应度高于现有最大的适应度才能将新个体所包含的模式保存下来,这是很困难的,因此搜索新区域的效率很低。

5 改进遗传算法的实现[5,6]

改进的自适应遗传算法IAGA(Improved Adaptive Genetic Algorithm)中,Pc和Pm按如下公式进行自适应调整:

式中,fmax为当前群体最大适应度值;

为群体平均适应度;

f'为待交叉的两个体较大适应度值;

f为要变异个体的适应度。

其中,Pc'和Pm'表示随群体的信息熵而调整的交叉概率和变异概率。Pc'和Pm'随信息熵的变化如图1所示。

IAGA的实现步骤如下:

1)初始化:设置控制参数,产生初始群体;

2)遗传操作:(1)采用赌轮或锦标赛等选择方法;(2)计算群体的信息熵;(3)从群体中选择两个个体进行基因交换,交叉概率根据式(5);(4)从群体中选择个体进行基因突变,变异概率根据式(6);

3)检验新一代群体是否满足结束条件,若满足结束条件则结束;否则,转向步骤2)。

用IAGA可以使群体的适应度信息熵保持在一定的水平,保证了群体的多样性,而且能够使群体的进化不易陷于局部极小值,避免成熟前收敛。

6 遗传算法的运用实例

这里用实验来检验IAGA,试验函数采用六峰值驼背函数:

该函数是检验遗传算法性能的标准测试函数之一,它共有六个局部极小点(-0.0989,0.7126)和(0.0989,-0.7126),其中两个为全局极小点和。试验结果如表1所示。

表1表明,IAGA不仅平均进化代数少于AGA,而且几乎不陷入极小点。从实验中可以看出极少IAGA进化代数稍多于AGA的代数。因为IAGA为避免陷入局部极小点,有时要加大变异概率,这难免会破坏一些优良的模式,会延误一些时间。当AGA没有陷入局部极小点,IA-GA的进化代数会长一些。然而只要不陷入局部极小点,多花点时间也是值得的。

7 结论

提出的改进的自适应遗传算法IA-GA能够衡量群体适应度的分散程度,而且可以有效避免局部极值点,预防遗传算法的早熟现象。仿真结果证明了该算法的有效性。

参考文献

[1]陈国良,王煦法,庄镇泉.遗传算法及其应用[M].北京:人民邮电出版社,1996.

[2]潘正君,康立山,陈毓屏.演化计算[M].北京:清华大学出版社,1998.

[3]Srinivas M,Patnaik L M.Adaptive Probabilities of Crossover and Mutationin Genetic Algorithms[J].IEEE Transactions on System,Man,and Cybernetics,1994,24(4):656-667.

[4]郝翔,李人厚.基于信息熵的自适应遗传算法[J].西安建筑科技大学学报,1997,29(1):34-38.

[5]云庆夏,黄光球,王占权.遗传算法和遗传规划[M].北京:冶金工业出版社,1997.

上一篇:单元化制造下一篇:《萧萧》