基于Lagrange乘子法的一种新型改进粒子群优化算法

张　克，　梁昔明

(北京建筑大学 理学院, 北京　100044)



基于Lagrange乘子法的一种新型改进粒子群优化算法

张克，梁昔明

(北京建筑大学 理学院, 北京100044)

摘要：社会和生产实践中抽象出来的模型一般为非线性约束优化，而约束优化一般很难直接求解.首先，我们通过引进增广lagrange乘子法，将约束优化转化为有界约束优化，然后引入粒子群优化算法来进行求解，并且我们提出来一种嵌入了最速下降法的改进粒子群优化算法，以此来解决标准粒子群算法中收敛速度慢和精度低的问题, 提高了搜索的效率，特别是局部搜索的效率.改进算法有效地结合了粒子群优化算法比较强的全局搜索能力和最速下降法的精细快速的局部搜索能力，相比于标准粒子群优化算法，克服了收敛速度慢的特点. 数值实验表明，通过改进的粒子群优化算法可以找到所求优化问题的全局最优解.

关键词：约束优化问题； Lagrange乘子法； 粒子群优化算法； 最速下降法； 数值实验

粒子群优化算法(Particle Swarm Optimization，PSO)[1]作为一种经典的优化算法，它最早是由美国的心理学家Kennedy、电气工程师Eberhart两个人一起提出来的新算法，他们是对早期鸟类的群体行为进行建模并且仿真研究，从中受到启发得来的. 目前粒子群优化算法已经广泛应用到无约束优化问题的求解，具有较好的全局收敛能力.

同时，在实际生活和实践中，好多问题可以划归为相关函数的优化问题，但是常常是有约束限定条件的，一般都很难直接用标准粒子群优化算法来对这些优化问题进行求解. 通过对粒子群优化算法和差别进化算法进行比较，将两者相结合，提出了一种混合的优化算法来求解约束优化问题，通过引入不可行解，避免算法在边界区域发生震荡或者发散的现象，加强对边界区域的搜索[2]. 对比处理约束问题的乘子法和粒子群优化算法，用乘子法来优化算法中出现的不可行粒子，设计一种混合的新的粒子群优化算法，提高了计算效率，降低了复杂性，提高了搜索的精度[3]. 通过对粒子群优化算法进行改进，将多个临近的个体粒子聚集成核，形成多子群的粒子搜索. 过程中还引入了罚函数的约束处理机制，简单易行. 这样使得算法更加有效率，更加容易靠近可行解[4]. 为了避免出现早熟收敛的情况，基于改进的约束自适应方法的动态邻域粒子群算法，引入了动态邻域的概念，增强了全局收敛能力，同时引入了序列二次收敛，增强局部搜索能力[5]. 利用外点法的局部搜索能力比较强的特点，同时处理约束条件的能力比较强，把一些不满足约束条件的粒子经过外点法处理，同时结合粒子群优化算法的特点，设计出来一种新的混合粒子群优化算法. 两者结合可以提高计算速度，并且提高了算法的效率[6].利用增广Lagrange函数的思想，将约束优化问题转变成无约束优化问题，通过寻找KKT点，达到寻找全局最优点的目的[7].利用增广 Lagrange罚函数，然后嵌入差分进化算法，根据个体的适应度值的不同， 在种群初始化时，采用佳点集初始化粒子，增加了种群多样性，提高了全局收敛能力[8]1673-1675. 差分进化算法针对不同复杂环境的研究内容, 包括约束、多目标、离散和噪声环境下的优化等[9].把约束条件跟目标函数看成两个目标，将此单目标优化问题转化为多目标优化问题；同时将种群粒子分类，设置一定标准，然后确定选择概率，进而可以提高算法的效率[10]47-53. 文献[11]分析研究了目前常用的约束处理技术，并与进化算法相结合对约束优化问题进行处理，最后还对一些常用算法进行了对比分析研究.

