求解多目標優(yōu)化問題的改進布谷鳥搜索算法

楊輝華，謝譜模，張曉鳳，馬 巍，劉振丙

（1.桂林電子科技大學(xué) 廣西信息科學(xué)實驗中心，廣西 桂林541004；2.北京郵電大學(xué) 自動化學(xué)院，北京100876；3.桂林電子科技大學(xué) 電子工程與自動化學(xué)院，廣西 桂林541004）

設(shè)計和決策問題需要對多個目標同時進行優(yōu)化，而此類問題中的各個目標之間往往互相矛盾，需要在多個目標間進行折中.通常而言，多目標優(yōu)化問題要難于單目標優(yōu)化問題，在單目標優(yōu)化問題中，一般可以在搜索空間找到一個全局最優(yōu)解，而多目標優(yōu)化問題中一般不存在使得多個目標同時最優(yōu)的全局最優(yōu)解.對于多目標優(yōu)化問題，通過折中優(yōu)化而得到的曲線或曲面，被稱為Pareto前沿，針對多目標優(yōu)化問題，求得一組分布良好的Pareto前沿.

Yang等［1］在2009年提出一種新的智能優(yōu)化算法——布谷鳥搜索（cuckoo search，CS）算法，CS算法過去幾年在很多領(lǐng)域，如工程設(shè)計、任務(wù)調(diào)度、背包問題、旅行商問題等取得了良好的優(yōu)化效果［2-5］，被證明性能好于一些現(xiàn)有啟發(fā)式算法，如PSO，GA.鑒于CS算法的簡單和高效，LI等［6-9］提出相關(guān)改進算法.2011年，Yang等［10］在CS算法基礎(chǔ)上提出了多目標布谷鳥搜索（multi-objective cuckoo search algorithm，MOCS）算法，自此該算法也開始受到人們的廣泛關(guān)注［11-12］.在MOCS算法中Lévy飛行的步長控制量α0為固定值，原種群nest經(jīng)Lévy飛行后得到新種群nest′，在nest和nest′上隨機選取2個個體進行非支配關(guān)系的比較，然后基于比較結(jié)果進行個體的替換.本文在MOCS算法的基礎(chǔ)上，對Lévy飛行的步長控制量α0，下一次迭代種群的選擇方法進行改進，提出改進的多目標布谷鳥 搜 索 算 法（improved multi-objective cuckoo search algorithm，IMOCS），在 基 準 測 試 實 例SCH、ZDT 系 列、LZ 上 對 比IMOCS 與MOCS、NSPSO、NSGA-II的性能.

1 多目標優(yōu)化問題的相關(guān)基本概念

一個多目標優(yōu)化問題可表示如下：

式中：目標向量F（x）含有k個目標fi（x）；gi（x）為約束條件；Ω 為可行域；x 為n 維決策向量，x＝［x1，x2，…，xn］.

在一般情況下，多目標優(yōu)化問題不存在使得所有目標同時最優(yōu)的全局最優(yōu)解，但是可以存在這樣的解：對一個或者多個目標不可能進一步優(yōu)化，而對其他目標不至于劣化，這樣的解稱為Pareto最優(yōu)解.有關(guān)Pareto的相關(guān)定義如下：

定義1（Pareto支配）：對于目標向量u＝［u1，u2，…，uk］以及v＝［v1，v2，…，vk］，稱uPareto支配v（記：u?v），當且僅當?i∈｛1 ，2，…，k｝ ：ui≤vi∧?i∈｛1 ，2，…，k｝ ：ui＜vi.

定義2（Pareto最優(yōu)解）：對于一個解x∈Ω，稱x為Pareto最優(yōu)解，當且僅當不存在x′∈Ω，使得v＝F（x′）＝［f1（x′），f2（x′），…，fk（x′）］支配

定義3（Pareto最優(yōu)解集合）：對于一個給定的多目標優(yōu)化問題，Pareto 最優(yōu)解集合（P）的定義如下：

