基于種群曼哈頓距離的自適應(yīng)多目標(biāo)粒子群優(yōu)化算法

李浩君，張鵬威，郭海東

(1.浙江工業(yè)大學(xué) 教育科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023；2.杭州市電子信息職業(yè)學(xué)校，浙江 杭州 310021)

0 引言

多目標(biāo)優(yōu)化問題廣泛存在于現(xiàn)實世界中，智能優(yōu)化算法作為一種解決多目標(biāo)優(yōu)化問題方法被深入研究，涌現(xiàn)出很多優(yōu)秀的多目標(biāo)優(yōu)化算法，并對這些算法進(jìn)行了改進(jìn)。如非支配排序遺傳算法(Non-Dominated Sorted Genetic Algorithm-Ⅱ, NSGA-Ⅱ)[1]、增強Pareto進(jìn)化算法(Strength Pareto Evolutionary Algorithm, SPEA-Ⅱ)[2]、精英保留進(jìn)化策略(Pareto Envelope-based Selection Algorithm Ⅱ, PESA-Ⅱ)[3]、基于分解策略的多目標(biāo)進(jìn)化算法(Multi-objective Evolutionary Algorithm Based on Decomposition, MOEA/D)[4]等；文獻(xiàn)[5]采用NSGA-Ⅱ框架提出了基于參考點的多目標(biāo)遺傳算法(Non-Dominated Sorted Genetic Algorithm-Ⅲ, NSGA-Ⅲ);文獻(xiàn)[6]對基于分解策略的多目標(biāo)進(jìn)化算法進(jìn)行改進(jìn)，提出了MOEA/D_FRRMAB(fitness-rate-rank-based multi-armed bandit)算法；傳統(tǒng)的進(jìn)化算法(Evolutionary Algorithm, EA)遵循著精英個體的適者生存規(guī)則，然而，常見的交叉算子在不同的情況下具有著不同的靈敏度[7]。Moore等[8]嘗試將粒子群算法用于解決多目標(biāo)優(yōu)化問題，與其他進(jìn)化算法相比，粒子群算法具有面向領(lǐng)導(dǎo)粒子的學(xué)習(xí)機制保證了快速收斂性能，且具有參數(shù)少、易于實現(xiàn)等優(yōu)勢[9]，在不同多目標(biāo)問題(Multi-objective Problem)上都具有較好表現(xiàn)[10-11]。

為了提高多目標(biāo)粒子群優(yōu)化算法的收斂性能和多樣性能，國內(nèi)外學(xué)者從引導(dǎo)粒子的選擇、外部檔案的維護(hù)與更新以及算法搜索方式和認(rèn)知參數(shù)調(diào)整等角度展開了眾多優(yōu)化工作。在引導(dǎo)粒子的選擇方面：文獻(xiàn)[12]采用擁擠距離策略進(jìn)行全局最優(yōu)粒子的選取；文獻(xiàn)[13]采用隨機策略從非支配解中選擇最優(yōu)粒子。在外部檔案的維護(hù)與更新方面：文獻(xiàn)[14]提出了較為經(jīng)典的(Multi-Objective Particle Swarm Optimization, MOPSO)算法，采用Pareto支配關(guān)系和自適應(yīng)網(wǎng)格技術(shù)進(jìn)行外部存檔的更新與維護(hù)；文獻(xiàn)[15]設(shè)計了融合共享學(xué)習(xí)和動態(tài)擁擠距離應(yīng)用策略的MOPSO算法，采用動態(tài)擁擠距離策略用于維護(hù)外部檔案；文獻(xiàn)[16]運用簡化的k-最近鄰方法進(jìn)行檔案維護(hù)。在算法搜索方式和認(rèn)知參數(shù)調(diào)整方面：文獻(xiàn)[17]使用外部檔案中的更新個體來指導(dǎo)群體進(jìn)化探索，并設(shè)計局部隨機最優(yōu)與全局最優(yōu)差分向量作為速度更新的一部分，有效解決了收斂速度過快往往導(dǎo)致多樣性丟失的問題；文獻(xiàn)[18]提出了時變多目標(biāo)粒子群算法，慣性權(quán)重和學(xué)習(xí)因子隨著迭代次數(shù)動態(tài)變化?，F(xiàn)有改進(jìn)策略在進(jìn)行算法優(yōu)化時，較多優(yōu)化策略未考慮種群的進(jìn)化信息，不能根據(jù)進(jìn)化環(huán)境檢測到的反饋信息實時調(diào)整優(yōu)化策略[19-20]，導(dǎo)致算法收斂性能與多樣性能的失衡。因此，有學(xué)者考慮算法的進(jìn)化狀態(tài)，分階段采用不同的策略實現(xiàn)算法整體性能的提升。文獻(xiàn)[20]利用平行單元坐標(biāo)系(Parallel Cell Coordinate System, PCCS)方法評估進(jìn)化環(huán)境，提出一種基于PCCS的自適應(yīng)多目標(biāo)粒子群優(yōu)化算法；文獻(xiàn)[21]根據(jù)預(yù)先設(shè)定的閾值大小，提出采用兩種搜索策略更新粒子位置，提高M(jìn)OPSO算法的搜索性能，保持種群多樣性；文獻(xiàn)[22]設(shè)計了一種完成-檢驗因子，并將該因子與外部檔案數(shù)量的關(guān)系作為進(jìn)化狀態(tài)判斷的依據(jù)，以此動態(tài)改變速度更新模式，分別采用全局探索與局部開采的速度更新模式，平衡勘探和開發(fā)；文獻(xiàn)[23]基于解分布熵分析進(jìn)化趨勢，判斷非支配解的分布狀態(tài)來選擇合適的引導(dǎo)粒子，并利用種群間隔信息spacing分析種群的分布狀態(tài)來設(shè)置自適應(yīng)飛行參數(shù)調(diào)整機制；文獻(xiàn)[24]根據(jù)Pareto熵和差熵來反應(yīng)種群的多樣性和進(jìn)化狀態(tài)信息，以此自適應(yīng)調(diào)節(jié)開發(fā)與開采過程的進(jìn)化策略；文獻(xiàn)[25]基于先驗解與粒子新解之間的主導(dǎo)關(guān)系判斷進(jìn)化過程中的多樣性信息，設(shè)計自適應(yīng)飛行參數(shù)，平衡算法的多樣性能和收斂性能；文獻(xiàn)[26]在算法進(jìn)化過程中，通過計算非支配解的數(shù)量來評估算法的全局和局部搜索能力，如果在搜索過程中發(fā)現(xiàn)更多的非支配解則使用Sigma方法來提高搜索精度和收斂速度，否則選擇具有更小密度值的非支配解，以增強算法的全局搜索能力，文獻(xiàn)[27]提出基于網(wǎng)格策略的多目標(biāo)粒子群優(yōu)化算法，當(dāng)非支配解分布指數(shù)低于給定閾值時，利用隨機方法從外部檔案中選擇非劣解引導(dǎo)種群飛行，但當(dāng)分布指數(shù)高于給定閾值時，引入了基于網(wǎng)格的全局最優(yōu)粒子選擇策略，增強多樣性能；文獻(xiàn)[28]將算法的進(jìn)化過程分為3個層次，以此獲得更好的粒子位置和全局最優(yōu)解，提高算法的收斂性和多樣性。文獻(xiàn)[29]通過統(tǒng)計方法評估種群的進(jìn)化狀態(tài)和多樣性，并以此提出兩種歸檔集維護(hù)策略和引導(dǎo)粒子選擇策略，根據(jù)算法進(jìn)化狀態(tài)動態(tài)切換優(yōu)化方式，所提策略同時兼顧了算法的收斂性能和多樣性能。

