基于改進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?？梢钥偨Y出，加速策略對智能算法的加速效果不僅與算法類型有關，而且與解的形式有關，而最為核心的是采用加速策略后，其鄰域規則的變化程度。

從加速穩定性上來看，由圖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.）