膜計算框架下的多目標煙花爆炸算法

毛宗楊，陳韜偉，余益民，趙 昆

(云南財經大學 信息學院, 昆明 650221)

優化問題是科研和工程實踐中常見的問題之一，按照目標函數的個數，可分為單目標優化和多目標優化。多目標優化問題(multi-objective optimization problems，MOPs)需要同時計算多個目標函數，這些目標函數之間通常是相互矛盾的，因此，存在一個折衷解的集合，稱為Pareto最優解集或非支配解集。

最初，多目標優化問題的解決方法是將多個目標函數加權轉化為單目標問題，采用數學規劃方法進行求解，但效率較低，且它們對于權值或目標次序難以科學地確定[1]。

膜計算也稱P系統，由Paun在1998年提出，并于2000年發表了第1篇相關論文[2]。 主要有以下幾種類型的P系統：細胞型P系統[3]、組織型P系統[4]和神經型P系統[5]。目前，膜計算理論框架已廣泛應用于計算機科學、語言學、經濟學和生物學等眾多領域。由于膜計算框架理論具有分布性、并行性、非確定性和可拓展性等特點[6]，它可引入上述的各種算法中實現進化計算、群智能計算與膜計算結合算法的新應用。Guo[7]利用膜系統的并行計算和分布式模型解決了SAT問題。Zhang等[8]將膜系統應用到GPU中，將GPU的串行方式改為并行方式。張群慧等[9]將粒子群算法引入膜系統中，并將其應用在云資源調度中從而提高了任務的處理效率。Sun等[10]將膜計算與PSO算法結合提出新算法MCBPSO,并用于處理復雜的優化問題。劉春秀等[11]將P系統與量子進化算法結合，并用于收集雷達輻射源信號。Lefticaru等[12]將膜系統與進化方法結合，拓展了膜計算的應用。Wang等[13]在膜計算的基礎上提出單閾值圖像分割技術，即利用膜計算的進化規則選取最優閾值。Pavel等[14]提出Enzymatic Numerical P系統，這是數值P系統的擴展。Song等[15]將信道狀態和反向運輸及通向轉移引入膜系統中。Pan等[16]用扁平膜系統最大并行度處理了SAT問題。Singh等[17]將粒子群優化規則與膜系統結合來處理Blasius微分方程。

總之，采用P系統與進化計算、群智能算法相結合求解近似優化算法是目前研究的一個方向。從研究的成果來看，與P系統結合的算法多數是針對單目標優化算法的求解，對于高維度的多目標優化問題的研究較少，仍需要進一步的研究。本文在前期研究的基礎上，將膜系統與煙花爆炸算法結合，提出了一種膜框架下的煙花爆炸算法。算法充分利用膜的分裂、合并等操作與基于煙花爆炸的尋優搜索方式相結合，能更好地平衡算法的局部開采和全局勘探的能力。在仿真實驗中，采用標準函數ZDT和DTLZ系列對提出的算法進行測試。結果表明：該算法所得的非支配解集更接近真實Pareto前沿，在多樣性、收斂性、準確性等方面優于或部分優于其他算法。

1 相關概念

1.1 多目標優化問題

多目標數學模型包括兩個部分：兩個及兩個以上的目標函數、約束條件。多目標優化的最小化描述為式(1)：

F(x)=min{f1(x),f2(x),…,fm(x)}

s.thj(x)≥0,j=1,2,…,p

gi(x)=0,i=1,2,…,q

(1)

式(1)中有n個決策變量；x=(x1,x2,…,xn)?Rn，Rn為n維決策空間；F(x)=Rm表示m維目標空間，目標函數F(x)定義了決策變量與目標空間的映射關系；gi(x)表示q個等式約束；hj(x)表示p個不等式約束。

定義1(可行解) 對任意x∈Rm，并滿足上式(1)中的約束條件，則稱x為可行解。