综述，目前我们采用最多的方法就是单目标优化问题、多目标优化问题、惩罚函数法、增广Lagrange乘子法等. 多目标优化问题普遍计算量比较大，一般会选择转化为单目标优化问题或者跟其他方法相结合的问题；罚函数作为常用的一种处理约束的方法，有其优点，也有其缺点，我们很难确定合适的惩罚因子，并且参数的选择很强烈的影响算法的效果. 本文在增广Lagrange乘子法的基础上引入最速下降法的粒子群优化算法，既保留了增广 Lagrange乘子法与粒子群优化算法的优点，又提高了算法的收敛效率，数值实验结果也表明了所得算法具有较高的收敛效率和优化性能.

1基于增广Lagrange乘子法的改进粒子群优化算法

1.1增广Lagrange乘子法

约束非线性规划问题的一般形式如下：

(1)

在求解过程中，对于此约束优化问题，我们将采用增广Lagrange乘子法. 增广Lagrange乘子法就是在罚函数的基础上引入Lagrange函数，它的核心思想就是在目标函数中加入惩罚项，其可以反映是否满足约束，从而就可以构成一个广义目标函数，于是就可以将约束优化问题(1)转变为如下界约束优化问题：

minP(x,λ,σ)(x∈[l,u])

(2)

其中P(x,λ,σ)是增广Lagrange罚函数.

(3)

(4)

增广Lagrange乘子法主要分两个部分呈现，里面的结构，我们主要进行数据的迭代，得到新的一组数据；在外面我们通过修改相应参数向量、检查收敛准则何时满足以决定是否终止算法. 参数向量的主要作用就是使得我们算出来的迭代点越来越靠近原问题(1)的驻点，如果我们发现原问题有可行解，那就代表乘子法函数在应用于该问题时就具有有限收敛性. 乘子向量λ和σ初始化时，λ0和σ0通常设置为任意正向量，比如取λ0=(1,1,…,1),σ0=(10,10,…,10). 在迭代过程中，Lagrange乘子向量λ的修正方法为：

(5)

(6)

σk+1=γσk

(7)

(8)

1.2嵌入最速下降法的改进粒子群优化算法

对界约束极小化问题(2)的求解，可以按照无约束优化问题求解目标函数最值，通常可以采用梯度法、拟牛顿法、粒子群优化算法等，界约束可以在自变量取值时体现. 对于复杂的高维大规模问题，一般常用粒子群优化算法来求解(粒子初始化时取值区间由界约束条件确定)，但粒子群优化算法和其它群体迭代算法一样，具有收敛速度慢的缺陷，因此，本文将对基本粒子群优化算法进行改进.

基本粒子群优化算法将每个个体看成n维搜索区间中的一个没有质量和体积的粒子，算法对参数初始化时粒子在整个搜索区间上随机分布，随着算法迭代的进行，粒子群在搜索区间上不断移动. 从理论上讲，只要迭代次数足够多，粒子群必定会取遍整个搜索区间，算法就一定能够找到问题的全局最优解. 然而，增加算法的迭代次数必定会导致算法运行时间增加，降低算法的效率，而且在粒子群进行自身位置更新时，虽然参考当前个体历史最优位置和群体历史最优位置信息，但是由于有随机数的参与，粒子的移动方向仍然具有随机性，则更新后的新位置不一定比原来位置更优.如果更新后的新位置比原位置差，这就意味着算法进行了一次无意义的迭代，降低了算法的效率. 如果在粒子群位置更新时，能够使粒子按照下降方向寻找下一个点，则不会存在无意义的迭代情况，算法效率会有较大提高. 无约束优化问题的经典算法——最速下降法就是从给定初始点出发，利用该点处负梯度信息寻找下一个点，由于负梯度方向是粒子下降方向，所以粒子按负梯度方向寻找的下一个点一定比原来点更优，不会出现无意义的迭代情况.所以最速下降法能够快速地找到问题的局部极小值，而不一定能找到全局最小值，尤其对于多峰函数，最速下降法很难找到问题的全局最优解. 结合基本粒子群优化算法较强的全局搜索能力和最速下降法计算量小且容易收敛的优点，本文将最速下降法引入到基本粒子群优化算法. 在基本粒子群优化算法中，每个粒子j的位置和速度更新如下：

