李枝勇，馬良，張惠珍（上海理工大學(xué)管理學(xué)院，上海200093）

多目標(biāo)0－1規(guī)劃問題的蝙蝠算法

李枝勇，馬良，張惠珍
（上海理工大學(xué)管理學(xué)院，上海200093）

如何獲取多目標(biāo)問題更多的Pareto最優(yōu)解具有十分重要的意義。在重新定義蝙蝠位置和速度更新公式的基礎(chǔ)上，提出了一種用于求解多目標(biāo)0－1規(guī)劃問題的改進(jìn)的蝙蝠算法。通過測試函數(shù)進(jìn)行仿真實驗，結(jié)果表明：與遺傳算法、蟻群算法、元胞蟻群算法和粒子群算法相比，所提出的算法能夠為多目標(biāo)0－1規(guī)劃問題找到更多的Pareto解，體現(xiàn)了蝙蝠算法在解決該問題上的有效性和優(yōu)越性。

智能優(yōu)化；組合優(yōu)化；多目標(biāo)0－1規(guī)劃問題；蝙蝠算法

在很多實際問題中，往往難以用一個指標(biāo)來衡量和判斷一個方案的優(yōu)劣，而是需要用多個目標(biāo)。與單目標(biāo)問題不同的是，多目標(biāo)優(yōu)化問題有著多種提法和模型。多目標(biāo)0－1規(guī)劃問題是一個經(jīng)典的難題，已被歸入所謂的NP?難問題，是否存在有效算法尚不可知。目前已有的精確算法都是指數(shù)級的，對于現(xiàn)實中的問題，特別是當(dāng)問題規(guī)模較大時，根本無法使用傳統(tǒng)的優(yōu)化方法和技術(shù)來求解，而對于多目標(biāo)的0－1規(guī)劃來說，由于增加了目標(biāo)函數(shù)的個數(shù)，使問題的求解復(fù)雜度進(jìn)一步加大。本文主要討論多目標(biāo)0－1線性規(guī)劃問題。

蝙蝠算法［2］（bat algorithm，BA）是X.S.Yang于2010年提出的一種新型啟發(fā)式算法，它模擬的是微型蝙蝠的回聲定位原理。自該算法提出以來，已有學(xué)者將該算法應(yīng)用于優(yōu)化問題［2～5］，他們的研究成果表明：在解決實際問題中，蝙蝠算法比粒子群算法、遺傳算法和和聲算法具有更大的潛能。

本文首先介紹了蝙蝠算法在迭代尋優(yōu)過程中的核心方程，接著根據(jù)多目標(biāo)0－1規(guī)劃問題的特點，重新定義蝙蝠速度和位置的更新公式，提出了求解多目標(biāo)0－1規(guī)劃問題的蝙蝠算法，最后，對4個測試算例進(jìn)行仿真實驗，并將其計算結(jié)果與遺傳算法、蟻群算法、元胞蟻群算法和粒子群算法的計算結(jié)果進(jìn)行比較，比較結(jié)果不但驗證了本文所提算法的有效性，而且體現(xiàn)出了在解決多目標(biāo)0－1規(guī)劃問題上，所提算法比上述算法具有更好的優(yōu)越性。

1 基本蝙蝠算法

假設(shè)在一個d維搜索空間中，第i只蝙蝠在第t代蝙蝠的位置為速度為，脈沖頻率為Fi，且當(dāng)前蝙蝠種群最好的位置為x?，則關(guān)于和的更新方程為

式中：β∈［0，1］是一隨機向量，F(xiàn)max和Fmin分別為脈沖頻率的最大值和最小值，其各個元素均服從均勻分布。

上述更新方程是針對全局搜索的，對于局部搜索，可以首先從現(xiàn)有的最優(yōu)解集中隨機選擇出一個當(dāng)前最好解xold，然后在其附近就近產(chǎn)生每只蝙蝠新待定的位置，如式（4）所示：

式中：ε∈［－1，1］是一個任意的數(shù)字，At＝是所有蝙蝠在該時間步驟里的平均響度。

