基于多目標(biāo)的競(jìng)爭(zhēng)粒子群優(yōu)化算法的研究

王 彬， 王丹妮， 江巧永， 楊家杰

(1.西安理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 陜西 西安 710048；2.滑鐵盧大學(xué) 數(shù)學(xué)院， 加拿大 滑鐵盧 N2L 3G1)

近年來(lái)，隨著時(shí)代的發(fā)展與科技的進(jìn)步，出現(xiàn)的許多復(fù)雜問題都已無(wú)法通過簡(jiǎn)單的模型求解，這些問題的決策變量多、問題規(guī)模大、數(shù)學(xué)性質(zhì)復(fù)雜，被歸類稱為大規(guī)模問題[1]。因此，設(shè)計(jì)高效可靠的算法解決大規(guī)模問題是十分必要的。

針對(duì)這些優(yōu)化問題，學(xué)者們提出了大量的啟發(fā)式隨機(jī)優(yōu)化算法，進(jìn)化算法就是在這種背景下提出的。受自然界生物進(jìn)化的啟發(fā)，如帝王蝶優(yōu)化算法(MOB)[2]、大象放牧優(yōu)化算法(EHO)[3]、磷蝦群算法(KH)[4]等，因其操作簡(jiǎn)單、優(yōu)化性能強(qiáng)的特點(diǎn)，在過去幾十年中得到了快速發(fā)展，但是，進(jìn)化算法在優(yōu)化大規(guī)模問題時(shí)仍存在一些不足，因此，很有必要利用算法的學(xué)習(xí)能力[5]，研究出高效可靠的算法來(lái)解決大規(guī)模優(yōu)化問題。

目前，針對(duì)大規(guī)模問題的進(jìn)化算法主流解決策略[6]分為三類：一是靜態(tài)的協(xié)同進(jìn)化，即將復(fù)雜的高維問題分解成簡(jiǎn)單的低維問題進(jìn)行優(yōu)化求解；二是動(dòng)態(tài)的協(xié)同進(jìn)化，即利用分組策略將不可分的決策變量分在不同組，給予不同組一個(gè)權(quán)重向量[7]，將對(duì)問題的優(yōu)化轉(zhuǎn)化為對(duì)權(quán)重的優(yōu)化。前兩種解決策略都要在算法的前期求解決策變量之間的相關(guān)性，這樣會(huì)耗費(fèi)大量的時(shí)間和精力。三是整體進(jìn)化，這是一種不使用分組策略的算法，主要是針對(duì)大規(guī)模問題的特點(diǎn)，在原有的算法中加入一些搜索策略或者是利用新的進(jìn)化機(jī)制等方式來(lái)提升原有算法的尋優(yōu)能力。

競(jìng)爭(zhēng)粒子群優(yōu)化算法(CSO)[8]就是整體進(jìn)化的新興代表，由于該算法結(jié)構(gòu)簡(jiǎn)單、性能良好，因此在求解工程類優(yōu)化問題時(shí)得到了廣泛應(yīng)用，且備受關(guān)注。為進(jìn)一步提高算法的性能，不少科研人員都基于該算法進(jìn)行了改進(jìn)。2019年，Mohapatra等[9]進(jìn)一步提出了ICSO，使用的是三競(jìng)爭(zhēng)機(jī)制，它將這種遺傳概念與CSO結(jié)合起來(lái)，以便更快地收斂。2020年，Zhang等[10]提出了CSO-MA，它通過變異種群中的輸家來(lái)增加種群多樣性，提高探索能力。同年，Xiong等[11]提出了WLCSODGM，其對(duì)優(yōu)勝者領(lǐng)先的搜索策略和動(dòng)態(tài)高斯變異算子的引入，有效地解決了傳統(tǒng)CSO容易陷入局部最優(yōu)的弊端。

然而，已有的CSO算法通常是以適應(yīng)度值的大小作為參考依據(jù)來(lái)判斷算子的優(yōu)劣，但是，衡量粒子群算法性能的關(guān)鍵標(biāo)準(zhǔn)有兩個(gè)：收斂速度和全局搜索能力。因此，如何平衡粒子收斂速度和全局搜索能力是有效改進(jìn)算法的關(guān)鍵。

