關聯變量分組的分解多目標進化算法及其應用

邱飛岳,胡 烜,王麗萍

1(浙江工業大學 信息工程學院,杭州 310023) 2(浙江工業大學 現代教育技術研究所,杭州 310023) 3(浙江工業大學 信息智能與決策優化研究所,杭州 310023) E-mail:qfy@zjut.edu.cn

1 引 言

多目標優化問題(Multi-objective Optimization Problem,MOP)是同時包含矛盾和沖突目標的一類復雜優化問題,其對應的解集往往是一組折衷解的集合.多目標進化算法(Multi-objective Evolutionary Algorithms,MOEA)以其隨機并行搜索的性質而適合于求解MOP.但隨著優化問題中決策變量個數的增加,MOEA的優化性能逐漸下降.究其原因,在于當前的MOEA將所有的決策變量視為一個整體進行優化,而當所求問題中決策變量個數增加時,種群中非支配解的比例將增大,算法在進化過程中面臨選擇壓力不足的困境,從而加大了問題的求解難度[1].

為解決這一問題,現有學者受到協同進化(Cooperative Coevolution)[2]的啟發,提出決策變量分解的策略,通過將高維決策變量分解為簡單低維的變量組來協同優化,從而有效提高算法的求解效率.但是這種“分而治之”策略存在的主要困難在于如何選擇一種較好的分解方法來使不同子問題間的關聯性最小.Yang[3]為此提出了多級協同進化(Multilevel Cooperative Coevolution,MLCC)框架,通過對決策變量進行隨機分組的方式來提高關聯變量被分到同組中的概率.Omidvar[4]提出了高頻率隨機分組策略,通過保證決策變量分組的隨機性來降低各分組間的依賴程度.雖然該分組策略在分組的初始階段較好地緩解了關聯變量對算法性能的影響,但隨著決策變量個數的增加,使用隨機分組來將關聯變量分到同組中的概率將大大降低,這就要求對決策變量進行更為頻繁的分組,因而大大增加了算法的計算復雜度.Omidvar[5]又提出了delta分組策略來優化每一維變量的改變值并以此確定分組方式.當優化問題中含有關聯變量時,該分組策略能在一定程度上緩解關聯變量對算法解集的影響.Mahdavi[6]則提出了基于高維模型表示(High Dimensional Model Representation,HDMR)的分解策略來識別決策變量間的關聯信息以實現變量分組的目的.該算法能夠較好地維護變量間的關聯性,并提高了對大規模變量優化問題的求解能力,但未充分考慮在算法求解過程中各子問題貢獻程度的大小,由此影響了算法的計算效率.Omidvar[7]還提出了一種差分分組的策略來自動判斷決策變量間的關聯性,它能較好地挖掘變量間的關聯信息并以此進行分組.在此基礎上,Mei[8]提出了一種競爭分治算法來解決大規模變量優化問題.該算法采用全局差分分組的方式來識別相互獨立的子問題并進行優化求解.雖然差分分組能較好地解決關聯變量的分組問題,但該策略要求在運行優化算法前必須對決策變量進行逐個篩選以找出關聯變量并進行分組,這無疑會導致算法復雜度將隨著變量個數的增加而急劇上升,所以不適于復雜大變量問題的求解.最近,Ge[9]在協同進化的基礎上設計出一種快速搜索算子來捕獲決策變量之間的關聯性并據此進行問題的分解,同時利用跨簇變異策略來進一步提高算法的優化性能.上述算法大多用來解決大變量的單目標優化問題,還未應用于MOP中.而Antonio[10]首次將隨機分組策略應用于大規模變量的多目標問題中,但由于缺乏考慮決策變量之間的關聯性,導致很難將關聯變量分到同一組中,因此該算法無法深入挖掘變量間的內在信息,從而影響算法性能.

解決大規模變量問題的關鍵就在于尋找決策變量之間的關聯性.Salomon[11]的研究表明決策變量間的關聯性可以顯著影響算法在連續域上的優化性能.研究表明大規模變量優化問題中的決策變量間存在一定的關聯性.當變量規模增加時,變量間的關聯性也會隨之加強.根據決策變量間的關聯性來對變量進行分解,使關聯變量盡可能地被分到同一組中,將大規模變量問題轉換為低維子問題來協同求解,可以最大程度地保證所求解集的質量.

