基于改进版粒子群优化算法的最优双层规划模型及其求解

黄文雅

（湖南工程学院 管理学院，湖南 湘潭 411104）

0 引言

双层规划模型是根据约束条件使用极值算法求最优解的一种数学模型，模型设定了上层规划（U）和下层规划（L）两类关系结构，其中上层规划模型（U）的表达方式为：

其中F表示上层规划的函数形式，x表示影响上层规划的关键因素，G表示上层规划的约束条件。下层规划（L）的表达方式为：

其中f表示下层规划的函数形式，g表示下层规划的约束条件，x和y是函数关系，用于上层规划和下层规划的作用协调：

上层规划通过x作用于下层规划，下层规划通过y作用于上层规划，该模型能够综合考量事物的整体性和系统性，所得出的最优算法较为准确。但由于该模型涉及到NP hard等问题使求解过程异常复杂，现在学界常用的求解方法是数值仿真，此方法降低了上层规划的计算难度，但其运行效率和收敛度相对较低。本文试图在现有研究成果的基础上提出利用粒子群优化算法对上层规划模型进行求解，以得出更为快捷准确的最优化解，并把实例计算结果与传统文献中的算法进行精度比较。

1 改进的粒子群优化算法

粒子群优化算法由Kennedy和Eberhart于1995年共同提出，之后该算法广泛应用于函数优化、预算定额求解等领域。但是粒子群优化算法求出的优化解很容易受局部范围的影响，整体性和系统性相对较差，很多研究者提出改进的粒子群优化算法试图尽量克服这一局限，如He的被动收敛粒子群优化算法、吕振苏的自适应变异粒子群优化算法等，这些改进在很大程度上提高了粒子群优化算法的精度。

粒子群优化算法把求解过程中的每一个解当作一个“粒子”看待，使用函数适应度来评价“粒子”的优劣，根据迭代算法的基本原理找到最优解，假设“粒子”的空间向量表达方式为：

粒子群优化算法的迭代计算公式为：

其中w表示权数，c1和c2表示学习因子，r1和r2表示0到1之间的随机数，P表示粒子的最佳位置，迭代次数iter的加权数w为：

粒子将会在允许的范围内根据速度向量不断的变换位置，即Pi和Pg在不断的变化，当粒子发现一个最优位置时其他粒子就会迅速向该粒子靠拢，如果该最优位置属于局部最优位置Pg，则求出的最优解是局部最优解，将会导致算法的精度降低，此时如果使用随机扰动项进行随机干扰，使粒子跳出局部最优解继续寻找系统最优解，将会在很大程度上解决算法精度问题，假设随机变量η服从标准正态分布，且其值大于0小于1，则改进后的粒子最优位置为：

本文改进后的粒子群优化算法的步骤可以概括为以下几个步骤：

首先，粒子向量初始化处理。根据约束条件随机产生上层规划模型和下层规划模型的初始解，此时粒子将从当前位置Pi按照速度V进行移动，当Pi移动到初始值最佳位置Pg时进行第二步操作。

其次，根据上层规划模型和下层规划模型之间的函数关系，把x和y相互代入目标函数，求出该粒子的适应度F，根据适应度的大小判断该粒子所处位置是否是最佳位置，如果是局部最优位置则继续搜索下一位置并进行位置更新，直到找到适应度最优的粒子全局最佳位置为止。

最后，根据上层规划模型输出粒子群优化算法的最优解Pg和yPg，把最优解带入起始的目标函数，此后可以根据目标函数对所有约束条件下的最优解进行求解。

2 参数检验与文献对比

为了检验本文的粒子群优化算法的准确性，接下来使用4组文献参数对粒子群优化算法和现有文献的求解结果进行比较研究，这里对参数的设置如下：

参数1：

参数2：

参数3：

参数4：

基于本文的粒子群优化算法使用计算机对上述4组参数进行60次独立计算，并且把相应文献的计算结果一起列于表1，通过粒子群优化算法和现有文献算法的比较，可以发现粒子群优化算法计算的准确度更高，通过该方法能够得出较为精确的全局最优解。

表1 粒子群优化算法和文献算法最优解

本文粒子群优化算法使用了双层规划模型，上层规划模型和下层规划模型具有极强的相关性，且上层规划模型处于主导地位，为了对基于上层规划模型的粒子群优化算法的性能进一步检验，对上层规划模型进行60次独立运算求解，最优解列于表2（见下页），从上层规划最优解来看除了4（2）以外所有实例均能全局收敛于最优解，而且最优解的方差非常小，4（2）的最优解虽然有误差但误差很小，表明本文构建的基于粒子群优化算法的最优预算双层规划模型非常有效，可信度较高。

表2 上层规划模型最优解

3 实例分析