基于以上考慮，本文通過主動(dòng)學(xué)習(xí)種群的多樣性來(lái)構(gòu)建多目標(biāo)模型，在原有的評(píng)判基礎(chǔ)上，將多樣性也作為評(píng)估粒子優(yōu)劣的條件，從而平衡種群的探索與開發(fā)能力。最后，在測(cè)試函數(shù)集CEC2008上，將本文所提算法與其他改進(jìn)算法進(jìn)行對(duì)比，驗(yàn)證本文算法的有效性。

1 相關(guān)理論

1.1 競(jìng)爭(zhēng)粒子群優(yōu)化算法

粒子群優(yōu)化算法(PSO)是基于模仿群居動(dòng)物的群居行為而產(chǎn)生的算法，其概念簡(jiǎn)單且搜索效率較高。在PSO的基礎(chǔ)上，CSO引入了生物學(xué)中的適者生存競(jìng)爭(zhēng)機(jī)制，不用在每一次更新時(shí)都要記住個(gè)體最優(yōu)值與全局最優(yōu)值。它是在一個(gè)種群內(nèi)采用成對(duì)競(jìng)爭(zhēng)機(jī)制，使用兩兩比較的模式更新種群。

一般情況下，考慮的都是問題最小化：

minf(X)s.t.x∈X

(1)

式中：X∈Rn是可行解解集；n表示搜索空間的維度，即決策變量的數(shù)量。

競(jìng)爭(zhēng)后輸家的更新公式為：

Vl,j(t+1)=R1(k,t)Vl,j(t)+R2(Xw,j(t)-

(2)

Xl,j(t+1)=Xl,j(t)+Vl.j(t+1)

(3)

1.2 多目標(biāo)優(yōu)化

實(shí)際應(yīng)用中，通常會(huì)遇到多個(gè)目標(biāo)需要同時(shí)優(yōu)化的問題，這類問題統(tǒng)稱為多目標(biāo)優(yōu)化問題[12](multiobjective optimization problem, MOP)，其數(shù)學(xué)公式為：

(4)

式中：X=(x1,x2,…,xn)被稱為決策變量，也是n維的決策空間；fi(x)(i=1,2,…,m)是第i個(gè)被最小化的目標(biāo)；gj(x)(j=1,2,…,q)定義為第j個(gè)不等式約束；hk(x)(k=1,2,…,p)定義為第k個(gè)等式約束。此外，所有的約束決定了可行解的集合Ω，Y={F(x)|x∈Ω}被稱為目標(biāo)空間。

對(duì)于多目標(biāo)問題而言，一個(gè)問題的優(yōu)化可能會(huì)導(dǎo)致另一個(gè)問題的退化，因此，對(duì)于多目標(biāo)問題的優(yōu)化，很難找到一個(gè)同時(shí)滿足各個(gè)問題最優(yōu)值的解，而是找到一個(gè)平衡各個(gè)目標(biāo)的Pareto最優(yōu)解集。

2 研究動(dòng)機(jī)

2.1 CSO在多樣性方面存在的問題

收斂性分析是刻畫競(jìng)爭(zhēng)粒子群優(yōu)化算法動(dòng)力學(xué)行為的一個(gè)重要方面，同時(shí)也是確保競(jìng)爭(zhēng)粒子群優(yōu)化算法可靠性的基本前提。文獻(xiàn)[8]證明發(fā)現(xiàn)，CSO具有良好的收斂性能，但卻無(wú)法保證種群收斂到全局最優(yōu)，且由于CSO的二元錦標(biāo)競(jìng)爭(zhēng)機(jī)制，每次迭代只依賴一半的粒子在搜索空間中進(jìn)行開發(fā)，對(duì)種群的搜索能力有很大的限制。因此，有必要通過提高種群多樣性來(lái)確保種群盡可能地收斂到全局最優(yōu)。

2.2 解決思路

為了有效平衡種群的探索與勘探能力，在原有CSO以適應(yīng)度值作為評(píng)價(jià)標(biāo)準(zhǔn)的基礎(chǔ)上，加入另一個(gè)評(píng)價(jià)標(biāo)準(zhǔn)——多樣性,這樣不僅能兼顧個(gè)體的收斂速度，同時(shí)也能考慮到全局搜索能力。如圖1所示，多樣性的引入，將原本的單目標(biāo)模型轉(zhuǎn)化為多目標(biāo)模型。

圖1 單目標(biāo)模型轉(zhuǎn)化為多目標(biāo)模型Fig.1 Single objective model transformed into a multi-objective model

3 基于多目標(biāo)的競(jìng)爭(zhēng)粒子群優(yōu)化算法

基于以上考慮，本節(jié)提出了一種基于多目標(biāo)的競(jìng)爭(zhēng)粒子群優(yōu)化算法(MOCSO)，不同于已有的CSO，MOCSO引入了多目標(biāo)模型，將原本的單目標(biāo)模型轉(zhuǎn)化為多目標(biāo)模型，從而在保證原有收斂性的基礎(chǔ)上，提高了算法的開發(fā)能力，有效平衡了種群的開發(fā)與探索能力。此外，選擇策略增加了隨機(jī)性，在引導(dǎo)種群進(jìn)化方向的同時(shí)，可防止種群陷入局部最優(yōu)。

3.1 構(gòu)建多目標(biāo)模型

事實(shí)上，種群中個(gè)體的價(jià)值不僅僅取決于它的適應(yīng)度值，當(dāng)它與其它個(gè)體交配時(shí)，個(gè)體在解空間中產(chǎn)生足夠分散的后代的能力也是非常重要的，因?yàn)樗兄谟行以敱M地探索解空間。因此，在種群進(jìn)化過程中，要盡可能使個(gè)體的探索能力和開發(fā)能力達(dá)到一個(gè)平衡，既要考慮盡快地達(dá)到全局最優(yōu)解，也要考慮個(gè)體對(duì)種群多樣性的影響。基于以上原因，本文采用多目標(biāo)模型。模型如圖2所示，將種群中的所有個(gè)體按照支配關(guān)系劃分在不同的非支配層中，很明顯，第一層的個(gè)體要比第二層的個(gè)體表現(xiàn)性能好，以此類推。

