自适应粒子群优化

2024-05-10

自适应粒子群优化（共7篇）

自适应粒子群优化篇1

0 引言

机组组合是在满足一定约束条件下,通过优化以达到总运行费用最小的目标[1]。机组组合属于大规模非线性、高维、混合整数的约束优化问题,许多学者经过研究提出大量了求解机组组合问题的方法,这些方法主要包括优先表法、动态规划法、分枝定界法、拉格朗日松弛法、内点优化法、Tabu搜索法、专家系统、人工神经网络算法、蚁群算法、遗传算法等[2]。其中,最简单和最快速的方法是优先表法,但是一般找不到最优解;动态规划法是一种广泛使用的机组组合方法,但是,随着机组数量和调度时间的增加,容易出现“维数灾”问题;拉格朗日松弛法是用于机组组合最有潜力的一种方法,但是由于对偶间隙的存在,制约了其使用的范围;遗传算法由于其可以得到全局最优解、实现简单及对目标函数没有特殊要求等特点而受到重视,但是遗传算法计算量大,效率低。

粒子群算法PSO(particle swarm Optimization Algorithm)是由Kennedy和Eberhart等于1995年开发出的基于群体智能的新型演化计算方法,其思想最初来源于对鸟群觅食过程的模拟,并最终发展成为一种有效的优化工具[3]。同遗传算法和蚁群算法等智能算法相比,PSO算法简单、容易实现,因此被广泛应用于非线性、多峰值等问题的优化。同时,和遗传算法类似,粒子群算法也存在早熟收敛现象,针对这些问题,国内外学者进行了大量研究工作,并提出了很多改进算法,Shi等引入惯性权重来更好地控制对解空间的开发[4],后来,Berhart和Shi又提出惯性权值线性递减算法[5],使粒子群算法的搜索能力明显改善,该方法在众多领域得到了应用[6,7]。

在可调整参数中,惯性权值是粒子群算法最重要的参数,较大的权值有利于提高算法的全局搜索能力,而较小的权值会增强算法的局部搜索能力。为了能在全局搜索和局部搜索之间取得更好的平衡,本文提出一种惯性权值自适应调整的粒子群算法,惯性权值随着粒子的状态变化而自动调整,计算结果表明该方法具有较好的性能。

1 数学模型

机组组合的约束包括功率平衡、备用容量要求、启停时间要求等条件,其目标是在调度期内,使总燃料费用、机组启停费用之和最小。机组组合的数学描述如下[8]。

1.1 目标函数

式中:Pij是机组i在j时段的出力;Fi(Pij)是机组i在发电功率为Pij时的燃煤费用,并且Fi(Pij)=ai+biPij+ci P2ij,ai,bi,ci为机组i燃煤费用系数;Uij是机组i在j时段的运行状态,当Uij=0时,表示机组i在j时段停机,当Uij=1时,表示机组i在j时段运行;σi,δi表示机组i冷/热启动系数;τi是机组i的起动耗量特性参数,Toff,ij表示机组i在j时段已经停机的时间。

1.2 约束条件

功率平衡约束:

式中:PDj为j时段系统的负荷功率需求。

旋转备用约束:

式中:PRj为j时段系统的旋转备用功率需求。

机组容量约束:

式中:Pimax为机组i的功率上限,Pimin为机组i的功率下限。

启停约束:

式中:Toni,Toffi为机组i的实际连续运行/停机的时间,MUTi、MDTi为机组i的允许最小连续运行/停机的时间。

2 改进的粒子群算法

2.1 基本粒子群算法

在基本粒子群算法中,首先在可行解空间中随机初始化m个粒子构成初始种群,并为每个粒子随机初始化一个速度,每个粒子都对应优化问题的一个解,并由目标函数为之确定一个对应的适应值,而速度用来决定粒子在解空间中的运动。在算法的每次迭代中,粒子将跟踪自身当前找到的最优解和种群当前找到的最优解,逐代搜索直到最后得到最优解。

设n维搜索空间中有m个粒子。第i个粒子表示为Xi=(x i1,xi2,,xin),它经历的最好位置(对应最好的适应值)记为Pi=(pi1,pi2,,pin),简称为Pbest。群所有粒子经历过的最好位置的用gbest表示。粒子的速度用Vi=(v i1,vi2,,v in)表示。对每一代,其速度和位置的调整如下式:

其中:ω为惯性权重,c1,c2为学习因子,rand()为[0,1)范围内变化的随机函数。

为了改善PSO算法的局部搜索能力,Shi引入了惯性权值w,其计算公式为:

式中:k为进化代数,kmax为设定的最大进化代数。

2.2 惯性权值自适应调整算法

线性权值递减策略简单、直观,且具有较好的寻优性能,但是惯性权值只和进化代数线性相关,不能适应算法中非线性变化的特性。事实上,惯性权值应该随着粒子进化速度的变化而变化。

定义:设gfun为粒子群最优的适应度值,avgfun为粒子群平均的适应度值,两者的差值反应进化停滞的程度,则进化停滞系数s=abs(gfun-avgfun)。

本文根据适应度的值将粒子群分成两个子群,对两个子群分别动态地使用不同的惯性权值,从而达到快速收敛的目的。假设优化目标是寻找极小值,将适应度小于平均值的粒子分成子群SUB1,将剩余的粒子分成另一子群SUB2,具体调整惯性权值的公式如下。

对于SUB1,不同的粒子采用不同的惯性权值,计算公式为:

对于SUB2,需要加大并采用统一的惯性权值,计算公式为:

其中:ωmin为最小惯性权重,一般取0.4;b1,b2为调整系数,一般1b=1.5,2b=0.3。

计算步骤如下:

step1:初始化粒子群,包括随机位置和速度;

step2:评价每个粒子的适应度;

step3:若算法满足要求,转step 8,否则执行step4;

step4:对每个粒子,将其适应值与其经历过的最好位置Pbest作比较,如果较好,则将其作为当前的最好位置Pbest,将其适应值与全局所经历的最好位置gbest作比较,如果较好,则重新设置gbest,并计算粒子群的平均适应度avgfun;

step5:计算进化停滞系数S,并根据适应度将粒子群分为2个子群;

step6:根据式(4)、(5)更新粒子的惯性权重,并进一步更新粒子的速度和位置;

step7:将迭代步骤次数加1,转step3;

step8:输出计算结果,结束。

3 机组运行状态识别和约束处理

3.1 机组运行状态识别

粒子每一维的取值范围为[0,Pimax],若某一维取值为[Pimin,Pimax],表示此时段该机组运行,输出功率等于相应的数值;若某一维取值为[0,Pimin],表示此时段该机组停运,并将输出功率置0。

3.2 约束处理

1)发电机出力约束处理

当Pi>Pimax时,取Pi=Pimax;当Pi

2)功率平衡约束处理

如果不满足功率平衡约束,采用随机调整的方式调整发电机的出力,具体调整过程如下:

4 算例

4.1 数学算例

用下面两个函数作为测试函数,求它们的最小值并和线性递减惯性权值方法对比。求解时,设定种群规模为30,最大迭代次数为200,粒子群惯性权重最大值为0.9,最小值为0.4,c1=c2=2,共计算20次,计算结果见表1。

在计算中,取粒子群数为30,迭代次数为500,计算结果如表1所示。

从表1中可以发现,对于两个函数,AWPSO的收敛精度较LDWPSO高,这表明自适应调整惯性权值的方法较线性递减惯性权值方法更能反应优化的搜索过程。

4.2 工程算例

为了进一步验证改进方法的效果,对10机系统24小时调度时段进行了计算,机组参数和运行参数具体见文献[8]。

表2是改进的自适应粒子群算法AWPSO和SGA(simple genetic algorithm)、PSO计算结果的比较[8,9],从表中可以发现,用改进的粒子群算法获得的总费用最低。这说明改进粒子群算法的搜索能力得到提高。

5 结论

惯性权值对算法的搜索能力有明显的影响,本文按照适应度的大小将粒子群分成两个子群,根据粒子群适应度的变化和粒子进化停滞系数自适应调整两个子群的惯性权值,提高算法的搜索能力。通过两个数学算例和一个10机24小时调度算例计算,证明该方法比线性递减惯性权值方法的收敛精度高,体现了该方法良好的性能。

参考文献

[1]Wood A J,Wollenberg B.Power Generation Operation and Control,2nd ed[M].New York:Wiley,1996.

[2]陈皓勇,王锡凡.机组组合问题的优化方法综述[J].电力系统自动化,1999,23(4):51-56.CHEN Hao-yong,WANG Xi-fan.A Survey of Optimization Based Methods for Unit Commitment[J].Automation of Electric Power Systems,1999,23(4):51-56(in Chinese).

[3]Kennedy J,Eberhart R.Particle Swarm Optimization[A].in:International Conference on Neural Networks IEEE[C].Perth,Australia:1995.1942-1948.

[4]SHI Yu-hui,Eberhart R.A Modified Particle Swarm Optimizer[A].in:The IEEE Congress on Evolutionary Computation[C].Anehorage:1998.69-73.

[5]Shi Y,Eberhart R.Empirical Study of Particle Swarm Optimization[A].in:International Conference on Evolutionary Computation[C].Washington(USA):1999.1945-1950.

[6]Robinson J,Rahmat Samii Y.Particle Swarm Optimization in Elect Romagnetics[J].IEEE Trans on Antennas and Propagation,2004,52(2):397-406.

[7]Elegbede C.Structural Reliability Assessment Based on Particles Swarm Optimization[J].Structural Safety,2005,27(10):171-186.

