基于改進Markov鄰域的非線性01規(guī)劃智能算法加速策略

李維鵬　曾靜　張國良

摘要：

大規(guī)模非線性01規(guī)劃問題求解時間較長，通過分析非線性01規(guī)劃問題特點及算法尋優(yōu)的Markov過程，提出一種基于改進Markov鄰域的智能算法加速策略。首先，根據(jù)01規(guī)劃問題解特點給出了非線性01規(guī)劃問題的改寫模型；隨后，基于該模型給出了改進的Markov鄰域，并推導(dǎo)和證明了改進鄰域下任意兩個狀態(tài)之間的可達概率及其條件；最后，通過進一步分析非線性01規(guī)劃模型并融合所提出的改進鄰域，設(shè)計了采用Markov過程的智能算法的約束條件和目標函數(shù)遞推更新策略對算法進行加速。采用不同算例進行多次測試，結(jié)果表明，在保持加速算法與原算法尋優(yōu)效果相當?shù)那疤嵯?，該策略對多種智能算法的尋優(yōu)效率均有不同程度的提升。

關(guān)鍵詞：

非線性01規(guī)劃；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.

英文關(guān)鍵詞Key words：

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

0引言

01規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，大量地應(yīng)用于描述和解決諸如線路設(shè)計、地址選定、工作任務(wù)分配等常見問題；然而現(xiàn)實世界中變量之間以及變量與目標之間均存在著大量的非線性關(guān)系，必須采用非線性 01規(guī)劃才能準確予以描述。

針對非線性01規(guī)劃問題的求解，人們已提出了許多有效的智能算法應(yīng)用，例如粒子群算法（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過程的智能優(yōu)化算法。目前，對于非線性01規(guī)劃問題求解的研究大多集中于：減少收斂步數(shù)[6]、優(yōu)化尋優(yōu)效果[7-8]、革新算法類型[3，5，9]以及應(yīng)用創(chuàng)新[7，10]等方面，而對于其更為實質(zhì)性的Markov過程及其狀態(tài)可達性的研究相對較少。

為了提高智能優(yōu)化算法對非線性01規(guī)劃問題的求解效率，本文基于對智能算法求解01規(guī)劃問題的Markov過程的研究，提出了一種基于改進Markov鄰域的非線性01規(guī)劃智能算法加速策略。首先，針對01規(guī)劃問題的特點，改進其智能算法優(yōu)化過程的Markov鄰域，并推導(dǎo)了基于改進鄰域的Markov鏈中，任意滿足約束的狀態(tài)之間的可達概率及其條件；隨后，基于該鄰域給出了目標函數(shù)和約束條件的遞推更新策略，提高了智能算法的運行效率；最后，通過仿真實驗對算法的有效性進行驗證，結(jié)果表示，加速策略縮短了基于Markov過程的智能優(yōu)化算對非線性01規(guī)劃問題的運行時間，較大地提高了各個算法的尋優(yōu)效率。

3.4分析與討論

由表1、表2可知，采用本文加速策略后，算例1背包問題中，粒子群算法（PSO）、工魚群算法（AFSA）、遺傳算法（GA）和模擬退火算法（SA）的平均耗時分別是原算法的61.94%、61.96%、83.18%和62.96%，且優(yōu)化效果略有提升；算例2系統(tǒng)可靠性優(yōu)化中，PSO和SA平均耗時分別是原算法的76.39%和37.5%，而優(yōu)化效果基本持平；算例3非線性最小代價問題中，PSO、AFSA、GA和SA的平均運行時間分別是原算法的36.6%、78.03%、37.19%和75.43%，而優(yōu)化效果基本持平。

從加速效果來看，對于線性01規(guī)劃問題，加速策略對各個算法的加速效果基本相當；而對于系統(tǒng)可靠性優(yōu)化問題，本文僅采用了PSO和SA兩類優(yōu)化算法進行了對比測試，加速策略對SA的加速效果要優(yōu)于PSO；對于最為復(fù)雜的非線性最小代價問題，加速策略對PSO和GA的加速效果顯著優(yōu)于AFSA和SA?？紤]到算例1和算例2的解為向量形式，而算例3解為矩陣形式，本文加速策略對算例1、2的鄰域改變顯著小于算例3。對比4種不同的智能算法，原算法與加速算法所用鄰域最為相近的是PSO和SA?？梢钥偨Y(jié)出，加速策略對智能算法的加速效果不僅與算法類型有關(guān)，而且與解的形式有關(guān)，而最為核心的是采用加速策略后，其鄰域規(guī)則的變化程度。

從加速穩(wěn)定性上來看，由圖5和圖6可知，加速AFSA的表現(xiàn)較不穩(wěn)定，這主要和算法的收斂性有關(guān)：算法越早熟，其收斂越快，從而對加速策略引起的鄰域變化越不敏感，導(dǎo)致加速效果穩(wěn)定?？梢灶A(yù)見的是，算法參數(shù)的調(diào)整會對算法收斂過程造成影響，進而影響加速策略的穩(wěn)定性。

4結(jié)語

本文針對大規(guī)模非線性01規(guī)劃問題的特點，給出了智能算法優(yōu)化過程通用的改進Markov鄰域，并基于該鄰域給出了約束條件和目標函數(shù)的遞推更新策略，降低了迭代過程運算量。算例測試表明，在保持尋優(yōu)效果的前提下，本文的算法加速策略有效提高了智能算法求解非線性01規(guī)劃問題的運行效率。然而，對于不同的智能算法，本文加速策略的表現(xiàn)有所差異，對這種差異的認識和改進則需要進一步深化對不同智能算法的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]

梁艷春，吳春國，石小虎，等.群智能優(yōu)化算法理論與應(yīng)用[M].北京：科學(xué)出版社，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規(guī)劃問題的人工魚群算法[J].計算機應(yīng)用研究，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規(guī)劃的元胞蟻群算法[J].系統(tǒng)管理學(xué)報，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.）