定義2(Pareto占優) 對滿足定義1的所有可行解組成的集合稱為可行解集合，并用X表示，則X?Rn；若存在兩個可行解分別為xa,xb∈X，xa與xb進行相比較，xa是Pareto占優的則滿足下面條件：

?i=1,2,…,m;fi(xa)

?j=1,2,…,m;fj(xa)≤fj(xb)

(2)

記作xa

定義3(Pareto最優解) 如果存在一個X*滿足：X*={x∈Rn|﹁ ?x′∈

定義4(Pareto前沿) 最優解集X*在目標函數空間上的映射，即：

PF=F(x*)=min{f1(x*),f2(x*),…,

fm(x*)|x*∈X*}

(3)

映射后的集合稱為Pareto前沿。

1.2 膜計算

膜計算(membrane computing)是從細胞的結構和功能以及組織或神經元中細胞的相互作用中抽象出來[18]。膜系統指由多個膜組成并且每層膜都是一個計算單元，所以膜系統有并行計算和分布式的特性。

膜系統由以下3部分組成：膜結構、對象多重集和反應規則[6]。用字符對象和多重集表示所求優化問題的可行解和可行解集。反應規則既有對膜結構的操作又有對字符對象的操作。本文采用細胞型的膜系統進行研究。細胞型膜系統的模型介紹如下：

∏={V,T,u,w1,w2,…,wn,R}

(4)

根據式(4)知：V為字母表，其中的元素為字符對象。細胞中分子和化學物質抽象為字符對象。T?V,T表示輸出字母表；u表示含有n個膜的膜結構，n為膜系統Π的度；wi∈V*，i=1,2,…,m，wi表示u中第i個膜內包含字符對象的多重集，V*為V中字符對象組成的字符多重集；R為進化規則的有限集合，Ri,i=1,2,…,m,為膜結構u中第i區域的進化規則。

細胞型膜系統的結構如圖1所示，圖中最外層的膜為表層膜，用于將細胞外和細胞膜的內部結構分隔開。每個膜都有一個確定的區域，每個區域中反映規則和多重集。若某個區域中不包含膜，稱為基本膜。

圖1 細胞型的膜系統結構

1.3 精英反向學習

反向學習(opposition based learning)由Tizhoosh提出，在全局最優的問題上反向解比當前解更接近最優解。反向學習是在個體當前所在的區域產生反向個體，同時將當前個體與反向個體一同競爭，競爭后產生的個體進入下一代。

定義6(反向解優化) 假設優化問題為公式(1)中最小化優化問題，假設存在一個當前解X，設X′為其反向解，則更新機制如下：如果XX′，則保留X′。如果X和X′彼此間非支配，則隨機選擇X或X′進行保留。

在多目標優化問題中一般將非支配解稱為精英個體，精英個體中包含許多將種群向最優Pareto前沿收斂的信息。加強對精英個體所在區域的搜索會使算法的收斂速度和全局搜索能力得到改善。

1.4 煙花爆炸算法

1.4.1 煙花爆炸算法的優化機制

煙花爆炸算法(fireworks algorithm，FWA)是模擬現實生活中煙花爆炸的現象，將煙花爆炸的空間看成優化問題的搜索空間，用爆炸點和爆炸點爆炸產生火花的位置來表示優化問題的解。根據已有的火花和爆炸點進行選擇，使相對較理想的火花位置保留下來，不停迭代直至得到滿意結果。

煙花爆炸算法具有全局搜索和局部搜索能力。每個火星產生的爆炸半徑和火星的個數是不同的，如果煙花的適應度值較好(適應度值較小)則在較小的范圍內產生較多的火星因此具有開采性，反之在較大的范圍內產生較少的火花因此具有勘探性。

*(rinit-rend)+rend

(5)

(6)

如果搜索空間是低維度，選擇坐標軸為爆炸方向，假設為n維(n<10)，那么爆炸的方向為2n個。如果搜索空間是高維度，繼續用2n個爆炸方向，此時會消耗大量的空間，所以每層爆炸方向采用從2n個方向中隨機選n/3個方向同時再加上這n/3個方向的相反方向。以二維的搜索空間為例，如圖2所示，其中圓心處黑點表示爆炸點，坐標軸上的圓圈表示火星。

圖2 二維空間爆炸點的方式

對火星和爆炸點的邊界進行限制設xi(i=1,2,…,n)為搜索空間中的決策變量，并且xi屬于[ai,bi]，如果有火星xj超出邊界[ai,bj]，則要將xj在第i維上的值重置，火星的重置有利于火星多樣性的提高，重置方式如(7)所示。

(7)

rand( )是[ai,bj]中的均勻隨機數。

1.4.2 選擇火星

從第二代開始將會產生大量火星，將火星和爆炸點一起進行選擇，選出較優的火星進行下一次爆炸。為保持火星多樣性和種群的規模采用基于距離的方式進行篩選。設xi屬于m,m是爆炸點和火星的集合，xi與m中其他元素的距離之和如式(8)所示。

(8)

選中xi的概率為P(xi),如式(9)所示。

(9)

對p(x)進行降序排序，選擇排序較前的個體。

綜上所述，因為膜系統是由多個膜組成，每層膜都是一個計算單元，所以膜系統有并行計算和分布式的特性。而煙花爆炸算法在求解優化問題時具有隨機性、局部性、爆發性、隱并行性、多樣性和瞬時性等特點，滿足在某一范圍內的解和其鄰域解擁有相似的性質。因此，將膜框架與煙花爆炸算法結合對求解優化問題是可行的。在基本膜中，煙花的種群中所有的煙花根據適應度值進行信息的交互和資源的分配，增加了種群的多樣性，克服算法早熟收斂。最后，在表層膜中的精英反向學習的應用，反向解比當前的解更接近全局最優，有利于多目標優化問題的求解。

2 膜計算框架下的煙花爆炸算法

用外部檔案來存放最優字符對象，為確保外部檔案內字符對象的多樣性和整體數量的穩定，引入精英反向學習和NSGA-Ⅱ算法中的擁擠距離與非支配排序。

擁擠距離指在相同的非支配等級中兩字符對象的距離，如式(10)所示。

(10)

通過式(10)計算完擁擠距離之后對字符對象進行擁擠距離排序，即將字符對象通過擁擠距離進行降序排序。

基于膜框架下的煙花爆炸算法的具體步驟如圖3所示。

圖3 算法執行流程

設搜索空間為m維，目標數目為n，字符對象規模為N，外部檔案的容量為M。則煙花爆炸算法的時間復雜度如下：

步驟1 在優化問題的約束條件得到滿足的基礎上，對字符對象進行初始化(初始化時間復雜度為O(mN))，即在表層膜內隨機生成N個字符對象，并且用十進制對字符對象進行編碼，描述形式如(式11)所示。

(11)

步驟2 對目標算法的每個字符對象進行計算，求出適應度值并根據適應度值確定火星質量的好壞。適應度值好的獲取的資源相對多；相反，適應度值差的獲取資源少。

步驟3 初始化操作后，在表膜的內部使用分裂規則，分裂出M個基本膜，將初始化后的M個多重集發送到M個基本膜內。使用并行膜結構的形式如式(12)所示。

[ ]0→[ [ ]1, [ ]2, …, [ ]m]

(12)

其中：M為基本膜層數；[ ]0為表膜；[ ]m為第m個基本膜。

為使每個基本膜都有與其對應的多重集，需要對多重集對象進行劃分，首先需求出各字符對象的適應度，并進行非支配排序，然后將排序好的多重集分成等大小的子集。具體操作見式(13)。

w*=sort(w)

w*={w1,w2,…,wm}

n=sizeof(w)/m

(13)

式中：w為多重集；sort( )為對w進行非支配排序；wi為多重集的第i個子集；sizeof(w)為多重集內字符對象的個數；n為每個基本膜內字符對象的個數。

步驟4 利用通信規則將表層膜內的多重集發送給基本膜。利用選擇規則依據擁擠距離選擇字符對象，擁擠距離與非支配排序的引入提高了算法的局部搜索能力。

步驟5 在基本膜內執行煙花爆炸算法實現字符對象的重寫規則。通過爆炸半徑計算方式(5)，爆炸點i產生火星的迭代公式(6)等對基本膜內的字符對象進行操作(一個爆炸點爆炸產生火星的時間復雜度為O(8n2/3),N個爆炸點產生火星的時間復雜度為O(8Nn2/3))。

步驟6 以上操作完成后調用溶解規則，當m個基本膜溶解后基本膜中的多重集全部進入表層膜中。并將字符對象放入外部檔案中，然后將字符對象進行精英反向學習(運行精英反向學習的時間復雜度為O(nM))，最后將表層膜和外部檔案中的字符對象進行非支配排序(外部檔案多樣性維護的時間復雜度為O(n(N+M)2log(N+M))，將非支配等級小的字符對象重新組合作為下一代多重集(產生下一代字符對象的時間復雜度為O(mN2))。

步驟7 外部檔案使算法能快速地收斂到真實的目標前沿，外部檔案中引入精英反向學習增強了算法全局搜索能力，因此該算法跳出局部極值的能力得到了提高。外部檔案實現如下：① 對字符對象進行擁擠距離和非支配排序操作；② 根據結果選取非支配等級相對較低的字符對象，若存在兩字符對象非支配等級相等，則比較兩字符對象的擁擠距離，選擇擁擠距離相對較大的對象；③ 通過以上操作，將選取的字符對象放入外部檔案內，然后將字符對象進行精英反向學習，最后刪除檔案中受支配的字符對象將外部檔案中剩余的字符對象作為下一代多重集。

步驟8 若不滿足終止條件，從步驟2開始繼續執行；若滿足條件，算法結束，將表層膜內的多重集輸出。

3 仿真實驗

3.1 實驗設置

1) 多目標優化算法及測試函數

為測試膜框架下煙花爆炸算法的性能選取6個多目標優化函數與其進行對比，分別為：GrEA、IBEA、MOMB-Ⅲ、NSGA-Ⅱ、NSGA-Ⅲ和SPEA-Ⅱ。測試函數采用ZDT和DTLZ系列的函數，ZDT系列的函數為：ZDT1、ZDT2和ZDT3，DTLZ系列的函數為：DTLZ1、DTLZ3和DTLZ7。

2) 參數設置

