車 旭，許 峰

(安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001)

現(xiàn)實(shí)中的最優(yōu)化問題有時(shí)為多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problem, MOP)，甚至為高維多目標(biāo)優(yōu)化問題(Large-dimensional Multi-objective Optimization Problem, LMOP)。此類問題要求算法既能平衡多目標(biāo)間的沖突，又要適應(yīng)高維多目標(biāo)中高維復(fù)雜空間的搜索需求，保證Pareto最優(yōu)解集的收斂性和分布性。多目標(biāo)進(jìn)化算法(Multi-objective Evolutionary Algorithm, MOEA)是目前公認(rèn)的求解MOP最有效的優(yōu)化方法，但在求解LMOP時(shí)算法性能通常大幅下降，普遍存在計(jì)算復(fù)雜度高，近似解不能很好地逼近真實(shí)Pareto前沿，分布不均勻，穩(wěn)定性差等問題。因此，如何針對(duì)高維多目標(biāo)優(yōu)化問題的特性，設(shè)計(jì)出高性能的MOEA以滿足LMOP的求解需求已成為進(jìn)化算法研究中的熱點(diǎn)問題。

目前，一些性能較優(yōu)的求解LMOP的MOEA已經(jīng)陸續(xù)被提出，主要分為兩類：一類是基于精英選擇的高維多目標(biāo)進(jìn)化算法，代表性算法有NSGA-III、GrEA、SPEA2+SDE等，這類算法適合求解目標(biāo)維數(shù)不太高但Pareto前沿較復(fù)雜的高維多目標(biāo)優(yōu)化問題；另一類是基于多目標(biāo)分解的高維多目標(biāo)進(jìn)化算法，代表性算法有MOEA/D、Adaptive-MOEA/D、MOEA/D-AGR等，這類算法適合求解目標(biāo)維數(shù)較高但Pareto前沿較簡(jiǎn)單的高維多目標(biāo)優(yōu)化問題。

2006年，Deb[1]和Brockhoff[2]分別從不同角度提出了在高維多目標(biāo)進(jìn)化算法中進(jìn)行目標(biāo)約簡(jiǎn)的思想；2015年，Bandyopadhyay[3]將目標(biāo)約簡(jiǎn)思想應(yīng)用于高維多目標(biāo)差分進(jìn)化算法；2016年，Blasco[4]在進(jìn)行高維Pareto前沿分析時(shí)引入了相似距離，并將其用于目標(biāo)約簡(jiǎn)；2018年，Monalisa[5]在一種多目標(biāo)差分進(jìn)化算法中引入聚類方法以進(jìn)行目標(biāo)約簡(jiǎn)。

本文在前人工作的基礎(chǔ)上，將聚類方法加入一種基于精英保留策略的高維多目標(biāo)差分進(jìn)化算法，用以進(jìn)行目標(biāo)約簡(jiǎn)，利用DTLZ測(cè)試函數(shù)對(duì)新算法進(jìn)行了數(shù)值實(shí)驗(yàn)和性能測(cè)試，并與其他算法進(jìn)行了比較。

1 高維多目標(biāo)差分進(jìn)化算法

1.1 多目標(biāo)差分進(jìn)化算法

差分進(jìn)化算法(Differential Evolution Algorithm, DE)是1995年Rainer Storn和Kenneth Price提出的一種基于進(jìn)化思想和種群差異的群智能優(yōu)化算法。DE算法的原理簡(jiǎn)單，受控參數(shù)少，全局收斂速度快。

多目標(biāo)差分進(jìn)化算法(Multi-objective Differential Evolution Algorithm, MODE)是在差分進(jìn)化算法的基礎(chǔ)上發(fā)展起來的一種多目標(biāo)進(jìn)化算法。本文采用的是基于精英保留的多目標(biāo)差分進(jìn)化算法，精英選擇主要包含快速非支配排序、擁擠密度估計(jì)和精英個(gè)體保留3項(xiàng)操作，算法流程如圖1所示。

圖1 精英選擇多目標(biāo)差分進(jìn)化算法流程圖

1.2 高維多目標(biāo)差分進(jìn)化算法

通常目標(biāo)維數(shù)超過4的多目標(biāo)優(yōu)化問題稱為高維多目標(biāo)優(yōu)化問題。高維多目標(biāo)優(yōu)化算法求解性能不佳的主要原因是目標(biāo)搜索空間和Pareto非支配解集均呈指數(shù)級(jí)增長(zhǎng)，精英選擇和解集的分布性不易實(shí)現(xiàn)，具體表現(xiàn)為：

1)Pareto最優(yōu)前沿為超曲面，計(jì)算復(fù)雜度急劇增加，收斂速度大幅下降；

2)Pareto支配關(guān)系成立的概率大幅下降，支配個(gè)體出現(xiàn)的比例大幅增加，使得精英選擇的壓力急劇減弱，收斂精度大幅下降；