定義4（Pareto前沿）：對于一個給定的多目標優(yōu)化問題，Pareto前沿（PF）的定義如下：

2 多目標布谷鳥搜索算法

在標準的MOCS［10］中，Lévy飛行表示如下：

式中：α0為步長控制量，α 為步長，Lévy（β）為服從Lévy分布的隨機步長，0＜β≤2為指數(shù)，xj（t）為在第t次迭代得到的結(jié)果中隨機選擇的一個不同于xi（t）的個體.MOCS算法描述如下：

3 改進的多目標布谷鳥搜索算法

3.1 動態(tài)自適應(yīng)步長控制量

在標準MOCS中步長控制量α0為定值，當α0較小時，在迭代初期不利于全局搜索，當α0較大時，在迭代后期不利于局部搜索.基此，在IMOCS中對α0進行改進，研究動態(tài)自適應(yīng)變化的α0對IMOCS性能的影響.

Rechenberg等［13］在研究進化計算的參數(shù)自動調(diào)整時提出了1／5原則，基于Rechenberg原則張永韡等［14］在研究布谷鳥搜索算法時提出一種α0動態(tài)自適應(yīng)變化的方法.本文提出一種更加簡單有效的α0動態(tài)自適應(yīng)變化的方法，定義如下：

式中：K 為變化率，r為新解改善的比例，T 為閾值.K的取值大于0，T 的取值根據(jù)Rechenberg原則，一般取0.2～0.3之間.r的計算方法為新解中相比原個體GD值變小的個體的總數(shù)除以種群大小.當r的值大于T 時，K（r-T）為正數(shù)，使得exp（K（r-T））的值大于1，αt＋10相對于αt0增大，此時種群的搜索范圍加大，趨于全局搜索；當r的值小于T 時，K（r-T）為負數(shù)，使得exp（K（r-T））的值小于1，αt＋10相對于αt0減小，此時種群的搜索范圍減小，趨于局部搜索；當r的值等于T 時，K（r-T）為0，exp（K（r-T））的值為1，αt＋1等于αt，此時種群的搜索范圍不變.對α0的值應(yīng)限定在一定范圍，防止過調(diào).

3.2 非支配集排序

Srinivas等［15］在1994年提出了一種基于排序選擇和小生境技術(shù)的非支配排序方法，并結(jié)合遺傳算法提出了一種求解多目標優(yōu)化問題的非支配遺傳算法（NSGA）.之后Deb等［16］于2002年對NSGA中非支配排序?qū)蛹壍挠嬎阋约靶枰O(shè)定共享半徑的適應(yīng)度共享策略進行改進，提出了NSGA-II，在NSGA-II中非支配排序?qū)蛹壍挠嬎銜r間復(fù)雜度更低，并且擁擠度距離的計算不需要人為設(shè)定參數(shù)，本文采用NSGA-II中非支配集排序的方法來計算每個個體的層級和擁擠度距離.

3.3 基于非支配排序選擇種群

在MOCS中個體的選擇是基于單個個體間的比較，即對種群nest中每個個體nestj，在新產(chǎn)生的種群nest′中隨機選擇一個個體nest′i，如果nest′i支配nestj，則 用nest′i替 換nestj.在IMOCS 中，將nest和nest′結(jié)合，組成包含2n 個個體的種群tempnest，對tempnest 進行非支配集排序，對tempnest中的每個個體i 增加2 個屬性irank和idistance.從tempnest中選出n 個個體，首先選擇層級較低的個體，若層級相同，則選擇擁擠度較大的個體.

3.4 IMOCS算法描述

IMOCS算法描述如下：

4 實驗仿真和分析

4.1 測試實例

為驗證IMOCS的改進效果，選擇廣泛使用的6個測試實例SCH，ZDT 系列及LZ，說明如下：

1）SCH［17］，其Pareto前沿為凸狀，

2）ZDT1［18-19］，其Pareto前沿為凸狀，

式中：d 為x 的維數(shù).

3）ZDT2，其Pareto前沿為非凸狀，

