結合分解技術的多目標引力搜索算法

畢曉君，刁鵬飛，王艷嬌，肖 婧

（1.哈爾濱工程大學信息與通信工程學院，150001哈爾濱；2.東北電力大學信息工程學院，132012吉林吉林；3.遼寧省交通高等?？茖W校信息工程系，110122沈陽）

結合分解技術的多目標引力搜索算法

畢曉君1，刁鵬飛1，王艷嬌2，肖 婧3

（1.哈爾濱工程大學信息與通信工程學院，150001哈爾濱；2.東北電力大學信息工程學院，132012吉林吉林；3.遼寧省交通高等專科學校信息工程系，110122沈陽）

針對基于分解的多目標遺傳算法在解決多目標問題時無法有效解決前沿面非均勻、不連續的問題，提出一種基于分解技術的多子群串行搜索的多目標引力搜索算法（MOGSA／D）.為充分利用算法優化分解出的目標函數所得到的進化信息、提高收斂速度，采取多種群串行的搜索方式；針對理想前沿面為非超平面的情況，提出一種預測理想前沿面形狀的方法，并針對預測結果選擇適合的權重系數生成方式；為提高解集的整體質量，提出一種基于目標權值的策略刪減種群.通過標準測試函數的實驗驗證，所提算法與其他多目標進化算法相比在解集的收斂性以及分布性上均有較大提高，驗證了算法的有效性.

引力搜索算法；多目標優化；分解；多種群策略

多目標優化問題MOP（multi-objective optimization problem）需要同時優化2個或2個以上的目標函數，且各個優化目標之間通常是相互沖突的，因此不存在能使所有目標都達到最優的解.

多目標進化算法MOEA（multi-objective evolutionary algorithm）是目前廣泛采用的一種解決MOP的方法，主要可以分為3類：1）基于Pareto占優關系的MOEA算法，如ε-占優機制［1］、E-占優機制［2］；2）基于評估指標的MOEA算法，如HypE［3］等算法；3）基于分解技術的MOEA算法，如MOEA／D算法［4］.其中基于分解的MOEA算法因其計算簡單、復雜度小和收斂性好受到廣泛關注，但當理想前沿面為不連續、非均勻等形狀時，所得到的優化結果的收斂精度及穩定性還有待進一步提高.

引力搜索算法GSA（gravitational search algorithm）是2010年提出的群智能優化算法，具有設置參數少、全局搜索能力強、計算簡單、收斂速度快等優點［5］.本文將GSA與分解技術相結合，提出一種基于分解技術的多目標引力優化算法.主要創新點：1）采用分解技術，將多目標問題分解成單目標問題，然后采用多子群串行搜索的策略對各子問題展開優化，提高進化搜索的效率；2）提出一種理想前沿面的預測策略，并根據預測結果選取適合的權重系數計算方式，一定程度上保證了解集分布的均勻性；3）針對解在各目標所得結果的線性加權和，提出一種種群刪減策略，提高了解集相對于理想前沿面的逼近性及分布的均勻性.

1 引力搜索算法及基于分解的多目標算法

1.1 引力搜索算法

可以把種群中的個體想象成是一組在空間中運動的粒子，它們在萬有引力的作用下，相互運動，其質量的大小是評價解優劣的標準，質量較大粒子的位置對應較優解.粒子通過相互作用、相互運動實現進化信息的共享，從而向最優區域展開搜索.

設空間中含有N個粒子，則第i個粒子的位置表示為

式中：Maj（t）和Mpi（t）分別為粒子j和粒子i的質量；ε是一個極小的常量；G（t）表示在t時刻的萬有引力常數，具體定義為

式中：T為設置的最大迭代次數，G0為初始時刻的引力常數，Rij（t）為粒子i與粒子j之間的歐氏距離．則在t時刻，粒子i在k維上受到的其他粒子的合力為

式中：rankj為變化區間在［0，1］之間的隨機數；為粒子j對粒子i在第k維空間上的作用力．依據牛頓第二定律，定義t時刻粒子i在k維上的加速度為

在進化過程中，粒子的速度和位置的更新方式為