3)目標(biāo)函數(shù)空間的數(shù)據(jù)具有稀疏性，各種基于距離的維護(hù)種群多樣性的方法基本無效，使得解集的分布性大幅減弱。

為了提高高維多目標(biāo)優(yōu)化算法的性能，許多學(xué)者提出了多種有效的改進(jìn)方法。這些改進(jìn)方法主要分為下列三類：

1)提高高維多目標(biāo)優(yōu)化算法的收斂性能，關(guān)鍵技術(shù)包括：新型Pareto支配方法、非Pareto支配方法、精英選擇策略等；

2)提高高維多目標(biāo)優(yōu)化算法解集分布性，關(guān)鍵技術(shù)包括：擁擠距離方法、網(wǎng)絡(luò)策略、小生境技術(shù)等；

3)降低高維多目標(biāo)優(yōu)化算法的維數(shù)和復(fù)雜度，關(guān)鍵技術(shù)包括：多目標(biāo)分解、冗余目標(biāo)刪除、偏好空間縮減等。

本文的算法主要涉及精英選擇策略和目標(biāo)約簡(jiǎn)。

1.3 多目標(biāo)優(yōu)化最優(yōu)解集的評(píng)價(jià)標(biāo)準(zhǔn)

通?？梢詫?duì)多目標(biāo)優(yōu)化最優(yōu)解集從解的收斂性和分布性兩方面進(jìn)行評(píng)價(jià)，常用的量化評(píng)價(jià)指標(biāo)有：

1)收斂性指標(biāo)γ

γ指標(biāo)衡量非支配解集Q對(duì)理論P(yáng)areto最優(yōu)解集P*的逼近程度，計(jì)算公式為

(1)

式中：di為非支配解集Q中的個(gè)體i與P*中距離最近個(gè)體的距離。顯然，γ越小，表明算法取得的非支配解集Q逼近理論P(yáng)areto最優(yōu)解集P*的程度越高，即算法的收斂性越好。

2)分布性指標(biāo)Δ

Δ指標(biāo)衡量非支配解集Q中個(gè)體的分布性和均勻性，計(jì)算公式為

(2)

2 基于聚類的多目標(biāo)約簡(jiǎn)差分算法

2.1 聚類與目標(biāo)約簡(jiǎn)

近年來陸續(xù)有學(xué)者從統(tǒng)計(jì)學(xué)角度出發(fā)，提出根據(jù)目標(biāo)函數(shù)間的相關(guān)性進(jìn)行目標(biāo)函數(shù)的約簡(jiǎn)[6-7]。本文采用的相關(guān)性指標(biāo)是相關(guān)距離，定義如下：

(3)

式中：A=(a1,a2,…,an)T,B=(b1,b2,…,bn)T是兩個(gè)n維向量。上述定義實(shí)際上就是對(duì)統(tǒng)計(jì)學(xué)中的樣本相關(guān)系數(shù)做了一個(gè)簡(jiǎn)單的變換，其目的是使得D(A,B)∈[0,2]。

根據(jù)相關(guān)距離利用聚類的方法進(jìn)行目標(biāo)約簡(jiǎn)的步驟如下：

1)對(duì)m個(gè)目標(biāo)f1(x),f2(x),…,fm(x)和n個(gè)個(gè)體X1,X2,…,Xn，得到下列n×m矩陣

2)對(duì)上述矩陣，根據(jù)式(3)計(jì)算得到下列對(duì)稱的相關(guān)距離矩陣如下

其中，D(fi,fj)為向量A=(fi(X1),fi(X2),…,

fi(Xn))T,B=(fj(X1),fj(X2),…,fj(Xn))T間的相關(guān)距離。

3)對(duì)相關(guān)距離矩陣，用K-均值聚類方法對(duì)其進(jìn)行聚類，在同一聚類中，最終只保留聚類中心。這樣做的目的是在若干相似的目標(biāo)函數(shù)中只保留一個(gè)最具代表性的目標(biāo)，其結(jié)果是既約簡(jiǎn)了目標(biāo)函數(shù)的維數(shù)，又在很大程度上保留了沖突較大的目標(biāo)函數(shù)，即確保了約簡(jiǎn)后的問題解的質(zhì)量不會(huì)大幅下降。

2.2 算法流程

本文提出的基于聚類的目標(biāo)約簡(jiǎn)高維多目標(biāo)差分進(jìn)化算法(Multi-objective Differential Evolution Algorithm using Clustering, MODEC)的流程如下：

1)種群初始化；

2) 根據(jù)2.1中的基于精英保留的多目標(biāo)差分進(jìn)化算法(MODE)對(duì)種群進(jìn)行非支配排序、選擇、交叉、變異、精英選擇，得到新種群；

3) 根據(jù)式(3)計(jì)算得到目標(biāo)函數(shù)的相關(guān)距離矩陣；