針對實際生活中的大規模變量優化問題,本文結合變量間關聯性分析和分組優化的思想提出一種新的關聯變量分組機制,并結合分解的多目標進化算法(MOEA/D)[12],形成一種關聯變量分組的分解多目標進化算法(MOEAD/IVG)來處理大規模變量的MOP.MOEAD/IVG通過對決策變量進行關聯性分析,將其分解為相互之間關聯性最小的低維變量組,并各自獨立優化每個變量組所對應的子問題,從而獲得最佳的全局最優解.將該算法應用于通信系統中多目標功率優化控制問題,實驗結果表明該算法與其他MOEA相比,具有一定優勢,能更好地搜索變量間的關聯性,并有效地提高了求解效率,進而優化了算法的整體性能.

2 背 景

2.1 多目標優化的概念

不失一般性,MOP均以最小化為例,最大化問題可通過簡單的方式轉換為最小化問題.對于由n個決策變量和m個目標函數所構成的最優化問題,模型如下[13]:

(1)

其中,F(x):Ω→Rm由m個需同時優化的實值連續函數組成.Ω為決策空間中的可行域.x=(x1,x2,…,xn)為在可行域Ω中的決策向量.

如果?i∈{1,…,m},fi(xu)≤fi(xv),F(xu)≠F(xv),說明決策向量xu支配xv(表示為xuxv).此外,當?i∈{1,…,m},fi(xu)

2.2 關聯變量定義和分析

在遺傳學中,如果兩個基因共同影響生物的特性,則稱這兩個基因是相互關聯的.研究表明,在大規模變量問題中不同變量間也存在著類似的關聯性.當一個變量改變并導致另一個變量也隨之改變時,將這類變量稱為不可分離變量,即關聯變量.反之,如果變量之間是相互獨立的,即某個變量的改變不影響其他變量,則稱之為可分離變量[7].下面給出關聯變量的數學定義.

定義1.兩個決策變量xi和xj是相互關聯的當且僅當存在x,a1,a2,b1和b2使下式成立[14].

f(x)|xi=a2,xj=b1f(x)|xi=a2,xj=b2>f(x)|xi=a1,xj=b2

(2)

其中,f(x)|xi=a2,xj=b1f(x1,…,xi-1,a2,…,xj-1,b1,…,xn).同時,對于如何識別關聯變量存在以下判斷準則.

定理1.f(x)為連續可微函數,若兩個決策變量xi和xj相互關聯,則?x,a1,a2,b1和b2滿足下式[7]:

f(x)|xi=a2,xj=b1-f(x)|xi=a1,xj=b1
≠f(x)|xi=a2,xj=b2-f(x)|xi=a1,xj=b2

(3)

3 關聯變量分組的分解多目標進化算法(MOEAD/IVG)

為有效地求解大規模變量優化問題,根據決策變量之間的關聯性來對變量進行分組是一種行之有效的方法.含有大變量的MOP中的決策變量往往具有一定的關聯性.當MOP中變量個數增多時,關聯變量也會隨之增加.如果忽視決策變量間的這種內在聯系而隨意進行變量分解,則會使分組得到的子問題之間存在依賴性,進而降低子問題最優解的質量,并最終影響全局最優解.因此,為了將關聯變量從全局變量中區分出來并使之盡可能地被分到同一組中,本文提出一種關聯變量分組的分解多目標進化算法(MOEAD/IVG),其中該算法中的關聯變量分組策略介紹如下.

3.1 關聯變量分組策略

關聯變量分組的作用在于能根據決策變量間關聯程度的大小將相互之間具有一定關聯性的變量分到同一組,而將各自獨立且不相關的變量分到一組,從而使高維變量優化問題被分解為一組簡單低維的子問題,最終通過分別優化各子問題來求目標函數的最優解.本文采用公式(2)和公式(3)來判斷決策變量間的關聯性.其中關于兩個決策變量間的關聯性識別和分組優化的步驟如下:

步驟1.在種群中隨機選出一個個體進行關聯變量的識別和分組,利用公式(3)對變量間的關聯程度進行判斷.

步驟2.求出不同目標函數下Δ的最大值.對變量之間的關聯性做如下判斷:如果Δ大于一個充分小的數ε,則表明兩個變量之間存在著一定的關聯性并將它們分到同一組中;否則,則說明兩者之間相互獨立.

步驟3.不斷重復上述過程直到將所有的關聯變量都進行識別和分組.

