朱玉菲 張紀會 段明

摘要： 針對多目標粒子群算法在選取全局最優(yōu)解和保持種群多樣性上存在的缺陷，本文提出了一種基于分解的自適應(yīng)多目標粒子群優(yōu)化算法。該算法采用切比雪夫聚合方法，將多目標問題聚合為若干個單目標問題，并對每一個單目標問題粒子的速度和位置更新公式進行改進，提高了算法搜索到Pareto解集的效率。同時，改進了慣性權(quán)重和加速因子，使其自適應(yīng)調(diào)整，能夠更好地平衡全局和局部搜索，采用網(wǎng)格技術(shù)存儲最優(yōu)解集，能有效保持進化群體的分布均勻性，并采用5個經(jīng)典的兩目標測試函數(shù)進行了仿真實驗。實驗結(jié)果表明，通過改進粒子群算法的速度和位置更新公式，可以提高非支配解對真實解的逼近程度，體現(xiàn)了本算法的有效性；多目標粒子群優(yōu)化算法求得的Pareto解集，在解的收斂性和分布性上都有明顯的提升。本算法為求解多目標優(yōu)化問題提供了一種新的方法。

關(guān)鍵詞： 切比雪夫分解； 網(wǎng)格技術(shù)； 粒子群優(yōu)化； 多目標優(yōu)化

中圖分類號： TP393； TP273+.2文獻標識碼： A

通訊作者： 張紀會（1969），男，博士，教授，博士生導師，主要研究方向為控制理論與控制工程。Email： minedocnments@126.com多目標優(yōu)化問題廣泛存在于眾多的科學領(lǐng)域中，而多目標優(yōu)化是國內(nèi)外許多專家學者研究的熱點問題。然而在多目標的優(yōu)化算法中，由于多目標問題的每個函數(shù)之間相互排斥，使多目標每個函數(shù)的解都達到最優(yōu)是沒有意義的，因此，國內(nèi)外專家學者在研究多目標優(yōu)化問題時求出的是多目標問題的一組解，而不是一個解，這組解集具有互不支配（nondominated set，NDS）關(guān)系，稱為帕累托最優(yōu)解集（paretooptimal set，POS），這些解集在目標空間上構(gòu)成的前沿面稱為Pareto前沿[1]。在處理多目標優(yōu)化問題時，數(shù)學規(guī)劃法是最早使用的一類方法，但是這些方法在處理多目標優(yōu)化問題時卻存在較大的局限性[2]。因此，為得到一組非支配解來估計帕累托前沿，并且這組解均勻分布在目標空間中，研究者們考慮使用一些其他方法直接處理多目標優(yōu)化問題。近年來，絕大部分的多目標優(yōu)化算法都是在帕累托這個概念的基礎(chǔ)上發(fā)展起來[16]。學者們?yōu)榱吮M可能地提高算法的效率，在早期多目標優(yōu)化算法基礎(chǔ)上，又提出了一系列的第2代多目標優(yōu)化算法[1，78]。上述研究在優(yōu)化多目標時都是將多目標問題看成是一個整體進行優(yōu)化[18]，但Zhang Q等人[910]提出了在多目標進化算法中使用數(shù)學規(guī)劃中的分解策略，即通過某種聚合方法，將多目標優(yōu)化問題轉(zhuǎn)化為單目標優(yōu)化問題進行優(yōu)化。為了進一步提高算法的收斂性和魯棒性，一些研究者在基于分解的多目標遺傳算法（multiobjective evolutionary algorithm based on decomposition，MOEA/D）的基礎(chǔ)上做了進一步研究，改進了MOEA/D[1112]。2008年，Peng W等人[13]在MOEA/D框架之下提出基于分解的多目標粒子群算法（multiobjective particle swarm optimizer based on decomposition，MOPSO/D）。在一些2目標和3目標測試函數(shù)上，MOPSO/D與非支配排序的多目標遺傳算法的二代算法（nondominated sorting genetic algorithmII，NSGAII）相比，顯示出更好的性能?；诖?，本文提出了基于分解的自適應(yīng)控制多目標粒子群優(yōu)化算法（adaptive multiobjective particle swarm optimization algorithon based on decomposition，AMOPSO/D），慣性權(quán)重w不再固定不變而是動態(tài)變化的，以平衡全局開拓能力和局部搜索能力；針對粒子群收斂速度快，易陷入局部最優(yōu)的缺陷，算法對粒子群的位置進行突變，自適應(yīng)調(diào)整粒子群在目標空間中的搜索，以增加種群的多樣性。同時，改進速度和位置更新公式，以提高算法搜索到Pareto解集的效率，并通過一系列2目標測試函數(shù)對算法性能進行驗證，證明了其有效性。

