趙 晶，曲相宇

(齊魯工業(yè)大學(xué)(山東省科學(xué)院)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南 250353)

1 引言

在多目標(biāo)優(yōu)化問題中，這些目標(biāo)往往互相矛盾，沒有一個(gè)單一的解決方案可以同時(shí)優(yōu)化所有目標(biāo)，因此其解集并不是唯一的[1-2]。如果想讓優(yōu)化問題中的每個(gè)目標(biāo)函數(shù)值達(dá)到最佳效果，需要對這些目標(biāo)函數(shù)進(jìn)行進(jìn)一步的處理，目前有很多算法用于求解多目標(biāo)優(yōu)化問題，如基于參考點(diǎn)的非支配排序遺傳算法(A Fast and Elitist Multi-objective Genetic Algorithm，NSGA-Ⅱ)[3]，基于分解的多目標(biāo)進(jìn)化算法(A Multi-objective Evolutionary Algorithm Based on Decomposition，MOEA/D)[4]。在各種智能優(yōu)化算法中，粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)是處理多目標(biāo)優(yōu)化問題的主流算法之一[5]。

在MOPSO算法中，如何提高算法所得的非支配解的收斂性和多樣性是算法亟待解決的主要難題，國內(nèi)外專家對此作了很多研究[6]。粒子群優(yōu)化算法的顯著特點(diǎn)是群中所有個(gè)體之間的協(xié)作，每個(gè)粒子都被群體中的全局最優(yōu)(gBest)和自己的個(gè)體最優(yōu)(pBest)所吸引從而改變自己的飛行方向，因此協(xié)作搜索策略使得粒子群算法具有更好的全局搜索能力[7-8]。另外，與其他進(jìn)化計(jì)算算法相比，粒子群優(yōu)化算法具有計(jì)算量小、收斂速度快的特點(diǎn)[9]。粒子群優(yōu)化算法的相對簡單性和作為單目標(biāo)優(yōu)化算法的成功，促使研究者將粒子群算法的應(yīng)用從單目標(biāo)優(yōu)化問題擴(kuò)展到多目標(biāo)優(yōu)化問題。然而，除了檔案維護(hù)外，MOPSO仍有兩個(gè)問題有待進(jìn)一步解決。

第一個(gè)是gBest和pBest的更新，多目標(biāo)問題因?yàn)闆]有絕對的最佳解決方案，而是一組非支配的解決方案。根據(jù)gBest和pBest的不同策略，可以從非支配集合中選擇不同的候選對象，gBest和pBest的不同選擇會(huì)導(dǎo)致粒子的飛行方向不同，這對粒子的收斂性以及MOPSO的多樣性有重要影響[10]。Knowles[11]等人通過增強(qiáng)多目標(biāo)問題中非支配解的多樣性，提出了自適應(yīng)超網(wǎng)格選擇全局最優(yōu)解策略，但該方法會(huì)使得全局最優(yōu)解朝著非代表性的支配前沿靠近，沒有兼顧到粒子的收斂性。Zhan[12]等人提出一種自適應(yīng)粒子群優(yōu)化算法，該算法預(yù)先定義粒子的4種進(jìn)化狀態(tài)，從而對慣性因子、加速因子及其它參數(shù)達(dá)到自動(dòng)控制的目的，有效平衡了解集的收斂性和多樣性。Zheng等人[13]通過綜合學(xué)習(xí)策略引入了一種新的MOPSO算法，該算法能夠保持群體的多樣性，并顯著提高進(jìn)化粒子的性能。Lee 等人[15]提出了一種基于偏好排序的MOPSO算法，將用戶的偏好引入進(jìn)化過程中，以確定非支配解的相對優(yōu)缺點(diǎn)，以選擇合適的gBest和pBest。在每一次優(yōu)化后，通過選擇全局評價(jià)值最高的方法來選擇最優(yōu)的粒子作為gBest。結(jié)果表明，用戶的偏好在優(yōu)化后的解中得到了很好的反映，而不損失整體解的質(zhì)量和多樣性，但在粒子收斂性方面還有待加強(qiáng)。Liu等人[17]提出了一種基于平衡收斂性和多樣性的個(gè)體適應(yīng)度計(jì)算策略(NMPSO)來定義解的新適應(yīng)度，用于更好地尋找gBest和pBest，結(jié)果表明，NMPSO在某些多目標(biāo)問題的表現(xiàn)不夠穩(wěn)定。對于上述算法，如何選擇合適的具有適當(dāng)收斂性和分布性的gBest和pBest仍然是一個(gè)挑戰(zhàn)[18-19]。

