一種用于MOPSO的全局極值確定和種群更新的新策略

劉少偉+朱永利

摘要：多目標粒子群優(yōu)化過程中，收斂速度和粒子的多樣性之間往往不能兼顧，且常易于陷入局部最優(yōu)。為了更好地解決此問題，該文結(jié)合Pareto支配的思想，提出了一種改進的多目標粒子群優(yōu)化算法。此方法使用帶有規(guī)模限制的外部檔案，并采用在線歸檔技術(shù)，改進了粒子群和外部檔案的更新方式。當外部檔案達到最大規(guī)模時，剔除密集距離最小的非劣解；在全局極值的確定中，除考慮概率外，選取稀疏距離最大的非劣解作為當前代的全局極值；另外采取多次迭代的方法更新種群。對幾個典型函數(shù)的仿真結(jié)果表明，算法在尋優(yōu)效率和Pareto前沿的性能指標方面達到了滿意的效果。該算法為其他更加復雜的多目標優(yōu)化問題提供了新思路。

關(guān)鍵詞：多目標優(yōu)化；外部檔案；密集距離；稀疏距離

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2017）27-0217-04

Abstract：In the MOPSO， it may be difficult to take into consideration both the convergence rate and diversity. Usually， locally optimal solution can be gained. In order to settle these questions much better， a modified MOPSO which combined with the conception of Pareto domination is proposed in this paper. External archive with size limitation is adopted，and online elite archive， which is benefit to the modification of updating method is referred to. While the size of external archive exceeds the edge， the Pareto optimal solution with minimal crowding distance will be deleted. Besides the probability， one of the solutions whose sparse distance value are biggest will be chosen as the global best value. In addition， several times of iteration are applied to update the swarm. The simulation results of typical functions show that the new approach has good effect on search efficiency and performance metrics of Pareto fronts. It will contribute to more complicate multi-objective problems.

Key words：multi-objective optimization； external archive； crowding distance； sparse distance

工程實踐中的很多實際問題在進行數(shù)學建模以后，都可以抽象為一個多目標的優(yōu)化問題。多目標優(yōu)化問題（Multi-objective Optimization Problem， MOP）通常不存在某個絕對的最優(yōu)解，使得各目標均同時達到令人滿意的結(jié)果[1]。隨著優(yōu)化問題的復雜程度越來越高，特別是帶有約束條件的MOP問題，現(xiàn)有的算法往往難以兼顧優(yōu)化過程中算法的收斂性和解集的多樣性。

傳統(tǒng)的多目標算法往往將多目標優(yōu)化問題轉(zhuǎn)換成單目標問題進行求解，其最大的缺點在于一次只能求出一個解。目前，基于Pareto支配機制的粒子群優(yōu)化算法常用于求解MOP，這些算法主要的區(qū)別在于全局極值的選取方式和最優(yōu)解集的保存形式上。文獻[2]提出一種基于免疫網(wǎng)絡的改進多目標粒子群優(yōu)化（Multi-objective Particle Swarm Optimization， MOPSO）算法，改進的多目標粒子群算法和改進的聚類免疫網(wǎng)絡算法保證了算法的有效性。文獻[3]利用外部精英存儲策略，利用余弦距離排擠機制來選取最分散的粒子，從而增強算法的全局尋優(yōu)能力。文獻[4]依據(jù)Pareto支配關(guān)系對個體極值進行選擇，并計算外部存儲中粒子與其他粒子的海明距離之和作為適應值，采用輪盤賭方式選取粒子的全局最優(yōu)位置。文獻[5]提出一種ε占優(yōu)的自適應多目標粒子群算法，粒子動態(tài)組建鄰居，粒子速度由所有鄰居調(diào)整。文獻[6]提出用自適應網(wǎng)格法來維護外部集，以網(wǎng)格中的粒子數(shù)作為網(wǎng)格密度定義網(wǎng)格適應度值，從而求取全局極值。

