劉少偉+朱永利

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

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

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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í)踐中的很多實(shí)際問題在進(jìn)行數(shù)學(xué)建模以后，都可以抽象為一個(gè)多目標(biāo)的優(yōu)化問題。多目標(biāo)優(yōu)化問題（Multi-objective Optimization Problem， MOP）通常不存在某個(gè)絕對(duì)的最優(yōu)解，使得各目標(biāo)均同時(shí)達(dá)到令人滿意的結(jié)果[1]。隨著優(yōu)化問題的復(fù)雜程度越來(lái)越高，特別是帶有約束條件的MOP問題，現(xiàn)有的算法往往難以兼顧優(yōu)化過程中算法的收斂性和解集的多樣性。

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

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

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

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

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

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

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

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

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

3 基于密度距離的多目標(biāo)粒子群算法

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

3.1 非劣解集的存儲(chǔ)與更新

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

算法1：空間分布距離

//x，y分別為兩個(gè)D維的向量

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

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

gxy=（gx-gy）.^2；

空間劃分距離=sqrt（gxy個(gè)分量求和）

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

算法2：密集距離求取

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

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

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

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

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

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

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

3.2 速度和位置的更新方式

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

3.3 外部檔案的更新方式

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

3.4 全局極值的選取方式

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

定義2：稀疏距離

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

算法3：稀疏矩陣算法

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

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

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

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

3.5 粒子的越界處理

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

3.6 算法流程

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

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

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

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

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

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

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

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

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

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

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

采用文獻(xiàn)[13]提出的算法評(píng)價(jià)標(biāo)準(zhǔn)對(duì)本文算法測(cè)試的三個(gè)經(jīng)典問題進(jìn)行評(píng)價(jià)，包括兩個(gè)方面：

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

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

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

5 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

[9] 王麗，劉玉樹，徐遠(yuǎn)清.基于在線歸檔技術(shù)的多目標(biāo)粒子群算法[J].北京理工大學(xué)學(xué)報(bào)，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] 劉剛，彭春華，相龍陽(yáng).采用改進(jìn)型多目標(biāo)粒子群算法的電力系統(tǒng)環(huán)境經(jīng)濟(jì)調(diào)度[J].電網(wǎng)技術(shù)，2011，35（7）：139-144.

[12] 裴勝玉，周永權(quán).基于Pareto最優(yōu)解集的多目標(biāo)粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與科學(xué)，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