[8]Gaing Zwe-Lee.Discrete Particle Swarm Optimization Algorithm for Unit Commitment[A].in:IEEE/PES General Meeting[C].2003.

[9]Swarup K S,Amashiro S.Unit Commitment Solution Methodology Using Genetic Algorithm[J].IEEE Trans Power Syst,2002,17:87-91.

自适应决策粒子群的相关搜索优化篇2

数字散斑相关方法(Digital Speckles Correlation Method,DSCM)是一种非接触的测量方法,它是通过对被测物变形前后的表面图像序列的灰度信息进行互相关计算,以获取被测物的全场机械力学性能。该方法在二十世纪80年代由日本的I.Yamaguchi及美国South Carolina大学的W.H.Peters和W.F.Ranson[1,2,3]等提出, 与传统力学测量方法相比较,数字散斑相关测量技术由于其对环境要求低,检测灵敏度高、具有非接触、不受工件几何外形和尺寸限制、全场实时检测、检测速率高、无需专门隔振等特点,被广泛地应用于机械制造、航空航天、汽车、船舶和高温条件下的材料性能等各方面的测量,是国际上的热门研究课题。数字散斑相关方法具有视觉测量的特点,通过采集试件形变过程中物体表面图像,进行相关计算来获得物体运动和变形信息[4,5]。

目前已有的相关计算方法包括Newton-Raphson方法(N-R)[6,7]、基于小波降噪相关搜索[8]、遗传算法[9]及粒子群优化方法[10]等。N-R方法计算精度高,原理简单,应用较为广泛,但是也存在着计算效率低,对迭代初值要求高,精度受噪声影响大等缺点。基于小波变换的方法在去噪和计算速度方面具有优势,而计算精度还有待提高。遗传算法改进了数字图像相关的匹配搜索过程,提高了搜索效率。由于该方法能够在较大范围内进行快速的全局搜索,且对相关系数的分布有较强的鲁棒性,故多用于整像的搜索。但该方法运算量大、计算过程较为复杂,实现相对困难。粒子群优化算法(Particle Swarm Optimization,PSO)是一种模拟生物群体习性的智能算法,于1995年由美国电气工程师Eberhart和社会心理学家Kennedy受到鸟群和鱼群的觅食行为的启发而共同提出,它是通过粒子间协作与竞争实现全局搜索,粒子通过内部速度进行更新。由于没有遗传算法的交叉、变异等操作,因此其算法结构简单,易于实现,计算效率高,但该方法依然存在因早熟导致的局部收敛问题。本文提出以下方法解决以上问题:1) 提出基于决策粒子群优化相关方法,该方法能够自行判断迭代终止,节省了在已经找到最佳相关点后还在进行的后续迭代时间,使得相关搜索时间缩短,提高了计算效率。2) 将决策终止方法与自适应惯性因子相结合,最终提出基于自适应决策粒子群新型优化相关搜索算法,该方法收敛速度更快,精度和稳定性更高,有效克服了过早收敛的问题。

1数字散斑相关基本原理

数字散斑相关方法是通过摄像机采集被测试件形变过程中散斑序列图,对所采集的序列图片进行相关计算,其中未变形的图片作为参考图片,变形过程中的图片作为待求的目标图片。

如图1所示的数字散斑相关方法原理图,设参考图片的灰度分布为F(x ,y),目标图片的灰度分布为G(x*,y*),所谓相关匹配就是为了能够在这两幅图片上找到参考图片上点P(x ,y)在目标图片上相关性最好的点P*(x*,y*)。因此当前问题就是如何计算相关系数,而单点灰度值之间的关系无法准确反映相关性,所以需要当前点邻域内所包含的信息共同构成搜索窗口,通常设窗口大小为(2M+1)×(2M+1)(习惯设当前点处于搜索窗口中心位置)。再通过相应搜索规则进行搜索,并利用相关公式计算两个窗口的相关系数,以求取相关系数极值点,这个极值点所处位置即所要寻找相关性最好的点。

在相关文献中了解到,实际测试应用中通常所使用的相关公式包括标准化相关函数、标准化协方差相关函数、最小平方距离相关函数等[11]。在选用相关公式时必须考虑如下因素:可操作性、可靠性、抗干扰性、较小计算量,本文在综合众多因素后选用的标准协方差相关公式为

标准化协方差相关法是将两个相关函数的均方差来对协方差相关函数进行了归一化处理,相关函数C计算结果的取值区间为[-1,1]。当相关系数C=1时,表示当前两个函数完全相同;当相关系数C=-1时,表示当前两个函数完全不相关。因为方差归一化相关方法是标准化的协方差函数,所以该方法对灰度线性变化具有不变性的特征。对上述的相关系数函数使用变形图像进行验证,模板大小为41×41,搜索目标区域为100×100,进行相关运算分析可以得到如图2所示的相关函数数值分布图,从所得的分布图可知,该相关系数函数能够在目标区域中找到极值点位置。

2基于传统粒子群算法的相关搜索方法(PSO)

粒子群算法(PSO)引入数字散斑相关算法后,由于是整像素搜索,则粒子的维度定为2,相应的相关公式(1)作为粒子群的适应度函数。粒子群算法的基本流程如下:

1) 在目标图片上的搜索区域内随机生成n个点,以这n个点为中心点按窗口大小取出各自的目标窗口作为第1代粒子,每个粒子记为xi1(1代表当前粒子的代数);

2) 按式(1)计算当代粒子的适应度,即相关系数R;

3) 分别寻找各个粒子在当前代数的最大相关系数pi-best,以及最大相关系数所处的点;并寻找所有粒子当前代数中的全局最大相关系数gbest,以及其所处点的坐标。

4) 按照式(2)和式(3)更新各个粒子飞行速度vk+1和下一代粒子xik+1;

式中:w为惯性因子,c1和c2学习因子。

5) 根据判断条件判断优化是否结束,判定条件有两种:1判断相关系数R是否达到所需精度要求;2判断是否已经达到最大代数。数字散斑相关测试系统选用的是第二种判定,以期追求更高的精度。如果判定条件为否,则代数N自加1,跳回第2)步。

PSO在散斑图像搜索范围内随机生成M个像素点,通过计算每代的相关系数,寻找自己的历史最优和全局最优从而更新位置和速度,达到最大代数Nmax则结束。在此过程中,粒子群在不断向最相关点集中。

3基于自适应决策粒子群新型优化相关搜索算法

3.1自适应惯性因子的粒子群相关搜索算法

在式(2)中w为惯性因子,w反映了粒子群聚集程度,若w越大则粒子所处位置越分散,全局信息更有利于搜索;若w越小则粒子群逐渐集中,局部信息更有利于搜索。根据这个特点,在已有线性惯性因子(Linear Decreasing Inertia Weight PSO,LDI-PSO)[12]的基础上,相关文献提出了一种自适应惯性因子的粒子群相关搜索算法[13](Adaptive Inertia Weight PSO,AIW-PSO),它能在粒子群最初阶段搜索范围更大,w比较大,不断迭代不断接近最佳点,w不断减小。

自适应惯性因子的粒子群(AIW-PSO)相关搜索算法能够避免过早收敛,并提高粒子群的动态能力。 AIW-PSO引入了群进化速度(ES,用VES表示)和群聚集度(AD,用FAD表示)两个新参数,VES和FAD主要用于更新粒子群在迭代时的惯性因子,其公式为

其中:

VES(k )表示粒子通过计算当前粒子群的全局最优和前一代全局最优从而动态进化。VES较大时说明粒子群已经接近最优解,同时FAD较大可避免粒子群过早收敛。惯性因子w可以通过式(5)计算得到,其中w*是初始惯性因子,k1和k2分别是进化系数和聚集系数,根据多次试验表明k1取值在区间[0.4,0.6],k2在 [0.05,0.2]范围内AIW-PSO算法效果最好。

AIW-PSO分两步计算被测试件形变过程中的位移,先计算出整像素位移然后再计算亚像素位移。该算法对整像素位移的搜索如前所述,而对亚像素位移的搜索过程如下:

1) 通过亚像素插值计算所得的整像素相关点邻域中的亚像素点灰度值;

2) AIW-PSO在计算亚像素位移时,整像素相关点邻域内插值计算出一定区域的灰度值,在此插值区域内随机生成初代粒子群,此时的粒子维度为6维,包括2个位移和4个位移导数;

3) 计算粒子群的相关系数,并寻找历史最优和全局最优,同时计算新的w以及新的速度和新的位置;

4) 根据所得新的位置,计算出新的像素点,同时计算出新的像素点的灰度值,继续循环计算,其循环过程和整像素搜索过程一样。

3.2基于决策粒子群优化相关方法原理

粒子群优化算法在判定是否迭代计算结束的条件有两种:1) 根据迭代的次数,判定是否达到最大的代数;2) 设定接近相关系数理想值的程度。由于第2)种条件在数字散斑相关方法的实际工程测试中无法完全保证其精度,则选用了第一种判定条件。在利用粒子群相关搜索的过程中,可观察到一种现象:在迭代过程中,随着粒子群不断接近相关点,接近真实值的粒子数目会越来越多。采用散斑模拟图验证这一现象, 水平位移u为5 pixels,竖直位移v为3 pixels,粒子群数目M为30个,最大代数Nmax,每隔5代统计达到最相关粒子数目,如图3所示。

根据这个现象,本文提出一种能够自行判断迭代终止的方法,统计粒子达到全局最优解数目,若已达到全局最优解的数目占粒子总数概率超过pmax,则判定迭代终止。