以上關聯變量分組的目的是為了充分檢測決策變量間的內在聯系,將關聯變量盡可能地分到同一組中,降低分組后子問題間的依賴性.關聯變量分組的流程見算法1.

算法1.關聯變量分組策略

1.fori= 1 tondo

2. randomly select an individualxlfrom the population and use the formula (3) to determine the relationship between variables.

3.fork= 1 tomdo

4. Δfk1|xj=b1←fk(xl)|xi=a2,xj=b1-fk(xl)|xi=a1,xj=b1

5. Δfk2|xj=b2←fk(xl)|xi=a2,xj=b2-fk(xl)|xi=a1,xj=b2

6. Δ=|Δfk1-Δfk2|

7.endfor

8. calculate the maximum value of the Δ.

9.ifΔ>εthen

10. detect the interaction between the variables and group the interacting variables into common subcomponents.

11.endif

12.endfor

3.2 MOEAD/IVG算法流程

MOEAD/IVG將關聯變量分組機制融入到MOEA/D中,其主要步驟分為以下兩個方面:決策變量分組過程和分組優化階段.在變量分組過程中,通過識別決策變量中潛在的關聯信息從而將關聯變量分到同一組中,由此形成的各個子集分別包含各自相關的決策變量,從而最大可能地降低了子集間的依賴性,提高了全局最優解的質量.在算法的分組優化過程中,利用MOEA/D來分別優化分組后所形成的各個子問題,最終獲得目標函數的全局最優解.MOEAD/IVG的步驟如下:

步驟1.設置初始參數,設定種群大小N和最大進化代數T,初始化父種群.

步驟2.對父種群進行交叉和變異操作產生子種群.

步驟3.結合父種群和子種群,根據算法1對混合種群進行關聯變量識別和分組操作.

步驟4.利用MOEA/D來對關聯變量分組后所產生的各個子問題進行優化求解.

步驟5.判斷是否達到最大進化代數,若是,則根據優化分組后各子問題的最優解來得到全局最優解并輸出;否則轉步驟3.

在MOEAD/IVG中,利用關聯變量分組和基于聚合函數分解策略來協同合作求解MOP.該算法首先通過關聯變量分組策略來將大規模變量的復雜優化問題分解為一系列簡單低維變量的子問題,然后利用MOEA/D來逐一協同優化分組后所得到的子問題.這樣就可以同時優化一組關聯變量而不是所有的變量,并以此來有效地求解全局最優解.

4 多目標優化的功率控制設計

4.1 問題描述

在現代移動通信系統中,無線資源管理的核心是追求資源的最優分配,同時確保每一個連接用戶的服務質量(Quality of Service,QoS).功率控制是干擾受限的通信系統的基本環節,其目的是控制用戶的傳輸功率盡可能地接近最優,通常我們把達到用戶指定QoS指標的最小功率當作最優傳輸功率的標準.功率控制可以降低用戶間的相互干擾,同時還可以增加系統容量.功率控制從20世紀90年代年被提出以來,得到了國內外廣泛的研究.迄今為止的大多數功率控制算法都是考慮在一定QoS的條件下,通過設置信號與干擾加噪聲比(Signal to Interference plus Noise Ratio,SINR)的下限值來達到各用戶傳輸功率之和最小的目的.在功率控制算法中我們需要優化不同的目標函數,比如數據傳輸速率、系統中斷概率、用戶傳輸功率等,但這些目標函數往往是相互矛盾的.傳統的功率控制算法采用聯合優化的方式來解決上述問題,即基于優化一個目標而將其他目標當作限制條件來處理.而MOEA則能較好地求出相互矛盾目標下的最優解,Elmusrati據此將用戶傳輸功率和QoS需求作為兩個不同的目標,將功率控制轉化為MOP,并在多目標優化理論的基礎上成功提出一種新的功率控制算法[15].這種新穎的建模方式無疑對無線資源調度具有巨大的啟發和重要的應用意義.基于此,本文就通過將通信系統中的功率控制問題建模為兩目標的優化問題,并采用MOEAD/IVG來解決各用戶傳輸上的功率分配.該功率控制的系統模型如下所述.

4.2 系統模型