粒子的質量與適應度值有關，質量越大的粒子越接近最優，并且它對其他粒子的作用力相應會更大，但移動速度較慢.粒子質量的計算方式為

式中：fi（t）為粒子i的適應度值；w（t）為質量最小粒子的適應度值；b（t）為質量最大粒子的適應度值．

圖1給出了GSA算法的操作流程圖.

圖1 GSA算法流程圖

1.2 基于分解的多目標算法

基于分解的多目標優化算法結合了多目標局部搜索和多個單目標Pareto抽樣的優點，而切比雪夫法又是其中解決效果最好的方法.在切比雪夫分解模型下，對于一個給定的權重向量，對應的單目標子問題可描述為

式中：權重向量λ=（λ1，…，λm）滿足λk≥0且為參考點，是由解集在各個目標函數上取得的最優值構成的虛擬點，對于最小化問題有z?i=min｛fi（x）｜x∈Ω｝，1，2，…，m．在滿足條件的情況下，對于任意一個給定的權重向量，存在一個使式（1）達到最小的最優解，該最優解就是原多目標優化問題的一個Pareto最優解.所以，可以通過設定N個不同的權重向量獲得N個最優解來構成Pareto最優解集．

2 基于分解的多目標引力搜索算法

提出一種基于分解技術的多目標引力搜索算法（MOGSA／D）.首先選取幾組具有偏好性的權重系數展開優化搜索，并以此判別理想前沿面的形狀.然后基于預測結果選取適合的權重系數計算方式.種群在對分解后的優化問題展開搜索時，相鄰子問題的解具有相似性，因此為充分利用這種近似性，提高求解能力尤其是非均勻不連續問題的優化效率，采用多子群串行搜索的策略.最后為提高解集的收斂精度并兼顧粒子分布的均勻性，提出一種基于目標權值的策略對種群進行刪減.

2.1 權重的自適應選取

MOEA／D通過構造多組權重系數將一個MOP分解為一組單目標優化問題，并通過子問題之間的合作來同時優化這組子問題，從而獲得對理想最優解集的一個逼近.但該方法存在2個問題：

1）傳統MOEA／D算法采用的權重系數生成方法是基于理想面是超平面的情況.針對理想面非均勻的情況，單一的權重系數生成方式會影響解集分布的均勻性，如圖2所示.

圖2 分布非均勻前沿面

2）當前沿面不連續時，若算法對處在斷開區域的子目標問題進行優化求解，則由于進化壓力容易得到相同的解，勢必會浪費計算資源，降低算法的整體優化性能，如圖3所示.

圖3 分布不連續前沿面

為解決上述問題，文獻［6］提出權重向量根據其自身的最優解進行自適應調整，文獻［7］提出一種加強的權重向量調整方法.但這些方法所適用的前提條件是理想前沿面是超平面的情況，當前沿面為非超平面或不連續時，上述方法均不能保證所得解集分布的均勻性，且會浪費計算資源.因此，權重系數的生成必須針對不同的前沿面形狀自適應產生.

基于以上分析，首先對理想前沿面的形狀進行預測.通過選擇具有明顯偏好性的權值系數可以得到理想前沿面的邊界點，若理想前沿面為超平面，則對2個目標問題有判別方式為

理論證明：當理想前沿面是超平面時，則對2個目標問題是一條直線，在極端情況下，當權重向量的取值為（1，0）時，所得的最優解在2個目標函數上的解是這條前沿面上的一個端點；同理，當權重向量取值為（0，1）時為前沿面的另一個端點；對一個等腰直角三角形，角分線也是中位線，即取權重向量為（0.5，0.5）時，所得的解應位于前沿面的中點位置上．

對3個目標問題，可判斷點和面的位置關系，即通過求解4組權重系數構成的子問題的最優值，判斷理想前沿面的形狀．設4組偏好權重系數構成的

根據得到的平面方程，通過比較點和面的位置關系得到前沿面的預測結果，具體描述如下：

若

若

若

當預測到前沿面形狀后，針對不同的預測結果，為有效解決非均勻不連續前沿面問題，必須保證權重系數構成的向量與前沿面的焦點均勻分布在前沿面上.提出一種權重系數的生成方式為