鑒于算法的進(jìn)化環(huán)境對算法收斂性能與多樣性能具有重要影響，本文提出利用種群曼哈頓距離檢測算法的進(jìn)化狀態(tài)，根據(jù)反饋信息調(diào)整優(yōu)化策略；已有研究表明，單速度更新模式易導(dǎo)致算法過度探索或過度開發(fā)[22]，且受多種搜索策略綜合運用能夠提高單目標(biāo)PSO性能的啟發(fā)[21]，本文在設(shè)計基于Levy飛行探索認(rèn)知行為的粒子速度更新策略基礎(chǔ)上，采用多種搜索策略提高算法性能；進(jìn)一步提出基于進(jìn)化狀態(tài)的參數(shù)自適應(yīng)調(diào)整策略，平衡算法的收斂性能和多樣性能。

1 多目標(biāo)粒子群優(yōu)化算法

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

不失一般性，一個多目標(biāo)優(yōu)化問題可以用下式表示：

minF(x)=(f1(x),f2(x),…,fm(x))T;

(1)

其中：x∈Ω是決策向量，Ω是決策空間，x∈(x1,x2,…,xn)T是搜索空間Ω中的一個點。F:Ω→Rm,Rm是目標(biāo)空間。(f1(x),f2(x),…,fm(x))表示m個目標(biāo)函數(shù)，gu(x)≤0,u=1,2,…,p;表示目標(biāo)函數(shù)的p個不等式約束條件：hv(x)=0,v=1,2,…,l;表示目標(biāo)函數(shù)的l個等式約束條件。一般情況下，式中f1(x),f2(x),…,fm(x)各個目標(biāo)之間是存在沖突的，因此，在決策空間Ω不會存在使所有目標(biāo)函數(shù)同時達(dá)到最優(yōu)的點。關(guān)于多目標(biāo)問題中的相關(guān)定義如下。

定義1可行解?？尚薪馐菨M足多目標(biāo)問題中約束條件的解，即

X={x|gu(x)≤0,hv(x)=0}。

(2)

定義2Pareto支配。如果向量x=(x1,x2,…,xM)∈RM支配向量y=(y1,y2,…,yM)∈RM，記作xyxy，當(dāng)且僅當(dāng)

(?i∈{1,2,…,m}:fi(x)≤fi(y))∧

(?j∈{1,2,…,m}:fj(x)≤fj(y))。

(3)