系統環境為由N個用戶所構成的單小區多用戶蜂窩通信系統,用戶i(i∈N)與基站之間的距離為di,pi表示第i個用戶的發射功率.為簡單起見,我們只考慮某種單一業務,且對于此類業務,預先設定目標SINRγtar與最小SINRγmin,在終端處達不到此最小值時,則認為該用戶不被系統所服務.SINR的表達式可以表示為[16]:

(4)

其中,Gi表示第i個用戶與基站之間的信道增益,cij表示用戶i與用戶j所用擴頻碼的碼相關系數,基站的背景噪聲功率則用σ2表示.信道增益的示意圖如圖1所示.

圖1 小區示意圖Fig.1 Example of a cell

在圖1中,BS表示小區中的基站,且基站使用全向天線并位于小區的中心.MS表示小區中的移動臺.信道增益Gi可由如下公式計算得到:

(5)

其中,A為一常數,α∈(3,6),并忽略信道中快衰落和陰影衰落的影響.

在建模功率優化控制問題時,主要考慮以下兩個目標:使系統終端的傳輸功率之和最小以及盡量使各終端的接收SINR接近γtar.以上這兩個目標在功率控制問題中是十分常見且極具代表性的,從公式(4)中可以看出這兩目標之間是相互矛盾的,即當降低各用戶的傳輸功率時會導致SINR的降低.因此如何在這兩個相互矛盾的目標中取得平衡,既使得系統終端的傳輸功率能夠最小,同時又能最大程度地提高通信系統的系統容量就成為了當前功率控制問題中研究的重點.本文通過MOEAD/IVG來解決上述問題,使得在最終求得的功率分配條件下,系統中各終端的SINR大于γmin,且盡可能地接近γtar,同時盡量降低各用戶的發射功率,從而增加系統容量.

4.3 數學函數優化模型

根據4.2節中功率優化控制的兩個研究目標,提出如下的功率控制數學模型:

(6)

(7)

(8)

(9)

對應上述這兩個相互矛盾的目標,傳統的功率控制算法很難為分布在各處的移動終端找到一種最優的解決方案.為了有效地解決該問題,本文采用基于多目標優化理論的MOEAD/IVG來求解.為了能夠將功率優化控制問題應用到MOEAD/IVG中,首先應明確各用戶終端的功率與算法中變量之間的關系,并將功率控制問題映射到算法中.進化算法以染色體為單位來進化搜尋問題的最優解.在實驗中設定種群規模大小為N,即種群是由N條染色體所構成.將通信系統中各用戶終端的發射功率映射到染色體上,即每個用戶的發射功率對應染色體中的各個基因,由所有用戶發射功率映射的基因就構成了染色體.

5 仿真實驗

5.1 參數設置

5.2 Pareto前沿對比分析

仿真實驗得到的Pareto前沿對比圖如圖2所示.其中,圖2仿真了在用戶終端個數為100,200和300的情況下,各算法得到的用戶傳輸功率和終端接收SINR與目標SINR之差的優化目標函數的Pareto前沿對比圖.

圖2 在不同用戶終端下優化目標函數的Pareto前沿對比圖Fig.2 Pareto front comparison chart of the optimization objective function under different user terminals

圖2清楚地表明當用戶傳輸功率之和取到最小值時,終端接收SINR與目標SINR偏差量達到最大;當傳輸功率之和最大時,終端接收SINR與目標SINR偏差量達到最小,表明這兩個優化目標之間是彼此矛盾并存在相互沖突,兩者是無法同時取到最優值,而只能在兩個目標之間按照決策者的需求來合理地選擇折衷解.從圖2可以看出在這五種進化算法的對比中,MOEAD/IVG得到的解集的整體質量最好,其次是RVEA和MOEA/D,而MOPSO和NSGA-II得到的解集質量較差.另外隨著優化問題中決策變量個數的增加,由RVEA、MOEA/D、 MOPSO以及NSGA-II求得的前沿逐漸惡化,而MOEAD/IVG得到的Pareto前沿無論在收斂性還是多樣性上都保持較好的性能,其得到的解集質量都要顯著優于其他算法.在實際生活中,決策者可從MOEAD/IVG所求解集中任選一個作為最終移動用戶終端功率設計的方案,或者進一步根據多目標決策方法來確定合適的最優解.

5.3 算法性能對比

為了進一步說明MOEAD/IVG在求解大規模變量優化問題中的收斂特性.以上一節的功率控制模型為例,比較了在不同移動用戶終端的情況下,系統中所有用戶在各進化算法迭代過程中平均發射功率的變化情況,實驗結果如圖3所示.在圖3中,橫坐標代表算法進化代數,縱坐標代表所有用戶的平均發射功率.