MOPSO的第二個(gè)問題是收斂性，為了實(shí)現(xiàn)MOPSO的快速收斂，人們提出了許多不同的策略。Nebro和Durillo等人提出了基于速度約束的多目標(biāo)粒子群優(yōu)化算法(Speed-constrained Multi-objective PSO，SMPSO)[16],該算法在傳統(tǒng)PSO基礎(chǔ)上引入收縮因子φ控制速度更新，提高了算法的收斂性，并跳出局部最優(yōu)。但在算法多樣性方面表現(xiàn)欠佳。Li和Xiao[20]提出了一個(gè)動(dòng)態(tài)MOPSO，在該模型中，群的數(shù)量在整個(gè)搜索過程中都是自適應(yīng)調(diào)整的。動(dòng)態(tài)MOPSO算法分配適當(dāng)數(shù)量的群以支持收斂和分集準(zhǔn)則。結(jié)果表明，在一些標(biāo)準(zhǔn)的基準(zhǔn)問題上，所提出的動(dòng)態(tài)MOPSO算法與所選算法相比具有一定的競爭力。韓等人[14]提出了一種基于種群多樣性信息的飛行參數(shù)調(diào)整機(jī)制來增強(qiáng)粒子收斂性，但在某些收斂時(shí)期易發(fā)生陷入局部最優(yōu)的風(fēng)險(xiǎn)。在這些MOPSO算法中，為了獲得更好的性能，還開發(fā)了其它策略(如模糊聚類、協(xié)同協(xié)同進(jìn)化等)[21，22]。然而，如何將MOPSO算法的收斂性和多樣性相結(jié)合的研究仍然不多[23]。

基于以上分析和回顧，本文提出一種基于速度約束和全局多樣性信息的多目標(biāo)粒子群優(yōu)化算法(SGDMOPSO)，SGDMOPSO算法主要從以下幾個(gè)方面進(jìn)行了改進(jìn)，原因如下：

1)速度更新方法中融入了速度收縮因子φ和新的由pBest到gBest的搜索方向，以提高整個(gè)粒子群的收斂速度，平衡粒子的全局搜索能力和局部開發(fā)能力。

2)采用基于精英庫多樣性信息的外部檔案維護(hù)策略，從非支配解的多樣性考慮，運(yùn)用多個(gè)指標(biāo)剔除劣勢解，能夠保持外部檔案中非劣解的多樣性。

3)從整個(gè)精英庫中的非支配解的多樣性考慮，非支配解的多樣性信息表征著算法在分布性方面的優(yōu)劣，將此指標(biāo)作為選取全局最優(yōu)粒子的選擇機(jī)制，而全局最優(yōu)解在本算法中影響著新的搜索方向，因此同時(shí)兼具了收斂性和多樣性，當(dāng)精英庫中非支配解的多樣性好時(shí)，全局最優(yōu)解的指標(biāo)為收斂度最高的解；當(dāng)精英庫中非支配解的多樣性不好時(shí)，全局最優(yōu)解的指標(biāo)為密集屬性最大的解。

通過上述改進(jìn)，使得該算法在進(jìn)化過程中具有更快的收斂速度和更高的處理MOPs的效率。

本文第二部分詳細(xì)介紹了SGDMOPSO算法：包括速度更新策略、外部存檔更新、算法流程；第三部分為仿真及結(jié)果分析；第四部分為總結(jié)。

2 SGDMOPSO算法

2.1 PSO算法及改進(jìn)

1)PSO

粒子群優(yōu)化算法(PSO)[24-25]是1995年由Kennedy和Eberhart提出的一種仿生啟發(fā)式算法，它模擬鳥群聚集的社會(huì)行為，算法結(jié)構(gòu)簡單、參數(shù)少、收斂速度比較快。自從摩爾和查普曼在1999年首次將其擴(kuò)展到多目標(biāo)優(yōu)化問題[26]以來，PSO算法已經(jīng)成為解決多目標(biāo)優(yōu)化問題的一種非常流行的方法[14]。