1基于分解的自適應(yīng)控制的多目標粒子群算法

1.1多目標優(yōu)化問題的數(shù)學模型

對于多目標優(yōu)化問題，其數(shù)學模型可描述為

min y=Fx=[f1x，f2x，L，fkx]（1）

s.t. x∈Ω

式中，Ω是n維決策空間；x=（x1，…，xn）T，x∈XRn為n維決策變量；fi1≤i≤k是目標函數(shù)；y=（y1，…，yk）T，y∈YRk為k維目標空間；Fx為n個由決策空間向k維目標空間的映射函數(shù)。

1.2切比雪夫聚合方法

分解策略是把多目標優(yōu)化問題通過一定的方法轉(zhuǎn)化為一組單目標優(yōu)化問題，并同時優(yōu)化這一組單目標問題。近年來，在許多元啟發(fā)式方法中都使用了分解思想。MOEA/D中采用切比雪夫聚合方法（Tchebycheff）和權(quán)重求和法來處理多目標問題[10]。本文只采用Tchebycheff方法，Tchebycheff方法的計算公式為

min g（x|λi，z*）=max（1≤j≤k）λijfj（x）-zj（2）

式中，x∈Ω；λi=（λi1，…，λik）T是第i個粒子的權(quán)重向量，并滿足λij≥0，1≤j≤k，λi1+…+λik=1；參考點為z*=z*1，…，z*kT，對于每一個j=1，…，k，有z*j=min1≤j≤kfjx|x∈Ω。因為函數(shù)g是關(guān)于權(quán)重向量λ的函數(shù)，所以，對式（2）求最小值時，總存在一個權(quán)重向量λ，使式（2）能得到一個最優(yōu)解，并且原多目標優(yōu)化問題的Pareto前沿面上應(yīng)該有一個最優(yōu)解與之相對應(yīng)，如果權(quán)重向量λj是λi的鄰居，那么g（x|λi，z*）的最優(yōu)解與g（x|λj，z）的最優(yōu)解應(yīng)該相接近，這樣，優(yōu)化由權(quán)重向量λj構(gòu)成的單目標子問題g（x|λj，z）的解，對優(yōu)化單目標子問題g（x|λi，z*）的解有幫助。因此，在優(yōu)化單目標子問題g（x|λi，z*）的解時，要確定權(quán)重向量λi的鄰居權(quán)重向量。

青 島 大 學 學 報 （ 工 程 技 術(shù) 版 ）第 33 卷

第1期朱玉菲， 等： 基于分解的自適應(yīng)多目標粒子群算法研究

1.3保持種群多樣性的策略

多目標優(yōu)化問題通過切比雪夫聚合方法轉(zhuǎn)化成單目標優(yōu)化問題，所以在單目標優(yōu)化算法中，許多能夠提高算法性能的技術(shù)和策略都可引入該算法中。

2009年，均值粒子群優(yōu)化算法（mean particle swarm optimization for function optimization，MeanPSO）被提出[14]，該算法主要用于解決單目標優(yōu)化問題。算法的主要思想是在速度更新式中比較pbest和gbest的線性組合（pbestij+gbestij）2和（pbestij-gbestij）2，而不僅是將pbest和gbest與粒子的當前位置進行比較。通過分析傳統(tǒng)粒子群算法速度的更新公式，提出新的速度更新公式。在每次迭代過程中，粒子i的速度和位置分別為