為保證算法在全局搜索和局部搜索之間達(dá)成一種良好的平衡關(guān)系，要求脈沖發(fā)射的響度Ai和速率ri要隨著迭代過程的進(jìn)行而有所更新。通常情況下，響度會逐漸降低，脈沖的發(fā)射速率會逐漸增加。具體的實現(xiàn)方式如式（5）和式（6）所示：

式中：α和γ是常量。對于任何0＜α＜1和γ＞0，當(dāng)t→∞時，有：→0，→。

2 求解多目標(biāo)0－1規(guī)劃問題的蝙蝠算法

考慮如下形式的多目標(biāo)0－1規(guī)劃問題：

式中：x為決策變量，Z為目標(biāo)向量，記D為決策變量的可行域。

在具體求解時，采用罰函數(shù)的方法，將約束條件轉(zhuǎn)化到目標(biāo)函數(shù)中，將問題轉(zhuǎn)化為無約束形式。

通常情況下，類似于單目標(biāo)優(yōu)化的最優(yōu)解在多目標(biāo)優(yōu)化中是不存在的，只存在Pareto最優(yōu)解，而且大都具有很多個Pareto最優(yōu)解［1］。其含義為：記當(dāng)前Pareto最優(yōu)解為x0，則不存在任何其他解x，使得Zi(x)≥Zi(x0)，i＝1，2，…，k，其中，至少有一個不等式嚴(yán)格成立。

定義：假設(shè)p和q是群體中任意2個不同的個體，若稱p支配q，則必須滿足以下2個條件：

1）?m∈{1，2，…，k} ，Ζm(p)≥Ζm(q)，即對所有的子目標(biāo)，p不比q差；

2）?l∈{1，2，…，k} ，Zl(p)＞Zl(q)，即至少存在一個子目標(biāo)，使得p比q好。這里，p為支配的，q為被支配的，可以表示成p?q。

由于基本蝙蝠算法是用來求解連續(xù)域的函數(shù)優(yōu)化問題，所以要將基本蝙蝠算法進(jìn)行離散化地改進(jìn)才能求解離散問題。為了將尋優(yōu)領(lǐng)域控制在0和1 2個整數(shù)之間，這里對蝙蝠算法的（2）～（4）進(jìn)行重新定義：

式中：round指四舍五入取整，xor和or分別指邏輯運算符的異或和或，xold為從當(dāng)前Pareto最優(yōu)解集中隨機產(chǎn)生的一個解，n指種群個數(shù)，d指維數(shù)。

下面給出求解多目標(biāo)0－1規(guī)劃問題的蝙蝠算法的基本步驟：

1）初始化。蝙蝠種群大小為n，初始種群中第i只蝙蝠位置x（i），速度v（i），脈沖發(fā)射速率R（i），脈沖響度A（i），脈沖頻率F（i），個體目標(biāo)函數(shù)集Zix i()()，i＝1，2，…，n，確定當(dāng)前Pa?reto最優(yōu)解集。

2）判斷是否滿足算法結(jié)束條件，如果滿足，則轉(zhuǎn)9），否則轉(zhuǎn)3）。

3）利用式（1）、（8）、（9）產(chǎn)生一個新的解xnew，并更新速度和位置。

4）if rand＞R i()

從當(dāng)前最優(yōu)解集中隨機選擇一個解xold，并利用式（10）得到一個局部解xnew；

endif

5）計算個體目標(biāo)函數(shù)集Zixnew()new。

6）if rand〈A i()＆Ζixnew()new〉

Zix i()()

x i()＝xnew

Zix i()()＝Zixnew()new

通過式（5）減小A i()，式（6）增大R i()；

endif

7）更新當(dāng)前Pareto最優(yōu)解集。如果xnew支配當(dāng)前Pareto最優(yōu)解集的一個或幾個解，則將被xnew支配的所有解移出當(dāng)前Pareto最優(yōu)解集，而將xnew移入當(dāng)前Pareto最優(yōu)解集；如果xnew與當(dāng)前Pareto最優(yōu)解集不存在任何支配關(guān)系，則直接加入到當(dāng)前Pareto最優(yōu)解集中；其他情況則保持當(dāng)前Pareto最優(yōu)解集不變。

8）轉(zhuǎn)2）。

9）輸入所求的Pareto最優(yōu)解集。