圖3 各算法進化迭代時用戶終端平均功率的變化情況Fig.3 Changes of average power of the user terminal in the evolutionary iteration of each algorithm

從圖3中可以發現,隨著算法進化代數的增加,所有用戶的平均功率會逐漸收斂到不同的功率值以保證通信需求.在用戶終端分別為100,200和300的情況下,MOEAD/IVG均收斂到最小的平均功率,REVA和MOEA/D次之,而MOPSO和NSGA-II收斂到的功率值最大.MOEAD/IVG及MOEA/D在求解時迭代到大約50代就開始趨于平緩,但MOEAD/IVG比MOEA/D收斂到的平均功率要小.而MOPSO和NSGA-II求解時會在進化迭代中出現明顯的波動,表明這兩種算法的收斂特性較差.圖3進一步說明了MOEAD/IVG在功率優化控制模型中求得的各用戶發射功率分配方案更節省終端功率,能夠在保證QoS要求,即SINR值不低于γmin的情況下,有效地降低傳輸功率并大大減小對其他用戶造成的干擾.

上述實驗結果表明,MOEAD/IVG與其他算法相比,在求解大變量優化問題時,通過關聯變量識別和分組策略可以有效地提高求解的收斂速度并使算法具有較好的收斂性能.

為了進一步說明MOEAD/IVG在求解大規模變量優化問題中的有效性.仿真了各算法求得的所有用戶平均功率隨移動終端個數的變化情況,實驗結果如圖4所示.橫坐標代表移動用戶終端的個數,縱坐標代表所有用戶的平均功率大小.

由公式(4)可以看出,用戶終端數目的不斷增加會逐漸導致系統中每個用戶干擾的增強,因此,用戶為了保證QoS都會不同程度地提高發射功率,這與圖4的仿真結果相一致.功率控制模型中各移動終端為了追求QoS而調整發射功率,但發射功率的增加必定會增大干擾.從圖4中可以看到,當系統中移動用戶終端個數為100時,這五種算法求得的各用戶平均發射功率都較小.但隨著用戶個數的增加,各算法求得的平均發射功率均有所增加,但由 MOEAD/IVG 所求的平均功求的性能表現上更為優越.實驗結果表明通過識別關聯變量和恰當的分組策略可以有效地解決大規模變量優化問題,MOEAD/IVG能夠在一定程度上提高所求解集的質量和算法的整體性能.為了更加客觀地體現MOEAD/IVG的優越性,本文將通過加法二進制ε指標值和算法運行效率這兩方面對算法的綜合性能進行對比.

圖4 各算法隨用戶數增加的性能比較Fig.4 Performance comparison of each algorithm for different numbers of users

率要比其他四種算法增長得慢,且獲得的解要更小.綜合系統功率資源消耗的表現,MOEAD/IVG性能最佳,RVEA和MOEA/D次之,而MOPSO和NSGA-II的表現相對較差,說明MOEAD/IVG在平衡系統功率資源消耗和各終端QoS要

5.4 解集質量對比

加法二進制ε指標[20]是由Zitzler提出用來比較兩個解集的優劣程度.在加法二進制ε指標中,任給兩個解集A和B,將其作為輸入可得到一對輸出(IA,IB),其中,

表1 加法二進制ε指標對比
Table 1 Comparison of additive binaryε-indicator

加法二進制ε指標用戶個數MOEAD/IVG與RVEAMOEAD/IVG與MOEA/DMOEAD/IVG與MOPSOMOEAD/IVG與NSGA-III(G,R)I(R,G)I(G,D)I(D,G)I(G,M)I(M,G)I(G,N)I(N,G)優化函數100-0.1334630.050219-0.2867710.078699-0.4791010.190764-0.5874030.389546200-0.2215690.053618-0.3883960.131058-0.8149430.370099-1.2006300.663007300-0.2828080.063886-0.4132850.273403-0.9669710.609016-1.4255500.954615

