整数规划的花授粉算法

谢瑜，高晓智，2（.上海海事大学信息工程学院，上海20306；2.阿尔托大学自动化与系统技术系，芬兰赫尔辛基FI-00076）

整数规划的花授粉算法

谢瑜1，高晓智1，2
（1.上海海事大学信息工程学院，上海201306；2.阿尔托大学自动化与系统技术系，芬兰赫尔辛基FI-00076）

整数规划是NP困难（Non-deterministic Polynomial-time hard，NP-hard）的经典问题之一。整数规划的花授粉算法（Integer Flower Pollination Algorithm，IFPA）是采用截断取整的方法，将最近开发的花授粉算法（Flower Pollination Algorithm，FPA）扩展到求解整数规划问题。通过对测试函数集进行仿真实验，结果表明IFPA拥有很好的性能和很强的全局寻优能力，可以作为一种实用方法用于求解无约束整数规划和有约束整数规划问题。

无约束整数规划；约束整数规划；测试函数；花授粉算法；最优化

0 引言

整数规划问题是运筹学中的一个重要研究课题，它广泛存在于各个领域，如机械、化工、经济、生物、军事等。

对于变量维数较小的整数规划问题，传统的求解方法[1]有分支界定法、割平面法以及将两者结合起来的分支割平面算法、隐枚举法等；对于较大规模的问题，传统的计算方法比较耗时，通常先采用实数域的一些优化算法，再将计算结果进行取整后作为整数规划的近似解。但在实际应用中，取整运算常常导致约束的不满足或远离最优解。进化计算方法提出以后，已有许多学者应用遗传算法、蜂群算法[2]、粒子群算法[3-5]等求解整数规划问题。

花授粉算法[6]（Flower Pollination Algorithm，FPA）是剑桥大学的Yang Xinshe受启发于花授粉过程提出的一种具有全局收敛的新型搜索算法，该算法主要优点是参数少、操作简单、易实现、随机搜索路径和寻优能力强等。目前，对花授粉算法的研究还处于起步阶段，主要集中在连续函数的优化问题[6-7]。

本文的主要目的是拓展连续函数优化中的花授粉算法，从而开发出整数规划的花授粉算法（Integer Flower Pollination Algorithm，IFPA）。通过仿真实验验证了所提算法的有效性，结果表明该算法具有良好的全局寻优能力和良好的收敛速度。

1 基本花授粉算法

1.1 花授粉的特性

花授粉可以采取两种主要形式：非生物传粉和生物传粉。约90%的花卉属于生物授粉，约10%的授粉采取非生物形式，不需要任何传粉者。传粉者是非常多样的。据估计，至少有两百万种传粉者，它们也可以开发出所谓的花恒常。即这些传粉者往往只拜访某种特定的花卉品种，而绕过其他花种。

授粉可以通过自花授粉或异花授粉来实现。异花授粉意味着授粉可发生于不同植物的花粉，而自花授粉是一朵花的受精来自同一种植物的同一朵或不同朵花的花粉，如桃花。

异花生物授粉可能发生在长距离的情况，并且传粉者如蜜蜂、鸟类以及苍蝇能飞很长的距离，因此，它们可以被看作是全局授粉。此外，蜜蜂和鸟类可能表现为莱维飞行行为，其飞行步长服从莱维分布[8]。根据两朵花的相似性或差异性，花恒常可以被用做一个步长增量。

1.2 花授粉算法

花授粉算法是受启发于开花植物的花授粉过程，已经扩展到多目标的优化。为了模拟该过程，需要做以下假设：

（1）生物异花授粉被认为是全局授粉过程，且传粉者以莱维飞行的方式传粉。

（2）非生物自花授粉被认为是局部授粉。

（3）花恒常可以被认为是正比于某两朵相似性的繁殖概率。

（4）局部授粉和全局授粉由转移概率P∈[0，1]控制。由于物理的近似性和其他因素（例如风），局部授粉在整体授粉活动中有显著的偏重P。

基于以上假设，可以给出基本FPA的更新方程。在全局授粉中，花粉通过传粉者（例如昆虫）传播，并且花粉可移动很长的距离。因此，假设（1）和（3）可以用数学公式表示为：

其中Γ（λ）是标准伽马函数，其分布对较大步长s>0是有效的。理论上须|s0|>>0，但是实际上s0可以小至0.1。产生步长最有效的方法是曼特尼亚算法，通过使用两个高斯分布的U和V变换计算步长大小s：

这里U～N（0，σ2）是指高斯正态分布具有零均值和σ2的方差。方差可由下式计算：

对于一个给定λ，σ2是一个常数。

在数学上已经证明了曼特尼亚算法可以产生服从莱维分布的伪随机样本。参考文献[7]中使用该伪随机数的算法绘制了一个连续50步大小的莱维飞行，如图1所示。