vij=wvij+c1r1（pbestij+gbestij）2-pij+c2r2（pbestij-gbestij）2-pij（3）

pij=pij+vij（4）

式中，w是慣性權(quán)重；c1和c2是加速因子；r1和r2是在0，1范圍內(nèi)取值的均勻分布隨機數(shù)。

粒子群優(yōu)化（particle swarm optimization，PSO）算法的收斂速度非常快，所以在用式（4）和式（5）計算時，所有的粒子在經(jīng)過多次迭代后其位置都趨近于同一個點，這個點就是局部最優(yōu)點，這時，所有粒子的搜索速度趨于0，位置也不再發(fā)生改變，這時就產(chǎn)生了粒子陷入了局部最優(yōu)的情況。為了克服這種缺陷，提高本算法的開拓能力，本文將式（4）和式（5）改為

vij=wvij+r1（c1pbestij+c2gbestij）2-pij+r2（c1pbestij-c2gbestij）2-pij（5）

pij=pij+βvij（6）

式中，β是0，1上均勻分布的隨機數(shù)。

慣性權(quán)重w具有平衡全局探測能力和局部搜索性能的作用，為了能更好地控制開拓和探索能力，專家學者們通過改進慣性權(quán)重w來對粒子群算法進行改進[1516]。2014年，敖永才等人[17]提出自適應(yīng)慣性權(quán)重的改進粒子群算法，該算法減少了無效迭代的次數(shù)，提高了算法收斂到最優(yōu)解的速度和穩(wěn)定性。本文改進動態(tài)慣性權(quán)重和加速因子，使粒子在某一位置上不局限其進行全局搜索或局部搜索，在第t次迭代時，慣性權(quán)重和加速因子自適應(yīng)調(diào)整為

w=αWmax-（Wmax-Wmin）tNt， c1=w+tNt， c2=w-tNt（7）

式中，Wmin和Wmax分別是w的上、下界；α是0，1上均勻分布的隨機數(shù)；Nt為總的迭代次數(shù)，t為當前代數(shù)；c1，c2為加速因子，當?shù)螖?shù)增加時，c1增加，c2減少。

本算法對粒子群的速度和位置更新公式進行改進，在一定程度上平衡了粒子的開拓能力和搜索性能，但粒子群的搜索速度經(jīng)過幾次迭代后仍然會越來越小，種群仍然會發(fā)生局部收斂。為了克服局部收斂問題，保持粒子群的多樣性，本文在算法中使用變異操作，變異操作是依概率在粒子的位置上隨機選擇某一維位置，并對該位置進行突變，具體操作如下：

ifrand

pid=r and

end

變異操作使粒子位置發(fā)生改變，從而使種群從局部最優(yōu)中跳出，在目標空間中重新進行搜索，這不僅保持了種群的多樣性，而且其全局搜索性能也得到了提高。

1.4外部檔案EA的保存

在保存非支配解時，由于非支配解的存儲特別快，使保存的非支配解分布性特別差，使用擁擠距離并不能保證非支配解有較好的分布性。網(wǎng)格技術(shù)[18]的主要思想是將目標空間劃分成不同的網(wǎng)格子空間，然后記錄網(wǎng)格中解集的分布情況。它在多目標優(yōu)化過程中能夠保持種群的分布性，其最大優(yōu)點是計算的復雜度小。新產(chǎn)生的非支配解分布在網(wǎng)格不同的子區(qū)域中，根據(jù)其分布的密集程度，對分布密度大的區(qū)域隨機刪除個體，以調(diào)整非支配解集在目標空間中的分布，從而達到獲得均勻分布解集的目的。因此，在存儲外部檔案時，本文算法使用了網(wǎng)格技術(shù)，當EA中存儲的數(shù)據(jù)個數(shù)大于設(shè)定值時，啟動網(wǎng)格技術(shù)。其具體過程如下：