4）ZDT3，其Pareto前沿不連續(xù)，

對于ZDT3，在其真實Pareto前沿中，f1從0變化到0.852，f2從-0.773變化到1.

5）ZDT4［20-21］，有很多局部Pareto前沿，

6）LZ［20-22］，其Pareto前沿為凸狀，

式中：J1＝｛j｜j為奇數(shù)并且2≤j≤d｝，J2＝｛j｜j為偶數(shù)并且2≤j≤d｝.

4.2 性能評價指標

為驗證IMOCS的性能，實驗中采用2個評價指標：廣義距離（generational distance，GD）和所求Pareto前沿（P＊）的多樣性Δ［23］.

GD 用于衡量所求P＊與真實前沿P 的接近程度，GD 越小，所求P＊越接近P，GD 定義如下：

式中：di為第i個個體與對應(yīng)真實Pareto前沿之間的歐氏距離，p 為優(yōu)化問題中的目標個數(shù)，對于2個目標的優(yōu)化問題，p ＝2.

Δ 用于衡量P＊的多樣性，定義如下：

4.3 參數(shù)說明

測試實例ZDT1，ZDT2，ZDT3中的維度d＝30，ZDT4中d＝10，LZ中d＝5.在IMOCS算法中發(fā) 現(xiàn) 概 率pa＝0.5 與MOCS［6］相 同，SCH，ZDT1，ZDT2，ZDT3的動態(tài)自適應(yīng)變化α0初始值為0.1，變化率K＝1.07，閾值T＝0.3，α0限定在［0.01，2］；ZDT4，LZ 的動態(tài)自適應(yīng)變化α0初始值為0.5，變化率K＝1.07，閾值T＝0.15，α0限定在［0.1，5］.以上參數(shù)的設(shè)置，α0的限定范圍、變化率K、閾值T 由實驗得出.

4.4 實驗結(jié)果與討論

本文在Pentium（R）Dual-Core T4300 ＠2.10GHz CPU，2GB RAM，Windows 7，MATLAB 2010b的計算環(huán)境下編程實現(xiàn)IMOCS 算法.為了減小數(shù)據(jù)隨機性對測試結(jié)果的影響，更準確地反映算法性能，IMOCS算法在測試中都獨立運行10次，然后計算GD 及Δ 的平均值與方差.

4.4.1 步長控制量對IMOCS性能的影響 為了驗證步長控制量α0對IMOCS性能的影響，本文分別在α0固定不變（α0＝0.01）和α0動態(tài)自適應(yīng)變化時對IMOCS的性能影響進行對比測試.設(shè)置n＝200，MaxIter＝100，如表1所示給出了6個測試實例的P＊與P 之間GD 的平均值GD和方差δ2，表2給出了P＊的Δ 的平均值和方差δ2.

從表1 中可以看出，動態(tài)自適應(yīng)變化的α0相比取固定值時使得IMOCS具有更好的性能，所有測試實例Pareto前沿的較α0固定時都有減小，即當IMOCS中α0動態(tài)自適應(yīng)變化時，其所求Pareto前沿更加接近真實Pareto前沿.且從表2中可以看出，當IMOCS中α0動態(tài)自適應(yīng)變化時，其所求Pareto前沿的多樣性也更好.

如圖1所示給出了各測試實例的Pareto前沿.針對ZDT4，α0動態(tài)自適應(yīng)變化下的IMOCS比α0固定下的IMOCS所求要小4個數(shù)量級，有很大的改進，這是由于固定α0下的IMOCS在10次獨立運行中都未能搜索到全局Pareto前沿，而動態(tài)自適應(yīng)變化α0下的IMOCS全部搜索到全局Pareto前沿，因而，這在ZDT4的Pareto前沿圖中更加直觀體現(xiàn)了這一點.

圖1 6個測試實例的Pareto前沿Fig.1 Pareto fronts of six test instances

表1 步長控制量動態(tài)自適應(yīng)變化時與固定不變時所求GD的均值和方差Tab.1 Mean and variance of GD under dynamic adaptive changing step-size control amount and fixed one

