黃瑾，張濤，郭陽(yáng)，胡玉蝶(長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

多目標(biāo)規(guī)劃問(wèn)題大量存在于工程實(shí)踐與科學(xué)研究中，引起了許多科研工作者的高度關(guān)注。多目標(biāo)優(yōu)化問(wèn)題往往有2個(gè)及以上的目標(biāo)，各個(gè)目標(biāo)之間相互排斥，為達(dá)到其中一個(gè)目標(biāo)通常要犧牲其他目標(biāo)，難以同時(shí)優(yōu)化所有目標(biāo)。另外，多目標(biāo)規(guī)劃問(wèn)題的最優(yōu)解往往不是唯一的，而是一個(gè)最優(yōu)解集合，通常稱(chēng)為Pareto最優(yōu)解集。與傳統(tǒng)的數(shù)值優(yōu)化方法相比，進(jìn)化算法求解多目標(biāo)優(yōu)化問(wèn)題具有較為明顯的優(yōu)勢(shì)，進(jìn)化算法運(yùn)行結(jié)束后，往往可以得到多個(gè)Pareto最優(yōu)解，從而形成了Pareto最優(yōu)解集[1]。

Schaffer于1985年首次提出了求解多目標(biāo)優(yōu)化問(wèn)題的進(jìn)化算法——矢量評(píng)價(jià)遺傳算法[2]。從此，多目標(biāo)進(jìn)化算法逐步引起了國(guó)內(nèi)外研究者的關(guān)注。20世紀(jì)90年代提出的算法被稱(chēng)作第1代進(jìn)化多目標(biāo)算法，包括Fonseca和Fleming提出的多目標(biāo)遺傳算法[3]、Srinivas和Deb提出的非支配排序遺傳算法[4]、Horn和Nafpliotis提出的多目標(biāo)小生境Pareto遺傳算法[5]。20世紀(jì)末21世紀(jì)初，進(jìn)化多目標(biāo)算法迎來(lái)第2代，算法的主要特點(diǎn)是精英保留機(jī)制。Zitzler和Thiele在1999年提出了強(qiáng)度Pareto進(jìn)化算法[6]，后來(lái)又提出了改進(jìn)的進(jìn)化算法——SPEA2算法[7]。2000年Knowles和Corn提出了Pareto外部集的進(jìn)化算法[8]，后來(lái)又提出了改進(jìn)的進(jìn)化算法PESA[9]和PESA-II[10]。Erichson、Mayer和Horn于2001年提出了在NPGA基礎(chǔ)上改進(jìn)的NPGA2算法[11]，后來(lái)Coello和Pulido研究遺傳算法得到了微遺傳算法[12]，2002年Deb等提出了相當(dāng)經(jīng)典的NSGA-II算法[13]。最近，Deb等采用主分量分析[14]和相關(guān)熵[15]的方法研究了高維多目標(biāo)規(guī)劃問(wèn)題的進(jìn)化算法，在此基礎(chǔ)上，Coello等研究了多目標(biāo)粒子群算法[16]，Gong和Jiao等研究了非支配鄰域遺傳算法[17]，Zhang和Zhou等研究得到了基于多目標(biāo)分布估計(jì)算法的規(guī)律性模型[18]，Zhang和Li研究了基于分解的多目標(biāo)進(jìn)化算法[19]。

作為近來(lái)提出的一種智能算法，粒子群優(yōu)化算法的特點(diǎn)與多目標(biāo)規(guī)劃問(wèn)題的結(jié)構(gòu)特征具有優(yōu)良的匹配性：算法在目標(biāo)函數(shù)、約束函數(shù)和模型結(jié)構(gòu)的性能要求上更加寬松，使其可以求解具有一般結(jié)構(gòu)的多目標(biāo)規(guī)劃問(wèn)題；算法以種群為操作單元且實(shí)數(shù)編碼，可以與多目標(biāo)規(guī)劃問(wèn)題的多解特征建立映射關(guān)系。利用改進(jìn)的粒子群算法解決多目標(biāo)規(guī)劃問(wèn)題近來(lái)雖然取得了一些結(jié)果[13，20～22]，但粒子群優(yōu)化算法也存在易陷入局優(yōu)、且所得解分布不均的缺陷。為此，筆者提出一種求解多目標(biāo)規(guī)劃問(wèn)題的基于精英策略的粒子群算法。

1 多目標(biāo)規(guī)劃問(wèn)題的模型及基本概念

假設(shè)x∈Rn,f:Rn→Rm,g:Rn→Rq，則多目標(biāo)規(guī)劃問(wèn)題可表述為：

(1)

其中，x為決策變量；f(x)表示目標(biāo)函數(shù)；g(x)為不等式約束函數(shù)；S={x|g(x,y)≤0}表示問(wèn)題(1)的可行域。

定義1如果x*是問(wèn)題(1)的可行解, 并且不存在x∈S, 使得f(x)f(x*), 則x*為問(wèn)題(1)的一個(gè)最優(yōu)Pareto最優(yōu)解, 其中，符號(hào)“”表示Pareto偏好。

定義2對(duì)于一個(gè)給定的多目標(biāo)優(yōu)化問(wèn)題f(x)，所有Pareto最優(yōu)解構(gòu)成Pareto最優(yōu)解集，記作：

P*={x∈S|?x*∈S,f(x*)f(x)}

定義3所有Pareto最優(yōu)解對(duì)應(yīng)的目標(biāo)向量構(gòu)成多目標(biāo)問(wèn)題的Pareto前沿，記作PF*，即：

PF*={f=f(f1(x),f2(x),…,fm(x))|x∈P*}

2 算法描述

算法具體步驟如下：

Step 1 初始化種群P，種群規(guī)模為N；初始化循環(huán)變量t=0，最大迭代次數(shù)為T(mén)；

Step 2 基于目標(biāo)函數(shù)f和約束函數(shù)g，對(duì)每個(gè)粒子分配一個(gè)非受控等級(jí)ND；對(duì)具有相同非受控等級(jí)值的粒子，基于目標(biāo)函數(shù)f，計(jì)算粒子的擁擠度距離CD；

Step 3 將種群P中ND=1的粒子存檔于精英集合At；

Step 4 更新粒子的速度和位置：

vj=ωvj+c1r1(pbestj-xj)+c2r2(gbestj-xj)

xj=xj+vj

Step 5 將更新后的粒子重新分配非受控等級(jí)ND及擁擠度距離CD；

Step 6 將父代種群Pt和子代種群Qt合并形成種群Rt，基于目標(biāo)函數(shù)f和約束函數(shù)g，對(duì)Rt中的粒子重新分配非受控等級(jí)ND，對(duì)具有相同非受控等級(jí)值的粒子，計(jì)算其擁擠度距離CD；

Step 7 從種群Rt中選取一半的粒子構(gòu)成新的種群St，先將ND=1的粒子按照CD值降序排列，然后進(jìn)行依次挑選。當(dāng)所有的ND=1的粒子挑選完后，再按上述方法挑選ND=2的粒子，直到St中具有N個(gè)粒子；

Step 8 更新精英集合At；

Step 9t=t+1，如果t≤T, 轉(zhuǎn)Step 4；否則, 輸出At。

算法中，粒子非受控等級(jí)排序方法、粒子擁擠度距離計(jì)算方法、精英集合更新規(guī)則、全局最優(yōu)粒子的選取及個(gè)體最優(yōu)粒子的選取規(guī)則具體闡述如下。

2.1 粒子非受控等級(jí)值排序方法

Step 1 假設(shè)種群為P，種群規(guī)模為N，p表示種群中的粒子;

Step 2 初始化i=1；

2.2 粒子擁擠度距離計(jì)算方法

假設(shè)同一級(jí)的非受控解集為I, 解集中粒子的個(gè)數(shù)為l，多目標(biāo)規(guī)劃問(wèn)題的目標(biāo)函數(shù)個(gè)數(shù)為m。

Step 1 對(duì)每個(gè)粒子i∈I，初始化I[i]distance=0；

Step 2 對(duì)每一個(gè)目標(biāo)函數(shù)fj(j∈m):

(i)對(duì)所有的粒子i∈I按升序排序；

(ii)令I(lǐng)[1]distance=I[l]distance=∞；

Step 3 從i=2到i=l-1計(jì)算粒子的擁擠度距離：

粒子非受控等級(jí)排序示意圖與擁擠度距離計(jì)算示意圖如圖1與圖2所示。

圖1 非受控等級(jí)排序示意圖 圖2 粒子擁擠度距離計(jì)算示意圖

2.3 精英集合更新規(guī)則

Step 1 存檔控制。假設(shè)原精英集合為A，si∈A(i=1,2,…,n)，精英集合的最大容量為N，當(dāng)前新解為Ns，那么：

(i)若A=Φ，則A=A∪{Ns};

(ii)若A≠Φ，則；

(Ⅰ)若Nssi∈A(i=1,2,…,n)，則A=A∪{Ns}且A=Asi；

(Ⅱ)若Ns與si∈A(i=1,2,…,n)互不受控，則A=A∪{Ns}。

Step 2 網(wǎng)格控制。(i)若Ns在網(wǎng)格范圍以內(nèi)，則正常插入；(ii)如果Ns超出網(wǎng)格范圍，重繪網(wǎng)格及重新定位，然后進(jìn)行插入并刪除部分具有較大擁擠度距離的粒子。

圖3表示控制器更新規(guī)則示意圖；圖4和圖5分別表示被插入的新解在網(wǎng)格范圍內(nèi)時(shí)以及新解超出網(wǎng)格范圍時(shí)進(jìn)行的插入和刪除工作。

圖3 控制器更新規(guī)則示意圖

圖4 新解在網(wǎng)格范圍內(nèi)時(shí)進(jìn)行的插入和刪除工作

圖5 新解超出網(wǎng)格范圍時(shí)進(jìn)行的插入和刪除工作

2.4 全局最優(yōu)粒子的選取

Step 1 假設(shè)精英集合中的解分布在k個(gè)網(wǎng)格中，每個(gè)網(wǎng)格中非受控粒子的個(gè)數(shù)分別為m1,m2,…,mk；

Step 2 計(jì)算每個(gè)網(wǎng)格的概率值：

Step 3 利用輪盤(pán)賭方式選擇一個(gè)網(wǎng)格；

Step 4 在由Step 3選中的網(wǎng)格中隨機(jī)挑選一個(gè)粒子作為全局最優(yōu)粒子。

2.5 最優(yōu)個(gè)體粒子的選取

假設(shè)當(dāng)前最好個(gè)體粒子為pbest[i]，新解為Ns[i]：

(i)若pbest[i]Ns[i]，則pbest[i]保持不變；

(ii)若Ns[i]pbest[i]，則pbest[i]=Ns[i]；

(iii)若Ns[i]與pbest[i]互不受控，則隨機(jī)選取當(dāng)前最好個(gè)體。

3 算例分析

粒子群優(yōu)化算法的相關(guān)參數(shù)設(shè)置如下:r1,r2∈(0,1)，慣性權(quán)重w=0.7298,社會(huì)系數(shù)和認(rèn)知系數(shù)c1=c2=1.49618，種群規(guī)模N=100,T=100。計(jì)算機(jī)運(yùn)行條件：(CPU:AMD Phenon (tm)ⅡX6 1055T 2.80GHz; RAM:3.25GB) 。利用C#編程進(jìn)行求解。

算例1

-4≤xi≤4,i=1,2,3，4，5

算例2

-5≤xi≤5,i=1,2，3

算例3

minz1(x)=x1

minz2(x)=g(x)h(x)

其中：

0≤x1≤1，-30≤x2≤30

圖6 算例1的Pareto最優(yōu)前沿面

算例1、算例2、算例3的Pareto最優(yōu)前沿面分別如圖6、圖7、圖8所示，可以很明顯地看出，筆者設(shè)計(jì)的算法所得多目標(biāo)規(guī)劃問(wèn)題的最優(yōu)前沿與理論前沿相當(dāng)接近，并且可以在理論前沿面上均勻分布。

4 結(jié)語(yǔ)

筆者設(shè)計(jì)的多目標(biāo)粒子群算法具有極強(qiáng)的全局搜索能力，通過(guò)3個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)檢驗(yàn)可以看出，算法在非劣解逼近Pareto非劣解的程度上比較顯著，非劣解分布比較均勻，所得結(jié)果比較穩(wěn)定。另一方面，相比于傳統(tǒng)算法的單一解，筆者所設(shè)計(jì)的算法得到了一組Pareto解集，從而可以為決策者提供了較大的選擇空間。

