關(guān)聯(lián)變量分組的分解多目標(biāo)進(jìn)化算法及其應(yīng)用

邱飛岳,胡 烜,王麗萍

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

1 引 言

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

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

解決大規(guī)模變量問題的關(guān)鍵就在于尋找決策變量之間的關(guān)聯(lián)性.Salomon[11]的研究表明決策變量間的關(guān)聯(lián)性可以顯著影響算法在連續(xù)域上的優(yōu)化性能.研究表明大規(guī)模變量?jī)?yōu)化問題中的決策變量間存在一定的關(guān)聯(lián)性.當(dāng)變量規(guī)模增加時(shí),變量間的關(guān)聯(lián)性也會(huì)隨之加強(qiáng).根據(jù)決策變量間的關(guān)聯(lián)性來對(duì)變量進(jìn)行分解,使關(guān)聯(lián)變量盡可能地被分到同一組中,將大規(guī)模變量問題轉(zhuǎn)換為低維子問題來協(xié)同求解,可以最大程度地保證所求解集的質(zhì)量.

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

2 背 景

2.1 多目標(biāo)優(yōu)化的概念

不失一般性,MOP均以最小化為例,最大化問題可通過簡(jiǎn)單的方式轉(zhuǎn)換為最小化問題.對(duì)于由n個(gè)決策變量和m個(gè)目標(biāo)函數(shù)所構(gòu)成的最優(yōu)化問題,模型如下[13]:

(1)

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

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

2.2 關(guān)聯(lián)變量定義和分析

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

定義1.兩個(gè)決策變量xi和xj是相互關(guān)聯(lián)的當(dāng)且僅當(dāng)存在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).同時(shí),對(duì)于如何識(shí)別關(guān)聯(lián)變量存在以下判斷準(zhǔn)則.

定理1.f(x)為連續(xù)可微函數(shù),若兩個(gè)決策變量xi和xj相互關(guān)聯(lián),則?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 關(guān)聯(lián)變量分組的分解多目標(biāo)進(jìn)化算法(MOEAD/IVG)

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

3.1 關(guān)聯(lián)變量分組策略

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

步驟1.在種群中隨機(jī)選出一個(gè)個(gè)體進(jìn)行關(guān)聯(lián)變量的識(shí)別和分組,利用公式(3)對(duì)變量間的關(guān)聯(lián)程度進(jìn)行判斷.

步驟2.求出不同目標(biāo)函數(shù)下Δ的最大值.對(duì)變量之間的關(guān)聯(lián)性做如下判斷:如果Δ大于一個(gè)充分小的數(shù)ε,則表明兩個(gè)變量之間存在著一定的關(guān)聯(lián)性并將它們分到同一組中;否則,則說明兩者之間相互獨(dú)立.

步驟3.不斷重復(fù)上述過程直到將所有的關(guān)聯(lián)變量都進(jìn)行識(shí)別和分組.

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

算法1.關(guān)聯(lián)變量分組策略

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將關(guān)聯(lián)變量分組機(jī)制融入到MOEA/D中,其主要步驟分為以下兩個(gè)方面:決策變量分組過程和分組優(yōu)化階段.在變量分組過程中,通過識(shí)別決策變量中潛在的關(guān)聯(lián)信息從而將關(guān)聯(lián)變量分到同一組中,由此形成的各個(gè)子集分別包含各自相關(guān)的決策變量,從而最大可能地降低了子集間的依賴性,提高了全局最優(yōu)解的質(zhì)量.在算法的分組優(yōu)化過程中,利用MOEA/D來分別優(yōu)化分組后所形成的各個(gè)子問題,最終獲得目標(biāo)函數(shù)的全局最優(yōu)解.MOEAD/IVG的步驟如下:

步驟1.設(shè)置初始參數(shù),設(shè)定種群大小N和最大進(jìn)化代數(shù)T,初始化父種群.

步驟2.對(duì)父種群進(jìn)行交叉和變異操作產(chǎn)生子種群.

步驟3.結(jié)合父種群和子種群,根據(jù)算法1對(duì)混合種群進(jìn)行關(guān)聯(lián)變量識(shí)別和分組操作.

步驟4.利用MOEA/D來對(duì)關(guān)聯(lián)變量分組后所產(chǎn)生的各個(gè)子問題進(jìn)行優(yōu)化求解.