PSO中的每個(gè)粒子有兩個(gè)屬性：位置x和速度v，它們由以下公式更新：

vi(t+1)=ω×v(t)+c1×r1×(pbesti-xi(t))

+c2×r2×(gbest-xi(t))

(1)

xi(t+1)=xi(t)+vi(t+1)

(2)

其中，xi為第t代粒子群中的第i個(gè)粒子，它的當(dāng)前速度為vi(t)，當(dāng)前位置為xi(t)，歷史最優(yōu)位置為pbesti；整個(gè)粒子群的歷史最優(yōu)位置為gbest；ω為慣性權(quán)重，用于調(diào)節(jié)粒子的飛行速度，如果ω大于1，會(huì)導(dǎo)致粒子的速度增加到無窮大，因此ω一般取小于1的隨機(jī)數(shù)；c1和c2分別表示向個(gè)體歷史最優(yōu)和歷史全局最優(yōu)的學(xué)習(xí)因子，r1和r2是兩個(gè)0到1之間的隨機(jī)數(shù)。

2)改進(jìn)MOPSO速度控制

為了平衡PSO算法的全局搜索能力和局部開采能力，Zhan等人對慣性權(quán)重ω進(jìn)行改進(jìn)，使其在一定數(shù)值區(qū)間內(nèi)作隨機(jī)調(diào)整[27]。Nebro和Durillo等人提出了基于速度約束的多目標(biāo)粒子群優(yōu)化算法(Speed-constrained Multi-objective PSO，SMPSO)，該算法在傳統(tǒng)PSO基礎(chǔ)上引入收縮因子φ控制速度更新，φ由學(xué)習(xí)因子c1和c2決定，其定義為[16]

(3)

Liu等人提出了一種平衡適應(yīng)度值估計(jì)的多目標(biāo)粒子群優(yōu)化算法(A Balanceable Fitness Estimation for Many-objective PSO，NMPSO)，在速度更新過程中加入pbest到gbest的搜索方向[17]。為了避免加入新的搜尋方向?qū)αＷ訉?yōu)影響過大而削弱學(xué)習(xí)因子c1和c2的作用，更好地提升算法收斂速度和精度，本文在NMPSO的思想上，對PSO算法的速度更新策略做了進(jìn)一步的改進(jìn)，融入了由兩個(gè)學(xué)習(xí)因子c1和c2決定的速度收縮因子，使得粒子在新速度更新中既增加了方向的精細(xì)性，又保持了全局搜索能力和局部勘探能力。提出新的SMOPSO(Multi-objective Particle Swarm Optimization based on Speed-constraints,SMOPSO)算法，在該算法中，定義第i個(gè)粒子xi的速度更新公式為：

(4)

其中c1、c2、c3為學(xué)習(xí)因子；r1、r2、r3為0到1之間的隨機(jī)數(shù)。改進(jìn)SMOPSO中xi的位置更新依然如PSO算子的式(2)一樣。通過在速度更新過程中增加由pbest到gbest的搜索方向，引導(dǎo)粒子群中的粒子向全局最優(yōu)方向進(jìn)化，加快粒子群的收斂速度。

在SMOPSO算法的速度控制策略中，進(jìn)一步對粒子的速度中每一維元素越界做了壓縮控制

(5)

其中，Δj=0.5×(uj-dj),j=1,2，…,m,m為目標(biāo)數(shù)，uj和dj分別為每個(gè)粒子速度第j元素的上下界限。

2.2 基于精英庫的外部檔案更新