圖7 算例2的Pareto最優(yōu)前沿面 圖8 算例3的Pareto最優(yōu)前沿面

[參考文獻(xiàn)]

[1]Coello C.A comprehensive survey of evolutionary-based multiobjective optimization techniques[J].Knowledge and Information Systems,1999，1(3):269～308.

[2]Schaffer J D.Multiple Objective Optimization with Vector Evaluated Genetic Algorithms[A].International Conference on Genetic Algorithms[C].1985:93～100.

[3]Fonseca C M.Genetic Algorithms for Multipobjective Optimization[J].Formulation Discussion and Generalization，1993:416～423.

[4]Srinivas N, Deb K.Muiltiobjective Optimization Using Nondominated Sorting in Genetic Algorithms[M].MIT Press, 1994.

[5]Horn J, Nafpliotis N, Goldberg D E.A Niched Pareto Genetic Algorithm for Multiobjective Optimization[A].The 1st IEEE Congress on Evolutionary Computation[C].1994:82～87.

[6]Zitzler E, Thiele L.Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation, 1999, 3(4):257～271.

[7]Laumanns M.SPEA2: Improving the Strength Pareto Evolutionary Algorithm[R].Technical Report Gloriastrasse, 2001.

[8]Knowles J D, Corne D W.Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy[J].Evolutionary Computation, 2000, 8(2):149～172.