圖2 多目標(biāo)模型的非支配排序Fig.2 Non dominated sorting of multi-objective

以個(gè)體適應(yīng)度值函數(shù)與個(gè)體多樣性度量函數(shù)為橫縱軸，表示要優(yōu)化的兩個(gè)目標(biāo)函數(shù)：

適應(yīng)度：ffitness(xi)=f(xi)

(5)

(6)

由于個(gè)體適應(yīng)度值越小，代表其越接近種群最優(yōu)解，而多樣性值越大，有利于在種群更新時(shí)生成盡可能分散的解，防止算法陷入局部最優(yōu)。因此，與種群中與每個(gè)個(gè)體有關(guān)的兩項(xiàng)目標(biāo)可界定為：

minffitness(xi)

(7)

min(-fdiversity(xi))

(8)

其中，多樣性采用歐氏距離，因其操作簡(jiǎn)單，易于計(jì)算。

(9)

采用非支配排序，將種群中的所有個(gè)體都劃分在不同的非支配層中，每一層的個(gè)體性能整體都要優(yōu)于后一層的，但在同一層面的個(gè)體都相互為非支配關(guān)系。

3.2 概率隨機(jī)選擇策略

非支配排序已經(jīng)將個(gè)體進(jìn)行優(yōu)劣劃分，為了有效平衡種群的探索與開發(fā)能力，在CSO中引入基于排序的選擇策略[13]，通過概率確定當(dāng)前的輸家和贏家。目的是讓表現(xiàn)良好的個(gè)體仍能保留自己的優(yōu)秀基因，從而有效地控制種群的進(jìn)化方向，加快種群收斂速度。但表現(xiàn)較劣的個(gè)體也有可能被選為贏家，這樣有利于增加種群多樣性，防止陷入局部最優(yōu)。詳細(xì)策略步驟如下。

1) 編號(hào)分配

環(huán)境選擇策略考慮了個(gè)體對(duì)種群收斂性和多樣性貢獻(xiàn)的大小，并按照其在Pareto前沿上的順序進(jìn)行全排序。其中，性能表現(xiàn)良好的個(gè)體排在首位，性能較差的個(gè)體排在末位，即越優(yōu)質(zhì)的個(gè)體，指標(biāo)就越小。為了以較大的概率選擇性能較好的個(gè)體作為贏家，需要重新定義種群編號(hào)。可表示為：