4) 對(duì)相關(guān)距離矩陣，用K-均值聚類方法對(duì)目標(biāo)函數(shù)進(jìn)行聚類，約簡(jiǎn)目標(biāo)函數(shù)；

5) 對(duì)約簡(jiǎn)目標(biāo)集用MODE算法進(jìn)行新的進(jìn)化，得到約簡(jiǎn)問題的Pareto最優(yōu)解集；

6) 若滿足終止條件，則算法終止；否則轉(zhuǎn)2)，對(duì)全目標(biāo)集用MODE算法進(jìn)行優(yōu)化，直至滿足終止條件。

算法之所以輪流在全目標(biāo)集和約簡(jiǎn)目標(biāo)集中搜索，主要目的是同時(shí)兼顧解集的質(zhì)量和算法的運(yùn)行效率。

3 數(shù)值實(shí)驗(yàn)與算法性能評(píng)測(cè)

為了評(píng)測(cè)MODEC算法的性能，選取4～20目標(biāo)的標(biāo)準(zhǔn)測(cè)試函數(shù)集DTLZ1～4[8]進(jìn)行數(shù)值實(shí)驗(yàn)。硬件配置為Intel Core I5 2.5GHz、4G內(nèi)存，開發(fā)環(huán)境為Matlab2014。實(shí)驗(yàn)參數(shù)設(shè)置：變量維數(shù)為20，進(jìn)化代數(shù)為1 000，種群規(guī)模為100，交叉概率為0.8。

圖2～圖9分別給出了DTLZ1～4的理論P(yáng)areto最優(yōu)前沿和MODEC算法生成的Pareto最優(yōu)前沿。其中，目標(biāo)維數(shù)為10。

圖2 DTLZ1理論P(yáng)areto最優(yōu)前沿

圖3 DTLZ1的MODEC算法Pareto最優(yōu)前沿

圖4 DTLZ2理論P(yáng)areto最優(yōu)前沿

圖5 DTLZ2的MODEC算法Pareto最優(yōu)前沿

圖6 DTLZ3理論P(yáng)areto最優(yōu)前沿

圖7 DTLZ3的MODEC算法Pareto最優(yōu)前沿

圖8 DTLZ4理論P(yáng)areto最優(yōu)前沿

圖9 DTLZ4的MODEC算法Pareto最優(yōu)前沿

從上述圖形中可以直觀地看出，MODEC算法不僅可以有效約簡(jiǎn)目標(biāo)維數(shù)，而且約簡(jiǎn)后的問題的Pareto最優(yōu)前沿較好地逼近了理論P(yáng)areto最優(yōu)前沿。

為了進(jìn)一步定量地評(píng)價(jià)MODEC算法的性能，本文將其與目前具有代表性的NSGA-III和MOGASd算法[9]581對(duì)DTLZ1～4的優(yōu)化情況進(jìn)行了比較，評(píng)價(jià)標(biāo)準(zhǔn)采用通用的γ指標(biāo)和Δ指標(biāo)。對(duì)比實(shí)驗(yàn)中的參數(shù)均采用相應(yīng)文獻(xiàn)中的推薦值，γ指標(biāo)和Δ指標(biāo)為各算法獨(dú)立運(yùn)行10次的平均值，具體結(jié)果見表1。

表1 三種算法的γ和Δ指標(biāo)對(duì)比

表1中的γ指標(biāo)和Δ指標(biāo)顯示，MODEC算法在解集的收斂性和分布性兩方面均明顯優(yōu)于NSGA-III，其原因在于NSGA-III僅僅是在NSGA-II基礎(chǔ)上改進(jìn)而得，對(duì)高維問題的優(yōu)化效果欠佳。與MOGASd算法相比，MODEC算法解集的收斂性略占優(yōu)，而在分布性方面則基本相當(dāng)，其原因是MOGASd算法采用了適應(yīng)值共享方法以維持種群多樣性[9]590。

4 結(jié)論

數(shù)值仿真實(shí)驗(yàn)和統(tǒng)計(jì)指標(biāo)表明，本文提出的基于聚類的目標(biāo)約簡(jiǎn)高維多目標(biāo)差分進(jìn)化算法具有較好的收斂性和分布性，可有效地求解高維多目標(biāo)優(yōu)化問題。需要指出的是，與其他群智能優(yōu)化算法類似，高維多目標(biāo)差分進(jìn)化算法也存在著諸多不足，如控制參數(shù)難以確定、搜索有一定的盲目性、后期收斂速度慢、易陷于局部最優(yōu)等。并且，差分進(jìn)化算法的理論基礎(chǔ)還比較薄弱，對(duì)算法性能的研究只能圄于對(duì)測(cè)試函數(shù)的對(duì)比實(shí)驗(yàn)，這在一定程度上阻礙了差分進(jìn)化算法的研究與應(yīng)用。