[9]Corne D W, Knowles J D, Oates M J.The Pareto Envelope-Based Selection Algorithm for Multiobjective Optimization[A].International Conference on Parallel Problem Solving From Nature[C].2000:839～848.

[10]Corne D W, Jerram N R, Knowles J D, et al.PESA-II: region-based selection in evolutionary multiobjective optimization[A].Conference on Genetic and Evolutionary Computation[C].2001:283～290.

[11]Erickson M, Mayer A, Horn J.The Niched Pareto Genetic Algorithm 2 Applied to the Design of Groundwater Remediation Systems[A].International Conference on Evolutionary Multi-Criterion Optimization[C].2001:681～695.

[12]Coello C, Pulido G T.A Micro-Genetic Algorithm for Multiobjective Optimization[A].Evolutionary Multi-Criterion Optimization[C].2001:126～140.

[13]Deb K, Pratap A, Agarwal S, et al.A fast and elitist multiobjective genetic algorithm: NSGA-II[J].IEEE Transactions on Evolutionary Computation, 2002, 6(2):182～197.

[14]Deb K, Saxena D K.On finding Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems[R].KanGAL Report，2005.

[15]Saxena D K, Deb K.Non-linear Dimensionality Reduction Procedures for Certain Large-Dimensional Multi-objective Optimization Problems: Employing Correntropy and a Novel Maximum Variance Unfolding[A].International Conference on Evolutionary Multi-Criterion Optimization[C].2007:772～787.