本文提出一種改進的多目標粒子群優(yōu)化算法，使用帶有規(guī)模限制的外部檔案和在線歸檔技術(shù)，并改進了全局極值的選取策略，同時加入粒子越界處理保證種群的可行性。對幾個典型函數(shù)的仿真結(jié)果表明，該算法能有效地提高Pareto最優(yōu)前沿的收斂性和均勻分布。

1 多目標優(yōu)化問題

MOP是指多個目標同時需要優(yōu)化的問題，這些目標包含兩個或者兩個以上，同時多個目標之間相互制約。這些目標之間存在約束條件。MOP解集不唯一，可能存在多個解。

上式中，x為向量，維數(shù)為D，m為待優(yōu)化的目標函數(shù)的數(shù)目，[fi（x）]是第i個目標函數(shù)，[gj（x）]和[hk（x）]分別是第j個不等式約束和第k個等式約束條件。A和B分別代表其約束的總數(shù)。[xmind]和[xmaxd]為第d維向量搜索的上下限。endprint

公式（1）是m個目標對應的目標函數(shù)，公式（2）和（3）為其約束條件。本文假設每個目標都要求其最小值。理想情況下，可求得使每個目標函數(shù)均能取到最小值的x值。實際情況下，求取這樣的x值，使某個或某些目標更優(yōu)但同時犧牲其他一些目標值。這些x值為Pareto最優(yōu)解。所有Pareto最優(yōu)解組成的集合為Pareto前沿。

2 粒子群優(yōu)化算法

在粒子群優(yōu)化算法中，每個粒子附帶一個速度使粒子可以在可行解區(qū)域內(nèi)飛行，粒子根據(jù)自己和其他粒子的經(jīng)驗來調(diào)整飛行方向。在算法的迭代過程中，粒子始終追蹤個體極值（pbest）和全局極值（gbest）來調(diào)整速度和位置，以此來實現(xiàn)群體的進化。

式中：i為粒子編號，j為粒子的某個維度；t為迭代次數(shù)；[pbesti，j（t）]為第i個粒子第j維在第t次迭代中的個體極值；[gbesti，j][gdbest]為第t次迭代中所有粒子第j維的最好位置；[vi，j（t）]、[xi，j（t）]分別為第i個粒子第j維在第t次迭代中的速度和位置；w、c1和c2為速度更新時的權(quán)重系數(shù)；[fr1]和[fr2]產(chǎn)生0到1之間的隨機數(shù)。

3 基于密度距離的多目標粒子群算法

在確定多目標問題的Pareto最優(yōu)解的過程中，主要的評價標準體現(xiàn)在兩個方面，最終求得的非劣解集越接近真實的Pareto前沿、沿著Pareto前沿分布地越均勻，則效果越優(yōu)。

3.1 非劣解集的存儲與更新

為了求出初始非劣解集BP，首先要構(gòu)造出一個數(shù)據(jù)結(jié)構(gòu)形成兩個N行（種群規(guī)模）D列（問題維度）的二維矩陣，其中一個矩陣表示各粒子的位置，另一個表示各粒子趨向于各個維度的速度，并對其進行隨機初始化。為了防止速度和位置值過大或過小而導致解集分布不均勻，設定它們的上下限。將第一個粒子的位置直接賦給BP，然后開始初始化，通過粒子間的相互支配關(guān)系確定非劣解集的個數(shù)即根據(jù)各粒子之間的相互支配關(guān)系的比較，剔除被支配的粒子的位置，得出最優(yōu)或互不支配的解集即為非劣解集BP。

算法1：空間分布距離

//x，y分別為兩個D維的向量

gx=變量x在特定測試函數(shù)下的適應度值

gy=變量y在特定測試函數(shù)下的適應度值

gxy=（gx-gy）.^2；

空間劃分距離=sqrt（gxy個分量求和）