Ri=NP+1-i,i=1,2,…,NP

(10)

式中：NP是種群規(guī)模；i是當(dāng)前種群中第i個(gè)個(gè)體的指標(biāo)。

2) 選擇概率

根據(jù)式(10)中對(duì)個(gè)體編號(hào)的計(jì)算，第i個(gè)個(gè)體被選擇為贏家的選擇概率為：

(11)

因此，適應(yīng)度值較低和多樣性較好的個(gè)體將有很大的概率在排序種群中被選擇作為贏家。

3.3 算法描述

基于以上對(duì)MOCSO的描述，多目標(biāo)的競(jìng)爭(zhēng)粒子群優(yōu)化算法(MOCSO)的算法流程如表1所示。與經(jīng)典CSO相比，MOCSO主要增加了一個(gè)雙目標(biāo)模型(step2.1和step2.2)和選擇策略(step2.4)。

4 實(shí)驗(yàn)及分析

4.1 對(duì)比算法

為驗(yàn)證所提算法的有效性，本節(jié)引入6種對(duì)比算法，分別是：競(jìng)爭(zhēng)粒子群優(yōu)化算法(CSO)[8]、繼承的競(jìng)爭(zhēng)粒子群優(yōu)化算法(ICSO)[14]、改良的競(jìng)爭(zhēng)粒子群優(yōu)化算法(MCSO)[15]、動(dòng)態(tài)分組的競(jìng)爭(zhēng)粒子群優(yōu)化算法(CSO-DG)[16]、反向?qū)W習(xí)的競(jìng)爭(zhēng)粒子群優(yōu)化算法(OBLCPSO)[17]、排序?qū)W習(xí)的競(jìng)爭(zhēng)離子群優(yōu)化算法(RBLSO)[18]。

4.2 測(cè)試函數(shù)

在CEC2008上對(duì)MOCSO進(jìn)行數(shù)值實(shí)驗(yàn)，為了確保運(yùn)算的準(zhǔn)確性，每個(gè)算法在每個(gè)測(cè)試函數(shù)上獨(dú)立運(yùn)行51次。CEC2008的測(cè)試函數(shù)主要分為兩類：?jiǎn)文y(cè)試函數(shù)(F1～F2)、多模測(cè)試函數(shù)(F3～F7)。

表1 MOCSO的算法流程Tab.1 Flow chart of MOCSO

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

所有仿真實(shí)驗(yàn)的測(cè)試平臺(tái)都是相同的，均為2.60 GHz CPU和4 GB RAM，Microsoft Windows 10操作系統(tǒng)，Intel(R) CoreTMi5-3230M；測(cè)試軟件是Microsoft Windows 10操作系統(tǒng)下的MATLAB 2016a。

為評(píng)估MOCSO的有效性，將MOCSO與現(xiàn)有CSO的不同改進(jìn)算法進(jìn)行比較，其公共參數(shù)設(shè)置如表2所示。

表2 對(duì)比算法中的公共參數(shù)設(shè)置Tab.2 Public parameter setting in comparative algorithm

此外，本文采用兩個(gè)標(biāo)準(zhǔn)來(lái)評(píng)估算法的性能：

1) 收斂速度：繪制了不同類型測(cè)試函數(shù)的收斂曲線，直觀地顯示出算法的收斂情況，并反映出最優(yōu)解在各個(gè)算法之間的誤差值；

2) 統(tǒng)計(jì)分析：為了更客觀地比較兩種算法的性能，本文采用0.05顯著性水平的Wilcoxon秩和檢驗(yàn)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì)和分析， 如果得到的概率值小于0.05，則認(rèn)為兩種算法的性能有顯著差異，用1表示，否則為無(wú)顯著差異，用0表示。

4.4 實(shí)驗(yàn)結(jié)果及分析

表3、表4和表5分別記錄了MOCSO與6組對(duì)比算法在CEC2008測(cè)試函數(shù)集上的相關(guān)實(shí)驗(yàn)結(jié)果，并給出了統(tǒng)計(jì)分析性能比較。從最后一行的“w/s/l”值可以看出，MOCSO與其他算法存在顯著差異，其在大多數(shù)基準(zhǔn)測(cè)試函數(shù)上的整體效果明顯優(yōu)于其他算法。