对于局部授粉，假设（2）和（3）均可表示为：

图1 连续50步莱维飞行

大多数花授粉活动都可以发生在局部和全局范围。在实践中，相邻或附近的花相比于距离较远的花更容易被局部授粉。大多数情况下，P=0.8时可取得较好结果。花授粉算法的基本步骤可以概括为伪代码如下：

目标函数f（x），x=（x1，…，xd）T

初始花粉种群xi（i=1，2，…，n）和vi（i=1，2，…，n）

寻找初始种群中的当前最优值g*

定义转移概率P∈[0，1]

While（t>误差容量）

for i=1：n（种群中所有的n个花粉）

if rand

取一个遵守莱维飞行的步长矢量L（d维）；

边界约束检查；

else

取一个服从均匀分布的ε；

在所有解决方案（花粉）中随机选择j和k；

边界约束检查；

end if

评价所有新的解；

如果新的解较好，接受新的解；end for

end while

2 整数规划的花授粉算法

整数规划问题可描述为：

其中Zd为所有d维格子点组成的点集，S为问题的所有可行解集。在求解过程中，可采取两种截断取整的方法：一是在循环迭代的过程中，先将每个花粉的位置进行取整操作，然后计算其对应的函数值，此外的其他过程则完全与连续域函数优化的过程一致；二是保持连续域函数优化的过程，只在比较和评价目标函数值的过程中，对花粉位置取整并计算取整后的位置所对应的目标函数适应值。

经实验验证，第二种方法的效果明显优于第一种方法。所以，将第二种方法的思想应用到基本FPA中，可得本文提出的整数规划的花授粉算法。其主要步骤如下：

（1）参数和种群初始化。迭代次数t=0，给定种群数量n，局部授粉和全局授粉的转移概率P。然后随机产生一个种群，产生方式为：

4.改革获认可，取得良好社会效应。广西税务部门代征社会保险费改革试点工作开展以来，各级党委政府高度重视，一直关注社会保险费代征工作进展和成效，对税务部门代征社会保险费改革试点工作给予充分肯定。税务部门提供多元化的缴费方式成为试点工作中缴费人最满意的地方，试点工作取得了良好的社会效应。

其中，“0”表示第0代，lb（j）和ub（j）分别代表第j个决策变量的上下界，rand（）是一个产生0和1之间随机数且满足均匀分布的函数，d为待优化函数f（x）所含决策变量的个数，即维数。

最优解为xi*=0，i=1，2，…，d，对应的最优值为f5（x*）=0。

最优解为xi*=0，i=1，2，…，d，对应的最优值为f6（x*）=0。最优解为x*=（2，-1），x*=（3，-2），x*=（4，-2），x*=（3，-1），对应的最优值为f7（x*）=-6。对应的目标函数适应值

最优解为x*=（0，12，23，17，6）和x*=（0，11，22，16，6），对应的最优值为f8（x*）=-737。

最优解为xi*=0，i=1，2，…，d，对应的最优值为f9（x*）=0。

最优解为x*=（1，1，1，1，1），对应的最优值为f10（x*）=0。

最优解为x*=（3，2），对应的最优值为f12（x*）=0。

在给定误差容量为10-5时，用整数花授粉算法来找到以上实例中各函数的最优解。IFPA中种群规模n取为40，其转移概率P取0.8，该算法独立运行20次。

实验统计指标有7个，前三个是20次独立运行所得目标函数值的最好值、平均值及最差值；第四到第六个包括这20次成功寻优中使用的最小迭代次数、平均迭代次数、最大迭代次数；最后一个指标是20次独立循环消耗的总时间（单位：s）。花授粉算法的运行结果见表1。均为d维行向量，fit和Fit均为n维行向量。分别找出fit和Fit中最好的元素（即最小的元素）及其对应的可行解，将fit和Fit中最好的元素分别记为fitbest和Fitbest，fitbest和Fitbest分别对应的可行解记为xbest和Xbest。

（3）判断是否满足算法结束条件，如果满足，即Fitbest等于全局最优值时，则转步骤（8），否则，转步骤（4）。

（4）利用转移概率P与一个随机产生的介于0和1之间的随机数比较结果，实现对种群位置的再次更新：当随机数大于P时利用式（1）对种群位置进行更新，否则利用式（2）更新。

（5）利用步骤（2）中方法，计算种群中每个花粉对应的目标函数适应值，即确定fitbest、Fitbest、xbest和Xbest。

（6）评价当前目标函数值Fitbest，并与历史最优函数值比较，确定当前迭代最优函数值。

（7）转步骤（3）。

（8）输出寻优得到的结果。

3 实例验证