為了保持解集的均勻性，防止其陷入局部最優(yōu)，我們引入空間分布距離SD。空間分布距離即表示向量間的距離關(guān)系的矩陣，它是隨非劣解的增加而逐漸增加的，例如：當非劣解只有兩個時，它的空間分布距離矩陣為兩行兩列，這時由于對角線上元素表示各粒子內(nèi)部自身即空間分布距離為零，并且其關(guān)于對角線對稱的各元素相等。當非劣解每增加一個時，空間分布距離矩陣就會增加一行一列，以保持其始終和非劣解相聯(lián)系。

算法2：密集距離求取

r=空間分布距離SD的行數(shù)

c=空間分布距離SD的列數(shù)

Initialize d（密集距離）=一行r列的零向量

d（i）=SD中第i行的最小值

綜上，對求得的空間分布距離進行密集距離的計算即依次求出非劣解中空間分布距離最小解元素，將其組成一行多列的向量。

定義1：最優(yōu)種群極限T

定義T為非劣解集的種群極限，它限定了非劣解集的最大數(shù)量，限制了種群粒子的活動范圍同時保持適應度值的均勻性并且節(jié)省了一定的存儲空間。一旦非劣解的個數(shù)超過了最優(yōu)種群極限，需要對其進行約束管理即剔除其中密度距離最小的元素，使其始終處于最優(yōu)狀態(tài)。

3.2 速度和位置的更新方式

在更新速度和位置時，在原有更新公式基礎之上，可采取更好的方法使粒子下一次飛行中趨向更好的位置，以便于求解更優(yōu)的個體極值和全局極值。假設此時粒子有n個趨向即可以有n個方向來更新速度，當粒子在每一個方向更新速度后，再通過位置公式更新位置，故此時粒子共有n個趨向位置，再通過支配關(guān)系比較，即把n個位置中被支配的位置剔除，其余為互不支配的較優(yōu)的位置，再從中隨機選擇一個當作粒子將要達到的位置，通過速度位置關(guān)系求出速度。綜上，此方法可以從多個趨向中選擇最優(yōu)的速度和位置，比單一的更新公式具有更好的收斂性和準確性，是一個值得推廣的算法。

3.3 外部檔案的更新方式

使用外部檔案（External Archive，EA）來存儲算法每一次迭代產(chǎn)生的一組非劣解。外部檔案初始化為空，隨著迭代的進行，每一代所產(chǎn)生的非劣解用來更新外部檔案。外部存檔的規(guī)模逐漸增加，其計算復雜度呈指數(shù)級別增長，傳統(tǒng)的PSO粒子優(yōu)化算法采用擁擠距離來限制外部檔案的規(guī)模[8]。為了防止粒子群的退化，使用一種在線歸檔技術(shù)來更新外部檔案[9]，即把外部檔案中的精英粒子引入下一代的進化種群中，使得外部檔案中的精英粒子和新一代種群中的粒子一起競爭，從而更新非劣解集。這樣做的好處是若粒子群在迭代過程中出現(xiàn)了退化的粒子，則直接淘汰，保證了種群一直向目標方向進化，提高了尋優(yōu)效率。

3.4 全局極值的選取方式

目前確定全局最優(yōu)位置的常用方法為從外部檔案中保存的已經(jīng)找到的最優(yōu)解中隨機選取最優(yōu)位置[10]。有的文獻里介紹全局極值的確定不但使用外部檔案選取，還應用輪盤賭方法根據(jù)各最優(yōu)解的擁擠距離來確定[11]。但該方法隨著迭代次數(shù)的增加，該外部集合中的最優(yōu)解數(shù)量也會迅速增加，從而會影響程序的運行速度。本文為了更為準確的求得全局極值，引入了稀疏距離的概念。

定義2：稀疏距離

通常來說，根據(jù)密集距離移除超出非劣解集規(guī)模限制情況下的某些粒子是一種維持外部檔案規(guī)模的有效方法。為了更廣泛地考察某粒子周圍其他粒子的分布情況，提出了稀疏距離的概念。稀疏距離更能反映出當前非劣解集中某粒子為核心的周圍群體的密度大小。在特定概率下，判定了每個非劣解的稀疏距離后，從而選取當前稀疏距離較大的粒子作為全局最優(yōu)解，在保證均勻分布的前提下保證了非劣解的多樣性。endprint