从上图可以看出随着代数不断增加,达到最优解的粒子数目也在不断增加,所以可以根据到达最优解数目判断是否终止判断,若已经超过所设定的概率,强制认为当前所求得全局最优解即为要搜索的最优相关点,此时终止继续迭代过程,这也节省了在已经找到最佳相关点后还在进行的后续迭代时间,使得相关搜索时间缩短。

根据上述特点,本文综合前两节最终提出一种基于自适应决策粒子群(Adaptive Decision Inertia Weight PSO,ADI-PSO)相关搜索算法,使得该算法能够通过在迭代过程不断更新惯性因子加快收敛速度,同时能够更加智能判定终止与否。ADI-PSO相关搜索算法的具体流程图,如图4所示。

4实验验证

本节采用计算机模拟散斑图,由两组对比实验分析了ADI-PSO的性能。

4.1ADI-PSO算法和N-R算法比较

由MATLAB软件生成散斑图(图5)在水平方向u为5.33 pixels,竖直方向v分别为2.1,2.2,…,2.8, 2.9 pixels,比较ADI-PSO算法和N-R算法计算性能。通过计算均匀分布在散斑图上的100个点的位移后, 将所计算的结果与真实值进行比较得到计算的误差和标准差,实验结果精度分析如图6(a),(b)所示。

利用Matlab2010软件编程并运行两种算法对比计算时间得知:N-R算法耗时52.841 03 s,ADI-PSO算法耗时19.476 31 s,N-R算法所用平均时间明显多于ADI-PSO算法。并且从图6可以看出ADI-PSO与N-R算法的计算结果的最大的差距在0.06 pixels以下,二者精度非常接近,由标准差曲线可以看出在稳定性方面两种算法的性能差距不大,ADI-PSO算法在有些结果上比N-R算法更为稳定。

4.2PSO、LDI-PSO、ADI-PSO算法比较

本文通过经典的Sphere测试函数对三种粒子群算法进行优化对比试验。

Sphere函数为:,其范围为[-100,100],初始边界[50,100],达标值:1.00E-01。

三种粒子群算法参数设定如下:传统PSO算法根据Shi[12]和Eberhart[14]所述方法计算得w=0.729,c1=c2=1.494 45为最佳,LDI-PSO算法w从1递减到0.4,c1=1,c2=1.7,ADI-PSO算法w*=1,c1=c2=2, Vmax=-Vmin=0.5,k1=0.5,k2=0.1。迭代次数为500次,每隔5代统计达到最相关粒子数目。测试结果如7图所示。

由图7得知在初始阶段,ADI-PSO和PSO的收敛速度优于LDI-PSO,这是因为在PSO中w较小,而在ADI-PSO中由群进化速度(ES)和群聚集度(AD)决定的w减小速度快,所以这两种算法初始时寻优能力要强于LDI-PSO;接着PSO到达一定代数后趋于稳定,原因为搜索前期w相对较小导致全局搜索能力较低,而后期w又相对较大难以收敛。而ADI-PSO虽然在迭代初期w快速减小,但其值减小幅度不大,大部分粒子w依然较大仍以全局搜索为主;在中后期由于群进化速度(ES)和群聚集度(AD)对w的影响,使得整体以局部搜索为主时,仍有少部分进行全局搜索,并且由于决策终止方法的作用使其在少于LDI-PSO迭代次数的情况下取得更高精度的解,缩短了运算时间。

利用三种算法进行模拟散斑图测量试验,计算均匀分布在散斑图上100点的位移,模拟散斑图水平位移u为5 pixels,竖直位移v为3 pixels,粒子群数目M为30个,最大代数100,每隔5代统计达到最相关粒子数目。独立运行20次,计算最佳适应度值的平均值和标准差,实验结果如表1所示。

采用三种不同质量的散斑图,如图8所示,其中(a)为粗糙散斑图;(b)为中等散斑图;(c)为精细散斑图。

1) 从最佳适应度值的平均值看,PSO在三组实验都存在早熟、局部收敛等问题;LDI-PSO有较好全局搜索能力,其中在无噪声情况下搜索到了期望的全局最大值,但在粗糙散斑情况下陷入局部最优;ADI-PSO在三种情况下都搜索到期望的全局最大值,分别是0.999 8、0.939 1和0.917 6。

2) 从最佳适应度值的标准差看,ADI-PSO算法在无噪声和中等噪声的情况下得到的标准差都为0; LDI-PSO在无噪声情况下标准差为0,除此之外,PSO和LDI-PSO在其余情况下的标准差都大于0。可见, ADI-PSO有较强的稳定性,且明显高于PSO和LDI-PSO。

在Matlab2010下,PSO、LDI-PSO、ADI-PSO算法耗时分别为21.896 30 s,40.694 75 s和19.476 99 s验证了相较于传统PSO、LDI-PSO,ADI-PSO收敛速度更快计算效率更高。

5结论

自适应粒子群优化篇3

电力系统无功优化[1],就是研究当系统结构参数和负荷情况己经给定的情况下,通过对系统中某些控制变量的优化计算,以找到在满足所有特定约束条件的前提下,使系统的某一个或多个性能指标达到最优时的运行控制方案。

在数学上,无功优化是典型的非线性规划问题,具有非线性、小连续、不确定因素较多等特点。目前求解无功优化的方法很多[2,3,4,5],传统的数学规划方法主要有非线性规划法和线性规划法等。常规方法存在的困难主要是离散变量的归整问题,易陷入局部最优以及产生“维数灾”问题。近些年来,为了弥补上述方法在无功优化中计算的不足,研究者将各种智能算法引入无功优化的计算中。

粒子群优化算法是一种基于迭代的多点随机搜索智能优化算法,具有简单易操作、所需设定参数较少等特点,已经被电力工作者应用于无功优化中,目前的粒子群无功优化算法是通过随机生成的初始粒子进行迭代,这对于多峰函数就有可能存在盲区而不被搜索到,易陷入局部解[6,7];此外,在迭代中不能自适应地调整权重系数,限制了全局搜索能力。

针对PSO算法在无功优化中的缺点,本文将混沌算法与粒子群结合,通过混沌算法进行粒子的初始化,并且通过自适应调节权重系数加快搜索能力,形成了自适应混沌粒子群(Adaptive Chaos Particle Swarm Optimization,ACPSO)算法进行多目标无功优化。

1 多目标无功优化的数学模型

1.1 目标函数

在电网有功潮流给定的情况下,多目标无功优化数学模型是在满足系统运行约束和发电机组运行约束的前提下,将系统有功网损Ploss最小、电压质量最好(即电压的偏移量d V最小)和静态电压稳定裕度VSM最大为目标,其中的静态电压稳定性指标采用常规收敛潮流雅可比矩阵的最小奇异值δmin来度量。则建立的多目标无功优化目标函数如下:

式中:Gij为节点i,j之间的电导;iV和Vj分别为节点i,j的电压幅值;θij为节点i,j之间的电压相角差;δmin为收敛潮流的雅克比矩阵的最小奇异值;lV为负荷节点l的实际电压,lVspec为期望电压值,∆Vlmax为最大允许电压偏差,其中∆Vlmax=Vlmax-Vlmin;NL为系统的负荷节点数。

1.2 功率方程约束

在无功优化的数学模型中,各个节点的有功和无功都必须满足系统的潮流方程,其表示为:

式中:PGi,QGi分别为发电机节点i上的有功和无功功率出力;PLi,QLi分别为负荷节点i上的有功和无功功率;Bij为节点i,j之间的电纳;N为系统的节点总数。

1.3 变量约束

无功优化的变量约束方程可分为控制变量约束和状态变量约束。控制变量为:发电机端电压GV,变压器的分接头tT和无功补偿容量CQ;状态变量为:可调发电机无功出力GQ和负荷节点运行电压VD。

满足控制变量的约束条件为:

满足状态变量的约束条件为:

式中:下标“max”、“min”分别表示上限和下限值;NG,NT,NC,ND分别为发电机数、可调变压器分接头数、无功补偿数、负荷节点数。

1.4 归一化处理及加权方法的采用

在多目标无功优化模型中,由于各个目标函数的量纲不同,不能直接进行加权。故先对三个目标进行归一化处理,使其具有可比性。

式中:Ploss 0,d V0,VSM 0分别取为初始状态下经潮流计算得到的有功网损、节点电压偏移量及静态电压稳定裕度;Plossmin,d Vmin,VSM max为分别对其进行单目标优化得到的最优值。Pl'oss,d V',VS'M均限定于0~1之间取值。

运用加权方法处理式(1)中的3个目标函数得到总的目标函数为

式中λ1、λ2、λ3为各个目标权重系数,其反映了对电网优化运行的经济性和电压稳定性的偏好,也称偏好系数,且满足λ1+λ2+λ3=1,其中λ1、λ2、λ3≥0,本文选取λ1=0.6,λ2=λ3=0.2。

2 粒子群无功优化算法

粒子群进行非线性规划的目标函数可以表示为

minF(x1,x 2,⋅⋅⋅,x n)

针对多目标无功优化问题式(7)中的F(x1,x2,⋅⋅⋅,x n)即为总目标函数式(6),x1,x 2,,xn为粒子群算法中的粒子结构,对应为无功优化的控制变量,每个粒子的维数为n,与发电机端电压、变压器分接头、无功补偿容量这些控制变量的个数相等。[aj,bj]为第j维控制变量的可行域即满足式(3)的约束条件;各个控制变量如表1所示,且n=G+T+C。其中,前G维是发电机端电压VG1~VGn;第G+1维到第G+T维是有载调压变压器的变比Tt1~Ttn;最后C维是无功补偿电容器容量QC1~QCn。

