多目標0－1規劃問題的蝙蝠算法

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

多目標0－1規劃問題的蝙蝠算法

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

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

智能優化；組合優化；多目標0－1規劃問題；蝙蝠算法

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

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

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

1 基本蝙蝠算法

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

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

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

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

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

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

2 求解多目標0－1規劃問題的蝙蝠算法

考慮如下形式的多目標0－1規劃問題：

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

在具體求解時，采用罰函數的方法，將約束條件轉化到目標函數中，將問題轉化為無約束形式。

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

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

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

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

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

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

下面給出求解多目標0－1規劃問題的蝙蝠算法的基本步驟：

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

2）判斷是否滿足算法結束條件，如果滿足，則轉9），否則轉3）。

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

4）if rand＞R i()

從當前最優解集中隨機選擇一個解xold，并利用式（10）得到一個局部解xnew；

endif

5）計算個體目標函數集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）更新當前Pareto最優解集。如果xnew支配當前Pareto最優解集的一個或幾個解，則將被xnew支配的所有解移出當前Pareto最優解集，而將xnew移入當前Pareto最優解集；如果xnew與當前Pareto最優解集不存在任何支配關系，則直接加入到當前Pareto最優解集中；其他情況則保持當前Pareto最優解集不變。

8）轉2）。

9）輸入所求的Pareto最優解集。

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

3 數值實驗

為了驗證本算法的性能，分別與遺傳算法、蟻群算法［1］、元胞蟻群算法［6］、蜂群算法［7］和粒子群算法［8］進行試驗比較，采用文獻［9］中4個多目標0－1規劃問題進行測試。參數設置為：蝙蝠個數為20，Fmax＝1，Fmin＝0，α＝γ＝0.9，初始頻率和初始速度均為0，脈沖的響度和發射速率從［0，1］隨機產生。環境為Win7系統下的MATLAB 7.8（R2009a）.計算結果見表1～表5。

算例1：

試驗結果見表1。

表1 測試1的結果比較Table 1 Comparing resu lts of test 1

算例2：

試驗結果見表2。

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

算例3：

用蝙蝠算法解得Pareto最優解見表3。對比結果分析見表4。

表3 測試3的結果Tab le 3 Result of test 3

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

算例4：

試驗結果見表5。

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

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

4 結束語

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

［1］馬良，朱剛，寧愛兵.蟻群優化算法［M］.北京：科學出版社，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］劉勇，馬良，許秋艷.多目標0?1規劃問題的元胞蟻群優化算法［J］.系統工程，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］韓燕燕，馬良，趙小強.多目標0?1規劃問題的蜂群算法［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］孫瀅，高岳林.一種求解多目標0?1規劃問題的自適應粒子群算法［J］.計算機應用與軟件，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］楊玲玲，馬良，張惠珍.多目標0?1規劃的混沌優化算法［J］.計算機應用研究，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年生，碩士研究生，主要研究方向為智能優化、系統工程。發表學術論文9篇。

馬良，男，1964年生，教授，博士生導師，主要研究方向為智能優化、系統工程。先后承擔完成包括國家自然科學基金在內的各類科研項目20多項，發表論文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

李枝勇，馬良，張惠珍.多目標0－1規劃問題的蝙蝠算法［J］.智能系統學報，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.

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

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