從算法的流程可以看出，所提算法的時間復(fù)雜度大小取決于Pareto最優(yōu)解集的構(gòu)造和產(chǎn)生辦法。本文選取的是排除法，其時間復(fù)雜度為：O kN()。故所提算法的時間復(fù)雜度為：O dknN()。其中，d為變量的維數(shù)，k為目標(biāo)函數(shù)個數(shù)，n為群體個數(shù)，N為Pareto最優(yōu)解集的容量。需要指出的是：下文中，由于所求問題的規(guī)模較小，所以并沒有給出其具體值，所以在運行過程中，N的值是動態(tài)變化的。

3 數(shù)值實驗

為了驗證本算法的性能，分別與遺傳算法、蟻群算法［1］、元胞蟻群算法［6］、蜂群算法［7］和粒子群算法［8］進(jìn)行試驗比較，采用文獻(xiàn)［9］中4個多目標(biāo)0－1規(guī)劃問題進(jìn)行測試。參數(shù)設(shè)置為：蝙蝠個數(shù)為20，F(xiàn)max＝1，F(xiàn)min＝0，α＝γ＝0.9，初始頻率和初始速度均為0，脈沖的響度和發(fā)射速率從［0，1］隨機產(chǎn)生。環(huán)境為Win7系統(tǒng)下的MATLAB 7.8（R2009a）.計算結(jié)果見表1～表5。

算例1：

試驗結(jié)果見表1。

表1 測試1的結(jié)果比較Table 1 Comparing resu lts of test 1

算例2：

試驗結(jié)果見表2。

表2 測試2的結(jié)果比較Table 2 Com paring resu lts of test 2

算例3：

用蝙蝠算法解得Pareto最優(yōu)解見表3。對比結(jié)果分析見表4。

表3 測試3的結(jié)果Tab le 3 Result of test 3

表4 測試3的結(jié)果比較Table 4 Com paring resu lts of test 3

算例4：

試驗結(jié)果見表5。

表5 測試4的結(jié)果比較Table 5 Com paring results of test 4

通過觀察和分析上述4個算例的測試結(jié)果，不難發(fā)現(xiàn)：文中所提出的算法能夠找到上述4個算例的所有Pareto最優(yōu)解，而遺傳算法、蟻群算法、元胞蟻群算法、蜂群算法和粒子群算法卻不能保證找到上述4個算例的所有Pareto最優(yōu)解，從而突出了文章所提出的算法性能的優(yōu)越性。

4 結(jié)束語

蝙蝠算法是一種元啟發(fā)式算法，啟發(fā)于微型蝙蝠利用回聲定位功能尋找食物、避開障礙物這一特殊現(xiàn)象。從實驗結(jié)果來看，它比目前應(yīng)用廣泛的蟻群算法、蜂群算法、遺傳算法、元胞蟻群算法和粒子群算法具有更好的適應(yīng)性。文章所提的算法是對多目標(biāo)規(guī)劃問題的一種新的嘗試，更多的工作尚待于進(jìn)一步展開，諸如將其應(yīng)用擴(kuò)展到多目標(biāo)整數(shù)規(guī)劃中去，以及其他的經(jīng)典組合優(yōu)化問題中去，從而豐富蝙蝠算法的應(yīng)用領(lǐng)域。

［1］馬良，朱剛，寧愛兵.蟻群優(yōu)化算法［M］.北京：科學(xué)出版社，2008：185?189.

［2］YANG X S.A new metaheuristic bat?inspired algorithm［M］／／Nature inspired cooperative strategies for optimiza?tion（NICSO 2010）.Berlin Heidelberg：Springer，2010：65?74.

［3］YANG X S.Bat algorithm for multi?objective optim isation［J］.International Journal of Bio?Inspired Computation，2011，3（5）：267?274.

［4］YANG X S，GANDOMI A H.Bat algorithm：a novel ap?proach for global engineering optimization［J］.Engineering Computation，2012，29（5）：267?289.

［5］GANDOMIA H，YANG X S，ALAVIA H，et al.Bat algo?rithm for constrained optimization tasks［J］.Neural Compu?ting and Applications，2013，22（6）：1239?1255.