vj(t+1)=wvj(t)+c1r1(pj(t)-xj(t))+

c2r2(pg(t)-xj(t))

(9)

xj(t+1)=vj(t+1)+xj(t)

(10)

其中，vj(t)为粒子j在第t代的速度，w表示惯性权重，是调整算法全局搜索能力和局部搜索能力的平衡因子.较大的惯性权重能增强算法的全局搜索能力，而较小的惯性权重则可以增强算法的局部搜索能力.c1为认知系数，c2为社会系数；r1,r2为服从均匀分布在区间(0,1)上的随机数，pj为粒子j的个体历史最优位置，pg为群体的历史最优位置. 由于最速下降法具有高效的局部搜索能力，为了提高算法效率，在根据式(9)和式(10)计算粒子下一代的速度vj(t+1)和位置xj(t+1)时，引入最速下降法，以粒子群当前最优位置pg为初始点.

(11)

为搜索方向，其中gk为当前最优位置pg的梯度向量，根据:

xk+1=xk+αdk

(12)

对最优位置pg进行下一个点搜索，其中步长α满足:

(13)

通常根据Amrijo准则来求解满足式(13)的α. 按照式(12)迭代求得的局部最优解将比基本粒子群优化算法得到的pg更优，但不一定是全局最优解. 所以从算法整体效率来考虑，可以适当放低最速下降法精度要求，或者设置最速下降法内部最大迭代次数. 本文的主要思想就是选取若干粒子，对每一个粒子连续使用若干次的最速下降法，可得到一个新位置，例如xmin，如果不满足粒子群优化算法终止条件，更新粒子个体历史最优位置和群体历史最优位置，然后进行下一次粒子群优化算法迭代；否则，判断是否满足外层Lagrange乘子算法终止条件，如果满足Lagrange乘子算法终止条件，则停止计算，输出原问题最优解；否则，修正Lagrange乘子法参数λ和σ，进行下一个界约束问题的求解.

1.3改进粒子群优化算法的具体流程

1)初始化Lagrange乘子法参数λ0和σ0；

2)借助Lagrange函数将约束优化问题(1)转化为界约束优化问题(2)；

3)初始化粒子群优化算法各参数，随机产生初始粒子及速度；

4)根据式(9)和式(10)计算微粒下一代的速度vj(t+1)和位置xj(t+1)；

5)将粒子按照优劣排序，并且更新各微粒的个体历史最优位置pj和群体历史最优位置pg；

6)选取若干粒子，比如令x0=pg,γ=0.001，eps=1.0e-3,d0=-g0，kk=0；

7)如果‖dkk‖≤eps或kk≥4转13)；否则，进行下一步；

8)令α=1；

9)xkk+1=xkk+αdkk；

11)计算：

令kk=kk+1，返回7)；

12)更新最优解pg=xkk；

13) 对于选取的其他粒子，重复采取6)～12)操作；

14) 判断最优解pg是否满足粒子群优化算法终止条件，如果满足，进行下一步，否则返回4)；

16) 根据式(5)～式(8)修正Lagrange乘子法参数λkk和σkk，转2).

2实验结果与分析

为了测试本文提出的混合粒子群优化算法的数值效果，我们选取国际上通行的7个基准测试问题来进行实验分析，即g01、g05、g06、g07、g09、g11和g13 进行测试[12]284-287. 本文通过调用最速下降法求下一迭代点时，采用了诸多思路，从诸多思路中找到运算次数最少，结果最接近标准结果的一种. 为提高算法效率，选取种群中的几个点，采用最速下降法对这几个点进行改进，用改进的点代替原来的点. 这样可以在不明显增加运算次数前提下，提高算法的准确性. 可以采取如下策略：