外部檔案主要用于存儲(chǔ)粒子在迭代過程中求得的較好的非支配解，當(dāng)非支配解的數(shù)量達(dá)到最大容量時(shí)，在MOPSO算法[28]中，本文提出基于精英庫的多樣性信息的外部存檔更新機(jī)制，將不同時(shí)期的外部存檔用多種規(guī)則靈活地進(jìn)行更新，保留當(dāng)前外部存檔時(shí)期最合適的非支配解，最大程度上維護(hù)解集的多樣性?；舅悸啡缦拢涸O(shè)At為第次迭代后產(chǎn)生的精英庫，At由第t次迭代產(chǎn)生的非支配解集Bt和前t-1次迭代保留下來的非支配解集Ct-1組成。如果在第t次迭代后算法產(chǎn)生的解被t-1代精英庫At-1中的解支配時(shí)，該解不是非支配解，不能進(jìn)入精英庫At；如果精英庫At-1中的解被第t次迭代產(chǎn)生的解所支配時(shí)，精英庫中該支配解不再為非支配解，將其放入集合Dt-1中。

定義1(密集屬性)：一個(gè)非支配解的密集屬性為該非支配解與其相鄰的兩個(gè)非支配解的平均歐氏距離，即

(6)

其中，Disti是第i個(gè)非支配解密集屬性，dist1i、dist2i是與第i個(gè)非支配解相鄰非支配解的歐氏距離。非支配解的密集屬性越小，表示該非支配解附近越擁擠。

定義2(支配屬性)：一個(gè)解x∈Bt的支配屬性EA(x)是x在精英庫At中能夠支配的解y∈Dt-1的數(shù)目，即

EA(x)=|{y|y∈Dt-1∧x>y∧x∈Bt}|

(7)

其中Bt是第t次迭代產(chǎn)生的精英庫At中的非支配解集，Dt-1是第t次迭代產(chǎn)生的精英庫At中所支配的解的集合。當(dāng)EA(x)為零時(shí)，該解支配屬性為零。

這里，非支配解集Bt中的解包含兩種：一種是可以支配Dt-1集合中的解(支配不為零)；另一種是不可以支配Dt-1集合中的解(支配屬性為零)。

定義3(收斂屬性)：一個(gè)解x∈Bt的收斂屬性是其與所有被其支配的解yi∈Dt-1的平均歐氏距離，即

(8)

其中，Dave(x)是解x的收斂屬性，yi是被解x支配的第i個(gè)解。非支配解集Ct-1中解的收斂屬性為零，無支配屬性的解其收斂屬性也為零。

精英庫At更新的具體流程如下：

Step1：若精英庫At容量未滿，則非支配解直接進(jìn)入。

Step2：若精英庫At容量已滿，執(zhí)行以下操作：從精英庫At中非支配解的多樣性考慮，計(jì)算精英庫At中每個(gè)非支配解的密集屬性，刪減解集Ct-1中密集屬性較小的解和非支配解集Bt中支配屬性為零的解。

Step3：如果刪減完密集屬性較小和支配屬性為零的解后仍然超出精英庫容量，考慮刪減Dt-1集合中支配屬性不為零的解。計(jì)算此時(shí)精英庫中非支配解的收斂屬性Dave，刪減Dave較小的解，若Dave相等，則執(zhí)行Step4。

Step4：計(jì)算解集Bt中解的支配屬性，比較支配屬性大小，優(yōu)先刪減支配屬性較小的解。

2.3 全局最優(yōu)選擇機(jī)制

由于PSO算法優(yōu)化過程中容易出現(xiàn)早熟現(xiàn)象，導(dǎo)致算法陷入局部最優(yōu)，為了更好地跳出局部最優(yōu)，收斂至全局最優(yōu)，在保證收斂性的情況下根據(jù)多樣性信息選擇最優(yōu)的全局最優(yōu)解。

定義4(多樣性信息)：本文的多樣性信息一共分為兩種，一種為種群多樣性信息，一種為精英庫非支配解的多樣性信息。

種群多樣性信息：從整個(gè)粒子群考慮，種群多樣性能反映種群的粒子分布情況。種群多樣性不好，有可能導(dǎo)致算法優(yōu)化過程中尋優(yōu)速度慢、精度不夠。其表達(dá)式為

(9)

式中，SPp(t+1)是第t+1次迭代粒子群的種群多樣性信息，dpt(t+1)是在第t+1次迭代第i個(gè)粒子與其它粒子之間最小的曼哈頓距離，dpi(t+1)是所有的dpi(t+1)的平均值，n1是粒子的個(gè)數(shù)。

