基于改进Markov邻域的非线性01规划智能算法加速策略

李维鹏　曾静　张国良

摘要：

大规模非线性01规划问题求解时间较长，通过分析非线性01规划问题特点及算法寻优的Markov过程，提出一种基于改进Markov邻域的智能算法加速策略。首先，根据01规划问题解特点给出了非线性01规划问题的改写模型；随后，基于该模型给出了改进的Markov邻域，并推导和证明了改进邻域下任意两个状态之间的可达概率及其条件；最后，通过进一步分析非线性01规划模型并融合所提出的改进邻域，设计了采用Markov过程的智能算法的约束条件和目标函数递推更新策略对算法进行加速。采用不同算例进行多次测试，结果表明，在保持加速算法与原算法寻优效果相当的前提下，该策略对多种智能算法的寻优效率均有不同程度的提升。

关键词：

非线性01规划；Markov邻域；智能算法加速；递推更新

中图分类号：

TP301.6

文献标志码：A

Abstract：

In order to reduce the time consumption in solving the problem of largescale nonlinear 01 programming， an intelligent algorithm acceleration strategy based on the improved Markov neighborhood was presented by analyzing the characteristics of nonlinear 01 programming and the Markov process of intelligent algorithm. First， a rewritten model of nonlinear 01 programming problem was given. Next， an improved Markov neighborhood was constructed based on the rewritten model， and the reachable probability between two random statuses with its conditions under the improved Markov neighborhood was derived and proven. With a further analysis of the structure of nonlinear 01 programming together with the improved Markov neighborhood， a recursive updating strategy of the constraint and objective function was designed to accelerate the intelligent algorithms. The experimental results illustrate that the proposed strategy improves the operating efficiency of intelligent algorithms while keeping a correspondence with the original algorithms in search results.

英文關键词Key words：

nonlinear 01 programming； Markov neighborhood； intelligent algorithm acceleration strategy； recursive update

0引言

01规划是一种特殊形式的整数规划，大量地应用于描述和解决诸如线路设计、地址选定、工作任务分配等常见问题；然而现实世界中变量之间以及变量与目标之间均存在着大量的非线性关系，必须采用非线性 01规划才能准确予以描述。

针对非线性01规划问题的求解，人们已提出了许多有效的智能算法应用，例如粒子群算法（Particle Swarm Optimization， PSO） [1-2]、人工鱼群算法（Artificial Fish Swarm Algorithm， AFSA）[3]、蜂群算法（Artificial Bee Colony， ABC）[4]、元胞蚁群算法（Cellular Ant Algorithm， CAA）[5]以及模拟退火算法（Simulated Annealing， SA）等。以上算法的共同特点是：它们都是基于Markov过程的智能优化算法。目前，对于非线性01规划问题求解的研究大多集中于：减少收敛步数[6]、优化寻优效果[7-8]、革新算法类型[3，5，9]以及应用创新[7，10]等方面，而对于其更为实质性的Markov过程及其状态可达性的研究相对较少。

为了提高智能优化算法对非线性01规划问题的求解效率，本文基于对智能算法求解01规划问题的Markov过程的研究，提出了一种基于改进Markov邻域的非线性01规划智能算法加速策略。首先，针对01规划问题的特点，改进其智能算法优化过程的Markov邻域，并推导了基于改进邻域的Markov链中，任意满足约束的状态之间的可达概率及其条件；随后，基于该邻域给出了目标函数和约束条件的递推更新策略，提高了智能算法的运行效率；最后，通过仿真实验对算法的有效性进行验证，结果表示，加速策略缩短了基于Markov过程的智能优化算对非线性01规划问题的运行时间，较大地提高了各个算法的寻优效率。

3.4分析与讨论

由表1、表2可知，采用本文加速策略后，算例1背包问题中，粒子群算法（PSO）、工鱼群算法（AFSA）、遗传算法（GA）和模拟退火算法（SA）的平均耗时分别是原算法的61.94%、61.96%、83.18%和62.96%，且优化效果略有提升；算例2系统可靠性优化中，PSO和SA平均耗时分别是原算法的76.39%和37.5%，而优化效果基本持平；算例3非线性最小代价问题中，PSO、AFSA、GA和SA的平均运行时间分别是原算法的36.6%、78.03%、37.19%和75.43%，而优化效果基本持平。

从加速效果来看，对于线性01规划问题，加速策略对各个算法的加速效果基本相当；而对于系统可靠性优化问题，本文仅采用了PSO和SA两类优化算法进行了对比测试，加速策略对SA的加速效果要优于PSO；对于最为复杂的非线性最小代价问题，加速策略对PSO和GA的加速效果显著优于AFSA和SA。考虑到算例1和算例2的解为向量形式，而算例3解为矩阵形式，本文加速策略对算例1、2的邻域改变显著小于算例3。对比4种不同的智能算法，原算法与加速算法所用邻域最为相近的是PSO和SA。可以总结出，加速策略对智能算法的加速效果不仅与算法类型有关，而且与解的形式有关，而最为核心的是采用加速策略后，其邻域规则的变化程度。

从加速稳定性上来看，由图5和图6可知，加速AFSA的表现较不稳定，这主要和算法的收敛性有关：算法越早熟，其收敛越快，从而对加速策略引起的邻域变化越不敏感，导致加速效果稳定。可以预见的是，算法参数的调整会对算法收敛过程造成影响，进而影响加速策略的稳定性。

4结语

本文针对大规模非线性01规划问题的特点，给出了智能算法优化过程通用的改进Markov邻域，并基于该邻域给出了约束条件和目标函数的递推更新策略，降低了迭代过程运算量。算例测试表明，在保持寻优效果的前提下，本文的算法加速策略有效提高了智能算法求解非线性01规划问题的运行效率。然而，对于不同的智能算法，本文加速策略的表现有所差异，对这种差异的认识和改进则需要进一步深化对不同智能算法的Markov过程的研究与认识。

参考文献：

[1]

MATSUI T， SAKAWA M， KATO K. Particle swarm optimization for nonlinear 01 programming problems [C]// Proceedings of the 2008 IEEE International Conference on Systems， Man and Cybernetics. Piscataway， NJ： IEEE， 2008： 168-173.

[2]

梁艳春，吴春国，石小虎，等.群智能优化算法理论与应用[M].北京：科学出版社，2009：100-135.（LIANG Y C， WU C G，SHI X H， et al. Theory and Application of Swarm Intelligence Optimization Algorithms [M]. Beijing： Science Press， 2009：100-135.）

[3]

李春梅，马良.非线性01规划问题的人工鱼群算法[J].计算机应用研究，2011，28（7）：2449-2451.（LI C M， MA L. Artificial fishswarm algorithm for nonlinear 01 programming problem [J]. Application Research of Computers， 2011， 28（7）： 2449-2451.）

[4]

劉勇，马良.非线性01规划的元胞蚁群算法[J].系统管理学报，2010，19（3）：351-355.（LIU Y， MA L. Solving nonlinear 01 programming by cellular ant algorithm [J]. Journal of Systems and Management， 2010， 19（3）： 351-355.）