多進(jìn)化策略自適應(yīng)免疫多目標(biāo)進(jìn)化算法

康 錳,許 峰

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

根據(jù)待優(yōu)化目標(biāo)函數(shù)的數(shù)量，科研和工程應(yīng)用中廣泛存在的優(yōu)化問題可分為單目標(biāo)優(yōu)化問題和多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problem， MOP)。由于多個(gè)目標(biāo)間往往是相互沖突的，所以多目標(biāo)優(yōu)化算法通常提供的是一組能平衡各目標(biāo)的均衡解，即Pareto最優(yōu)解集(Pareto Optimum Solution Set， PS)，目標(biāo)函數(shù)在PS上值的集合稱為Pareto最優(yōu)前沿(Pareto Optimum Front， PF)。多目標(biāo)優(yōu)化要求算法的解既要盡可能地逼近真實(shí)的PF，又要沿著真實(shí)PF盡可能地均勻分布，即Pareto最優(yōu)解集的收斂性和分布性。由于進(jìn)化算法基于種群的特性，多目標(biāo)進(jìn)化算法(Multi-objective Evolutionary Algorithm， MOEA)被公認(rèn)為求解MOP最有效的方法。

優(yōu)化中著名的“No free lunch”定理表明，沒有一種優(yōu)化方法對所有問題都是有效的，各種方法都有其相應(yīng)的優(yōu)勢和劣勢。對于某些復(fù)雜的優(yōu)化問題，單一的優(yōu)化方法很難獲得令人滿意的解。因此，將不同優(yōu)化算法混合，通過交叉、融合產(chǎn)生新算法是智能優(yōu)化算法的一種重要研究思路。免疫多目標(biāo)進(jìn)化算法正是將人工免疫系統(tǒng)引入多目標(biāo)進(jìn)化算法而產(chǎn)生的新型多目標(biāo)進(jìn)化算法。

大多數(shù)免疫多目標(biāo)進(jìn)化算法均采用克隆選擇，其優(yōu)點(diǎn)是收斂速度較快，但過強(qiáng)的選擇壓力也使得這種選擇方法在一定程度上降低了種群的多樣性，容易導(dǎo)致算法陷入局部收斂。2002年，文獻(xiàn)[1]最先注意到了基于克隆選擇的免疫多目標(biāo)進(jìn)化算法的這個(gè)缺陷;2003年，文獻(xiàn)[2]提出了一種平衡收斂速度和種群多樣性的思路。近年來，利用混合的思路改善免疫多目標(biāo)進(jìn)化算法的工作取得了不少進(jìn)展[3-4]。2009年，文獻(xiàn)[5]將差分進(jìn)化策略引入免疫多目標(biāo)進(jìn)化算法;2015年，文獻(xiàn)[6]提出了一種基于克隆選擇和差分進(jìn)化的免疫多目標(biāo)進(jìn)化算法;2016和2017年，文獻(xiàn)[7-8]分別給出了一種在免疫多目標(biāo)進(jìn)化算法中進(jìn)行自適應(yīng)選擇參數(shù)和自適應(yīng)選擇進(jìn)化策略的方法。

文獻(xiàn)[9]最早在量子遺傳算法中用目標(biāo)函數(shù)的梯度確定量子旋轉(zhuǎn)門的轉(zhuǎn)角，文獻(xiàn)[10]42將目標(biāo)函數(shù)的變化率用于自適應(yīng)調(diào)用蟻群和遺傳算法。本文將目標(biāo)函數(shù)變化率引入基于克隆選擇的免疫多目標(biāo)差分進(jìn)化算法，用以進(jìn)行兩種差分進(jìn)化策略的自適應(yīng)選擇，利用DTLZ測試函數(shù)對新算法進(jìn)行了數(shù)值實(shí)驗(yàn)和性能測試，并與其他算法進(jìn)行了比較，驗(yàn)證了新算法的有效性。

1 克隆選擇多目標(biāo)進(jìn)化算法

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

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

多目標(biāo)差分進(jìn)化算法(Multi-objective Differential Evolution Algorithm， MODE)是在差分進(jìn)化算法的基礎(chǔ)上發(fā)展起來的一種多目標(biāo)進(jìn)化算法。本文采用的是基于克隆選擇的多目標(biāo)差分進(jìn)化算法。

1.2 克隆選擇