表2 步長控制量動態(tài)自適應(yīng)變化時與固定不變時所求多樣性的均值和方差Tab.2 Mean and variance of diversity under dynamic adaptive changing step-size control amount and fixed one

如圖2所示給出了6個測試實例的GD 收斂曲線.針 對 只 有1 維 變 量 的SCH，2 類α0下 的IMOCS都收斂很快；對于ZDT1，ZDT2，ZDT3，動態(tài)自適應(yīng)變化α0下的IMOCS比固定α0時收斂速度明顯要快；對ZDT4，在30次迭代以前動態(tài)自適應(yīng)變化α0下的IMOCS 所求GD 曲線在固定α0下的IMOCS所求GD 曲線之上，這主要是由于動態(tài)自適應(yīng)變化α0下的IMOCS處于探索期，α0的變化幅度較大，而30次迭代以后動態(tài)自適應(yīng)變化α0下的IMOCS所求GD 曲線在固定α0下的IMOCS所求GD 曲線之下，并且最終其GD 的數(shù)量級為10-5，在圖1（e）中體現(xiàn)為動態(tài)自適應(yīng)變化α0下的IMOCS達到了全局Pareto前沿，而固定α0下的IMOCS陷入了局部Pareto前沿，其最終的GD 數(shù)量級為10-2，從LZ 的收斂曲線圖中可以看出，固定α0下的IMOCS在搜索中GD 值有幾處明顯的波動，而動態(tài)自適應(yīng)變化α0下的IMOCS較穩(wěn)定.由此可知：動態(tài)自適應(yīng)變化α0能使IMOCS快速、穩(wěn)定的收斂.

如圖3所示為動態(tài)自適應(yīng)變化的α0在1 000次迭代過程中的變化曲線，其測試實例為ZDT4.由圖3可以看出，在40次迭代以前，α0的值有較大的波動，這是α0的一個自適應(yīng)調(diào)整過程，算法處在探索期，在這期間GD 的值減小較快，這在圖2（e）中GD 的收斂曲線體現(xiàn)出來；40次迭代到70次迭代，α0的值穩(wěn)定在1.3 左右，算法處在收斂期，在這期間GD 的值緩慢減小到數(shù)量級10-4附近，表明搜索達到全局Pareto前沿，這在圖1（e）中體現(xiàn)為動態(tài)自適應(yīng)變化α0下的IMOCS達到了全局Pareto前沿，而固定α0下的IMOCS陷入了局部Pareto前沿；70次迭代以后，α0的值逐漸減小，在120次以后變?yōu)樵O(shè)定的最小值0.1，算法已進入停滯期，此后GD 的值穩(wěn)定在數(shù)量級10-5附近，不再有明顯的變化.

4.4.2 IMOCS與MOCS的性能比較分析 為了驗證IMOCS算法的有效性，本文將其與MOCS的性能進行對比分析.Yang 等［10］給出了MOCS 在n＝50，MaxIter＝500時5個測試實例的GD值，本文計算IMOCS在相同條件下的GD 值，將2種算法的實驗結(jié)果列于表3.從表3中可知，IMOCS所求GD值都小于MOCS，說明IMOCS性能好于MOCS.4.4.3 IMOCS 與NSPSO 的 性 能 比 較 分 析 Li［21］在2003年提出了基于非支配排序的粒子群優(yōu)化算法（NSPSO）算法來解決多目標優(yōu)化問題，算法主要基于非支配排序和小生境技術(shù).為了驗證IMOCS算法的有效性，本文將其與NSPSO 的性能進行對比分析.Li［21］給出了NSPSO 在n＝200，MaxIter＝100時4個測試實例的測試結(jié)果，本文給出了IMOCS在相同條件下的測試結(jié)果.如表4所示為4個測試實例P＊與P 之間的GD 的平均值和方差δ2，如表5所示為P＊的Δ 平均值和方差δ2.