1）當前沿面為超平面時，則p取值為1，即λ構成的面也為超平面；

2）當前沿面為凸平面時，則p取值為2，即λ構成的面也為凸平面；

3）當前沿面為凹平面時，則p取值為0.5，即λ構成的面也為凹平面．

2.2 多子群串行搜索

對于非連續理想前沿面，由于進化壓力的驅使，必然會導致幾組相似權重系數所構建出的子問題具有相同的解.為解決前沿面不連續所帶來的資源浪費問題，結合GSA的收斂速度快、求解精度高、進化步長可控等特性，采取多子群串行搜索的策略對構造出的子問題進行優化.相鄰權重系數所對應的解也具有相似性，根據這種相似性，可以為下一個種群粒子的初始化設定一個較小的范圍，相比于在整個空間隨機初始化種群縮小了搜索區域，提高了種群搜索最優解的速度.因此，當一個子種群完成對其優化問題的求解時，參考此前最優解初始化種群，粒子生成方式為

2.3 刪減策略

為了利于決策者的選擇，提高解集中解的代表性，需要對優化得到的最優解集進行篩選，以提高其分布的均勻性及收斂程度.以最小化問題為例，能夠使各目標值都取較小的點，將更容易支配其他的解也即更靠近理想前沿面，但對互不支配的2個解則較難判斷其優劣.對此，通過比較2個相似非支配解在各目標上整體的逼近程度加以刪減.對非支配解尤其是較為相似的2個解，可通過計算其歸一化后的各目標值的加權和進行篩減，具體描述如下：

將解集中各粒子按照歐式距離進行排序，對于相對距離小于閾值u的2個粒子，先分別將各目標值歸一化，然后計算其各目標上的加權和，即

則說明此時2個解相同，任意刪除一個．若

則第j個解優于第i個解，刪除第i個解．

基于目標加權和的判定方式，可以較好地對相似非支配解進行刪減，使最終得到的解集更佳逼近前沿面.對于擁擠區域的刪減，在一定程度上保證了分布的均勻性，同時，降低了決策者的選擇壓力.

2.4 算法實現流程

步驟1算法初始化，設定問題維數D，種群規模N1和N2以及2個種群各自的最大迭代次數，問題的函數評價次數，以及κ、u、G0、a、H．

步驟2對多目標問題的個數，選擇相應的幾組偏好權值系數（若目標個數為2，則選擇3組帶有偏好性的權值系數，若目標個數為3，則選擇4組帶有偏好性的權值系數）構成目標函數.

步驟3計算每個個體的適應度值，并求出其相應的慣性質量.

步驟4根據個體的慣性質量，求得每個個體所受的合力，進而求得其加速度.

步驟5判斷是否滿足終止條件，若不滿足轉到步驟3.

步驟6當完成對各組偏好權重系數構成的單目標函數的求解后，采用式2.1節描述的方法判斷前沿面的形狀.若前沿面形狀是凹的，則p=0.5；若前沿面形狀為凸的，則p=2；否則p=1，具體的權重系數生成方式如2.1節所示.

步驟7根據得到的一系列權重系數，按步驟3、步驟4進行優化搜索.

步驟8當滿足終止條件時，重新初始化新的子種群，初始化方式采用式（2）所示方式進行.

步驟9當達到最終的函數評價次數后，采用刪減策略對解集進行刪減，即將解集中各粒子按照歐式距離進行排序，對于相對距離小于閾值u的2個粒子，先分別將各目標值歸一化，然后計算并比較粒子各目標上的加權和，保留較優粒子.

步驟10輸出最終的解集.

3 仿真實驗與結果分析

所有實驗在硬件配置為Intel?CoreTM2 Duo CPU P7570 2.26 GHz、2 G內存、2.27 GHZ主頻的計算機上進行，開發環境為Matlab2 010.b.

3.1 測試問題

實驗選用二目標ZDT和三目標DTLZ兩個系列的多目標測試函數［8］，具體包括ZDT1、ZDT2、ZDT3、ZDT4、ZDT6、DTLZ1和DTLZ2等7個函數.這些測試函數具有理想前沿面形狀為凹形、凸形、不連續以及多模等特點，可驗證所提算法的有效性.