定義3Pareto最優(yōu)解。若x*是多目標(biāo)F(x)的Pareto最優(yōu)解，當(dāng)且僅當(dāng)滿足以下條件：對?x∈Ω不存在f(x)≤f(x*)(或f(x)

?xx*。

(4)

1.2 多目標(biāo)粒子群優(yōu)化算法

粒子群算法模仿鳥群覓食行為的過程，最初被用于解決單目標(biāo)優(yōu)化問題，隨著對PSO算法的研究改進(jìn)及實際問題的需求，提出了多目標(biāo)粒子群優(yōu)化算法(MOPSO)，用來解決復(fù)雜的多目標(biāo)優(yōu)化問題。在MOPSO算法中，粒子速度向量的更新同樣由速度慣性、自我學(xué)習(xí)和社會學(xué)習(xí)3部分組成，粒子在t+1代的位置更新由粒子第t代的位置與t+1代的速度向量決定。具體如下：

(5)

i=1,2,…,n。

(6)

其中：i表示粒子；j表示粒子的維度；ω是慣性權(quán)重；t表示迭代次數(shù)；c1表示自我學(xué)習(xí)因子，c2表示社會學(xué)習(xí)因子，c1和c2用來調(diào)粒子個體學(xué)習(xí)部分和社會學(xué)習(xí)部分的比重；r1和r2是[0,1]之間的隨機數(shù)；pij表示粒子i的個體最優(yōu)解；gij表示種群中找到的全局最優(yōu)解。

2 基于種群曼哈頓距離(PMD)的pmdMOPSO算法

pmdMOPSO(multi-objective particle swarm optimization algorithm based on population manhattan distance)算法通過曼哈頓距離檢測種群實時的進(jìn)化信息。在算法初始進(jìn)化階段，算法采用基本的粒子搜索模式；之后計算第t-1代種群曼哈頓距離與前t-2代中最小種群曼哈頓距離之間的關(guān)系，將進(jìn)化狀態(tài)分為探索和收斂兩個階段，分別采用不同策略的速度更新模式。針對粒子速度更新方程，本文提出具有Levy飛行探索認(rèn)知行為的速度更新策略，賦予最優(yōu)粒子探索解空間新區(qū)域的能力，增強算法的全局尋優(yōu)性能。在此基礎(chǔ)上，種群進(jìn)化時，根據(jù)曼哈頓距離信息動態(tài)非線性設(shè)計進(jìn)化參數(shù)，實現(xiàn)進(jìn)化參數(shù)的自適應(yīng)調(diào)整，平衡算法全局探索和局部開采的能力，實現(xiàn)算法收斂性能和多樣性能的平衡。pmdMOPSO算法采用個體間的支配關(guān)系選擇個體歷史最優(yōu)，采用支配關(guān)系和輪盤賭策略從外部檔案中挑選全局最優(yōu)粒子；外部檔案的維護(hù)采用自適應(yīng)網(wǎng)格技術(shù)。

2.1 定義種群曼哈頓距離

種群的進(jìn)化處于動態(tài)的不斷變化中，合理判斷種群的進(jìn)化狀態(tài)是設(shè)計認(rèn)知參數(shù)的重要前提，只有根據(jù)進(jìn)化狀態(tài)動態(tài)調(diào)整認(rèn)知參數(shù)才能符合種群的進(jìn)化需求，實現(xiàn)算法性能的提升。本文通過種群曼哈頓距離檢測種群的多樣性狀態(tài)來反應(yīng)算法的整體進(jìn)化情況。

定義種群曼哈頓距離PMD(population Manhattan distance)為種群中每個粒子與其它粒子之間最小曼哈頓距離的均值。粒子之間的曼哈頓距離MD(Manhattan distance)可以用式(7)計算：

(7)

式中：dim表示維度。dij即為第i個粒子和第j個粒子之間的曼哈頓距離MD，對MD排序獲得每個粒子與其他粒子之間的最小曼哈頓距離min(MD)，如式(8)所示：

Sort(MD)→min(MD)。

(8)

進(jìn)一步對min(MD)求均值獲得種群曼哈頓距離PMD，如式(9)所示：

(9)

設(shè)算法最大迭代次數(shù)為T，則第t-1代的種群曼哈頓距離可用PMD(t-1)表示，1≤t≤T。定義表達(dá)式(10)為前t-1代種群曼哈頓距離的集合：

PMD[1:(t-1)]。

(10)

則前t-2代中最小種群曼哈頓距離可以用式(11)計算：

min(PMD[1:(t-2)])。

(11)

2.2 利用種群曼哈頓距離檢測進(jìn)化狀態(tài)

通過判定第t-1代種群曼哈頓距離PMD(t-1)的值與前t-2代中最小種群曼哈頓距離之間的大小關(guān)系，將種群進(jìn)化狀態(tài)分為探索與收斂階段。如果第t-1代PMD值大于前t-2代中最小PMD值，判定當(dāng)前進(jìn)化狀態(tài)為探索階段，種群多樣性較好，此時第t代種群采用局部開采能力強的速度更新方程提升搜索精度。如果第t-1代PMD值小于前t-2代中最小PMD值，判定當(dāng)前進(jìn)化狀態(tài)為收斂階段，收斂階段種群多樣性較差，此時第t代種群采用全局探索能力強的速度更新方程增強多樣性；通過不同階段采用對應(yīng)的速度更新方程，實現(xiàn)算法全局探索與局部開采的平衡，提升算法的收斂性能和多樣性能。

2.3 基于Levy飛行最優(yōu)粒子探索認(rèn)知的速度動力學(xué)方程

基本的多目標(biāo)粒子群算法中，速度更新方程由粒子當(dāng)前位置、個體認(rèn)知和全局認(rèn)知3部分組成。在pmdMOPSO算法中，除上述3部分外，設(shè)計了基于Levy飛行的最優(yōu)粒子探索認(rèn)知部分，當(dāng)種群多樣性能較差時，最優(yōu)粒子通過探索認(rèn)知提高探索解空間新區(qū)域的能力，提高多樣性，帶領(lǐng)種群向偏離局部最優(yōu)的方向進(jìn)化，有效避免種群陷入局部最優(yōu)?；贚evy飛行最優(yōu)粒子探索認(rèn)知實現(xiàn)的速度動力學(xué)方程如下：

(12)

式中：ω為慣性權(quán)重，c1為自我認(rèn)知系數(shù)，c2為社會認(rèn)知系數(shù)，c3為探索認(rèn)知系數(shù)；pij為個體歷史最優(yōu)，gij為全局最優(yōu)；r為一個隨機數(shù)。

Levy公式如下:

(13)

(14)

其中：r1(1,d)、r2(1,d)為[0,1]之間的隨機數(shù)；levy(λ)為隨機步長，λ為冪次數(shù)；β=1.5。

2.4 pmdMOPSO算法自適應(yīng)速度更新模式

pmdMOPSO算法在搜索初期，采用基本的速度更新模式v1，如式(5)所示。pmdMOPSO算法通過種群曼哈頓距離將種群進(jìn)化狀態(tài)分為探索與收斂兩個階段，如果t-1代的種群曼哈頓距離小于或等于前t-2代最小種群曼哈頓距離時，表明粒子多樣性能較差，種群處于收斂階段，此時在t代采用全局探索能力強的速度更新模式v2幫助種群跳出局部最優(yōu)，如式(12)所示。如果t-1代的種群曼哈頓距離大于前t-2代最小種群曼哈頓距離時，表明粒子多樣性能較好，種群處于探索階段，此時在t代采用局部開采能力強的速度更新模式v3提高算法精度，如式(15)所示：

(15)

(16)

式(16)為pmdMOPSO算法自適應(yīng)速度更新模式，pmdMOPSO算法通過采用不同功能的速度更新模式，有效平衡算法在進(jìn)化過程中的探索與開采階段，實現(xiàn)收斂性能與多樣性能的均衡。

2.5 認(rèn)知參數(shù)自適應(yīng)調(diào)整策略

pmdMPSO算法的認(rèn)知參數(shù)包含慣性權(quán)重參數(shù)ω、個體認(rèn)知參數(shù)c1、社會認(rèn)知參數(shù)c2和探索認(rèn)知參數(shù)c3。根據(jù)種群曼哈頓距離檢測到的種群進(jìn)化狀態(tài)信息，結(jié)合算法的進(jìn)化代數(shù)，設(shè)計自適應(yīng)進(jìn)化參數(shù)如下：

(17)

(18)

(19)

其中：pmd(t-1)表示第(t-1)代種群曼哈頓距離；min(pmd[1:(t-2)])表示前(t-2)代中最小種群曼哈頓距離。以二者的差分向量為基礎(chǔ)構(gòu)建自適應(yīng)調(diào)整策略。當(dāng)ω、c1較大時，全局探索能力強，反之局部開采能力強，因此，設(shè)計式(17)和式(18)使二者呈整體遞減趨勢；當(dāng)c2較大時，算法開采能力強，因此設(shè)計式(19)使全局認(rèn)知呈整體遞增趨勢，c3為探索認(rèn)知系數(shù)，探索認(rèn)知行為有助于算法在進(jìn)化后期維持種群多樣性，跳出局部最優(yōu)，因此采用和c2相同的策略使探索認(rèn)知呈整體遞增趨勢。

2.6 pmdMOPSO算法的引導(dǎo)粒子選擇策略

pmdMOPSO算法根據(jù)支配關(guān)系選擇最優(yōu)個體；如果當(dāng)前個體xi支配個體歷史最優(yōu)pi，則將當(dāng)前xi作為最優(yōu)個體；如果個體歷史最優(yōu)pi支配當(dāng)前個體xi，則個體最優(yōu)保持不變；如果二者互不支配，則從中隨機選擇一個作為最優(yōu)個體。全局最優(yōu)粒子從外部檔案中選擇，在進(jìn)化過程中，通過支配關(guān)系將支配粒子存入外部檔案，并采用輪盤賭選擇策略從外部檔案中選取全局最優(yōu)粒子。

2.7 pmdMOPSO算法的檔案存儲及更新策略

pmdMOPSO算法根據(jù)Pareto支配關(guān)系和自適應(yīng)網(wǎng)格技術(shù)實現(xiàn)外部檔案的存儲與更新。首先，如果當(dāng)前粒子支配外部檔案中的粒子，則將當(dāng)前粒子存放到外部檔案中，并刪減外部檔案中被支配的粒子；然后，檢測當(dāng)前非支配解數(shù)量與所設(shè)定的外部檔案數(shù)量的大小，如果儲存的當(dāng)前非支配解個數(shù)超過所設(shè)定大小，則采用自適應(yīng)網(wǎng)格技術(shù)刪減密度比較大的個體，實現(xiàn)外部檔案的更新和維護(hù)。

2.8 pmdMOPSO算法流程

pmdMOPSO算法如下：

輸入：種群數(shù)量N，目標(biāo)數(shù)量M，外部檔案Archive，迭代次數(shù)T；

輸出：外部檔案集，即多目標(biāo)pareto最優(yōu)解集。

步驟1初始化粒子種群數(shù)量，初始化認(rèn)知參數(shù)、領(lǐng)導(dǎo)粒子及外部檔案等；

步驟2判斷迭代次數(shù)是否小于等于2，如果是，則粒子采用基本的速度更新公式進(jìn)行速度更新，并更新粒子位置；如果否，則判斷第t-1代種群曼哈頓距離與前t-2代中最小種群曼哈頓距離之間的關(guān)系，如果t-1種群曼哈頓距離大于前t-2代中最小種群曼哈頓距離，說明當(dāng)前種群多樣性較好，則在第t代采用局部開采能力較強的粒子速度更新公式；反之，說明當(dāng)前種群多樣性較差，則在第t代采用全局探索能力較強的粒子速度更新公式。

步驟3計算各粒子在M個目標(biāo)函數(shù)上的適應(yīng)度值；

步驟4如果隨機值小于變異因子pm，則對粒子位置進(jìn)行變異，計算新解；并判斷新解與當(dāng)前解的支配關(guān)系，如果新解支配當(dāng)前解，選擇新解作為新的當(dāng)前解；否則保持當(dāng)前解不變；

步驟5計算當(dāng)前粒子與種群中其他粒子之間的曼哈頓距離，獲得當(dāng)前粒子的最小曼哈頓距離；

步驟6計算種群中所有粒子之間的曼哈頓距離，獲得種群中所有粒子的最小曼哈頓距離，求其均值，即為種群曼哈頓距離PMD；

步驟7根據(jù)當(dāng)前解與個體最優(yōu)的支配關(guān)系，利用獲得的新非支配解更新M個目標(biāo)上的粒子個體最優(yōu)；

步驟8判斷新非支配解與外部檔案中非支配解的支配關(guān)系，若新非支配解不被外部檔案中任何一個解所支配，則將新非支配解存入外部檔案中作為新增非支配解，否則不加入外部檔案中；如果外部檔案數(shù)量超出設(shè)定數(shù)量，采用自適應(yīng)網(wǎng)格技術(shù)對外部檔案進(jìn)行維護(hù)；

步驟9采用輪盤賭策略從外部檔案中選擇領(lǐng)導(dǎo)粒子；

步驟10更新慣性權(quán)重及認(rèn)知參數(shù)。

步驟11如果未達(dá)到終止條件，則返回步驟2；否則輸出多目標(biāo)pareto最優(yōu)解集。

pmdMOPSO算法偽代碼

開始

初始化：種群數(shù)量N、目標(biāo)個數(shù)M

外部檔案Archive數(shù)量、領(lǐng)導(dǎo)粒子；

慣性權(quán)重ω、認(rèn)知系數(shù)c1、c2、c3及曼哈頓距離MD；

for t=1:MaxIt

for i=1:noP

if t≤2

采用公式(5)進(jìn)行速度更新；

elseif PMD(t-1)≤min(pmd[1:(t-2)])

采用公式(12)進(jìn)行速度更新；

elseif PMD(t-1)>min(pmd[1:(t-2)])

采用公式(15)進(jìn)行速度更新；

end

更新粒子位置；

分別計算粒子i在M個目標(biāo)函數(shù)上的適應(yīng)度值；

計算變異概率pm

if rand≤pm

對粒子當(dāng)前位置進(jìn)行變異；

判斷當(dāng)前位置與新位置的支配關(guān)系，保留支配解；

end

根據(jù)粒子支配關(guān)系更新粒子在M個目標(biāo)上的個體最優(yōu)；

根據(jù)新非支配解與外部檔案中非支配解的關(guān)系判斷新非支配解是否加入到外部檔案中。

for j=2:noP

計算粒子i與其它粒子之間的曼哈頓距離MD；

end

當(dāng)前粒子與其他所有粒子之間最小的曼哈頓距離min(MD)；

end

儲存每一代的種群曼哈頓距離PMD；

rep←～(IsDominated)

刪除rep中被支配解

采用自適應(yīng)網(wǎng)格技術(shù)對rep進(jìn)行維護(hù)；

采用輪盤賭策略從外部檔案中選擇全局最優(yōu)；

慣性權(quán)重ω、個體認(rèn)知系數(shù)c1、社會認(rèn)知系數(shù)c2、探索認(rèn)知系數(shù)c3自適應(yīng)更新。

end

pmdMOPSO算法通過曼哈頓距離檢測種群的進(jìn)化狀態(tài)，實現(xiàn)搜索模式與認(rèn)知參數(shù)的自適應(yīng)調(diào)整，有效提高算法的收斂性能和多樣性能。

2.9 pmdMOPSO算法復(fù)雜度分析

假設(shè)種群規(guī)模為N，優(yōu)化的目標(biāo)數(shù)為M，本文設(shè)置外部檔案數(shù)量為(1/2)N，則在某一次迭代內(nèi)，pmdMOPSO算法主要操作的復(fù)雜度估計為：

(1)初始化操作的復(fù)雜度為O(MN)；

(2)計算粒子適應(yīng)度值的復(fù)雜度為O(MN)；

(3)計算粒子與種群中其他粒子之間的曼哈頓距離的復(fù)雜度為O(MN(N-1))；

(4)非支配解的選擇與外部檔案維護(hù)的復(fù)雜度為O(M×(N2/2))；

因此，pmdMOPSO算法總的時間復(fù)雜度為O(MN2)，其主要由計算曼哈頓距離的復(fù)雜度和非支配解選擇與外部檔案維護(hù)的復(fù)雜度所支配。參考文獻(xiàn)[14]可知，MOPSO算法的復(fù)雜度為O(MN2)，主要是由動態(tài)網(wǎng)格歸檔的復(fù)雜度所支配；參考文獻(xiàn)[5]可知NSGA-Ⅲ算法的總體最壞情況復(fù)雜度為O(N2M)或O(N2logM-2N)，以較大者為準(zhǔn)。參考文獻(xiàn)[6]可知，MOEA/D_FRRMAB算法的復(fù)雜度為O(MTN2)，其中T表示鄰域大小。

3 實驗仿真

為驗證所提pmdMOPSO算法的優(yōu)化性能，將pmdMOPSO算法在文獻(xiàn)[30]中提出的MOP1～MOP7等7個測試函數(shù)上分別與NSGA-Ⅲ算法[5]、多目標(biāo)粒子群算法MOPSO[14]、分解類多目標(biāo)進(jìn)化算法MOEA/D_FRRMAB[6]三個算法作對比，觀察各個算法在7個測試問題上收斂性能IGD、多樣性能Delta、成功率以及尋優(yōu)時間等4個評測指標(biāo)上的優(yōu)化效果，驗證pmdMOPSO算法的優(yōu)越性。

pmdMOPSO算法的編碼采用實數(shù)編碼方式。一個粒子是一個向量，表示多目標(biāo)問題的一個潛在解。假設(shè)需要優(yōu)化的目標(biāo)函數(shù)數(shù)量為M，則把粒子維數(shù)長度設(shè)置為M，每一維代表了多目標(biāo)問題中一個目標(biāo)的潛在解。如果x(i)為多目標(biāo)優(yōu)化問題的一個解，可以記為x(i)=[x1(i);x2(i);…;xm(i)]。粒子向量中每一元素被限制在[0,1]之內(nèi),且對粒子向量初始值采用四舍五入方式對其進(jìn)行取整處理。比如：多目標(biāo)優(yōu)化問題的數(shù)量為2，則粒子向量可以表示為x(i)=[x1(i);x2(i)]=[0.452 2;0.596 8]，初始值進(jìn)行取整處理后x(i)=[0.000 0;1.000 0]。種群中粒子個體就是多目標(biāo)問題的潛在解。

3.1 測試函數(shù)

本文選擇文獻(xiàn)[30]中提出的MOP1～MOP7等7個測試函數(shù)進(jìn)行測試，g(x)的搜索空間[0,1]n為，n=10。在7個測試函數(shù)中，MOP1～MOP5是具有兩個目標(biāo)的多目標(biāo)測試函數(shù)，包含凸凹函數(shù)和非連續(xù)函數(shù)；MOP6和MOP7是具有三目標(biāo)的多目標(biāo)測試函數(shù)，具體測試函數(shù)如表1所示。

表1 測試函數(shù)

續(xù)表1

3.2 實驗參數(shù)設(shè)置

最大迭代次數(shù)T設(shè)為100；種群數(shù)量N為100，外部檔案數(shù)量設(shè)為50。pmdMOPSO算法中，ω初始值為0.4，ωMax=0.4,ωMin=0.3;網(wǎng)格數(shù)量nGrid為10；個體認(rèn)知參數(shù)c1初始值設(shè)置為1，c1Max為2，c1Min為1；社會認(rèn)知參數(shù)c2初始值設(shè)置為2，c2Max、c2Min與個體認(rèn)知相同；探索認(rèn)知參數(shù)c3初始值設(shè)置為0.001，c3Max、c3Min與個體認(rèn)知相同。

3.3 實驗環(huán)境

算法仿真實驗環(huán)境為Windows 7操作系統(tǒng)，編程語言環(huán)境為MATLAB R2012a。硬件環(huán)境為intel酷睿處理器i5-4570，主頻為3.20 GHz，內(nèi)存為4 GB。

3.4 實驗結(jié)果及分析

3.4.1 收斂性能IGD指標(biāo)測試

逆世代距離IGD(inverted generational distance)性能指標(biāo)[31]用來評測算法在測試問題上的收斂性能，表示的是算法搜索到的非劣解集與真實帕累托前沿的距離。

(20)

式中：P*表示真實Pareto前沿的最優(yōu)解集；P表示算法在測試函數(shù)中搜索到的最優(yōu)非劣解集，d(v,P)表示v和P的點中最小的歐式距離，v∈p*。在MOP1～MOP5上P*=500，在MOP6和MOP7上P*=1 000。通過設(shè)置較大的值，以滿足IGD對算法收斂性和多樣性的綜合檢測要求[32]。

表2是各個算法在MOP1～MOP7測試問題上獨立運行30次獲得的逆世代距離IGD的均值和方差。從表中均值數(shù)據(jù)可以看出，NSGA-Ⅲ算法未在一個測試上獲得最優(yōu)均值，MOPSO算法只在一個測試函數(shù)MOP7上獲得了最優(yōu)均值，MOEA/D_FRRMAB算法同樣只在一個測試函數(shù)MOP6上獲得了最優(yōu)均值，而本文所提pmdMOPSO算法在MOP1、

MOP2、MOP3、MOP4和MOP5五個測試函數(shù)上都獲得了最優(yōu)的均值；說明pmdMOPSO算法表現(xiàn)出了較好的收斂性能。從方差數(shù)據(jù)角度看，NSGA-Ⅲ和MOEA/D_FRRMAB在7個測試上都未獲得最優(yōu)方差，MOPSO在MOP1、MOP6和MOP7三個測試函數(shù)上獲得了最優(yōu)方差；本文所提pmdMOPSO算法雖然未在上述3個測試函數(shù)獲得最好的方差值，但獲得的方差僅次于MOPSO算法；而且pmdMOPSO在MOP2、MOP3、MOP4和MOP5四個測試函數(shù)上都獲得了最優(yōu)方差值，說明所提pmdMOPSO算法表現(xiàn)出較好的穩(wěn)定性能。表3數(shù)據(jù)表明pmdMOPSO算法不僅具有較好的收斂性能，還具有較好的穩(wěn)定性。這是因為pmdMOPSO算法根據(jù)種群曼哈頓距離合理利用了進(jìn)化狀態(tài)信息，并采用具有Levy飛行探索認(rèn)知行為的速度更新策略和自適應(yīng)參數(shù)調(diào)整策略，提高了算法的整體優(yōu)化性能。

表2 各算法的IGD指標(biāo)值

3.4.2 多樣性能Delta指標(biāo)測試

多樣性能指標(biāo)可以用來測量非支配解集的多樣性情況，包括不是Pareto最優(yōu)集合的解集[1]。定義為：

(21)

表4是各個算法在7個測試問題上獨立運行30次獲得的多樣性能Delta指標(biāo)的均值和方差。從表4可知，MOPSO算法在一個測試函數(shù)MOP4上得到最優(yōu)值；NSGA-Ⅲ算法在MOP6、MOP7兩個測試函數(shù)上得到最優(yōu)值；本文所提pmdMOPSO算法在MOP1、MOP2、MOP3和MOP5四個測試函數(shù)上得到了最優(yōu)值。這表明pmdMOPSO算法比其他3個對比算法具有較好的多樣性能，基于種群曼哈頓距離進(jìn)行自適應(yīng)速度更新和自適應(yīng)參數(shù)調(diào)整策略能夠有效增強算法的多樣性，改善種群多樣性在尋優(yōu)后期丟失的現(xiàn)象。

表4 各算法的Delta指標(biāo)值

圖1展示了各個算法的收斂情況及分布狀態(tài)，上述IGD指標(biāo)反映了算法的收斂性能，Delta指標(biāo)反映了非支配解的多樣性能，而非支配解在Pareto前沿上的分布性能較多采用Spacing指標(biāo)測試；鑒于文章篇幅，非支配在Pareto前沿的分布性能可以從圖1中觀察。圖1中PF表示Pareto最優(yōu)前沿，各個算法得到的解用不同的符號標(biāo)記。從MOP1～MOP5二目標(biāo)測試函數(shù)圖像上可以觀察到，4種算法得到的二目標(biāo)解大部分都能夠?qū)ふ业絇areto前沿，即二目標(biāo)的解大部分都能夠落在PF前沿線上。pmdMOPSO算法、MOPSO算法和MOEA/D_FRRMAB算法在5個二目標(biāo)測試函數(shù)上獲得的解都尋找到了Pareto前沿，但NSGA-Ⅲ算法在MOP3上獲得的部分二目標(biāo)解未找到Pareto前沿。pmdMOPSO算法在MOP1、MOP2、MOP3和MOP5四個函數(shù)上獲得的二目標(biāo)解在Pareto前沿圖像上均具有較好的分布，說明分布性能優(yōu)于其他3個對比算法；MOEA/D_FRRMAB算法獲得的二目標(biāo)解雖然都找到了Pareto前沿，但是分布性能差于MOPSO算法，在MOP1、MOP4和MOP5三個二目標(biāo)函數(shù)上的分布性差于NGSA-Ⅲ算法。NGSA-Ⅲ算法在MOP2和MOP3兩個二目標(biāo)函數(shù)上分布性最差；MOPSO算法在MOP4測試函數(shù)的Pareto前沿上具有最好的分布性能，在其他的二目標(biāo)函數(shù)上分布性能僅次于pmdMOPSO算法。從MOP6和MOP7三目標(biāo)測試函數(shù)圖像上可以觀察到，pmdMOPSO算法得到的三目標(biāo)解大部分都位于Pareto前沿面上；MOEA/D_FRRMAB算法和MOPSO算法分布在MOP6和MOP7上尋找到了最佳的pareto前沿，分布性能優(yōu)于其他算法。而NSGA-Ⅲ算法在MOP6上基本失去Pareto前沿，在MOP7上部分解位于Pareto前沿面上。