表（5）為IMOCS和NSPSO 所求多樣性均值與方差，由表5可知，IMOCS所求Δ 都小于NSPSO，表明IMOCS所求的Pareto前沿多樣性更好，而且其偏差較小，進一步說明IMOCS的穩(wěn)定性.

4.4.4 IMOCS與NSGA-II的性能比較分析 為了驗證IMOCS算法的有效性，本文將其與NSGAII的性能進行對比分析.Deb［23］在2002 對NSGA進行改進，提出了NSGA-II，但并未給出實驗分析.Yang等［10］給出了NSGA-II在n＝50，MaxIter＝500時5個測試實例的GD值，本文計算IMOCS在相同條件下的GD 值，將2 種算法的實驗結(jié)果列于 表6.從 表6 中 可 知，IMOCS 所 求GD 值 都 小 于NSGA-II，說明IMOCS性能好于NSGA-II.

圖2 6個測試實例的GD收斂曲線Fig.2 GD convergence curves of six test instances

表3 IMOCS與MOCS所求的GD值Tab.3 GD for IMOCS and MOCS

表4 IMOCS與NSPSO 所求的GD均值和方差Tab.4 Mean and variance of GD for IMOCS and NSPSO

表5 IMOCS與NSPSO 所求多樣性的均值和方差Tab.5 Mean and variance of diversity for IMOCS and NSPSO

表6 IMOCS與NSGA-II所求的GD值Tab.6 GD for IMOCS and NSGA-II

圖3 ZDT4中α0 的變化曲線Fig.3 Variation curve ofα0for ZDT4

5 結(jié) 語

通過對MOCS算法的2點改進：使用動態(tài)自適應(yīng)的步長控制量α0及基于層級和擁擠度距離選擇種群，本文提出了IMOCS算法.在測試實例SCH、ZDT 系列和LZ 上進行性能測試，研究了α0對IMOCS 尋優(yōu)效果的影響，并與MOCS，NSPSO，NSGA-II進行比較.結(jié)果表明動態(tài)自適應(yīng)變化α0下的IMOCS所求Pareto前沿的廣義距離和多樣性都優(yōu)于MOCS和NSPSO，而且動態(tài)自適應(yīng)變化的α0能使IMOCS 收斂速度更快、求解更加穩(wěn)定.IMOCS中非支配集排序算法是不受目標數(shù)量和決策變量限制的，針對2個目標以上的多目標優(yōu)化問題，同樣能夠為每個個體計算其層級和擁擠度距離，而廣義距離GD 和種群多樣性Δ 的計算方法由其定義可知是可以隨目標的數(shù)量拓展的，在后續(xù)研究中，將研究2個目標以上的多目標優(yōu)化問題.

（

）：

［1］YANG X S，DEB S.Cuckoo search via Lévy flights［C］∥World Congress on Nature ＆Biologically Inspired Computing.NaBic：IEEE Publications，2009：210-214.

［2］FISTER J I，YANG X S，F(xiàn)ISTER D，et al.Cuckoo search：A brief literature review［M］.London：Springer International Publishing，2014：49-62.

［3］YANG X S，DEB S.Cuckoo search：recent advances and applications［J］.Neural Computing and Applications，2014，24（1）：169-174.

［4］GHERBOUDJ A，LAYEB A，CHIKHI S.Solving 0-1 knapsack problems by a discrete binary version of cuckoo search algorithm［J］.International Journal of Bio-Inspired Computation，2012，4（4）：229-236.

［5］OUAAARAB A，AHIOD B，YANG X S.Discrete cuckoo search algorithm for the travelling salesman problem ［J］.Neural Computing and Applications，2014，24（7／8）：1659-1669.

［6］LI Xiang-tao，WANG Jia-nan，YIN Ming-hao.Enhancing the performance of cuckoo search algorithm using orthogonal learning method［J］.Neural Computing and Applications，2014，24（6）：1233-1247.

