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

李維鵬　曾靜　張國良

摘要：

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

關(guān)鍵詞：

非線性01規(guī)劃；Markov鄰域；智能算法加速；遞推更新

中圖分類號(hào)：

TP301.6

文獻(xiàn)標(biāo)志碼：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è)計(jì)、地址選定、工作任務(wù)分配等常見問題；然而現(xiàn)實(shí)世界中變量之間以及變量與目標(biāo)之間均存在著大量的非線性關(guān)系，必須采用非線性 01規(guī)劃才能準(zhǔn)確予以描述。

針對(duì)非線性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）等。以上算法的共同特點(diǎn)是：它們都是基于Markov過程的智能優(yōu)化算法。目前，對(duì)于非線性01規(guī)劃問題求解的研究大多集中于：減少收斂步數(shù)[6]、優(yōu)化尋優(yōu)效果[7-8]、革新算法類型[3，5，9]以及應(yīng)用創(chuàng)新[7，10]等方面，而對(duì)于其更為實(shí)質(zhì)性的Markov過程及其狀態(tài)可達(dá)性的研究相對(duì)較少。

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

3.4分析與討論

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

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

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

4結(jié)語

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

參考文獻(xiàn)：

[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].計(jì)算機(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é)報(bào)，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.）