由上述分析可知，pmdMOPSO算法不僅能夠獲得較好的收斂性能，還能夠保證較好的多樣性。這是因為pmdMOPSO算法根據(jù)種群曼哈頓距離合理利用了算法的進(jìn)化狀態(tài)信息，針對不同的進(jìn)化狀態(tài)選擇不同功能的速度更新公式，并采用了基于Levy飛行探索認(rèn)知的速度更新策略，有效提升了收斂性能；pmdMOPSO算法中認(rèn)知參數(shù)根據(jù)進(jìn)化狀態(tài)非線性更新，提高了種群的多樣性?；谏鲜霾呗?，pmdMOPSO算法有效平衡了全局探索與局部尋優(yōu)的能力，保證了算法收斂性與多樣性的平衡。由于pmdMOPSO算法中引導(dǎo)粒子的選取和外部檔案的維護(hù)采用基本多目標(biāo)粒子群算法中的優(yōu)化策略，因此，pmdMOPSO算法的實驗可以說明使用曼哈頓距離檢測進(jìn)化狀態(tài)信息，并利用反饋信息設(shè)計自適應(yīng)進(jìn)化參數(shù)和多速度搜索策略有助于算法的優(yōu)化。

3.4.3 成功率測試

對算法的成功率作以下定義：算法尋優(yōu)精度達(dá)到指定精度的次數(shù)與總尋優(yōu)次數(shù)之比為成功率。如圖2所示為4種算法在MOP1～MOP7七個測試函數(shù)上的成功率對比圖，從圖中可以清晰的看出算法成功率的高低。本文通過式(22)計算指定精度AC的數(shù)值：