根據文獻[19]將煙花爆炸算法的半徑遞減指數α設為5，算法的初始爆炸半徑rinit=a*(xi,max-xi,min)，a∈[0.05,0.3]，rend的值為10-6。論文的膜系統由5層膜組成。

進行比較實驗時各多目標優化算法在兩個目標的測試函數中將外部檔案的容量M=100,字符對象設置為N=100，算法的迭代次數為1 000；3個目標的測試函數外部檔案的容量M=100,字符對象設置為N=100，算法的最大迭代次數為10 000。

仿真實驗在聯想天逸310筆記本上運行，使用Windows 10 X64 操作系統，4 G內存，2.4 GHz雙核CPU，算法用Matlab實現。

3) 性能指標

本文用反轉世代距離(inverted generational distance，IGD)的方法對算法性能進行評估。IGD是度量算法獲取的近似Pareto前沿與真實Pareto前沿之間的距離。IGD的值越低，說明算法的多樣性和收斂性越好。IGD的表達式如式(14)所示：

(14)

3.2 實驗結果分析

多目標優化算法在兩個目標的測試函數(ZDT1、ZDT2和ZDT3)下運行的結果分別如圖4～6所示。

圖4 基于ZDT1測試函數分布

圖5 基于ZDT2測試函數分布

圖6 基于ZDT3測試函數分布