采用世代距離指標（generational distance metric，GD）和空間度量指標（spacing metric，SP）［9-10］兩種評價標準測試所提算法的性能.GD和SP的定義為

式中：N表示通過算法求得的解集中解的個數；di為求得的解集中第i個解到理想最優解集的最小歐幾里得距離；ˉd為算法求得所有解di的平均值．

GD的值越小，表明算法求得的解集與問題的理想最優解集越接近，算法收斂性越好.SP的值越小，表明算法求得的解集中的解分布的越均勻，算法的均勻性越好.

3.2 參數設置

實驗結果與目前解決多目標問題效果較好的NSGAII［11］，MOEA／D-AWA［7］，Adaptive-MOEA／D［12］和HMOEA［9］進行了比較，相關參數如表1所示.

選取的二目標偏好權重向量個數為3，即分別偏好2個目標的向量，以及任意選取的向量分別為（0.99，0.01）、（0.01，0.99）、（0.5，0.5）；選取的三目標偏好權重系數個數為4，即分別偏好3個目標的權重向量以及任意選取的一組向量，分別為（0.90，0.05，0.05）、（0.05，0.90，0.05）、（0.05，0.05，0.90）、（0.33，0.33，0.34）.

表1 參數設置

3.3 多子群串行搜索策略驗證

為驗證多子群串行搜索策略在解決多目標問題時的有效性，通過觀察算法對測試問題搜索的漸變過程進行實驗，驗證多子群策略的有效性.函數ZDT3具有前沿面不連續的特點，因此選取該函數作為實驗函數.實驗結果如圖4所示.

圖4 隨迭代得到解集的漸進變化趨勢

從圖4可以看出，隨著函數評價次數的不斷增加，所得到的解集逐漸遍布了整個理想前沿面，取得了較好的逼近效果，說明多子群串行搜索的有效性.圖中出現離散點，這是因為對子問題的搜索會產生一些非支配解，這些解對于當前子問題不是最優解但對于其他子問題來說則是最優解，體現了多種群串行搜索策略在優化多目標問題時，不會漏掉得到的較優解，具有較好的全局搜索性能.

3.4 刪減策略有效性驗證

為驗證刪減策略在解決多目標問題中的有效性，選取測試函數ZDT1進行驗證，實驗結果如圖5所示，指標SP和GD的對比如表2所示.

圖5 刪減前后算法所得前沿面對比

表2 解集在刪減前后的GD值和SP值

從圖5可以看出，在算法未對解集進行刪減時，所得到的前沿面存在較多被支配解，當對其進行刪減后，得到的解集則是由一群非支配解構成.由表2可以看出，采取刪減策略對解集進行刪減后，指標GD和SP均得到較大的提升，即得到的解集無論是收斂性還是均勻性均得到了提高，驗證了刪減策略的有效性.

3.5 求解性能對比

主要考察MOGSA／D算法與對比算法在標準測試函數上的性能比較，測試結果如表3及表4所示.其中表3給出各算法在優化各問題時所得GD指標的均值及方差，表4給出各算法在優化各測試問題時所得SP指標的均值及方差.

從表3中可以看出，對于ZDT1、ZDT2、ZDT3和ZDT4等4個測試函數，MOGSA／D算法在指標GD以及指標SP上都取得了優于其他對比算法的性能，也即收斂性以及分布性都是最好的；對函數ZDT6以及函數DTLZ2，MOGSA／D算法的GD是最小的，也即收斂性是最好的，分布性指標也僅次于MOEA／D-AWA；對函數DTLZ1，MOGSA／D算法在收斂性指標上沒有得到較好的效果，但分布性仍優于其他對比算法.綜合來看，在求解ZDT和DTLZ問題上，本文所提算法無論在收斂性、魯棒性還是分布性上均優于其他同類算法.

表3 各算法的GD值（第一行）及其標準差（第二行）

表4 各算法的SP值（第一行）及其標準差（第二行）

4 結 語