以下实验过程的运行环境是Window7系统下的MATLAB2 013a。选择参考文献[9]中的测试函数来验证所提出的IFPA在无约束整数规划问题中的应用；选择参考文献[5]中的实例来验证IFPA在约束整数规划问题中的应用。

3.1 无约束整数规划测试函数

最优解为x*=（1，1），对应的最优值为f1（x*）=0。

最优解为x*=（1，1），对应的最优值为f2（x*）=0。

最优解为x*=（0，0，0，0），对应的最优值为f3（x*）=0。

最优解为x*=（0，1），对应的最优值为f4（x*）=-3 833.12。

表1 IFPA在无约束整数规划中的实验结果

由表1可以看出，IFPA具有较强的全局搜索能力，能够在更短的时间范围内收敛到全局最优值，即IFPA可以很好地解决无约束整数规划问题。

3.2 有约束整数规划

花授粉算法不仅可以解决无约束整数规划问题，同样可以解决有约束的整数规划问题。

实例1：

理论上，该线性整数规划的最优解为（700，201），最优值为2 502。若去掉整数的约束，则线性规划的最优解为（699.8，201.8）。利用IFPA可以很容易找到与理论相同的解x*=（700，201），f（x*）=2 502。程序仿真时，每次迭代的最优值随迭代次数的函数关系如图2所示。

图2 最优个体适应度值变化曲线

从图2可见，前270代当前最优值呈上升趋势，花授粉算法对有约束非线性整数规划的求解有很快的收敛速度。

实例2：

理论上，该非线性整数规划的最优解为（50，99，0，99，20），最优值为51 568。利用IFPA很容易找到与理论相同的解x*=（50，99，0，99，20），f（x*）=51 568。该实例仿真函数关系如图3所示。

从图3中前140代当前最优值的上升趋势来看，可行域内的整数规划花授粉算法对有约束非线性整数规划的求解也有很快的收敛速度。

4 结论

在工程和工业中解决整数规划问题往往是具有挑战性的，因此需要特殊的技术来解决。近年来，启发式方法已经显示出其前景并得到了普及。本文提出了一种整数规划的花授粉算法（IFPA），将最近提出的花授粉算法拓展到解决整数规划的问题中。经过标准测试函数和实例的验证，说明了该算法能够很好地解决有约束整数规划和无约束整数规划问题。

图3 最优个体适应度值变化曲线

[1]杜枯康，英凯.整数规划问题智能求解算法综述[J].计算机应用研究，2010，27（2）：408-412.

[2]LIU Y，MA L．Bee colony foraging algorithm for integer programming[C].Business Management and Electronic Information（BMEI），2011 International Conference on．IEEE，2011，5：199-201．

[3]谭瑛，高慧敏，曾建潮．求解整数规划问题的微粒群算法[J]．系统工程理论与实践，2004，24（5）：126-129．

[4]高尚，杨静宇．非线性整数规划的粒子群优化算法[J].计算机应用，2007，28（2）：126-130．

[5]祁辉，熊鹰，周树民.基于粒子群算法的整数规划问题的求解算法[J].江汉大学学报，2009，37（1）：25-29．

[6]YANG X S.Flower pollination algorithm for global optimization[J].In Unconventional Computation and Natural Computation，2012，7445：240-249.

[7]YANG X S，KARAMANOGLU M，HE X S.Multi-objective flower algorithm for optimization[J].Procedia Computer Science，2013（18）：861-868.

[8]YANG X S.Review of Meta-heuristics and generalised evolutionary walk algorithm[J].International Journal of Bio-Inspired Computation，2011，3（2）：77-84.

[9]吴炅，健勇.整数规划的布谷鸟算法[J].学理论与应用，2013，33（3）：99-106.

Flow er pollination algorithm for solving integer programm ing

Xie Yu1，Gao Xiaozhi1，2
（1.College of Information Engineering，Shanghai Maritime University，Shanghai 201306，China；2.Department of Automation and Systems Technology，Aalto University，Helsinki FI-00076，Finland）

Integer programming is a famous NP-hard problem.Integer flower pollination algorithm（IFPA）is the use of rounding off method.It extends the recently developed flower pollination algorithm（FPA）to solve integer programming.The results of simulation experiments on a set of test functions show that IFPA has good performance and strong global optimization ability and can be used as a practical way to solve integer programming problems.

unconstrained integer programming；constrained integer programming；benchmark；flower pollination algorithm；optimization

TP301

A

1674-7720（2015）03-0082-04

2014-10-02）

谢瑜（1987-），女，硕士研究生，主要研究方向：最优化理论应用及其研究。

高晓智（1972-），男，教授，阿尔托大学博士生导师，主要研究方向：软计算理论及其应用。