［6］劉勇，馬良，許秋艷.多目標(biāo)0?1規(guī)劃問題的元胞蟻群優(yōu)化算法［J］.系統(tǒng)工程，2009，27（2）：119?122.LIU Yong，MA Liang，XU Qiuyan.Solving multi?objective 0?1 programming by cellular ant algorithm［J］.Systems En?gineering，2009，27（2）：119?122.

［7］韓燕燕，馬良，趙小強.多目標(biāo)0?1規(guī)劃問題的蜂群算法［J］.運籌與管理，2012，21（2）：23?26.HAN Yanyan，MA Liang，ZHAO Xiaoqiang.Bee colony al?gorithm for the multi?objective 0?1 programming problem［J］.Operations Research and Management Science，2012，21（2）：23?26.

［8］孫瀅，高岳林.一種求解多目標(biāo)0?1規(guī)劃問題的自適應(yīng)粒子群算法［J］.計算機應(yīng)用與軟件，2009，26（12）：71?73.SUN Ying，GAO Yuelin.An adaptive particle swarm optimi?zation algorithm for solvingmulti?objective 0?1 programming problem［J］.Computer Application and Software，2009，26（12）：71?73.

［9］楊玲玲，馬良，張惠珍.多目標(biāo)0?1規(guī)劃的混沌優(yōu)化算法［J］.計算機應(yīng)用研究，2012，29（12）：4486?4488.YANG Lingling，MA Liang，ZHANG Huizhen.Chaotic opti?m ization algorithm formulti?objective 0?1 programm ing prob?lem［J］.Application Research of Computers，2012，29（12）：4486?4488.

李枝勇，男，1986年生，碩士研究生，主要研究方向為智能優(yōu)化、系統(tǒng)工程。發(fā)表學(xué)術(shù)論文9篇。

馬良，男，1964年生，教授，博士生導(dǎo)師，主要研究方向為智能優(yōu)化、系統(tǒng)工程。先后承擔(dān)完成包括國家自然科學(xué)基金在內(nèi)的各類科研項目20多項，發(fā)表論文300余篇，出版專著1部，主編教材2部。

Bat algorithm for themulti?objective 0－1 programm ing problem

LIZhiyong，MA Liang，ZHANG Huizhen
（School of Management，University of Shanghai for Science and Technology，Shanghai200093，China）

Obtainingmore Pareto solutions is very important for the multi?objective problem.This paper presented an improved bat algorithm for solving themulti?objective 0－1 programming problem with linear constrains.The pro?posed algorithm，which is based on redefining the updating formulas of the velocity and position aboutevery bat，is implemented through several tests.The algorithm is compared with a genetic algorithm，an ant colony optimization algorithm，a cellular ant colony algorithm and a particle swarm optimization algorithm.The comparisons showed that the proposed algorithm can getmore Pareto solutions and bemuch more effective to solve such problems.

intelligent optimization；combinatorial optimization；multi?objective 0－1 programming problem；batal?gorithm

TP301.6；N945

A

1673?4785（2014）06?0672?05

李枝勇，馬良，張惠珍.多目標(biāo)0－1規(guī)劃問題的蝙蝠算法［J］.智能系統(tǒng)學(xué)報，2014，9（6）：672?676.

英文引用格式：LI Zhiyong，M A Liang，ZHANG Huizhen.Bat algorithm for the multi?objective 0－1 programm ing problem［J］.CAAI Transactions on Intelligent System s，2014，9（6）：672?676.

10.3969／j.issn.1673?4785.201310038

http：／／www.cnki.net／kcms／doi／10.3969／j.issn.1673?4785.201310038.htm l

2013?09?12.

日期：2014?09?30.

上海市一流學(xué)科建設(shè)基金資助項目（S1201YLXK）；上海高校青年教師培養(yǎng)資助計劃資助項目（slg12010）；高等學(xué)校博士學(xué)科點專項科研基金聯(lián)合資助課題資助項目（20123120120005）；上海市教育委員會科研創(chuàng)新基金資助項目（14YZ090）；上海市研究生創(chuàng)新基金資助項目（JWCXSL1202）；上海理工大學(xué)博士科研啟動基金資助項目（1D?10?303?002）.

李枝勇.Email：lizhiyong.2180869＠163.com.