表1　4种策略比较

本文采用Matlab 2014a实验平台进行数值实验，并对每个测试函数进行30次独立试验. 经过试验后发现，在运算次数相等的前提下，策略2和策略4的运算结果更加精确，例如对于g13函数而言，当迭代80次时，策略1和策略2的运算结果的平均值仅仅是0.061 624和0.063 829，而策略2和策略4则分别达到了0.057和0.055 12，因此排除策略1和策略3. 对于策略2和策略4，我们可以对它们进行改进，在保证结果精确的情况下，减少运算次数. 两种策略改进如表2.

表2　2种改进策略比较

接下来我们就要对表2这两种思路都进行实验，设置Lagrange 罚函数的内层粒子群优化算法种群规模N为30. 本文采用Matlab 2014 a实验平台进行数值实验，并对每个测试函数进行30次独立试验，经过多次试验，我们可得优化后的策略4在保证计算结果精度的情况下，种群迭代次数只有100次，是所有策略中种群迭代次数最低的. 因此，策略4是本文要选择的策略，记为ZK_PSO_SD算法. 将增广Lagrange差分进化算法记为ALCODE 算法[8]1673-1675，多目标差分进化方法记为MODE算法[10]47-53，随机排序算法记为 SR算法[12]284-287. 在比较实验中，ALCODE 算法的参数设置是: 种群规模N取为每个约束问题自变量个数n的10 倍，对所有的测试问题适应值评价次数均设置为350 000次. MODE算法和SR算法的参数设置是：种群的大小N为60，最大的迭代次数为5 800次. 实验结果与其他3种算法进行比较，其中mean为独立运行30次得到最优解的平均数，best为独立运行30次得到的最好值，worst为独立运行30次得到的最差值. 结果如表3所示.

表3　4种算法结果比较

从表3可以看出，经7个测试问题测试，4种算法基本都可以得到最优解，但每个算法均有利弊. 对于问题g01和g11，4种算法都能够得到最优解，而且算法很稳定；对于问题g05，本文算法能够求得最优解，但是另外3种对比算法都没能得到最优解；对于问题g06和g07，ALCODE算法、MODE算法和本文算法均能够稳定的得到最优解，SR算法虽能求得最优解，但从最优解平均值看，稳定性较差；对于问题g09, ALCODE算法和MODE算法能够稳定的求得最优解，SR算法虽然也能够得到最优解，但稳定性不高，有时也会陷入局部极值；对于问题g13，SR算法和本文算法均能够得到最优解，但从最优解平均值看，MODE算法和SR算法稳定性较低，同时MODE算法得不到全局最优解. 从各个方面分析看，本文算法占绝对优势. 对于问题g13，本文算法外层循环迭代次数仅为3次，内层循环迭代次数为100次，因此其外层循环和内层循环总的最大迭代次数为300次.而种群规模N为30，每一次粒子群迭代都需要进行7次最速下降法求解最小值，所以算法的最大适应值评价次数为11 100次.ALCODE算法虽然结果相对较好，但是算法设置的适应值评价次数为350 000次，是本文算法的近32倍，因而ALCODE算法的运行时间将是本文算法的近32倍；MODE算法和SR算法原文没有给出最大适应值评价次数，但给出的最大迭代次数为5 800次，是本文算法的近19.4倍. 在结果相差不大的情况下，本文算法运行时间短，性能较优. 总的来说，对于7个测试函数，本文提出的ZK_PSO_SD算法均能够求得全局最优解，而且算法的迭代次数较少，运行时间短，相比其他算法更优. 本文算法引入了最速下降法，克服了粒子群优化算法在搜索方向随机性这一弊端，提高了种群向最优解逼近的速度. 这些都表明，该方法是行之有效的.

3结论