基于分解的多目標引力搜索算法MOGSA／D，通過對理想前沿面的估計，自適應選取與之匹配的權重系數生成方式；采用多子群串行搜索各子目標問題方法，為充分利用子問題的相似性，提出一種擾動生成新種群的策略；根據所得解集中粒子間的擁擠度，提出一種基于各目標加權和的方式刪減較劣解，以保證解集更均勻地逼近理想前沿面.通過對測試函數集ZDT和DTLZ上的實驗證明，MOGSA／D算法與現有的MOEAs相比，具有更好地收斂性及和分布的均勻性.

［1］HERNáNDEZ-DíAZA，SANTANA-QUINTERO L，COELLO COELLO C，et al.Pareto-adaptive∈-dominance［J］. Evolutionary Computation，2007，15（4）：493-517.

［2］郭思涵，龔小勝.正交設計的E占優策略求解高維多目標優化問題研究［J］.計算機科學，2012，39（2）：276-279，310.

［3］BADER J，ZITZLERE.HypE：an algorithm for fasthypervolumebased many-objective optimization［J］.Evolutionary Computation，2011，19（1）：45-76.

［4］LIHui，ZHANGQingfu.Multiobjective optimization problems with complicated pareto sets，MOEA／D and NSGA-II［J］. IEEE Transactions on Evolutionary Computation，2009，13（2）：284-302.

［5］RASHEDI E，SARYAZDI S.GSA：a gravitational search algorithm［J］.Information Sciences，2009，179（13）：2232-2248.

［6］WANG R，PURSHOUSE R C，FLEMING P J.Preferenceinspired co-evolutionary algorithm using weights for manyobjective optimization［C］／／Proceeding of the fifteenth Annual Conference Companion on Genetic and Evolutionary Computation Conference Companion.New York：ACM，2013：101-102.

［7］QIYutao，MA Xiaoliang，LIUFang，et al.MOEA／D with adaptive weightadjustment［J］.Evolutionary Computation，2014，22（2）：231-264

［8］TAN Yanyan，JIAO Yongchang，LIHong，etal.MOEA／D+ uniform design：a new version of MOEA／D for optimization problems with many objectives［J］.Computers＆Operations Research，2013，40（6）：1648-1660.

［9］TANG L，WANG X.A hybrid multiobjective evolutionary algorithm for multiobjective optimization problems［J］. IEEE Trans on Evolutionary Computation，2013，17（1）：20-45.

［10］SIMON D.Biogeography-based optimization［J］.IEEE Transactions on Evolutionary Computation，I2008，12（6）：702-713.

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

［12］SUCIU M，PALLEZ D，CREMENE M，et al.Adaptive MOEA／D for QoS-based web service composition［M］. Berlin：Springer，2013.

（編輯王小唯）

M ulti-objective gravitational search algorithm based on decom position

BIXiaojun1，DIAO Pengfei1，WANG Yanjiao2，XIAO Jing3
（1.College of Information and Communication Engineering，Harbin Engineering University，150001 Harbin，China；2.College of Information Engineering，Northeast Dianli University，132001 Jilin，Jilin，China；
3.Dept.of Information Engineering，Liaoning Provincial College of Communications，110122 Shenyang，China）

When the ideal frontier is discontinuous or inhomogeneous，the multi-objective evolutionary algorithm can’t solvemulti-objective problems effectively by decomposition.In order to improve this situation，a novelmultiobjective gravitational search algorithm based on decomposition（MOGSA／D）is proposed.In MOGSA／D，the multi-population serial strategy is good for the population study evolutionary information.According to shape prediction of ideal frontier，a suitable generation method of weight coefficient is selected.A pruning strategy is adopted to prune the solution set.Experimental results show that MOGSA has a good performance to solve multiobjective problems in comparison with othermulti-objective optimization algorithms.

gravitational search algorithm（GSA）；multi-objective optimization；decomposition；multi-population strategy

TP18

：A

：0367-6234（2015）11-0069-07

10.11918／j.issn.0367-6234.2015.11.012

2014-11-30.

國家自然科學基金（61175126）；中央高?；究蒲袠I務費專項資金（HEUCFZ1209）；高等學校博士學科點專項科研基金（20112304110009）.

畢曉君（1964—），女，教授，博士生導師.

畢曉君，398317196＠qq.com.