PSO算法进行优化问题的求解同其他智能群体优化算法相类似,首先在控制变量可行域的范围内随机地初始化m个粒子形成一个粒子群体。每个粒子由位置和速度两个变量控制其变化,在无功优化中位置代表相应控制变量每次迭代的解,可以用向量xi=[x i1,x i2,,x in]=[Q CT,V GT,T BT]表示,速度代表相应控制变量的迭代修正量,可以用向量vik=[v ki1,vki2,,v kin]=[∆QCT,∆VGT,∆TBT]表示。利用每次迭代得到的一组控制变量代入式(6)求出总目标函数的值作为粒子群算法中粒子的适应值,采用该数值的大小来衡量所求得解的优劣程度,通过k次迭代,得到当前为止控制变量的最优解为个体最优解,用向量Pbesti=[Pbest i1,Pbesti 2,,Pbestin]表示,m个粒子中最好的个体最优解为群体最优解,用向量gbestk=[Pbestk 1,Pbestk 2,,Pbestkn]表示,当找到了Pbesti和gbestk这两个最优解后,各组控制变量在每一次迭代过程中,根据公式(8)、(9)更新各控制变量的数值和迭代修正量:

式中:i=1,2,,m;j=1,2,,n;k为迭代次数;w为惯性权重;c1,c2为学习因子,表示每组控制变量追寻两个最好极值的加速系数;r1,r2为两个均匀分布在(01),之间的随机数;ivk,j表示第k次迭代时粒子速度,在[-Vjmax,Vjmax]之间取值,本文Vjmax取为控制变量取值范围的20%。

通过各组控制变量的不断迭代更新,反复进行潮流计算,最终找到优化问题的最优解。

无功优化中发电机端电压GV是连续控制变量,对其直接采用实数编码;变压器分接头tT和无功补偿容量cQ是离散控制变量,采用一定的映射方法将其转换为连续变化的整数变量,对其采用整数编码。采用这样的整实数混合编码更加符合电力系统无功优化的实际情况。

3 自适应混沌粒子群算法的无功优化

3.1 利用混沌算法初始化各控制变量

上述的粒子群无功优化算法,采用的是随机生成初始粒子,这样对于多峰函数就有可能存在盲区而不被搜索到。由于混沌优化算法具有对初值不敏感的特点,本文在利用粒子群进行无功优化的前期采用混沌算法进行初始化,优选初始粒子群体——无功优化控制变量。

(1)混沌初始化粒子群无功优化中发电机端电压、无功补偿容量和变压器分接头这些控制变量的位置和速度。随机产生一个n维且各分量值均在0~1之间的混沌矢量Z1=(z11,z12,,z1n),以Z1为初始值由Logistic完全混沌迭代公式zt+1=4zt(1-zt)t=0,1,2,计算得N个矢量Z1,Z2,,ZN。利用混沌变量进行迭代搜索,再通过公式xij=aj+(bj-aj)zij,(i=1,2,,N;j=1,2,,n)将混沌变量Zi(i=1,2,,N)的各分量变换到式(3)的约束范围,其中aj,bj与式(7)的含义相同,为无功优化控制变量约束式(3)的上下限值。

(2)根据多目标无功优化的总目标函数式(6)来计算各矢量所对应的适应度值,根据适应度值的大小从中择优选取前m个作为粒子群的初始位置,同时在无功优化控制变量的限制范围内随机生成m个初始速度,本文m取为30。

3.2 利用混沌算法对优选的控制变量值进行操作

由于粒子群算法进行无功优化在迭代后期产生“惰性”运动使各粒子趋于同一性(失去了多样性)而导致通过该算法无功优化得到各控制变量易陷入局部解区域,故对迭代更新后择优选取的前M(M=20)个较优控制变量值进行混沌操作。

(1)首先将群体中的每组控制变量Xp=(xp1,x p2,,xpn),(p=1,2,,M)的各分量x pj(j=1,2,,n)通过zpj=(xpj-aj()bj-aj)方程映射到混沌空间,再依据迭代公式zt+1=4zt(1-zt),t=0,1,2,产生混沌变量序列zp(sj),用混沌变量进行搜索寻优。

(2)将该序列通过逆映射方程xp(js)=aj+(bj-aj)·zpj(s)转回到原解空间得Xp(s)=(xp(1s),xp2(s),,xp(ns)),计算混沌变量经历的每一个可行解Xp(s)的适应度值并择优选取前M个解Xp*。

(3)用Xp*取代当前群体中任意M组控制变量值,若Xp*中存在适应值优于全局最优解的控制变量,则以其代替全局最优点gbest并更新全局极值。

3.3 自适应调节惯性权重

在PSO算法进行无功优化中,式(8)的惯性权重w的取值对算法的性能具有十分重要的作用,即平衡算法的全局寻优和局部寻优。w取值大时利于全局寻优,但很难得到精确的解;w取值小时利于局部寻优,但w易陷入局部极值点。为提高算法的性能,本文采用一种基于粒子个体适应值的自适应调节w的策略,即每个粒子的w依据其自身当前的适应值来进行调节变化,其公式表达为:

式中:wmin,wmax分别为惯性权重系数的最小值和最大值;fi为当前粒子的适应值;fav,fmin分别为当前整个粒子群体适应值的平均值和最小值。可见,个体适应值较好的粒子对当前最优解临近区域做局部细致搜寻,个体适应值差的粒子会以较大步长搜寻以便能找到更好解,进而保证了整个群体解的多样性及好的收敛性。

3.4 自适应混沌粒子群多目标无功优化的基本步骤

(1)读入原始数据,包括网络结构数据、构成无功优化解的可行域的各控制变量上下限约束。

(2)根据无功优化控制变量的个数确定粒子群体粒子的维数n,在三类控制变量即发电机端电压GV、变压器分接头tT和无功补偿容量CQ的上下限约束范围内进行混沌初始化粒子群中各粒子,即控制变量的位置和速度。

(3)根据粒子编码的控制变量值,对初始群体中的每个粒子利用粒子群无功优化算法进行无功优化,无功优化中采用牛顿拉夫逊法进行潮流计算。

(4)根据总目标函数式(6)来确定每个粒子的适应度值,比较粒子的优劣,进而更新群体中的个体最优解Pbesti及全局最优解gbestk,由式(10)自适应计算各粒子的惯性权重w。

(5)择优选取前M个较优粒子进行混沌优化。

(6)根据粒子群无功优化算法中的公式(8)和(9)更新粒子的速度和位置——即控制变量的迭代修正量和数值。

(7)若满足终止条件则停止运行,输出全局最优解,否则返回步骤(3)继续进行迭代计算。

4 算例分析

采用本文所提方法对IEEE 30节点系统和IEEE118节点系统进行多目标无功优化,并与PSO算法和文献[8]中的遗传算法(GA)进行比较,结果如表2所示。

IEEE 30节点数据参见文献[9],初始条件下,设发电机端电压在0.9~1.1 p.u.之间连续取值,可调变压器的变比调节步长为0.025,变比调节范围为0.9~1.1,分八个档,补偿电容的调节步长为0.05,分十个档,补偿上限为0.5 p.u.,发电机的初始电压及变压器的初始变比均为1.0,功率基准值SB=100MVA。

算法中相关参数设置如下:粒子群规模n=40,学习因子c1=c2=2,wmin=0.4,wmax=0.9,最大迭代次数iiter max=100,独立运行50次,表2给出了在相同基本条件下,各优化算法得到的平均优化结果。

从表2可以看出,采用本文提出的ACPSO算法进行多目标无功优化,计算后有功损耗由5.46MW降到4.87 MW,降幅为10.89%,其结果优于另外两种算法。电压偏移量和静态电压稳定裕度指标的优化结果也都具有一定的优势。

表3给出了三种算法优化后各控制变量的最优值。从表中可以看出,ACPSO算法优化后各节点电压距其上下限有一定的距离,具有较好的电压质量,很好地解决了无功电源的出力接近极限,减少了无功优化目标函数与系统电压安全之间的冲突,较好地协调了二者之间的关系。

表2和表3的比较结果显示,自适应混沌粒子群算法进行多目标无功优化能够在全局范围内搜索到更优的解。

图1所示为ACPSO、PSO和GA算法在求解多目标无功优化过程中目标函数的收敛曲线图。

从图中可以看出,ACPSO算法在开始几代下降速度很快,显示了混沌初始化使该算法能从较好的初始值开始寻优,进而加快了搜索速度和整体提高了ACPSO的优化效率,其在迭代40次左右时已经能够非常接近最优解,而PSO算法要迭代到50次才能达到最优解,GA要迭代65次左右才能达到最优解,可见本文提出的算法具有较好的收敛性。

表4是ACPSO与PSO分别取相同粒子群数、迭代次数,独立运行50次时,得到的多目标无功优化问题最优解。

由表4可知,随着群体数的不断增加,两种算法所得的三个优化指标都越来越好,符合通常算法的优化规律。当群体数相同时,两种算法的优化结果相似,说明两种算法都能有效地搜索到多目标无功优化问题中的最优解,但ACPSO所得的平均最优解始终比PSO所得的好,且优化时间短,与原算法相比改进后的算法稳定搜索能力确实有所提高。当群体数从20增加到50时,ACPSO算法求得的平均最优值相差较小,也说明该算法具有良好的收敛稳定性。