1）建立一個k維的超空間，把k維的超空間平均劃分為nk個網(wǎng)格。網(wǎng)格劃分時要在目標函數(shù)的取值范圍內(nèi)，且每個網(wǎng)格的大小都相等。

2）為超空間中每個網(wǎng)格分配索引號和網(wǎng)格坐標。

3）當種群中的所有粒子飛到對應(yīng)的網(wǎng)格中后，利用網(wǎng)格坐標采用輪盤賭的方式，刪除在網(wǎng)格中聚集密度大的個體。

1.5AMOPSO/D算法的流程

本算法的全局變量如下：

1）種群具有N個粒子x1，…，xN，第i個粒子的位置向量為pi，速度向量為vi，個體最優(yōu)向量為pbesti。

2）定義第i個粒子的全局最優(yōu)向量為gbesti。

3）一個參考點：z*=z*1，…z*iT。

4）在搜索過程中，每次迭代產(chǎn)生的非支配解都用一個外部檔案EA來儲存。

初始化為：

1）EA=。

2）鄰居向量的選擇。計算λi和λj（λi≠λj）的歐氏距離，按升序進行排序，選取前T個最小距離對應(yīng)的權(quán)重向量λi1，…，λiT作為λi的鄰居權(quán)重向量，λit表示第i個權(quán)重向量的第t個鄰居權(quán)重向量。

3）初始化種群中粒子的位置和速度。每個粒子的初始位置設(shè)置為（0，1）上的隨機數(shù)，服從均勻分布；粒子的初始速度設(shè)置為服從正態(tài)分布的隨機數(shù)。

4）種群的個體最優(yōu)值和全局最優(yōu)值的初始化。for i=1，…，N，令pbesti=gbesti=pi。

迭代：

for i=1，…，N do

1）根據(jù)式（4）～式（6），更新種群中每個粒子的速度和位置，并依概率在粒子的位置上隨機選擇某一維位置，對該位置進行突變。

2）參考點Z的更新。forj=1，…，k如果zj

3）種群中每個粒子個體最優(yōu)值的更新。如果gpi'|λi≤gpbesti|λi，那么pbesti=pi'。

4）種群中粒子全局最優(yōu)值的更新。對于每一個j∈Bi，如果gpi'|λj≤gpbestj|λj，則gbestj=pi'。

5）更新鄰域解。對于每一個鄰居權(quán)重向量λj，j∈i1，…，iT，如果gpi'|λj，z≤gpj|λj，z，令pj=pi'，F(xiàn)（pj）=Fpi'。

6）更新EA。把EA中所有被支配的解從EA中移除，如果EA中不存在支配的解，將存入EA中。

7）終止條件。達到最大迭代次數(shù)，停止并輸出EA，否則繼續(xù)進行迭代。

2評價指標與參數(shù)設(shè)置

2.1測試函數(shù)

本算法在驗證其性能時，測試函數(shù)采用2目標ZDT系列。測試函數(shù)的一組在目標空間上均勻分布的真實解集是已知的，所以可以用來評價本文算法的實驗數(shù)據(jù)。

2.2算法的性能評價指標

多目標優(yōu)化算法的性能評價指標有很多，如C指標、D指標和反向世代距離（inverted generational distance，IGD）指標[1920]等。IGD指標主要評估多目標優(yōu)化算法中非支配解集對真實Pareto解集的逼近程度和在目標空間中分布的均勻性，所以本文利用IGD指標來評價實驗得出的結(jié)果。IGD指標為

IGD=∑ni=1d2in

式中，將第i個真實的Pareto解和近似解中每個粒子的歐氏距離進行比較，與它歐氏距離最小的距離為di，n是真實的帕累托解的數(shù)目。IGD值越小，表明得到的近似解與真實的Pareto解的距離就越小，算法的收斂性就越好，在目標空間中的分布就越均勻，近似解與真實的Pareto前沿就越逼近。

2.3算法的實驗參數(shù)設(shè)置