［7］王李進，尹義龍，鐘一文.逐維改進的布谷鳥搜索算法［J］.軟件學(xué)報，2013，24（11）：2687-2698.WANG Li-jin，YIN Yi-long，ZHONG Yi-wen.Cuckoo search algorithm with dimension by dimension improvement［J］.Journal of Software，2013，24（11）：2687-2698.

［8］SRIVASTAVA P R，KHANDELWAL R，KHANDELWAL S.Automated test data generation using cuckoo search and tabu search（CSTS）algorithm ［J］.Journal of Intelligent Systems，2012，21（2）：195-224.

［9］胡欣欣，尹義龍.求解函數(shù)優(yōu)化問題的合作協(xié)同進化布谷鳥搜索算法［J］.模式識別與人工智能，2013，26（11）：1041-1049.HU Xin-xin，YIN Yi-long.Cooperative co-evolutionary cuckoo search algorithm continuous function optimization poblems［J］.Pattern Recognition and Artificial Intelligence，2013，26（11）：1041-1049.

［10］YANG X S，DEB S.Multi-objective cuckoo search for design optimization［J］.Computers ＆ Operations Research，2011，40（6）：1616-1624.

［11］LAYEB A，LAHOUESNA N，KIRECHE B.A multiobjective binary cuckoo search for bicriteria knapsack problem［J］.International Journal of Information Engineering ＆Electronic Business，2013，5（4）：8-15.

［12］CHANDRASEKARAN K，SIMON S P.Multi-objective scheduling problem：Hybrid approach using fuzzy assisted cuckoo search algorithm ［J］.Swarm and Evolutionary Computation，2012，5（1）：1-16.

［13］B?CK T.Evolutionary algorithms in theory and practice：Evolution strategies，evolutionary programming，genetic algorithms ［M］.Oxford：Oxford University Press，1996：161-164.

［14］張永韡，汪鐳，吳啟迪.動態(tài)適應(yīng)布谷鳥搜索算法［J］.控制與決策，2014，29（4）：617-622.ZHANG Yong-wei，WANG Lei，WU Qi-di.Dynamic adaptation cuckoo search algorithm ［J］.Control and Decision，2014，29（4）：617-622.

［15］SRINIVAS N，DEB K.Multi-objective optimization using non-dominated sorting in genetic algorithms［J］.Evolutionary computation，1994，2（3）：221-248.

［16］DEB K，PRATAP A，AGARWAL S，et al.A fast and elitist multi-objective genetic algorithm：NSGA-II［J］.Evolutionary Computation，IEEE Transactions on，2002，6（2）：182-197.

［17］SCHAFFER J D.Multiple objective optimization with vector evaluated genetic algorithms［C］∥Proceedings of the 1st international Conference on Genetic Algorithms.New Jersey：L.Erlbaum Associates Inc，1985：93-100.

［18］ZITZLER E，THIELE L.Multi-objective evolutionary algorithms：a comparative case study and the strength Pareto approach［J］.Evolutionary Computation，IEEE Transactions on，1999，3（4）：257-271.

［19］ZITZLER E，DEB K，THIELE L.Comparison of multi-objective evolutionary algorithms：Empirical results［J］.Evolutionary Computation，2000，8（2）：173-195.

［20］ZHANG Qing-fu，LI Hui.MOEA／D：A multi-objective evolutionary algorithm based on decomposition［J］.Evolutionary Computation，IEEE Transactions on，2007，11（6）：712-731.

［21］LI Xiao-dong.A non-dominated sorting particle swarm optimizer for multi-objective optimization［C］∥Genetic and Evolutionary Computation—GECCO 2003.Chicago：Springer Berlin Heidelberg，2003：37-48.

［22］LI Hui，ZHANG Qing-fu.Multi-objective optimization problems with complicated Pareto sets，MOEA／D and NSGA-II［J］.Evolutionary Computation，IEEE Transactions on，2009，13（2）：284-302.

［23］DEB K Multi-objective optimization using evolutionary algorithms［M］.Chichester：John Wiley ＆ Sons，2001：320-332.