(22)

根據(jù)表3計算可知，MOP1～MOP7測試函數(shù)上指定精度值A(chǔ)C分別為：1.665 3E-02、1.739 2E-02、7.725 5E-02、1.445 5E-02、1.727 3E-02、1.900 2E-01、3.183 2E-01。NSGA-Ⅲ算法、多目標(biāo)粒子群算法MOPSO、分解類多目標(biāo)進(jìn)化算法MOEA/D_FRRMAB和pmdMOPSO算法達(dá)到AC值的次數(shù)和成功率分別如表5～表8所示，從表中數(shù)據(jù)可以看出，pmdMOPSO算法在7個測試函數(shù)上都能夠達(dá)到較好的成功率。圖2為4個算法成功率的曲線圖，從圖2中可以直觀地觀察到pmdMOPSO算法的成功率曲線一直處于最高水平，表明pmdMOPSO算法在7個測試問題上達(dá)到指定精度的成功率高于其他3個對比算法。pmdMOPSO算法能夠獲得較高成功率的原因在于利用了種群的進(jìn)化狀態(tài)選擇不同優(yōu)勢的速度更新策略，提高算法的搜索精度；并將慣性權(quán)重與學(xué)習(xí)因子根據(jù)進(jìn)化狀態(tài)實現(xiàn)動態(tài)調(diào)整，有效實現(xiàn)了算法全局搜索與局部開采的平衡。