進(jìn)一步分析可知，MOCSO在每個(gè)測(cè)試函數(shù)中的排名一般位于前兩名，整體收斂效果良好，這是因?yàn)樵谠u(píng)判標(biāo)準(zhǔn)中加入了多樣性，又保留了原始算法中粒子優(yōu)秀的探索能力，同時(shí)考慮到粒子的勘探能力，使得種群在更新過程中能有效平衡粒子收斂速度和全局搜索能力。

表3 MOCSO與6組對(duì)比算法在30維的CEC2008上獨(dú)立運(yùn)行51次的統(tǒng)計(jì)結(jié)果Tab.3 Statistical results of MOCSO and 6 groups of compared algorithms running 51 times independently on 30 dimensional CEC2008

表4 MOCSO與6組對(duì)比算法在50維的CEC2008上獨(dú)立運(yùn)行51次的統(tǒng)計(jì)結(jié)果Tab.4 Statistical results of MOCSO and 6 groups of compared algorithms running 51 times independently on 50 dimensional CEC2008

表5 MOCSO與6組對(duì)比算法在100維的CEC2008上獨(dú)立運(yùn)行51次的統(tǒng)計(jì)結(jié)果Tab.5 Statistical results of MOCSO and 6 groups of compared algorithms running 51 times independently on 100 dimensional CEC2008

從秩和檢驗(yàn)的結(jié)果來(lái)看，MOCSO在30維、50維和100維上，有超過一半的基準(zhǔn)函數(shù)其性能明顯優(yōu)于其他對(duì)比算法，為了更直觀地比較MOCSO與6組對(duì)比算法的收斂效果，圖3給出了MOCSO在測(cè)試函數(shù)集CEC2008上與其他算法的收斂速度的對(duì)比圖，從圖3中也可以看出，MOCSO的整體收斂效果還是具有一定優(yōu)勢(shì)的。

圖3 MOCSO與6組對(duì)比算法在50維的7個(gè)測(cè)試函數(shù)上的收斂曲線Fig.3 Convergence curves of MOCSO and 6 groups of compared algorithms for 7 test functions of 50 dimensions

4.5 計(jì)算效率分析

通過比較MOCSO與其他6組算法的復(fù)雜度來(lái)分析MOCSO的計(jì)算效率，結(jié)果如表6所示。

表6 7組算法的復(fù)雜度對(duì)比Tab.6 Complexity comparison of seven groups of algorithms

由表6可知，MOCSO的計(jì)算成本要高于其他改進(jìn)算法，因?yàn)镸OCSO設(shè)置了多目標(biāo)，因此每次迭代需要消耗大量額外的計(jì)算資源，為降低成本，該算法還有待進(jìn)一步改進(jìn)。

5 結(jié) 論

為了提高競(jìng)爭(zhēng)粒子群優(yōu)化算法(CSO)的性能，進(jìn)一步平衡種群中粒子的探索能力與開發(fā)能力，本文提出了一種基于多目標(biāo)的競(jìng)爭(zhēng)粒子群優(yōu)化算法，它在原有CSO的基礎(chǔ)上提出了以下改進(jìn)：

1) 設(shè)計(jì)多目標(biāo)演化機(jī)制，在演化過程中考慮了適應(yīng)度值和擁擠距離，即在兼顧原有算法收斂速度的同時(shí)，又保留了種群的全局搜索能力；

2) 引入隨機(jī)選擇策略，在每一次迭代中選擇輸贏家，這種策略在很大程度上保存了種群中的優(yōu)秀基因。

在CEC2008測(cè)試函數(shù)集上對(duì)MOCSO算法進(jìn)行數(shù)值實(shí)驗(yàn)，并與CSO、ICSO、CSO-DG、MCSO、OBLCPSO、RBLSO進(jìn)行性能對(duì)比。實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有CSO及其改進(jìn)方法相比，MOCSO在測(cè)試函數(shù)集上的整體效果明顯占優(yōu)。

通過仿真實(shí)驗(yàn)，雖然驗(yàn)證了MOCSO具有一定的有效性，但由于該算法設(shè)置了雙目標(biāo)，使得計(jì)算效率下降，其后續(xù)還有待進(jìn)一步改進(jìn)。