圖4為各多目標優化函數在測試函數ZDT1下的運行結果，圖中黑線為真實Pareto前沿，從圖4可以看出FWA算法更接近真實Pareto前沿，其他算法的效果相對比較差。圖5為ZDT2測試函數下不同算法的測試結果，相對于NSGAⅢ算法，其他算法比較逼近真實Pareto前沿，效果最好的是FWA算法。圖6為ZDT3測試函數下不同算法的分布情況效果，比較理想的是FWA算法。

煙花爆炸算法在3個目標的測試函數DTLZ1、DTLZ3和DTLZ7下的測試結果如圖7所示。

對7個多目標優化算法在6個測試函數下IGD的平均值(mean)、標準差(std.)的比較如表1所示，圖中粗體字表示在相同測試函數下IGD最小的值。

由表1可以得出：在相同測試函數下膜框架下的煙花爆炸算法比其他算法的IGD值都小，因此該算法比其他算法更占優。

因為IGD能同時反映一個算法的多樣性和收斂性，本文提出算法與其他算法對比顯示出較好的多樣性和收斂性，說明煙花爆炸算法與膜系統結合較好地平衡了煙花算法的開采和勘探過程。

圖7 基于3個目標測試函數分布

測試函數GrEAMeanStd.IBEAMeanStd.MOMB-IIIMeanStd.NSGA-IIMeanStd.NSGA-IIIMeanStd.SPEA-IIMeanStd.FWAMeanStd.ZDT12.32×10-18.63×10-13.37×10-11.24×10-12.86×10-19.14×10-22.88×10-13.40×10-15.49×10-11.50×10-12.32×10-14.08×10-12.87×10-23.97×10-2ZDT22.75×10-11.22×10-14.52×10-12.57×10-23.40×10-11.33×10-13.23×10-18.21×10-15.71×10-19.98×10-23.07×10-18.20×10-23.01×10-23.08×10-2ZDT31.02×10-13.01×10-24.12×10-11.47×10-11.99×10-11.15×10-11.45×10-11.06×10-13.90×10-11.08×10-11.35×10-18.70×10-28.03×10-28.44×10-2DTLZ12.63×10-11.29×10-12.12×10-18.33×10-21.94×10-11.54×10-14.02×10-17.88×10-34.58×10-13.16×10-12.30×10-12.94×10-17.80×10-28.92×10-2DTLZ35.61×10-02.12×10-04.50×10-01.76×10-06.16×10-02.06×10-04.26×10-03.06×10-08.19×10-02.55×10-04.18×10-02.64×10-03.54×10-14.19×10-1DTLZ72.26×10-24.77×10-42.79×10-22.56×10-32.54×10-21.98×10-25.94×10-33.20×10-41.87×10-26.68×10-34.15×10-21.38×10-31.53×10-33.32×10-4

論文給出7種多目標優化算法在6種測試函數下的均值和方差排名情況，如圖8所示。

圖8 IGD均值和方差

圖8顯示結果可以看出：膜框架下的煙花爆炸算法在方差排名及均值排名相對于其他優化算法比較占優。這表明膜框架下的煙花爆炸算法相對于其他優化算法有較好的穩定性和準確性。

因為IGD能反映一個算法的多樣性和收斂性，故采用IGD排名的方差和均值來比較各算法的穩定性與準確性。因此，由表1和圖8可以得出：膜框架下煙花爆炸算法的多樣性、收斂性、穩定性和準確性均優于其他多目標優化算法。

4 結束語

為了更好地解決生活中復雜的多目標優化問題，本文將膜系統與煙花爆炸算法結合，同時在外部檔案中應用精英反向學習的方法。文中將該算法與其他6種多目標優化算法在6種測試函數上進行測試并得出IGD的值。實驗表明：膜框架下的煙花爆炸算法相對于其他優化算法有顯著的穩定性、準確性和收斂性，說明煙花爆炸算法與膜系統結合能有效地解決多目標優化問題。