表5 NSGA-Ⅲ算法在7個測試函數(shù)上實驗結(jié)果

表6 MOPSO算法在7個測試函數(shù)上實驗結(jié)果

表7 MOEA/D_FRRMAB算法在7個測試函數(shù)上實驗結(jié)果

表8 本文pmdMOPSO算法在7個測試函數(shù)上實驗結(jié)果

3.4.4 尋優(yōu)時間測試

當(dāng)智能優(yōu)化算法對精度的提升是以大量時間為代價時，往往是不被接受的。因此，通過各個算法運行30次得到的時間均值，觀察各個算法所用的尋優(yōu)時間。表5～表8中尋優(yōu)時間是4個算法在7個測試函數(shù)上運行30次得到的時間均值，圖3以曲線圖的形式將時間數(shù)據(jù)更加直觀的展示出來。從圖中可以看出，MOPSO算法在各個測試函數(shù)上所用時間最少，NSGA-Ⅲ由于采用了非支配排序，因此所用時間最多。pmdMOPSO算法監(jiān)測了種群的進(jìn)化狀態(tài)，計算了種群之間的曼哈頓距離，因此所用時間略多于MOPSO算法，但從曲線走勢可以看出，pmdMOPSO算法所用時間更加具有穩(wěn)定性。

4 結(jié)束語

本文提出一種基于種群曼哈頓距離的自適應(yīng)多目標(biāo)粒子群優(yōu)化算法pmdMOPSO。引入種群曼哈頓距離實現(xiàn)對算法進(jìn)化狀態(tài)的劃分，在不同的進(jìn)化階段分別采用具有較強局部搜索和全局搜索能力的速度更新模式，提升算法優(yōu)化性能；利用種群曼哈頓距離差分向量設(shè)計參數(shù)自適應(yīng)更新模式，可以根據(jù)算法進(jìn)化狀態(tài)自適應(yīng)調(diào)整參數(shù)，平衡算法收斂與多樣性能。實驗表明，上述策略不僅提高了算法的收斂性能，還維護(hù)了種群多樣性，表明pmdMOPSO算法是一種有效實現(xiàn)收斂性與多樣性平衡的優(yōu)化算法。本文算法在測試函數(shù)上實現(xiàn)了較好效果，但并未對實際問題展開測試，下一步將利用所提算法優(yōu)化具體的實際問題，探究算法在具體問題中的優(yōu)化效果。