IEEE118节点系统包含54台发电机、8台可调变压器及14个无功补偿点,系统参数参考文献[9]。将该算法独立运行50次,同样与另外两种算法做比较得出的平均优化结果如表5所示。

由表5中结果可知,在求解高维优化问题时,ACPSO算法显示出它的优越性,由于ACPSO算法对维数不敏感的特性,使其更适于应用在大规模复杂电力系统无功优化的求解中。通过以上两个典型算例分析可知,本文所提算法是值得信赖且有效的。

5 结论

采用自适应混沌粒子群算法进行无功优化可以通过混沌初始化无功优化控制变量值,使PSO算法能从较好的初始值开始进行寻优,同时,迭代更新控制变量值的过程中自适应调节惯性权重系数加快了迭代收敛的速度,并采用混沌算法优化部分较优的控制变量值等改进措施有效地克服了PSO算法容易早熟、陷入局部极值的缺陷,从而增强了算法找到全局最优解的能力。算例分析验证了ACPSO算法进行无功优化的有效性。

参考文献

[1]许文超,郭伟.电力系统无功优化的模型及算法综述[J].电力系统及其自动化学报,2003,15(1):100-104.XU Wen-chao,GUO Wei.Summer of reactive power optimization model and algorithm in electric power system[J].Proceedings of the EPSA,2003,15(1):100-104.

[2]张勇军,任震,李邦峰.电力系统无功优化调度研究综述[J].电网技术,2005,25(2):50-57.ZHANG Yong-jun,REN Zhen,LI Bang-feng.Survey on optimal reactive power dispatch of power systems[J].Power System Technology,2005,25(2):50-57.

[3]李秀卿,王涛,王凯.基于蚁群算法和内点法的无功优化混合策略[J].继电器,2008,36(1):22-26.LI Xiu-qing,WANG Tao,WANG Kai.A hybrid strategy based on ACO and IPM for optimal reactive power flow[J].Relay,2008,36(1):22-26.

[4]万黎,袁荣湘.最优潮流算法综述[J].继电器,2005,33(11):80-87.WAN Li,YUAN Rong-xiang.The arithmetic summarize of optimal power flow[J].Relay,2005,33(11):80-87.

[5]Kenney J,Eberhart R.Particle swarm optimization[C].//Proceedings of IEEE Conference on Neural Networks,Perth,Australia,1995.

[6]王秀云,邹磊,张迎新,等.基于改进免疫遗传算法的电力系统无功优化[J].电力系统保护与控制,2010,38(1):1-5.WANG Xiu-yun,ZOU Lei,ZHANG Ying-xin,et al.Reactive power optimization of power system based on the improved immune genetic algorithm[J].Power System Protection and Control,2010,38(1):1-5.

[7]张峰,段余平,邱军,等.基于粒子群算法与内点法的无功优化研究[J].电力系统保护与控制,2010,38(13):11-16.ZHANG Feng,DUAN Yu-ping,QIU Jun,et al.Research on reactive power flow based on particle swarm optimization and interior point method[J].Power System Protection and Control,2010,38(13):11-16.

[8]谢敬东,王磊,唐国庆.遗传算法在多目标电网优化规划中的应用[J].电力系统自动化,1998,22(10):20-22.XIE Jing-dong,WANG Lei,TANG Guo-qing.The application of genetic algorithm in the multi-objective transmission network of optimization planning[J].Automation of Electric Power Systems,1998,22(10):20-22.

自适应粒子群优化篇4

电力系统无功优化主要目的是在合理的电压质量要求下尽量降低网络损耗, 其主要控制手段有调节发电机端电压、控制有载调压变压器的分接头和可投切并联电容/电抗器。其中, 发电机端电压 (或无功出力) 是连续变量, 补偿电容器/电抗器和有载变压器分接头档位是整数变量, 因此, 无功优化是一个典型的整、实数混合的多变量、非线性的优化问题。

粒子群优化算法PSO (Particle Swarm Opti-mization) 最初源于对鸟群捕食行为的研究, 是一种新的进化计算方法 (Evolutionary Computation) , 也是一种群智能优化算法 (Swarm Intelligent Optimization) 。此算法及其在相关领域的应用已引起各国学者广泛关注, 被越来越多地应用于智能优化、模式识别、神经网络的训练等诸多领域。

1 电力系统无功优化的数学模型

本文采用有功网损最小为控制优化目标函数, 以发电机无功出力和节点电压为状态变量, 以有载调压变压器变比、无功补偿电容器容量和发电机端电压为控制变量, 数学模型如下:

等式约束方程为:

控制变量不等式约束:

状态变量不等式约束:

式中:NE为支路号集合, Ni为与节点i有关联的节点号集合, NPQ为P·Q节点号集合, NB为总的节点号集合, NG为发电机节点号集合, Nr为变压器支路集合, NC为补偿电容器节点集合;S为平衡节点;Gij为支路ij的电导;Bij为支路ij的电纳;Vi, Vj为节点ij的电压幅值;θij为节点ij的电压相角差;QCi为节点i的无功补偿容量。

2 自适应粒子群算法无功优化过程

采用连续变量和离散变量混合的实数编码, 求解步骤如下:

步骤1:输入系统数据, 初始化粒子群。首先输入系统的结构、网络数据和控制参数, 其中发电机节点电压的上下限、电容器容量的上下限、变压器分接头上下限等构成了解的可行域。其次确定粒子的维数M。

步骤2:计算目标函数值。对群体中的每个粒子, 分别进行潮流计算, 得到每组控制变量取值下的有功网损, 并判断是否违反节点电压以及发电机无功出力等约束, 将电压及发电机无功越界值作为罚函数项计入到目标函数。

步骤3:记录两个极值。比较所有粒子对应的目标函数值, 首先记录粒子i (i=1, 2, …, N) 当前的个体极值PBest (i) 及答应的目标函数值F (PBest (i) ) ;从PBest (i) 中确定整体极值GBest, 并记录GBest答应的目标函数值F (GBest) 。

步骤4:计算适应值判断可行解:计算各粒子适应值, 并验证是否是问题的可行解, 是可行解的粒子按适应值由小到大排序, 分类记录迭代结果。

步骤5:更新最优值:若粒子是问题可行解且适应值优于历史群体最优值, 则更新群体最优值;取问题可行解的前4个最好粒子替代历史其余粒子的最好解进行速度更新。

步骤6:混沌变异:若粒子相邻三代适应值无变化或变化率小于某极小值, 且此粒子的适应值不是群体最优值, 则此粒子陷入局优, 应对每维变量进行变异。

步骤7:输出问题的解, 包括发电机机端电压、补偿电容器组数和变压器分接头档位等控制变量的取值情况, 系统各节点电压、发电机无功出力等状态变量的数据, 以及对应的网损值。

3 算例仿真分析

为了检验上述利用粒子群优化算法求解无功优化问题的有效性, 本文使用IEEE30节点试验系统进行计算。系统参数均用标么值表示, 其基准功率是100MW。P-V节点和平衡节点的电压上下限设置为0.9和1.1。P-Q节点的电压上下限设置为0.96和1.04。表1列出了分别采用原对偶内点法和本文算法 (取群体规模N=30) 优化前后各变量的取值情况, 其中方法一为原对偶内点法, 方法二为本文粒子群优化算法。

可以看出采用粒子群算法优化后, 发电机无功出力和无功补偿都在约束范围内, 系统节点电压普遍得到了改善, 最低电压由0.94提高到1.02, 可以取得更好的经济效益。

4 实际算例分析

算例为七台河某地区电力系统, 有2台发电机, 6个并联电容器 (节点16、20、22、25、28、31) , 6台可调变压器, 系统负荷load S=125.24+j79.71, 并联电容器无功出力调节范围:节点16、20为-0.06~0.06;节点22、25为-0.06~0.18;节电28、31为-0.06~0.24;可调变压器抽头变化范围均为0.9~1.1。运用算法优化后, 网损显著下降, 其中本文提出的IDE算法的降损效果最好。系统无功优化前, 有9个节点电压标幺值低于0.95, 最低点电压发生在节点31, 其标幺值为0.874, 电压质量情况很不理想;优化后, 各节点电压质量明显提高, 最低节点电压 (节点31) 标幺值为0.99。图1为优化前后各节点电压曲线。

4 结论

本文提出了一种粒子群优化算法, 采用符合均匀分布规律的粒子作为初始粒子种群, 为确保更好地在全局范围搜索, 在粒子速度和位置更新时不仅仅考虑粒子的个体最优和群体最优两个极值, 提出了粒子自身探索机制。经过IEEE-30节点系统的计算分析, 此PSO方法具有优越的计算效率和良好的收敛性, 非常适用于求解电力系统无功电压的综合控制问题, 具有较强的实用价值。

参考文献

[1]Clerc M, Kennedy J.The Particle Swam Explo-sion, Stability and Convergence in a Multidi-mensional Com-plex Space[J].IEEE Trans on Evolutionary Computation, 2002, 6 (1) :58-73.

[2]张勇军, 任震, 李邦峰.电力系统无功优化调度研究综述[J].电网技术, 2005, 29 (2) :50-56.

自适应粒子群优化篇5