在對比實驗中,本文用字母G,R,D,M和N來分別代表5種算法MOEAD/IVG,RVEA,MOEA/D,MOPSO和NSGA-II所產生的解集.加法二進制ε指標值見表1.從表1中可以清楚地發現,在MOEAD/IVG與RVEA的對比中,當用戶終端個數分別為100,200和300時,均有I(G,R)<0,I(R,G)>0,表明在所有情況下MOEAD/IVG所求得的解集均嚴格優于RVEA.同理,當MOEAD/IVG分別跟MOEA/D、MOPSO和NSGA-II進行對比時,均有I(G,D)<0,I(D,G)>0;I(G,M)<0,I(M,G)>0以及I(G,N)<0,I(N,G)>0,說明MOEAD/IVG在所有情況下所求解集均嚴格優于MOEA/D、MOPSO和NSGA-II.綜上,由加法二進制ε指標值的對比結果可以得出MOEAD/IVG產生的解集整體上更優.實驗結果表明在求解大規模變量問題時,在MOEA/D中引入關聯變量識別和分組策略是成功的,可以顯著提高算法在大變量問題優化時的求解性能.

5.5 算法運行效率對比

為了比較各算法的運行效率,本文統計了20次五種算法在用戶終端個數分別為100,200和300時,迭代運行至300代來求解功率優化控制模型所消耗時間的平均值,如表2所示.表中黑體對應各算法中最佳的運行時間.

從算法運行時間的平均值來看,在不同用戶個數的情況下,RVEA、MOEA/D、MOPSO和NSGA-II的運行時間都比MOEAD/IVG長,表明這四種算法的復雜度要高于MOEAD/IVG.隨著用戶個數的增加,各算法的運行時間都呈上升遞增趨勢.與其他算法相比,MOEAD/IVG的增長趨勢較為緩慢,說明變量個數的增加對算法運行效率的影響較小,說明MOEAD/IVG在解決大變量優化問題時所用的關聯變量識別及分組優化策略能夠有效提高問題的求解速度.與之相反,RVEA、MOEA/D、MOPSO和NSGA-II在解決大變量問題時將所有的決策變量視為一個整體來進行優化,該方式使得算法的求解效率低下,導致運行時間隨著決策變量個數的增加而顯著遞增.

表2 算法運行時間(單位:秒)
Table 2 Runtime of the algorithms (unit:seconds)

運行時間用戶個數MOEAD/IVGRVEAMOEA/DMOPSONSGA-II優化函數10050.152.458.370.172.920072.376.987.2103.7107.4300105.7112.4123.5145.8153.7

功率優化控制模型的求解說明,本文提出的MOEAD/IVG能夠有效地解決移動蜂窩通信系統中用戶功率優化分配的問題.在與另外四種進化算法的對比中,MOEAD/IVG無論是在所求解集質量、收斂速度還是運行效率方面,整體上都優于RVEA、MOEA/D、MOPSO和NSGA-II.由于Pareto占優在解決大規模變量問題上的局限性,NSGA-II在算法性能的對比中取得最差的結果,其獲得的Pareto前沿出現明顯的惡化現象.RVEA和MOPSO在處理大變量的優化問題時,同樣有著解集收斂效果不佳的現象.為了能夠較好地解決大規模變量優化問題,MOEAD/IVG在MOEA/D的基礎上引入關聯變量識別和分組策略,有效地彌補了MOEA/D在求解大變量問題中缺陷.MOEAD/IVG通過識別決策變量間內在的關聯性,將關聯變量分到同一組以使得高維變量問題被分解為簡單低維變量的子問題,在一定程度上減少子問題之間的依賴性,從而提高子問題優化后得到的解集質量并以此來獲得最佳的全局最優解.仿真實驗的對比表明,引入關聯變量識別和分組策略的MOEAD/IVG在解決大規模變量問題時有著其他算法所不具有的優勢和巨大潛力,該算法在求解大變量優化問題時比其他算法有著更好的收斂性和多樣性且所獲解集的整體質量更高.

6 總 結

本文引入關聯變量識別和分組策略,并據此提出關聯變量分組的分解多目標進化算法.該算法通過分析大規模決策變量中的關聯信息,將關聯變量分組,使得復雜多變量的優化問題被分解為簡單低維變量的子問題來進行分組優化.通過分析變量之間的關聯性并進行分組,可以盡可能地降低子問題間的依賴性并提高解集的整體質量.將該算法應用于求解通信系統中用戶功率優化控制設計的工程問題,將降低系統用戶功率消耗和使各用戶的接收SINR接近目標值作為目標并建立數學模型,完成系統中各終端功率的最優分配,滿足了用戶QoS需求和功率消耗盡量低這兩個矛盾問題的折衷協調,從而驗證了該算法的有效性.與RVEA、MOEA/D、MOPSO以及NSGA-II相比,MOEAD/IVG的綜合性能更優,在求解精度和收斂速度上都有著顯著的提升.在本文的實驗中僅考慮了MOEAD/IVG在兩維目標優化問題中的求解情況,因此下一步將研究該算法在高維目標優化問題上的求解性能.