本算法使用ZDT系列的測試函數(shù)，種群大小設(shè)置為100，鄰居數(shù)T為30，EA最大為500，Wmin=035，Wmax=10，變異概率Pm=05，最大迭代次數(shù)為300，網(wǎng)格膨脹參數(shù)為10-5，每一維的網(wǎng)格數(shù)為10。本算法得出的結(jié)果都是獨立運行20次求出的平均值。

3實驗結(jié)果與分析

各算法在IGD指標上的均值統(tǒng)計結(jié)果如表1所示。由表1可以看出，在2目標問題上，本算法在ZDT1～ZDT4測試函數(shù)上要明顯比其他幾個函數(shù)的IGD指標小，這體現(xiàn)了本算法比其他幾個算法在收斂性和分布均勻性上都要好。對比AMOPSO/D和MOEA/D兩類算法可以看出，本算法雖然在ZDT6測試函數(shù)上的IGD指標比MOEA/D算法大，但前4組測試函數(shù)的IGD指標比MOEA/D小，說明本算法在MOEA/D計算框架下，改進的粒子群優(yōu)化算法在解的收斂性上具有巨大優(yōu)勢。表1各算法在IGD指標上的均值統(tǒng)計結(jié)果

測試函數(shù)NSGAIISPEA2MOEA/DSMPSOMOPSOAMOPSO/DZDT11.863 7×10-41.528 6×10-47.593 7×10-51.349 8×10-41.387 9×10-45.525 6×10-5ZDT21.914 5×10-41.561 9×10-45.841 5×10-51.401 3×10-41.431 4×10-44.288 8×10-5ZDT32.554 1×10-42.352 4×10-41.304 7×10-42.034 7×10-42.182 0×10-46.529 8×10-5ZDT42.471 4×10-41.425 7×10-43.059 4×10-41.373 9×10-41.893 6×10-45.332 2×10-5ZDT63.537 9×10-46.538 8×10-42.061 3×10-51.161 5×10-41.220 2×10-43.290 9×10-5表1中，有下劃線的為優(yōu)勝值。ZDT系列測試函數(shù)的真實值與在本算法上的估計值（500個目標）如圖1所示。由圖1可以看出，在2目標ZDT問題的收斂性上，AMOPSO/D的表現(xiàn)水平與真實值相當，但是AMOPSO/D相比于真實值均勻性很好；結(jié)合圖1和表1可以看出，AMOPSO/D的IGD指標要比其他幾個算法小，進一步說明AMOPSO/D求出的解比部分已知的其他優(yōu)化算法產(chǎn)生的解要好。

綜上所述，通過改進粒子群算法的速度和位置更新公式，可以提高非支配解對真實解的逼近程度，體現(xiàn)了本算法的有效性。

圖1ZDT系列測試函數(shù)的真實值與在本算法上的估計值（500個目標）4結(jié)束語

本文在對MOEA/D計算框架進行分析的基礎(chǔ)上，提出了基于分解的自適應(yīng)控制多目標粒子群算法AMOPSO/D，該算法通過引入變異操作，保持了種群的多樣性，避免陷入早熟收斂，改進的慣性權(quán)重和加速因子可平衡全局開拓能力和局部搜索性能；改進粒子速度公式和位置公式，不僅提高了算法搜索到非支配解集的效率，而且也提高了非支配解對真實解的逼近程度，在存儲非支配解集時使用了網(wǎng)格技術(shù)，有效地保持整個種群的分布性。實驗結(jié)果表明了該算法的有效性，但是本算法在解決3目標問題上還存在一定的缺陷，不能得到一個收斂性和分布性都比較好的Pareto前沿面，所以今后的主要工作是繼續(xù)改進算法，使其能更好地解決3目標及更多目標優(yōu)化的問題。

參考文獻：

[1]Deb K， Kalyanmoy D. MultiObjective Optimization Using Evolutionary Algorithms[M]. New York： John Wiley & Sons， 2001.

[2]劉加光， 陳義保， 羅震. 連續(xù)體結(jié)構(gòu)的模糊多目標拓撲優(yōu)化設(shè)計方法研究[J]. 系統(tǒng)仿真學報， 2007， 19（5）： 10951099.