通过4组文献参数检验粒子群优化算法，发现本文构建粒子群优化算法的最优预算双层规划模型在最优求解过程中效率高、误差少且抗干扰性强，为检验模型实用性，接下来引入统计数据对模型进行实例演算。预算定额限定在某个工程事件中消耗造价成本的极限，属于约束条件的一种，与本文模型运算的约束条件相符。因此利用预算定额数据为样本，收集20组公司2016年的预算定额数据，数据来源为2016年《中国上市公司发展报告》。运用本文构建的模型，确定20组公司预算定额的最优解，并与其实际预算定额相比较，以期为这些公司提供参考。根据20组公司的规模大小来确定迭代次数，用预算定额代表公司规模，其中预算定额500万元以下的为1～5组，预算定额为500～1000万元的公司为6～10组，预算定额为1000～1500万的为11～15组，预算定额为1500万以上的为16～20组，参数及迭代次数设定见表3所示。

表3 样本参数设定

把相应参数带入本文所构建的双层规划模型，使用计算机软件SPSS对20组不同规模预算定额的公司进行求解，求解结果见表4所示，从表4的求解结果来看，除第10组和第15组稍有误差以外（第10组误差为0.2，第15组误差为0.1），其他所有组别均能收敛于同一最优解。

表4的计算结果表明有两组公司出现一定偏差，为了对这种偏差的大小进行检验，接下来对20组的最优解、平均最优解和最优解方差进行计算，计算结果见表5所示。从表5的计算结果可以看出最优解和平均最优解的差别很小，最优解的方差也非常小，只有第10组和第15的最优解误差稍大，进一步验证了本文构建的双层规划模型的稳健性。因此现实生活中公司可以根据公司规模的大小设定相应的参数和迭代次数，一般预算规模较大的公司可以设定较高的迭代次数，以保证估计结果的精准性，用于求出本公司预算的最优解，为公司利润的最大化提供政策建议。

表4 20组预算定额粒子群优化算法的最优解结果

表5 20组预算定额的上层规划模型最优解

4 结束语

双层规划模型是目前较为常用的根据约束条件使用极值算法求最优解的一种数学模型，该模型能够综合考量事物的整体性和系统性，所得出的最优算法较为准确。但由于该模型涉及到NP hard等问题使求解过程异常复杂，现在学界常用的求解方法是数值仿真，此方法降低了上层规划的计算难度，但其运行效率和收敛度相对较低。本文试图在现有研究成果的基础上利用粒子群优化算法对上层规划模型进行求解，以期得出更为快捷准确的最优化解，并通过实例计算与传统文献中的算法进行精度比较。

通过本文的研究可以得出以下主要启示，粒子群优化算法广泛应用于函数优化、预算定额求解等领域。但是粒子群优化算法求出的优化解很容易受局部范围的影响，整体性和系统性相对较差，很多研究者提出改进的粒子群优化算法尽量克服这一局限，这些改进在很大程度上提高了粒子群优化算法的精度。本文使用随机扰动项进行随机干扰，使粒子跳出局部最优解继续寻找系统最优解，在很大程度上提高了算法的精度，并使用实例对粒子群优化算法和现有文献的求解结果进行比较研究，发现粒子群优化算法计算的准确度更高，通过该方法能够得出较为精确的全局最优解。本文对基于上层规划模型的粒子群优化算法的性能进一步检验，求解结果认为基本所有实例均能全局收敛于最优解，而且最优解的方差非常小，表明本文构建的基于粒子群优化算法的最优预算双层规划模型可信度较高。公司可以根据预算规模的大小设定相应的参数和迭代次数，一般来说预算规模较大的公司可以设定较高的迭代次数，从而保证估计结果的精准性，用于求出本公司预算的最优解，为公司利润的最大化提供政策建议。

[1]Nye K S.The Effect of Finance Risk CPI in the City Analsis of Cargo Hanling Operatins[J].Physica-Verlag HD,2013,(4).

[2]Weber J.Theory of the Travel Indasty Location of City[M].Chicago:The University of Chicago Press,2014

[3]Moiuer E M.The Location of Travel in Economic Activity of Inflation.[M].New York:Mc Graw-Hill,2015,(4).

[4]Wardman K.Interurban Travel Demand Elasticities and Employment Risk Competition in Great Britain:Evidence From Direct Demand Models of City[J].Transportation Research,2015,5(4).

[5]Hoonoum M.Zhang A,Zhang Y M.Optimal Demand for Travel Lease of City Eco-tourism[J].Transportation Research,2013,(6).

[6]Lally D A.Is Employment Travel Risk Expenditure Productive?[J].Journal of Monetary Economics,2014,(23).

[7]Monkhouse.Is Travel Risk Expenditure Stimulative?[J].Contemporary Policy Issues,2013,(7).

[8]Warlkejtn P.Travel Risk Economic Activity Demand Elasticities and Risk Inflation Competition in United States:Evidence From Direct Demand Models of Inflation[J].Transportation Research,2013,24(3).

[9]梁银海,蔡承智.基于粒子群优化算法的分散式废水处理网络的综合[J].经济研究,2015，(10).

[10]高自友,张好智,孙会君.城市交通网络设计问题中双层规划模型、方法及应用[J].中国工业经济,2015，(8).

[11]赵志刚.求解双层规划模型的粒子群优化算法[J].世界经济,2016，(4).

[12]张晓敏,张跃胜.基于GVAR模型的我国装备制造业货币政策效应研究[J].管理学刊，2016，(3).