算法3：稀疏矩陣算法

r=空間分布距離SD的行數(shù)；

c=空間分布距離SD的列數(shù)；

Initialize s（稀疏距離）=zeros（1，r）；

s（i）=SD中第i行的兩個次小值求均值

3.5 粒子的越界處理

在粒子的不斷運動和更新中，有一定的幾率會飛出事先設定好的上下界，所以有必要在算法中進行越界處理。我們考慮到了三種處理方法，其中一種是使越界的粒子停留在邊界處，速度方向與之前相反，大小不變；另一種是通過相關(guān)的越界公式對粒子的位移和速度進行隨機初始化；第三種是返回粒子越界前的位置，然后對其速度進行隨機初始化，然后重新更新粒子的位移。

3.6 算法流程

1） 隨機初始化粒子種群，設置參數(shù)。

2） 求解各目標的函數(shù)值，按照適應度確定支配關(guān)系。如果新粒子支配原種群中的粒子，則剔除原粒子加入新粒子，如果互不支配，則加入新粒子。

3） 從非劣解集中選取全局極值。同時確定個體極值。并且更新外部檔案。

4） 根據(jù)速度和位置更新公式，更新種群位置。若是超出邊界，則按粒子的越界處理方式拉回邊界。

5） 滿足迭代次數(shù)算法結(jié)束，否則回到步驟2）。

4 仿真結(jié)果及分析

在這里我們選用文獻[12]中的三個測試函數(shù)進行測試，在相同的配置環(huán)境下，通過多次測試，對結(jié)果進行分析。

在仿真計算過程中，公式（5）中的相關(guān)參數(shù)設置如下：慣性權(quán)重[ω]從1.0慣性下降到0.4，[fr1]和[fr2]為[0，1]的隨機數(shù)，種群規(guī)模分別設置為50和100兩種不同的情況，以便對比仿真結(jié)果?？偟螖?shù)為200次，外部檔案的大小為100。算法采用Matlab編程，重復運行30次。

仿真結(jié)果如圖1至圖6所示。

算法的局部時間復雜度分析如下。對于每個多目標優(yōu)化的標準測試函數(shù)來說，假設迭代過程中設定種群規(guī)模為N，問題維度為D，非劣解集的容量為T，目標數(shù)為m。在確定一個新的粒子x是否應進入非劣解集時，需要判斷此粒子與所有非劣解的支配關(guān)系，而支配關(guān)系的值取決于x與此解各目標函數(shù)值的關(guān)系，因此這個比較過程的時間復雜度為[Ο（Tm）]，則種群中所有粒子的判定過程時間復雜度為[Ο（NTm）]。

從仿真結(jié)果可以看出，對粒子群的迭代達到一定次數(shù)，Pareto解集趨向穩(wěn)定，解集呈現(xiàn)均勻性。從算法的角度來看，大約經(jīng)過50次左右迭代基本可以找到Pareto前沿。通過對同一個測試函數(shù)在不同的種群規(guī)模下迭代的結(jié)果進行比較可以看出，隨著種群規(guī)模的不斷增大，其曲線的平滑度更好，非劣解的密度更大，從而在具體問題上給決策者提供更多選擇。

采用文獻[13]提出的算法評價標準對本文算法測試的三個經(jīng)典問題進行評價，包括兩個方面：

1） 收斂度。從目標空間中真實Pareto前沿均一地尋找一個空間解的集合H=500。對于算法獲得的每一個解，我們計算它與Pareto最優(yōu)前沿上H個選定解的最小歐氏距離。這些距離的平均值作為對問題尋優(yōu)結(jié)果的收斂度。

2） 多樣性。若所得Pareto非劣解集均勻分布在決策空間中，則認為解保持了較好的多樣性。定義如下：