最典型的人工免疫算法是克隆選擇算法。著名免疫學(xué)家Burnet于1958年提出了生物克隆免疫學(xué)說，其核心思想是：抗原有選擇性地與相應(yīng)的抗體進(jìn)行反應(yīng)。文獻(xiàn)[12]根據(jù)Burnet的抗體克隆選擇學(xué)說，提出了一種通用的克隆選擇算法，流程圖如圖1所示。

圖1 通用克隆選擇算法流程圖

1.3 最優(yōu)解集的評價(jià)標(biāo)準(zhǔn)

通常， 可以對多目標(biāo)優(yōu)化最優(yōu)解集從解的收斂性和分布性兩方面進(jìn)行評價(jià)， 常用的量化評價(jià)指標(biāo)[10]43有：

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

γ指標(biāo)衡量非支配解集Q對理論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 多進(jìn)化策略多目標(biāo)進(jìn)化算法

2.1 兩種差分進(jìn)化策略

差分進(jìn)化策略已被證明是多目標(biāo)優(yōu)化算法中的一種簡單、有效的進(jìn)化方法[13]3。在DE中，設(shè)置不同的控制參數(shù)可以使得DE呈現(xiàn)不同的搜索特性。本文采用下列兩種DE策略[8]52：

DE1：Ui，j={Xr1，j+F·(Xr2，j-Xr3，j)+F·(Xr4，j-

Xr5，j)，r

(3)

DE2：Ui，j={Xr1，j+F·(Xr1，j-Xr2，j)，

r

(4)

式中：Ui，j稱為試驗(yàn)向量，Xi，j是當(dāng)前種群中的目標(biāo)向量，F(xiàn)是比例因子，Cr是交叉率，r是[0，1]中的隨機(jī)數(shù)，下標(biāo)r1～r5是從[1，2，…，n]中隨機(jī)選擇的整數(shù)，下標(biāo)j表示第j個(gè)決策變量。大量實(shí)驗(yàn)顯示[13]31，F(xiàn)，Cr的取值范圍應(yīng)為：F∈(0.3，0.9)，Cr∈(0.1，0.9)。本文中，DE1中的參數(shù)為：F=0.7，Cr=0.4;DE2中的參數(shù)為：F=0.3，Cr=0.7。

F的值決定了搜索步長即搜索速度，F(xiàn)越大(小)，搜索步長越大(小)，搜索速度越快(慢)。Cr的值決定了子代(試驗(yàn)向量)可以從其父代(目標(biāo)向量)中繼承信息量的多少，Cr越小(大)，子代從父代中繼承的信息量越多(少)。因此，相比較而言，DE1側(cè)重于開拓新的搜索區(qū)域且搜索速度較快，即具有較強(qiáng)的全局搜索能力，而DE2則較容易生成新的個(gè)體，即有助于維持種群的多樣性。

2.2 基于目標(biāo)函數(shù)變化率的進(jìn)化策略自適應(yīng)選擇方法

在進(jìn)化早期，通常采用DE1以加快搜索進(jìn)度，而在進(jìn)化后期，則采用DE2以維持種群多樣性，避免算法陷入局部最優(yōu)。如何合理地動(dòng)態(tài)調(diào)用不同的進(jìn)化策略是進(jìn)化計(jì)算中一個(gè)值得研究的問題。

考慮到在進(jìn)化早期，目標(biāo)函數(shù)的變化率較大，而在進(jìn)化后期，目標(biāo)函數(shù)的變化率則較小，本文采用下列方法自適應(yīng)地動(dòng)態(tài)調(diào)用DE1和DE2[10]44。

定義

(5)

其中

(6)

(7)

對于離散優(yōu)化問題，f(X)不存在梯度，則

(8)

(9)

(10)

其中，Xp，Xc分別表示父代和子代個(gè)體。

當(dāng)γij小于設(shè)定的閾值ε(通常取為10-2)時(shí)，選擇DE1，否則選擇DE2。

2.3 算法流程

本文提出的多進(jìn)化策略自適應(yīng)免疫多目標(biāo)進(jìn)化算法(Adaptive Immune Multi-objective Evolutionary Algorithm with Multi-evolutionary Strategy， AIMOEA)的流程如下：

Step1 種群初始化;

Step2 根據(jù)1.2中的算法對種群進(jìn)行克隆選擇;

Step3 對選擇后的種群，根據(jù)2.2中的方法，選擇DE1或DE2進(jìn)行進(jìn)化，生成新種群;

Step4 對新種群進(jìn)行非支配排序，生成非支配集;

Step5 選擇非支配等級低且擁擠密度小的個(gè)體作為精英個(gè)體，構(gòu)成下一代進(jìn)化種群;

Step6 若滿足終止條件，則算法終止;否則轉(zhuǎn)Step2，直至滿足終止條件。

上述算法中之所以采用了精英選擇，主要目的是防止在優(yōu)化過程中由于隨機(jī)因素和群體規(guī)模的限制而丟失優(yōu)良解。

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

為了評測AIMOEA算法的性能，選取DTLZ6和DTLZ1兩個(gè)測試函數(shù)進(jìn)行數(shù)值實(shí)驗(yàn)。選用這兩個(gè)測試函數(shù)的原因是前者的PF為空間曲線，而后者的PF為空間曲面。硬件配置為Intel Core I5 2.5GHz、4G內(nèi)存，開發(fā)環(huán)境為Matlab2014。實(shí)驗(yàn)參數(shù)設(shè)置：進(jìn)化代數(shù)為100，種群規(guī)模為100，交叉概率為0.8。

圖2～圖7分別給出了AIMOEA、NSGA-II和MOEA/D-DE三種算法生成的DTLZ6和DTLZ1的最優(yōu)前沿。選擇NSGA-II和MOEA/D-DE作為對比算法是由于NSGA-II是經(jīng)典的第二代多目標(biāo)進(jìn)化算法，MOEA/D-DE[8]61則是收斂性和分布性較為均衡的多目標(biāo)進(jìn)化算法。

圖2 DTLZ6的AIMOEA算法最優(yōu)前沿

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

圖4 DTLZ6的NSGA-II算法最優(yōu)前沿

圖5 DTLZ1的NSGA-II算法最優(yōu)前沿

圖6 DTLZ6的MOEA/D-DE算法最優(yōu)前沿

圖7 DTLZ1的MOEA/D-DE算法最優(yōu)前沿

從上述圖形中可以直觀地看出，AIMOEA算法得到的Pareto最優(yōu)前沿較好地逼近了理論P(yáng)areto最優(yōu)前沿，而且具有較好的分布性和均勻性。

為了進(jìn)一步定量地評價(jià)AIMOEA算法的性能，本文將其與NSGA-II和MOGA/D-DE對DTLZ6和DTLZ1的優(yōu)化情況進(jìn)行了比較，評價(jià)標(biāo)準(zhǔn)采用通用的γ指標(biāo)和Δ指標(biāo)。對比實(shí)驗(yàn)中的參數(shù)均采用相應(yīng)文獻(xiàn)中的推薦值，γ指標(biāo)和Δ指標(biāo)為各算法獨(dú)立運(yùn)行20次的平均值，具體結(jié)果見表1。

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

表1中的γ指標(biāo)和Δ指標(biāo)表明，AIMOEA算法在解集的收斂性和分布性兩方面均在一定程度上優(yōu)于NSGA-II;與MOEA/D-DE相比，AIMOEA算法在解集的收斂性上稍遜一籌，但在分布性方面則占有一定優(yōu)勢。在一定程度上說明，AIMOEA算法中的克隆選擇可以保證算法的收斂性，而自適應(yīng)動(dòng)態(tài)調(diào)用兩種不同的差分進(jìn)化策略的確可以改善種群的多樣性，從而提高解集的分布性和均勻性。MOEA/D-DE算法收斂性較好的原因是其在MOEA/D算法的基礎(chǔ)上也加入了差分進(jìn)化策略。

4 結(jié)論

數(shù)值實(shí)驗(yàn)結(jié)果和統(tǒng)計(jì)指標(biāo)顯示，本文提出的多進(jìn)化策略自適應(yīng)免疫多目標(biāo)進(jìn)化算法可以根據(jù)目標(biāo)函數(shù)變化率動(dòng)態(tài)地選擇不同的差分進(jìn)化策略，在保持克隆免疫算法收斂速度高的同時(shí)，所得的解比單進(jìn)化策略算法的解具有更好的分布性和均勻性。雖然大多數(shù)學(xué)者都認(rèn)為人工免疫系統(tǒng)可以有效地克服進(jìn)化算法中早熟和種群多樣性下降等缺陷，但至今沒有理論上的結(jié)果，對算法性能的研究只能局限于對測試函數(shù)的對比實(shí)驗(yàn)，在一定程度上影響了進(jìn)化算法的研究和應(yīng)用價(jià)值。另外，實(shí)驗(yàn)表明，參數(shù)F，Cr的取值對算法的收斂性和解的分布性、均勻性有一定影響。因此，如何選擇、優(yōu)化參數(shù)F，Cr是今后值得研究的問題。