基于群体智能理论的计算技术的研究成为了近几年研究的热点, 蚁群算法、粒子群优化算法、混合蛙跳算法等等都是基于群体协作的搜索算法。粒子群优化算法[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。

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

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

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.

自适应粒子群优化篇6

旅行商问题( TSP) 是典型的NP完全问题,随着问题规模的增大,解空间极具膨胀。对于大规模旅行商问题,常规递归搜索算法难于在容忍的时间内获得满意解。但由于旅行商问题具有广泛的应用价值,如智能交通控制、管道焊接最佳距离选择,网络路由路径选择、大规模电路图自动布图,智能物流配送,电力系统输电线路规划以及GPS路径导航等诸多领域问题的求解都能转化为旅行商问题模型,在不能获得全局最优的情况下,高效寻找高质量的近似解是当前解决这一问题的主要途径。近年来,多种启发式搜索方法都在这一领域获得了成功应用。目前求解旅行商问题的启发式搜索方法包括湖水能量优化算法、遗传算法、郭涛算法、量子算法、近邻搜索、杂草优化算法以及粒子群优化算法等[1,2,3,4,5,6,7,8]。

文献[9]成功实现了基本粒子群优化算法求解小规模旅行商问题,文献[10]提出的增强型自探索粒子群优化算法很好地解决了城市规模100 左右的旅行商问题,文献[11]在此基础上提出了改进,对于200 节点以内的旅行商问题,能够以较高概率获得当前已知全局最优解,但其依然属于随机搜索算法,没有利用进化过程信息,对于大规模旅行商问题很难获得高质量的解。为此,本文在原有算法中引入变异机制,同时对进化过程中获得的进化信息进行学习,提出自适应混合粒子群优化算法求解大规模旅行商问题。自适应性包括进化过程自适应进行、重要参数自适应变化和粒子结构依据进化信息自适应调整三个方面。算法进化分多批次自适应进行,每个批次包括两个阶段———第一个阶段,利用混合算法进行多次搜索,并将获得的多个局部最优解,并记录在周游边结构中,同时记录多次实验所获得的最佳周游路线; 第二阶段,首先,对第一阶段所产生的周游边结构进行学习,找出所有公共边,产生多个关键边序列段,每个序列段看成一个整体,以此缩小问题规模。用这些关键序列段和剩余单个节点集,再结合公共边结构中记录的边的情况,依概率重新初始化种群,同时用这些关键边序列段处理记录的最佳周游路线,使其和重新初始化后的种群具有相同的粒子结构,并把处理后的序列作为当前全局最优解,并清空周游边结构; 在此基础上继续进行下一个批次的进化搜索和记录周游边; 上述过程反复进行,直到在某批次的第一阶段多次进化都收敛于同一个局部最优解为止。仿真实验结果分析对比表明,这种自适应方法求解大规模旅行商问题能够获得高质量的近似解。

1 粒子群算法优化算法

PSO算法求解旅行商问题的基本迭代公式如式( 1 ) 和式( 2) 所示。基本粒子群优化算法及增强型自探索粒子群优化算法及其求解旅行商问题详细设计、参数说明与求解过程详见文献[9 - 11]。

2 旅行商问题简述

旅行商问题属于NP完全组合优化问题,解空间随着问题规模N呈阶乘增加。对称TSP问题的解空间大小为( ( N - 1) !/2) ,对于较大规模( N ≥ 18) TSP问题,传统递归搜索都不能在容忍时间内获得满意解,为此常被用于检测和验证启发式算法的有效性。旅行商问题描述如下。

有N个城市,从某一个城市出发,遍历完所有城市并回到出发城市,找出所有可能遍历路径中的最短路径。其形式化描述为: 给定一个连通图G( X,E) ,其中,X为城市节点的集合,E为赋权边的集合,即两两城市距离的集合。问题的目标是寻找一条周游距离最短的Hamilton周游回路。设城市节点集合为X ={ 1,2,…,N} ,采用双城市节点表示边,即E = { ( i,j,wij) i,j ∈EG,wij∈ R+} ,两个城市i和j之间的距离为wij,如果是对称问题,则两个城市之间来回的距离相等wij= wji。假设第i个粒子的表示为Xi= ( xi1,xi2,…,xik,…,xi N) ,1 ≤ xik≤ N,1 ≤ k ≤ N。则粒子i所表示的TSP周游路线总长度为:

假定从城市编号1出发,如果k=N,则k+1=1。目标找出f(Xi)最小的粒子位置Xi。若边(xik,xi(k+1))∈E,则存在正整数Wxikxi(k+1)∈R+,否则表示城市xik和城市xi(k+1)没有直接通路,设置Wxikxi(k+1)为一较大数值。

3 自适应混合粒子群优化算法

为了提高混合算法求解大规模TSP问题的能力,需要对进化过程获得的有用信息进行记录和利用,为此,本文提出周游边结构用以记录高质量周游路线边的分布。

3. 1 周游边结构

针对旅行商问题周游边为城市节点的顺序,为了能够反映局部最优解边的分布情况,本文采用双节点表示边,提出链式周游边结构,即记录每个节点之后出现过的所有节点情况,并且记录每个节点出现的频次,以此记录该边出现的频次,新出现的节点插入到链表最后。这样可以记录周游路线中一个城市节点边的情况,以数组方式管理所有城市节点。周游边结构如表1所示。

表1 中,城市节点结构用于描述与某个城市节点K相关联的边的情况。边的总数量用于描述与该城市节点K相关联边总数量。节点标记在生成关键边时,用来标记该城市节点是否已经输出到路径中,防止再次输出。边结构指针指向边结构,表示与K节点相关联的边的城市节点的情况。其中,城市节点编号描述与K相连的另一个城市节点的编号,频次表示该城市节点出现在K节点之后的总次数,边结构指针表示与K节点相关联的另一条边的情况。例如6 个城市节点TSP问题,单向记录周游路线( 1,2,3,6,4,5) 和( 1,2,3,5,6,4) 之后,其周游边结构记录信息如表2 所示。

从表2 中可以看出,经过记录上述两条周游边后,与城市节点2 单向相连的边只有1 条( 2,3) 并且出现2 次。如果该问题为对称TSP问题,即两两城市之间来回的距离相等,则将两条周游路线逆转后再单向记录一遍。即再将边( 1,5,4,6,3,2) 和( 1,4,6,5,3,2) 记录后,形成如表3 所示周游边记录信息表。

从表3 中可以看出,经过记录上述两条周游边及其逆转序列( 共4 条周游路线) 后,与城市节点2 单向相连的边只有2 条( 2,3) 和( 2,1) 并且都出现2 次。

3. 2 自学习进化信息生成关键边序列段

经过对多个高质量局部最优解周游边情况的记录,将得到能够反应高质量局部最优解周游边分布的信息结构。该结构能够反映与某城市节点k相连的所有边的情况,并按出现的频次排列。为了能够有效减少搜索空间,如果多个局部最优解都包含某条边,则该边将以较高概率出现在全局最优解中。本文称这些边为关键边,并采用如下策略寻找所有关键边。

针对对称旅行商问题,为了确保关键边能以高概率出现在全局最优解中,依据周游边结构特点,凡某节点k之后只有2 条边,说明与该节点连接的两条边将以高概率出现在全局最优解中,则这两条边为关键边而且相连,与之相关联的城市节点形成关键序列段。针对非对称TSP问题,凡某节点之后只有1 条边,说明与该节点连接的这条边顺序已定,至少这两个节点可以归约为一起。

对于6 城市对称TSP问题,从表3 可以看出与城市节点2相连的边有且只有2 条边,则边( 2,3) 和( 2,1) 为关键边,且共用同一个城市节点,则这两个关键边可以连接起来,形成关键边序列段,简称关键序列段,表示为: 1 - 2 - 3 或3 - 2 - 1,由于是对称问题故二者等价。关键序列段看成一个整体,原有6 个城市的TSP问题缩减为一个关键序列段和3 个城市节点的组合优化问题,原有问题规模从6 缩小到4,解空间得到有效缩减,由原来的120 条周游路线,缩减为12 条。对于大规模问题,缩减效果更佳明显。

如果是非对称TSP问题,则不需要对周游边进行逆转和二次记录,直接依据如表2 可以看出,节点1 后只有一条边( 1,2) ,节点2 后也只有一条边( 2,3) ,由于顺序已定,且共用同一个节点,故可以将二者合并,同样可以得到序列段1 - 2 - 3。

对于具有n个城市节点的TSP问题,采用类似的方式可以找到多个关键边,并将具有共用城市节点的关键边连接起来形成关键序列段。对于大规模TSP问题,通过上述方法可以获得多个关键序列段,为了提高后续进化的效率,继续利用周游边结构中记录有效信息重新初始化种群,采用策略如下。

首先要从公共边结构中删除( 标记) 序列段中间节点,避免再次出现在解序列中。其次,为了有效缩减搜索空间,由关键边组成的序列段不再改变。最后,为了提高收敛速度,避免无效搜索,继续利用公共边结构纪录的信息,依概率连接各个序列段或游离节点,即如果序列段边界节点及游离节点,具有多个可选节点,则根据随机概率进行分配选择。具体实现如下。

将关键边序列段和游离节点以集合形式组织起来( 总数量Gnumber = 序列段+ 游离节点= 问题规模总数- 每个序列段包含节点的总和+ 序列段个数) ,并编号。根据公共边结构所记录的边的情况( 出现概率) ,随机生成解序列。为了提高计算效率,对关键序列段做如下处理。

如果序列段中包含1 节点,则以第1 个关键序列段( 包含1节点) 为起始节点。否则,仍旧以1 节点为起始节点,其他节点依概率随机排列。

为了提高收敛的效率,采取精英保持策略,即使用记录多次实验的最佳局部最优解作为当前全局最优解,即学习的目标,用以指导种群在规模缩小后的高效指导作用。但该局部最优解与当前重新初始化后的种群中的个体具有不同的粒子结构,该粒子不具有关键序列段,需要用生成的关键序列段对其进行处理,使其具有和其他粒子相同的结构即可进行下一个轮回的进化计算。

通过上述方法可以将于大规模TSP问题约减为较小规模的TSP问题,然后继续使用混合粒子群优化算法进行求解多次,如果能够获得更好的解则更新原来记录的多个局部最优解信息,并在多次进化结束后继续进行学习和继续进化,如果多次进化都收敛与同一个解则算法终止。该解即为算法获得的最终解。

3. 3 自适应策略

为了提高算法的整体性能,在前期工作和实验总结的基础上,自适应性策略包括以下三个方面。

3. 3. 1 进化过程多批次分阶段自适应进行

为了算法尽可能获得高质量的近似全局最优解,整个进化过程分多批次分阶段自适应进行,每个批次包括两个阶段。第一阶段,进行多次混合搜索实验并记录每次搜索所得的最佳周游路线边信息于周游边结构。第二阶段,对周游边结构进行学习,获取关键序列段,并以此自适应调整粒子结构,重新初始化种群。同时记录多次实验的最佳解,并用关键序列段进行处理,使其与重新初始化的种群具有相同的粒子结构,该解即为下个批次实验第一阶段多次实验的当前全局最优解。算法不设定搜索的批次数,只设定第一阶段的进化搜索次数,搜索过程依据每次所获得的解自适应进行,如果在某批次第一阶段进化搜索都收敛于同一个局部最优解时,则退出搜索过程,算法整个进化过程结束。

3. 3. 2 粒子结构自适应变化

为了减少进化过程中的无效搜索,提高算法搜索的效率,提出了粒子结构自适应变化思想。算法在进化搜索的开始,粒子由一个个单独的城市节点构成,经过第一个阶段的进化,并对进化过程有用信息的学习,将多个关键边归结为一个关键序列段,并看作一个整体,该序列段中的节点顺序不再改变,从而减少了无效搜索的次数。例如: 6 个城市的TSP问题,开始时,粒子结构( 1,2,3,6,4,5) ,经过第一阶段进化以及对进化过程信息学习后,获得关键序列段1 - 2 - 3,则粒子结构可变为( 1 - 2 - 3,6,4,5) ,即粒子结构由关键序列段和自由城市节点组成。

3. 3. 3 进化参数自适应变化

为了提高算法的搜索效率,混合算法中的几个关键参数在进化中根据进化代数和问题规模( 关键序列段的引入,相当于问题规模缩小) 自适应变化。惯性权重依据进化代数自适应变化,如式( 4) 所示[10]。

另外,学习因子c1 和c2 依据问题规模分区间自适应设定。当问题规模N < 100 时,c1 = 0. 2,c2 = 0. 3,当500 > N ≥ 100,c1 = 0. 02,c2 = 0. 03,当N ≥ 500 时,c1 = 0. 002,c2 = 0. 003 。

最后,序列段调整算法中的序列段最大长度K依据问题归约规模N自适应变化,K = N/4 。

3. 4 混合粒子群优化算法

改进增强型自探索粒子群优化算法属于随机搜索算法,由于其采用黑板学习模型,会导致所有粒子向当前全局最优粒子靠拢,一旦陷入某局部最优的束缚,单靠粒子本身的学习和探索能力难于逃出束缚,限制了算法的全局搜优能力。为此,借鉴生物进化过程中出现的变异现象,在改进增强型自探索粒子群优化算法的基础上,再次引入变异机制,从而形成混合粒子群优化算法。增强型自探索粒子群优化算法及其改进求解旅行商问题实现过程详见文献[10,11]。

算法中粒子的位置信息是所有城市编号的一个全排列,速度为位置置换序列,通过改变置换序列,可以达到改变粒子位置的目的,从而实现粒子摆脱局部最优的束缚的目的。故算法中采用速度变异机制,简述如下。在算法中,设置一个种群最大停滞常数TZmax和一个种群停滞代数统计变量Bt,如果种群在某代进化后,当前全局最优没有得到任何改善,即没有搜索到比Pgbest更好的解,则Bt = Bt + 1,否则,Bt = 0。当Bt > TZmax时,算法进行速度变异,即通过轮盘赌算法选择一部分粒子,清除原有速度,重新随机生成。这样经过速度变异后的粒子会快速脱离原有位置,即逃离局部最优的束缚,在新的位置重新开始搜索,这样增大了其发现全局最优的机会,提高了算法的全局搜优的能力。

4 SAHPSO求解TSP问题算法流程

根据上述思想,自适应混合粒子群优化算法求解旅行商问题算法流程描述如下:

Step 1

设置所求解问题的系统参数,如问题的规模,两两城市之间的距离权值和种群规模以及边界条件等,设置每个阶段多次进化搜索的搜索次数Sn等。

Step 2

设置进化次数i = 1 。

Step 3

如果i > Sn ,则转Step13。如果关键序列段不为空,则使用关键序列段和游离节点,并根据周游边结构信息,初始化种群,并使用记录的最优解替换Pgbest,并根据关键序列段和游离节点信息设置当前搜索问题规模。否则,随机初始化种群,即随机产生位置向量和调整序,初始化Pbesti和Pgbest 。

Step 4

计算问题归约规模,并根据归约规模自适应设置学习因子c1 和c2,最大进化代数Mt,设置当前进化代数t = 0 。

Step 5

根据式( 3) 计算每个粒子的适应值f( Xi) ,如果该位置优于Pbesti,则Pbesti被当前位置替换; 否则Pbesti保持不变。

Step 6

在当前个体的最优解Pbesti中选择一个最优值,如果它优于Pgbest,则用其更新Pgbest 。

Step 7

按式(4)计算惯性权重w,并随机产生r1和r2。

Step 8

按式(1)和式(2)进行速度和位置更新。

Step 9

对每个粒子依据单点调整算法和序列段调整思想进行粒子增强型和改进增强型自探索搜索和位置更新。

Step 10

如果Pgbest没有得到改善,则Bt = Bt + 1; 否则,Bt = 0; 如果Bt > TZmax,则进行速度变异,并Bt = 0 。

Step 11

t = t + 1,如果t < Mt,转到Step 3,继续迭代; 否则终止迭代。Pgbest所记录的位置即为本次实验的最优解。

Step 12

将Pgbest记录于周游边结构,i = i + 1 ,转到Step3。

Step 13

如果Sn实验获得同一个解,则转Step 15。

Step 14

对周游边结构进行学习,获得关键序列段; 用获得的关键序列段处理Sn次实验所记录的最优解,并用该最优解作为下次进化的全局最优解,否则转Step 2。

Step 15

算法终止,多次获得的同一个解即为算法获得的最佳近似解,输出该解的周游线路图。

5 算例分析

本文实验采用Intel E7400 CPU,4 GB内存,Windows XP SP3操作系统,用Delphi 7. 0 开发Windows窗体单线程应用程序,能够实时显示进化过程信息和周游路线图实时绘制显示功能,故算法运行耗时偏高,CPU占用率约为50% 左右。

为了说明算法自适应策略的有效性,同时提高算法的执行效率和结果的可对比性,每个阶段都采用文献[11]中的实验策略,分别进行30 次独立实验( d1291 和Fl1400 两个实例,自学习后进行10 次独立实验) ,实验结果对比如表4 所示。误差对比如表5 所示。其中,ACOMGR为文献[2]中的方法,ILSBCO为文献[3]中的方法,Closet-point算法和CPBOA为文献[12]中的方法。表中“- ”表示文献没有对该算例进行求解。

从表4 可以看出,对于较大规模的9 个旅行商问题,本文提出的自适应混合粒子群算法( SAHPSO) 无论平均解的质量还是与已知最优解的误差都要远远小于文献[12]和文献[3]中的实验结果。平均每次求解的时间也在可接受的范围内,最长时间仅为4083 秒。对于Pcb442 和u724 两个实例,本文的算法获得的解劣于文献[2]中的结果,说明这两个实例存在的局部最优对本文求解方法影响较大。从表4 和表5 可以看出,随着问题规模的增大,平均求解时间随之增加,误差逐步变大( 特殊情况属于实验策略以及局部最优对算法求解的影响所致) 。

文献[11]改进增强型自探索PSO算法,所能求解的最大规模算例为Pr226 问题,多次实验获得的最佳解为80 373,平均解80 861. 01( 误差0. 612% ) ,而改进后的自适应混合PSO算法多次实验都能够无误差地收敛于已知最优解80 369,而且具备更大规模的求解能力,这说明了改进措施的可行性和有效性。另外,本文算法获得的最优解明显优于文献[1]中洪水能量算法发现的最优解为82 913( 误差3. 17% ) 。

对于d1291 实例,算法最终都收敛于同一个局部最优解53 101,误差为4. 53% ,其周游路线如图1 所示。对于Fl1400 实例,算法最终都收敛于同一个局部最优解20 392,误差仅为1. 32% ,该似解优于文献[2]中的结果,其周游路线如图2所示。

虽然实例Fl1400 比d1291 的规模大很多,但从图1 和图2的节点分布看实例Fl1400 的城市分布基本属于单环形分布,而实例d1291 属于多环形分布,故局部最优解对算法影响较大,这就是为什么规模小的反而误差较大的原因。从图1 和图2 可以看出,虽然算法获得的近似解不是全局最优解,但是其周游路线依然比较完美,没有交叉点。说明对于这两个求解实例,算法在较短时间内,获得了与已知最优解误差较小的高质量的近似解。

上述分析都说明了自适应混合粒子群优化算法求解较大规模TSP问题的可行性和有效性。

6 结语

本文针对改进增强型自探索粒子群优化算法求解大规模TSP问题的不足,提出了自适应混合粒子群优化算法求解较大规模TSP问题,通过多种自适应策略,分阶段自适应进化,算法获得解的质量明显提高。通过对多个标准TSP问题的仿真测试,实验结果对比分析说明了自适应混合粒子群优化算法求解大规模旅行商问题能够的获得高质量的解。但本文算法仅仅利用了多个局部最优解的交集信息,如何更进一步利用多个局部最优解隐藏的信息,并形成有效的启发式规则以高效求解更大规模的TSP问题是今后要研究的重点。

参考文献

[1]冯翔,马美怡,虞慧群.TSP湖水能量优化算法[J].计算机研究与发展,2013,50(9):2015-2027.

[2]冀俊忠,黄振,刘春年,等.基于多粒度的旅行商问题描述及其蚁群优化算法[J].计算机研究与发展,2010,47(3):434-444.

[3]苏晓勤,孙鹤旭,潘旭华.改进蜂群算法的旅行商问题仿真[J].计算机工程与设计,2013,34(4):1420-1424.

[4]安晶,徐森.一种结合粒子群优化理论改进的郭涛算法及其应用[J].计算机应用与软件,2014,31(2):296-299,320.

[5]李熠,马良.用量子蚁群算法求解大规模旅行商问题[J].上海理工大学学报,2012,34(4):355-358.

[6]贾瑞玉,李亚龙,菅玉勇.求解旅行商问题的混合量子蚁群算法[J].计算机工程与应用,2013,49(22):36-39.

[7]饶卫振,金淳,黄英艺.求解TSP问题的最近邻与插入混合算法[J].系统工程理论与时间,2011,31(8):1419-1428.

[8]彭斌,胡常安,邵兵,等.求解TSP问题的混合杂草优化算法[J].振动测试与诊断,2013,33(S1):52-55.

[9]王翠茹,张江维,王玥,等.基于改进粒子群优化算法求解旅行商问题[J].华北电力大学学报,2005,32(6):47-51.

[10]熊伟,张江维,张火林.增强型自探索粒子群优化算法求解TSP问题[J].华北电力大学学报,2009,36(6):69-74.

[11]Zhang Jiangwei,Si Wenjian.An Improved Enhanced Self-Tentative Particle Swarm Optimization Algorithm for TSP[C]//Sixth international conference on natural computation,Yantai,Shandong,China,2010,Piscataway,IEEE computer society,2010:279-283.

自适应粒子群优化篇7

关键词：双层规划,自适应粒子群优化算法,分层迭代

1 引言

双层规划研究的是具有两个层次系统的规划与管理问题。上层决策者只是通过自己的决策去指导下层决策者,并不直接干涉下层的决策;而下层决策者只需要把上层的决策作为参数,他可以在自己的可能范围内自由决策。这种决策机制使得上层决策者在选择策略以优化自己的目标达成时,必须考虑到下层决策者可能采取的策略对自己的不利影响。因此,双层规划是一种NP hard问题,具有一定的复杂性与现实意义。

目前对于双层规划模型通常采用数值仿真计算,以期在合理的时间内获得模型的近似最优解。但是,当前国内外一些学者提出的求解算法或求解方法,都是针对特定的双层规划模型提出的,并且算法的运行效率和收敛精度都不高。本文在分析和借鉴现有的一些较优秀的算法思想的基础上,提出采用自适应粒子群优化算法求解双层规划模型。实验研究表明,本文提出的算法不仅能有效求解双层规划模型,可以获得高质量的全局最优解,而且该算法具有通用性和普遍性,不依赖于具体的双层规划模型。

2 双层规划模型

双层规划模型的基本思想可以用下面的数学模型来描述:

设上层决策者控制的变量为

下层决策者控制的变量为

上层规划的数学模型为:

其中y=y(x)由下层规划求解。

下层规划数学的模型为:

双层规划模型是由以上两个相互关联的子模型(U)和(L)组成,F是上层规划所确定的目标函数,x为上层规划的决策变量,G是对变量的约束;f为下层规划所确定的目标函数,y为下层规划的决策变量,g是对变量y的约束。上层决策者通过设置x的值影响下层决策者,因此限制了下层决策者的可行约束集,而下层决策者的行为反过来又会通过y影响上层的决策,所以下层决策变量y是上层决策变量x的函数,即y=y(x),这个函数一般称为反应函数。

一般来说,求解线性双层规划问题是非常困难的,Jeroslow指出线性双层规划是一个NP-hard问题,Ben-Ayed及Bard对此结论给出了简短的证明;Hallsen对性双层规划是强NP-hard问题给出了严格的证明。后来,Vicente指出,寻找线性双层规划的局部最优解也是NP-hard问题,不存在多项式求解算法。即使双层规划上、下层中目标函数和约束函数都是线性的,它也可能是一个非凸问题,并且是非处处可微的。非凸性是造成求解线性双层规划问题异常复杂的重要原因。

3 粒子群优化算法模型

3.1 基本粒子群优化算法

粒子群优化算法是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法,在PSO中,每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值,每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。

PSO初始化为一群随机粒子(随机解),然后通过迭代找到最优解,在每一次叠代中,粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解,这个解叫做个体极值pBest,另一个极值是整个种群目前找到的最优解,这个极值是全局极值gBest。粒子在找到上述两个极值后,就根据下面两个公式来更新自己的速度与位置:

其中,Vk为迭代第k步粒子的速度,Xk为第k步粒子的位置,pBestk为第k步粒子本身所找到的最优解的位置,gBestk为第k步整个粒子群当前找到的最优解的位置;rand是[0,1]之间的随机数,c1和c2被称作学习因子,通常,c1=c2=2,w是加权系数,一般取值在0.1-0.9之间。

3.2 自适应粒子群优化算法

为了平衡PSO算法的全局搜索能力和局部改善能力,采用非线性的动态惯性权重系数,公式如下:

其中wmax、wmin分别表示w的最大值和最小值,f表示粒子当前的目标函数值,favg和fmin分别表示当前所有粒子的平均目标值和最小目标值。在上式中,惯性权重随着粒子的目标函数值而自动改变,因此称为自适应权重。

当各粒子的目标值趋于一致或者趋于局部最优时,惯性权重将增加,而各粒子的目标值比较分散时,惯性权重将减小,同时对于目标函数优于平均目标值的粒子,其对于的惯性权重因子较小,从而保护了改粒子,反之对于目标函数值差于平均目标值的粒子,其对于的惯性权重因子较大,使得该粒子向较好的搜索区域靠拢。

3.3 双层规划模型求解方法

双层规划问题是一个多目标优化难题,对于一个非线性双层规划问题,对其求解会更加复杂。粒子群优化算法结构简单,控制参数更少,本文将利用分层迭代的思想,采用改进的粒子群算法求解双层规划问题。算法的基本流程如下:

步骤1(初始化)初始化自适应粒子群算法中的参数;随机产生下层模型的初始解(需满足约束条件)。

步骤2 (求解上层规划)将下层模型的解代入上层模型,利用算法求解上层模型,获得上层模型的最优解。

步骤3(求解下层规划)将上层模型的解代入下层模型,利用传统优化方法求解下层模型,获得下层模型的最优解。

步骤4(判断)若满足算法终止条件(误差足够好或者达到最大迭代条件),则停止,否则转步骤2。

4 算例研究

下面通过几个双层规划模型的数值例子,来验证本文给出的自适应粒子群算法求解双层规划模型的可行性与有效性,并与参考文献中的结果做比较。

例1

例2

在上例中,取离子数为40,学习因子都取2,最大惯性权重为0.9,最小惯性权重为0.6,迭代步数取100,最后得到的结果和文献比较如表1所示。

从上述的例子结果可以看出,本文算法的计算结果和文献基本相符合,充分可以得出本文算法的有效性,另外,由于粒子群算法的简单与智能化,参数设定比较少,因此,在解决类似问题具有一定的优势。

5 结论

采用自适应粒子群算法求解双层规划模型是一项崭新的尝试,通过对算例的数值计算,表明本文提出的算法是非常有效的。自适应粒子群算法不仅能够有效的求解双层规划模型,而且具有一定的通用性和普遍性。本研究期望能为以合理的代价用智能算法求解大型复杂模型指明一条新的路径。

参考文献

[1]Kennedy J.Eberhart R.Particle swarm optimization[C].IEEE International Conference on Neural Networks(Perth,Austra1ia),IEEE Service Center,Piscataway,N J,1995,IV:1942-1948.

[2]Shi Y.Eberhart R.A modified particle swarm optimizer[C].IEEE International Conference on Evolutionary Computation,Anchorage,Alaska,May4-9,1998.

[3]孙会君,高自友.供应链分销系统双层优化模型[J].管理科学学报,2003,6(3):66-70.

[4]吕振肃,侯志荣.自适应变异的粒子群优化算法[J].电子学报,2004,32(3):416-420.

[5]江燕,胡铁松等.基于粒子群算法的非线性二层规划问题的求解算法[J].运筹与管理,2006,15(2).

[6]刘佳,秦四平.不确定性决策在配送中心选址y元素中的应用研究[J].物流技术.2006.(12):52—54.

[7]龚纯,王正林.精通MATLAB最优化设计[M].北京:电子工业出版社,2009.271-290.

【自适应粒子群优化】推荐阅读：