创新粒子群算法：求解二层非线性规划问题的新途径

程红萍

(西安欧亚学院基础部，西安710065)

由于双层规划满足了绝大多数层次决策问题的实际要求，因此在许多层次决策领域中双层规划得到了大量的应用，如：资源分配问题、电力价格和计划问题、信贷的利率问题、运输网络的设计问题、军事指挥等.但双层规划问题较难求解，它是一个典型的非凸不可微规划，所以多年来，在经济管理、工程设计、决策和最优控制等领域中引起了国内外学者们的广泛关注.国际上在双层规划领域表现突出的著名学者有Bard，Wen Aiyoshi，Shiminzu，Outrala，Yi等.其中Mathieu R1998年在遗传算法的基础上，提出了一种求线性二层规划问题全局最优解的方法，Bard JF提出了一种网格搜索方法求非线性双层规划的方法.在国内，多层规划的研究在20世纪90年代初才引起关注，较早从事研究的单位有东南大学、中科院系统研究所和自动化研究所、湘潭大学、天津大学和西安电子科技大学等，滕春贤、李智慧的著作《二层规划的理论与应用》研究了二层线性规划以及多目标二层非线性规划的基本概念，性质以及最优性条件和应用等问题.但目前对二层非线性规划理论和算法的研究大多数仅局限于某些特殊的形式和结构，因此本文对一般的二层非线性规划的求解方法进行了研究.

1 将二层非线性规划利用KKT条件转化为单层非线性规划问题

二层非线性规划问题一般可表示为：

利用KKT条件将二层非线性规划问题转化为单层规划问题.

可定义：设变量y的可行域为Y，对于固定的x，将(1)的下层约束中对于y*起作用的下标集用I={i|G2i(x，y*)=0}来记.若{▽xG2i(x，y)|i∈I}关于变量y线性无关，则称(1)满足约束规格.

利用罚函数方法求解二层非线性规划问题时，主要思想是先将下层规划问题用等价的KKT条件做替代，然后把互补条件作为目标函数的罚项，从而可构造出一个新的非线性规划.

具体操作为：若f，G2在点(x*，y*)处关于y可微，且对于(1)满足上面所述的约束规格，则(x*，y*)是(1)的解，当且仅当存在l*(l*∈Rn2)使得点(x*，y*，l*)是问题

然后再把(2)中的互补条件作为目标函数的罚项，于是就可以将问题(2)转化为：

2 创新的粒子群算法

Eberhart和Kennedy提出了粒子群算法，它是一种基于种群的算法，是在一些种群的社会行为规律的引导下提出来的，把种群称做粒子群，种群中的个体称做粒子.设一个群体中有M个粒子，其中第i个粒子表示为一个 N维的向量xi=(xi1，xi2，…，xin)，i=1，2，…，M，也就是说用xi表示第i个粒子在N维的搜索空间中的位置，用ui=(ui1，ui2，…，uin)来记第i个粒子的飞行速度(它也是一个N维的向量)，用pi=(pi1，pi2，…，pin)来记第i个粒子目前搜索到的最优位置.整个种群目前搜索到的最优位置为pg=(pg1，pg2，…，pgn).粒子群算法早期对粒子进行操作采用的是下面的公式：

过去传统的粒子群算法，记录每个粒子获得的信息时，只记录群体的最优位置和其本身的最优位置，而不记录其它粒子的信息，其它粒子的最优信息对粒子的运动是否有参考价值?鉴于此原因，在这里我们可以把传统粒子群算法中的速度和位置公式更新为：

新算法的具体步骤为：

Step1：初始化.在初始化范围内，对种群(即粒子群)进行随机初始化.

Step2：计算每个粒子的适应度.

Step3：位置更新.对于每个粒子，把它的适应度和以前所经历过的最好位置的适应度作对比，如果较好，则把目前粒子所在的位置更新为最好位置.

Step4：全局判断.对粒子群中的每一个粒子(个体)，将其历史最好位置的适应度和全局经历的最好位置的适应度作对比，如果较好，则把它记为目前全局的最好位置.

Step5：根据(6)式和(7)式对粒子的位置和速度做比较.若未达到结束条件，则回到步骤Step2.

3 数值验证

对于上述创新的粒子群算法，是否可行和有效呢?下面通过数值试验来验证.

根据上述创新的粒子群算法，将此非线性二层规划转化为下面的单层非线性规划问题：

4 结语

对于二层规划问题，由于其本质的非凸性和非处处可微性，从而为求解二层非线性规划问题的全局最优解带来了非常大的困难，所以本文首先利用KKT条件将二层非线性规划问题转化为单层规划问题，其次用创新的粒子群优化算法求解单层规划问题，最后运用数值验证，不但验证了该方法的有效性和实用性，而且从数值验证可以看出，创新的粒子群算法不但提高了求得全局最优解的可靠性和有效性，而且算法简单，可操作性强.

［1］腾春贤，李智慧.二层规划的理论与应用［M］.北京：科学出版社，2005.

［2］雍龙泉，张建科，张晓清.求解一类随机问题的粒子群优化算法［J］.武汉大学学报(理学版)，2005，(S2)：51－53.

［3］刘兵兵.一类非线性二层混合整数规划问题全局最优解的遗传算法［J］.燕山大学学报，2007，31(6)：554－557.

［4］郭广寒，王志刚.一种改进的粒子群算法［J］.哈尔滨理工大学学报，2010，15(2)：31－34.

［5］刘兵兵.一类混合整数二层线性规划问题的等价形式［J］.安庆师范学院学报(自然科学版)，2011，17(1)：42－45.

［6］吴睿，程红萍.利用改进的粒子群算法求解二层非线性规划问题［J］.中国证券期货，2011，(9)：210.