[16]Coello C, Pulido G T, Lechuga M S.Handling multiple objectives with particle swarm optimization[J].IEEE Transactions on Evolutionary Computation, 2004, 8(3):256～279.

[17]Gong M, Jiao L, Yang D.Corrections on the Box Plots of the Coverage Metric in “Multiobjective Immune Algorithm with Nondominated Neighbor-based Selection”[J].Evolutionary Computation, 2009, 17(1):131.

[18]Zhang Q, Zhou A, Jin Y.Errata to “RM-MEDA: A Regularity Model-Based Multiobjective Estimation of Distribution Algorithm”[J].IEEE Transactions on Evolutionary Computation, 2007, 12(1):41～63.

[19]Zhang Q, Li H.MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition[J].IEEE Transactions on Evolutionary Computation, 2007, 11(6):712～731.

[20]Coello C, Lechuga M.A proposal for multiple objective particle swarmoptimization[A].In Congress on Evolutionary Computation[C].2002:825～830.

[21]Yen G, Leong W.Dynamic Multiple Swarms in Multiobjective Particle Swarm Optimization[J].IEEE Transactions on Systems, Man and Cybernetics-Part A: Systems and Humans, 2009, 39(4):890～911.

[22]Tsai S， Sun T， Liu C, et al.An improved multi-objective particle swarm optimizer for multi-objective problems[J].Expert Systems with Applications, 2010, 37(8):5872～5886.