非支配解多樣性信息：從精英庫中非支配解的多樣性考慮，非支配解的多樣性代表了算法在分布性方面的性能，非支配解多樣性越好表示算法分布多樣性越好。其表達(dá)式為

(10)

根據(jù)式(10)計(jì)算的非支配解多樣性信息可以作為精英庫中非支配解集的多樣性度量指標(biāo)，通過比較非支配解多樣性SPn(t+1)值與α值的大小關(guān)系(α為非支配解多樣性信息SPn(t+1)優(yōu)劣性的分界值，在文中方法中定義α=0.05)，判斷當(dāng)前整個(gè)精英庫中非支配解集的分布狀態(tài)。

全局最優(yōu)解選擇機(jī)制為：

1)若SPn(t+1)≤α，說明整個(gè)精英庫非支配解的多樣性比較好，從算法角度考慮應(yīng)提高算法收斂速度，此時(shí)全局最優(yōu)解應(yīng)選取收斂屬性最大的非支配解。

2)若SPn(t+1)>α，說明整個(gè)精英庫非支配解的多樣性比較差，從算法角度考慮應(yīng)增加粒子分布的多樣性，此時(shí)全局最優(yōu)解應(yīng)選取密集屬性最大的非支配解。

2.4 SGDMOPSO算法流程

Step1：參數(shù)初始化：設(shè)置種群規(guī)模，最大迭代次數(shù)，個(gè)體粒子的速度、位置、慣性權(quán)重、學(xué)習(xí)因子，并將各粒子的初始位置設(shè)為其當(dāng)前個(gè)體最優(yōu)位置pbesti。

Step2：計(jì)算各粒子的適應(yīng)度值，根據(jù)適應(yīng)度值得到精英庫，根據(jù)式(6)(7)和(8)分別計(jì)算各個(gè)非支配解的密集屬性、支配屬性和收斂屬性。

Step3：計(jì)算當(dāng)前整個(gè)精英庫非支配解多樣性SPn(t+1)，根據(jù)1.3節(jié)全局最優(yōu)選擇策略確定全局最優(yōu)解。

Step4：比較Step2中精英庫中各個(gè)非支配解的密集屬性、支配屬性和收斂屬性的值，按照精英庫更新策略，生成新的精英庫。

Step5：按照式(1)和(2)更新粒子的位置和速度。

Step6：判斷是否達(dá)到迭代次數(shù)，如達(dá)到迭代次數(shù)，則結(jié)束更新，否則轉(zhuǎn)到Step2。

3 實(shí)驗(yàn)

3.1 MOP測試函數(shù)

1)性能標(biāo)準(zhǔn)

在多目標(biāo)優(yōu)化問題中，衡量一個(gè)算法應(yīng)從收斂性和多樣性的角度來評價(jià)，因此本文采用以下兩個(gè)定量指標(biāo)來說明算法效果。

①反向世代距離Inverted Generational Distance(IGD)：IGD通過計(jì)算所求得的近似Pareto最優(yōu)解集前沿面的距離來綜合評價(jià)算法的收斂性與多樣性，IGD可定義為

(11)

其中，dist(x,P)為真實(shí)前沿P*中一個(gè)解x和所獲Pareto前沿之間的最小歐氏距離，|P*|表示真實(shí)的Pareto最優(yōu)解集上的點(diǎn)的數(shù)量。IGD越小表明算法的收斂性和多樣性越好。

(12)

其中，Vol(·)表示勒貝格測度。其中P中所有的解都應(yīng)能支配zr，如果不能支配，則將該解從P中刪除。HV越大表明算法的多樣性和收斂性越好。

2)標(biāo)準(zhǔn)測試函數(shù)

為了驗(yàn)證SGDMOPSO算法的性能，本文采用標(biāo)準(zhǔn)測試函數(shù)ZDT1、ZDT2、ZDT3、ZDT4、ZDT6、DTLZ2和DTLZ7對4種算法進(jìn)行測試。

為了對比不同算法的有效性能，將SGDMOPSO算法與SMPSO算法[16]、NSGA-Ⅱ算法[3]、NMOPSO算法[17]的測試數(shù)據(jù)相比較。在比較實(shí)驗(yàn)中，算法執(zhí)行時(shí)的參數(shù)設(shè)置為：各算法種群大小和精英庫外部存檔的最大容量均為100，最大迭代次數(shù)為2000。各算法的具體參數(shù)設(shè)置如表1所示，測試函數(shù)的參數(shù)設(shè)置如表2所示。