步驟5.判斷是否達(dá)到最大進(jìn)化代數(shù),若是,則根據(jù)優(yōu)化分組后各子問題的最優(yōu)解來得到全局最優(yōu)解并輸出;否則轉(zhuǎn)步驟3.

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

4 多目標(biāo)優(yōu)化的功率控制設(shè)計(jì)

4.1 問題描述

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

4.2 系統(tǒng)模型

系統(tǒng)環(huán)境為由N個(gè)用戶所構(gòu)成的單小區(qū)多用戶蜂窩通信系統(tǒng),用戶i(i∈N)與基站之間的距離為di,pi表示第i個(gè)用戶的發(fā)射功率.為簡(jiǎn)單起見,我們只考慮某種單一業(yè)務(wù),且對(duì)于此類業(yè)務(wù),預(yù)先設(shè)定目標(biāo)SINRγtar與最小SINRγmin,在終端處達(dá)不到此最小值時(shí),則認(rèn)為該用戶不被系統(tǒng)所服務(wù).SINR的表達(dá)式可以表示為[16]:

(4)

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

圖1 小區(qū)示意圖Fig.1 Example of a cell

在圖1中,BS表示小區(qū)中的基站,且基站使用全向天線并位于小區(qū)的中心.MS表示小區(qū)中的移動(dòng)臺(tái).信道增益Gi可由如下公式計(jì)算得到:

(5)

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

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

4.3 數(shù)學(xué)函數(shù)優(yōu)化模型

根據(jù)4.2節(jié)中功率優(yōu)化控制的兩個(gè)研究目標(biāo),提出如下的功率控制數(shù)學(xué)模型:

(6)

(7)

(8)

(9)

對(duì)應(yīng)上述這兩個(gè)相互矛盾的目標(biāo),傳統(tǒng)的功率控制算法很難為分布在各處的移動(dòng)終端找到一種最優(yōu)的解決方案.為了有效地解決該問題,本文采用基于多目標(biāo)優(yōu)化理論的MOEAD/IVG來求解.為了能夠?qū)⒐β蕛?yōu)化控制問題應(yīng)用到MOEAD/IVG中,首先應(yīng)明確各用戶終端的功率與算法中變量之間的關(guān)系,并將功率控制問題映射到算法中.進(jìn)化算法以染色體為單位來進(jìn)化搜尋問題的最優(yōu)解.在實(shí)驗(yàn)中設(shè)定種群規(guī)模大小為N,即種群是由N條染色體所構(gòu)成.將通信系統(tǒng)中各用戶終端的發(fā)射功率映射到染色體上,即每個(gè)用戶的發(fā)射功率對(duì)應(yīng)染色體中的各個(gè)基因,由所有用戶發(fā)射功率映射的基因就構(gòu)成了染色體.

5 仿真實(shí)驗(yàn)

5.1 參數(shù)設(shè)置

5.2 Pareto前沿對(duì)比分析

仿真實(shí)驗(yàn)得到的Pareto前沿對(duì)比圖如圖2所示.其中,圖2仿真了在用戶終端個(gè)數(shù)為100,200和300的情況下,各算法得到的用戶傳輸功率和終端接收SINR與目標(biāo)SINR之差的優(yōu)化目標(biāo)函數(shù)的Pareto前沿對(duì)比圖.

圖2 在不同用戶終端下優(yōu)化目標(biāo)函數(shù)的Pareto前沿對(duì)比圖Fig.2 Pareto front comparison chart of the optimization objective function under different user terminals

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

5.3 算法性能對(duì)比

為了進(jìn)一步說明MOEAD/IVG在求解大規(guī)模變量?jī)?yōu)化問題中的收斂特性.以上一節(jié)的功率控制模型為例,比較了在不同移動(dòng)用戶終端的情況下,系統(tǒng)中所有用戶在各進(jìn)化算法迭代過程中平均發(fā)射功率的變化情況,實(shí)驗(yàn)結(jié)果如圖3所示.在圖3中,橫坐標(biāo)代表算法進(jìn)化代數(shù),縱坐標(biāo)代表所有用戶的平均發(fā)射功率.

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

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

上述實(shí)驗(yàn)結(jié)果表明,MOEAD/IVG與其他算法相比,在求解大變量?jī)?yōu)化問題時(shí),通過關(guān)聯(lián)變量識(shí)別和分組策略可以有效地提高求解的收斂速度并使算法具有較好的收斂性能.