[3]Fonseca C M， Fleming P J. Genetic Algorithm for MultiObjective Optimization： Formulation， Discussion and Generation[C]//The 5th International Conference on Genetic Algorithms. San Mateo， CA： Morgan Kaufmann， 1993： 416423.

[4]Zitzler E， Thiele L. Multiobjective Optimization Using Evolutionary Algorithmsa Comparative Case Study[C]∥International Conference on Parallel Problem Solving from Nature. Berlin： Springer Berlin Heidelberg， 1998： 292301.

[5]Knowles J， Corne D. The Pareto Archived Evolution Strategy： A New Baseline Algorithm for Pareto Multiob Jective Optimisation[C]// Proc Congress on Evolutionary Computation. Washington， DC， USA： IEEE， 1999： 98105.

[6]Srinivas N， Deb K. Multiobjective Optimization Using NonDominated Sortingin Genetic Algorithms[J]. Evolutionary Computation， 2014， 2（3）： 221248.

[7]Deb K， Pratap A， Agarwal S， et al. A Fast and Elitist Multiobjective Genetic Algorithm： NSGAII[J]. IEEE Transactions of Evoluationary Computation， 2002， 6（2）： 182197.

[8]Zitzler E， Laumanns M， Thiele L. SPEA2： Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization[C]//Evolutionary Methods for Design， Optimization and Control with Applications to Industrial Problems. Athens Greece： Proceedings of the Eurogen， 2001： 1921.

[9]Zhang Q， Li H. MOEA/D： A Multiobjective Evolutionary Algorithm Based on Decomposition[J]. IEEE Transactions on Evolutionary Computation， 2007， 11（6）： 712731.

[10]Li H， Zhang Q. Multiobjective Optimization Problems with Complicated Pareto Set， MOEA/D and NSGAII[J]. IEEETransactions on Evolutionary Computation， 2009， 13（2）： 284320.

[11]Trivedi A， Srinivasan D， Sanyal K， et al. A Survey of Multiobjective Evolutionary Algorithms Based on Decomposition[J]. IEEE Transactions on Evolutionary Computation， 2016， 21（3）： 440462.

[12]Wang R， Zhang Q， Zhang T. DecompositionBased Algorithms Using Pareto Adaptive Scalarizing Methods[J]. IEEE Transactions on Evolutionary Computation， 2016， 20（6）： 821837.

[13]Peng W， Zhang Q. A DecompositionBased MultiObjective Partile Swarm Optimization Algorithm for Continuous Optimization Problems [J]. IEEE International Conference on Granular Computation， 2008， 15（3）： 534537.

[14]Deep K， Bansal J C. Mean Particle Swarm Optimization for Function Optimization [J]. International Journal Computational Intelligence Studies， 2009， 1（1）： 7292.

[15]Shi Y， Eberhart R C. Parameter Selection in Particle Swarm Optimization [J]. International Conference on Evolutionary Programming， 1998， 1447（25）： 591600.

[16]董平平， 高東慧， 田雨波， 等. 一種改進的自適應(yīng)慣性權(quán)重粒子群優(yōu)化算法[J]. 計算機仿真， 2012， 29（12）： 283286.

[17]敖永才， 師奕兵， 張偉， 等. 自適應(yīng)慣性權(quán)重的改進粒子群算法[J]. 電子科技大學學報， 2014， 43（6）： 874880.

[18]李召軍， 王希誠. 一種基于網(wǎng)格的多目標優(yōu)化方法[J]. 大連理工大學學報， 2012， 52（6）： 787793.

[19]邱興興， 張珍珍， 魏啟明. 混合分解和強度帕累托多目標進化算法[J]. 計算機應(yīng)用， 2014， 34（10）： 28802885.

[20]李飛， 劉建昌， 石懷濤， 等. 基于分解和差分進化的多目標粒子群優(yōu)化算法[J]. 控制與決策， 2017， 32（3）： 403410.