本文在求解约束优化问题时, 首先利用增广Lagrange 函数作为价值函数, 将约束优化问题转化为界约束优化问题, 然后再利用粒子群优化算法求解界约束优化子问题. 由于基本粒子群优化算法搜索方向具有较大的随机性，因而在进行局部搜索时效率较低.本文结合基本粒子群优化算法较好的全局收敛能力和最速下降法快速精确的局部搜索能力，在增广Lagrange乘子法中嵌入最速下降法的改进粒子群优化算法，数值实验结果也表明了所得改进算法是一种实用的、高效的算法. 同时，本文模型及方法的建立，对于解决约束优化问题，具有一定的理论意义和参考价值.

参考文献：

[1]Kennedy J, Eberhart R C. Particle swarm optimization [A]∥Proc.of IEEE International Conference on Neural Networks[C]. Piscataway,USA: IEEE Press, 1995: 1942-1945

[2]李炳宇,萧蕴诗,吴启迪. 一种基于粒子群算法求解约束优化问题的混合算法[J].控制与决策，2004, 19(7):804-807

[3]张利凤,胡小兵. 求解非线性约束问题的混合粒子群优化算法[J].计算机科学,2011,38(S1):178-180

[4]吴茜,郑金华,宋武. 改进的粒子群算法求解非线性约束优化问题[J].计算机应用研究，2007，43(24):61-64

[5]彭虎,田俊峰,邓长寿.求解约束优化问题的动态邻域粒子群算法[J].计算机应用研究,2011,28(7): 2476-2478

[6]刘伟,蔡前凤,刘海林. 一种求解约束优化问题的新粒子群算法[J].计算机应用与软件, 2008,25(8): 254-256

[7]赵富强,曾玲,王晨. 基于增广Lagrange 函数的等式约束优化算法[J]. 桂林电子科技大学学报, 2007, 27(3): 236-238

[8]龙文,徐松金. 结合增广Lagrange 罚函数的约束优化差分进化算法[J]. 计算机应用研究,2012,29(5)

[9]刘波,王凌,金以慧.差分进化算法研究进展[J].控制与决策, 2007, 22(7): 721-729

[10]刘若辰,焦李成,雷七峰,等．一种新的差分进化约束优化算法[J]．西安电子科技大学学报,2011,38(1)

[11]王勇,蔡自兴,周育人,等.约束优化进化算法[J].软件学报, 2009(1): 11-29

[12]Runarsson T P, Yao Xin．Stochastic ranking for constrained evolutionary optimization[J].IEEE Trans on Evolutionary Computation, 2000, 4(3)

[责任编辑：佟启巾]

A New Improved PSO Algorithm Based on the Augmented Lagrange

Zhang Ke，Liang Ximing

(School of Science, Beijing University of Civil Engineering and Architecture, Beijing 100044)

Abstract:Since the model abstracted from social practice is generally nonlinear constrained optimization problem, it is difficult to be solved directly. The constrained optimization problem is changed into a bound constrained optimization problem at first using augmented Lagrange multiplier method, and the resulting bound constrained optimization problem is then solved by particle swarm optimization algorithm. The particle swarm optimization (PSO) algorithm is improved by coupling with steepest descent method to overcome its slow speed convergence and low accuracy computation. Through repeatedly using steepest descent method for several times, the local searching efficiency is improved. The proposed algorithm is combined with the strongly global search ability of PSO and the fast local search ability of steepest descent method, and overcomes the slow speed convergence in basic PSO. Numerical experiment results show that the proposed algorithm is a kind of efficient method for solving the constrained optimization problem.

Key words:constrained optimization problem; lagrange multiplier method; particle swarm optimization (PSO); steepest descent method ; numerical experiment

中图分类号：TP301.6

文献标志码：A

作者简介：张克(1989—)，男，硕士研究生，研究方向：智能优化算法.

基金项目：北京自然科学基金项目(4122022)；中央支持地方科研创新团队项目(PXM2013_014210_000173)

收稿日期：2015-07-31

文章编号：1004-6011(2016)01-0074-06