表1 算法參數(shù)設(shè)置

表2 測試函數(shù)參數(shù)設(shè)置

3.2 實(shí)驗(yàn)結(jié)果與分析

表3和表4分別列出了4種算法在ZDT和DTLZ系列測試函數(shù)上的IGD和HV，Mean和Std分別表示同一算法在相同測試問題上獨(dú)立運(yùn)行30次后的均值和方差，它們的最優(yōu)數(shù)據(jù)用粗斜體表示，由此可反映出IGD和HV測試性能的綜合評價(jià)效果。圖1～6為4種算法得到的非劣支配解和真實(shí)的非劣支配解之間的相互關(guān)系。

從表3和表4可以看出，算法SGDMOPSO在給定的7個(gè)測試問題中分別獲得5個(gè)最優(yōu)IGD值和4個(gè)HV值，可見SGDMOPSO算法在這7個(gè)測試問題的多樣性和收斂性表現(xiàn)優(yōu)秀，在以上幾種測試問題上幾乎都優(yōu)于其它3種算法。對于ZDT4測試問題，SGDMOPSO性能上要稍遜于NSGA-Ⅱ，在其它測試問題均優(yōu)于NSGA-Ⅱ；對于DTLZ2和DTLZ7測試問題，SGDMOPSO性能上要稍遜于NMOPSO，在其它測試問題上都優(yōu)于NMOPSO。從總體結(jié)果來看，本文算法在綜合性能優(yōu)于其它的3種比較算法。

圖1 ZDT1的Pareto曲線

圖2 ZDT2的Pareto曲線

圖3 ZDT3的Pareto曲線

圖4 ZDT4的Pareto曲線

圖5 ZDT6的Pareto曲線

圖6 DTLZ2的Pareto曲線

表3 SGDMOPSO算法與其它算法的IGD指標(biāo)

表4 SGDMOPSO算法與其它算法的HV指標(biāo)

從圖1～6可以看出，SGDMOPSO在測試問題ZDT1、ZDT2、ZDT3、ZDT4、ZDT6和DTLZ2求得的非支配解的分布性和收斂性均較好。對于ZDT1、ZDT2和ZDT3測試問題，4種算法雖然都能夠較好地求得Pareto前沿，但SGDMOPSO算法得到的非支配解的分布性更加均勻。對于ZDT4測試問題，NMPSO算法所求得的Pareto前沿效果分布性較差,SGDMOPSO算法求得的Pareto前沿分布依然最均勻。對于ZDT6測試問題，SGDMOPSO算法獲得的Pareto前沿分布效果比其它3種算法好，不僅能夠較好地與真實(shí)Pareto前沿趨于吻合，且解的分布情況也比較均勻。對于三維測試問題DTLZ2，SGDMOPSO算法和NMPSO算法在DTLZ2的測試效果要好于其它兩種算法。換句話說，SGDMOPSO算法在大部分測試目標(biāo)上都優(yōu)于其它3種算法。

4 結(jié)語

為了更好地提高收斂速率和避免陷入局部最優(yōu)，本文提出SGDMOPSO算法，通過改進(jìn)速度更新公式和全局多樣性信息選取最優(yōu)解來提升算法的性能，將粒子速度方向控制、全局最優(yōu)選擇策略、精英庫外部檔案維護(hù)策略較好地統(tǒng)一在一起。實(shí)驗(yàn)結(jié)果表明，提出的算法能夠獲得較好的Pareto最優(yōu)前沿分布特性和較快的收斂速率。盡管SGDMOPSO算法已經(jīng)能夠獲得較高地收斂精度和較好的多樣性，但是對于處理某些具體實(shí)際問題還存在一定局限性，下一步的研究考慮融入其它智能優(yōu)化算法的思想，如微分進(jìn)化算法、遺傳算法等，從而更好地從多樣性和收斂性兩方面來探究求解高維多目標(biāo)優(yōu)化問題的有效性和可行性。