兩個性能指標的計算結(jié)果和與其他主流算法的對比情況如表2和表3所示。可以看出，在收斂度方面，本文算法在多次測試中取得了較滿意的均值和方差。SCH測試函數(shù)的優(yōu)化情況與NSGAⅡ和SPEA算法相當，而在ZDT1和ZDT2兩個函數(shù)中，效果均明顯好于NSGAⅡ，但略遜于SPEA。這與測試函數(shù)的特點及算法迭代的隨機效果密切相關(guān)。解的多樣性方面，對每個測試函數(shù)的均勻分布情況的計算均收到了較好的效果。且多次運行的結(jié)果所得多樣性的方差值均較小，說明算法的穩(wěn)定性較好。未來的研究將進一步改善算法，并分析用于其他問題的優(yōu)化中。

5 結(jié)論

本文主要對基于粒子群算法實現(xiàn)多目標優(yōu)化問題進行研究，提出了一種求解多目標優(yōu)化問題的多目標粒子群算法。采用改進的外部存檔方式保存非劣解集；利用密集距離保持解集的多樣性，稀疏距離選取全局極值，引導粒子飛行，保證解集分布的均勻性。同時加入對粒子的越界處理，使得粒子在規(guī)定范圍內(nèi)飛行，保證收斂效果。通過對幾個典型測試函數(shù)的仿真計算可以看出，該算法能較好地解決一般的多目標問題，得到滿意的Pareto前沿，今后有望用于工程實踐中的其他多目標優(yōu)化問題。

參考文獻：

[1] 陳深，肖俊陽，黃玉程，等. 基于改進量子粒子群算法的微網(wǎng)多目標優(yōu)化調(diào)度[J]. 電力科學與技術(shù)學報，2015，30（2）：41-47.

[2] 馮琳，毛志忠，袁平.一種改進的多目標粒子群優(yōu)化算法及其應用[J].控制與決策，2012，27（9）：1313-1319.

[3] 方欣欣，龔如賓，李大為. 基于余弦距離的多目標粒子群優(yōu)化算法[J]. 電子科技，2016，29（03）：48-52+57.

[4] 陳萍，毛弋，童偉，鄧海潮，陳艷平，胡躲華. 基于多目標粒子群算法的配電網(wǎng)多目標優(yōu)化重構(gòu)[J]. 電力系統(tǒng)及其自動化學報，2016，28（7）：68-72.

[5] 劉衍民，趙慶禎，牛奔，邵增珍.基于ε占優(yōu)的自適應多目標粒子群算法[J].控制與決策，2011，26（1）：89-95.

[6] 劉華鎣，王靜，許少華，孫毅.基于空間劃分樹的多目標粒子群優(yōu)化算法[J].吉林大學學報：理學版，2011，49（4）：696-702.

[7] 徐鳴，沈希，馬龍華，等.一種多目標粒子群改進算法的研究[J].控制與決策，2009，24（11）：1713-1718，1728.

[8] 劉衍民，牛奔，趙慶禎.多目標優(yōu)化問題的粒子群算法仿真研究[J].計算機應用研究，2011，28（2）：458-460.

[9] 王麗，劉玉樹，徐遠清.基于在線歸檔技術(shù)的多目標粒子群算法[J].北京理工大學學報，2006，26（10）：458-460.

[10] Peng Chunhua， Sun Huijuan， Guo Jianfeng. Multi-objective optimal PMU placement using a non-dominated sorting differential evolution algorithm[J]. International Journal of Electrical Power and Energy Systems， 2010， 32（8）：886-892.

[11] 劉剛，彭春華，相龍陽.采用改進型多目標粒子群算法的電力系統(tǒng)環(huán)境經(jīng)濟調(diào)度[J].電網(wǎng)技術(shù)，2011，35（7）：139-144.

[12] 裴勝玉，周永權(quán).基于Pareto最優(yōu)解集的多目標粒子群優(yōu)化算法[J].計算機工程與科學，2010，32（11）：85-88.

[13] Kalyanmoy Deb， Amrit Pratap， Sameer Agarwal， T. Meyarivan. A fast and elitist multiobjective genetic algorithm： NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary computation， 2002， 6（2）：182-197.endprint