為了進(jìn)一步說明MOEAD/IVG在求解大規(guī)模變量?jī)?yōu)化問題中的有效性.仿真了各算法求得的所有用戶平均功率隨移動(dòng)終端個(gè)數(shù)的變化情況,實(shí)驗(yàn)結(jié)果如圖4所示.橫坐標(biāo)代表移動(dòng)用戶終端的個(gè)數(shù),縱坐標(biāo)代表所有用戶的平均功率大小.

由公式(4)可以看出,用戶終端數(shù)目的不斷增加會(huì)逐漸導(dǎo)致系統(tǒng)中每個(gè)用戶干擾的增強(qiáng),因此,用戶為了保證QoS都會(huì)不同程度地提高發(fā)射功率,這與圖4的仿真結(jié)果相一致.功率控制模型中各移動(dòng)終端為了追求QoS而調(diào)整發(fā)射功率,但發(fā)射功率的增加必定會(huì)增大干擾.從圖4中可以看到,當(dāng)系統(tǒng)中移動(dòng)用戶終端個(gè)數(shù)為100時(shí),這五種算法求得的各用戶平均發(fā)射功率都較小.但隨著用戶個(gè)數(shù)的增加,各算法求得的平均發(fā)射功率均有所增加,但由 MOEAD/IVG 所求的平均功求的性能表現(xiàn)上更為優(yōu)越.實(shí)驗(yàn)結(jié)果表明通過識(shí)別關(guān)聯(lián)變量和恰當(dāng)?shù)姆纸M策略可以有效地解決大規(guī)模變量?jī)?yōu)化問題,MOEAD/IVG能夠在一定程度上提高所求解集的質(zhì)量和算法的整體性能.為了更加客觀地體現(xiàn)MOEAD/IVG的優(yōu)越性,本文將通過加法二進(jìn)制ε指標(biāo)值和算法運(yùn)行效率這兩方面對(duì)算法的綜合性能進(jìn)行對(duì)比.

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

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

5.4 解集質(zhì)量對(duì)比

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

表1 加法二進(jìn)制ε指標(biāo)對(duì)比
Table 1 Comparison of additive binaryε-indicator

加法二進(jìn)制ε指標(biāo)用戶個(gè)數(shù)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)優(yōu)化函數(shù)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

在對(duì)比實(shí)驗(yàn)中,本文用字母G,R,D,M和N來分別代表5種算法MOEAD/IVG,RVEA,MOEA/D,MOPSO和NSGA-II所產(chǎn)生的解集.加法二進(jìn)制ε指標(biāo)值見表1.從表1中可以清楚地發(fā)現(xiàn),在MOEAD/IVG與RVEA的對(duì)比中,當(dāng)用戶終端個(gè)數(shù)分別為100,200和300時(shí),均有I(G,R)<0,I(R,G)>0,表明在所有情況下MOEAD/IVG所求得的解集均嚴(yán)格優(yōu)于RVEA.同理,當(dāng)MOEAD/IVG分別跟MOEA/D、MOPSO和NSGA-II進(jìn)行對(duì)比時(shí),均有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在所有情況下所求解集均嚴(yán)格優(yōu)于MOEA/D、MOPSO和NSGA-II.綜上,由加法二進(jìn)制ε指標(biāo)值的對(duì)比結(jié)果可以得出MOEAD/IVG產(chǎn)生的解集整體上更優(yōu).實(shí)驗(yàn)結(jié)果表明在求解大規(guī)模變量問題時(shí),在MOEA/D中引入關(guān)聯(lián)變量識(shí)別和分組策略是成功的,可以顯著提高算法在大變量問題優(yōu)化時(shí)的求解性能.

5.5 算法運(yùn)行效率對(duì)比

為了比較各算法的運(yùn)行效率,本文統(tǒng)計(jì)了20次五種算法在用戶終端個(gè)數(shù)分別為100,200和300時(shí),迭代運(yùn)行至300代來求解功率優(yōu)化控制模型所消耗時(shí)間的平均值,如表2所示.表中黑體對(duì)應(yīng)各算法中最佳的運(yùn)行時(shí)間.

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

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

運(yùn)行時(shí)間用戶個(gè)數(shù)MOEAD/IVGRVEAMOEA/DMOPSONSGA-II優(yōu)化函數(shù)10050.152.458.370.172.920072.376.987.2103.7107.4300105.7112.4123.5145.8153.7

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

6 總 結(jié)

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

[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.