[1] Liu Y,Yao X,Zhao Q,et al.Scaling up fast evolutionary programming with cooperative coevolution[C].Proceedings of IEEE Congress on Evolutionary Computation,Seoul,2001:1101-1108.

[2] Yang Z,Tang K,Yao X.Large scale evolutionary optimization using cooperative coevolutionary[J].Information Sciences,2008,178(15):2985-2999.

[3] Yang Z,Tang K,Yao X.Multilevel cooperative coevolution for large scale optimization[C].Proceedings of IEEE Congress on Evolutionary Computation,Hong Kong,2008:1663-1670.

[4] Omidvar M N,Li X,Yang Z,et al.Cooperative co-evolution for large scale optimization through more frequent random grouping[C].Proceedings of IEEE World Congress on Computation Intelligence,Barcelona,2010:1754-1761.

[5] Omidvar M N,Li X,Yao X.Cooperative co-evolution with delta grouping for large scale non-separable function optimization[C].Proceedings of IEEE World Congress on Computation Intelligence,

Barcelona,2010:1762-1769.

[6] Mahdavi S,Shiri M E,Rahnamayan S.Cooperative co-evolution with a new decomposition method for large-scale optimization[C].Proceedings of IEEE Congress on Evolutionary Computation,Beijing,2014:1285-1292.

[7] Omidvar M N,Li X,Mei Y,et al.Cooperative co-evolution with differential grouping for large scale optimization[J].IEEE Transactions on Evolutionary Computation,2014,18(3):378-393.

[8] Mei Y,Omidvar M N,Li X,et al.A competitive divide-and-conquer algorithm for unconstrained large-scale black-box optimization[J].ACM Transactions on Mathematical Software,2016,42(2):1301-1324.

[9] Ge H,Sun L,Yang X,et al.Cooperative differential evolution with fast variable interdependence learning and cross-cluster mutation[J].Applied Soft Computing,2015,36:300-314.

[10] Antonio L M,Coello C A C.Use of cooperative coevolution for solving large scale multiobjective optimization problems[C].Proceedings of IEEE Congress on Evolutionary Computation,Cancun,2013:2758-2765.

[11] Salomon R.Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions:a survey of some theoretical and practical aspects of genetic algorithms [J].BioSystems,1996,39(3):263-278.

[12] Zhang Q,Li H.MOEA/D:a multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.

[13] Li K,Zhang Q,Kwong S,et al.Stable matching-based selection in evolutionary multiobjective optimization[J].IEEE Transactions on Evolutionary Computation,2014,18(6):909-923.

[14] Chen W,Weise T,Yang Z,et al.Large-scale global optimization using cooperative coevolution with variable interaction learning[C].Proceedings of International Conference on Parallel Problem Solving from Nature,Berlin:Springer-Verlag,2010:300-309.

[15] Elmusrati M, Jantti R, Koivo H N. Multiobjective distributed power control algorithm for CDMA wireless communication systems[J]. IEEE Transactions on Vehicular Technology,2007,56(2):779-788.

[16] Elmusrati M,El-Sallabi H,Koivo H.Applications of multi-objective optimization techniques in radio resource scheduling of cellular communication systems [J].IEEE Transactions on Wireless Communications,2008,7(1):343-353.

[17] Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II [J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[18] Coello C A C,Pulido G T,Lechuga M S.Handling multiple objectives with particle swarm optimization[J].IEEE Transactions on Evolutionary Computation,2004,8(3):256-279.

[19] Cheng R,Jin Y,Olhofer M,et al.A reference vector guided evolutionary algorithm for many-objective optimization[J].IEEE Transactions on Evolutionary Computation,2016,20(5):773-791.

[20] Zitzler E,Thiele L,Laumanns M,et al.Performance assessment of multiobjective optimizers:an analysis and review [J].IEEE Transactions on Evolutionary Computation,2003,7(2):117-132.