兩階段動態(tài)差分智能元胞機算法

王亞良，倪晨迪，曹海濤，錢其晶，金壽松

(浙江工業(yè)大學 機械工程學院，浙江 杭州 310023)

0 引言

在工業(yè)領域如計算機科學[1-2]，航空航天工程[3-4]和機械制造[5]等存在大量的多目標優(yōu)化問題(Multi-objective Optimization Problems, MOPs)，MOPs的子目標間可能相互沖突，所有子目標不能同時達到最佳。在工程實踐中需對它們進行妥協(xié)折中處理，期望得到一個非支配解集(Non-dominated solutions)，集合中每個解都是帕累托最優(yōu)(Pareto optimum)，被繪制在目標空間時即為帕累托前端(Pareto front)。傳統(tǒng)的優(yōu)化方法在求解MOPs時存在求解困難或多樣性收斂性不佳的問題[6]。進化算法(Evolutionary Algorithms，EA)是一種基于種群的啟發(fā)式搜索算法，可分為4類[7]：遺傳算法(Genetic Algorithm，GA)、遺傳規(guī)劃(Genetic Programming，GP)、進化策略(Evolution Strategy，ES)和進化規(guī)劃(Evolution Programming，EP)。進化算法比較適合處理MOP，目前比較經(jīng)典的求解MOPs算法如NSGA-Ⅱ(Non-dominated Sorting Genetic AlgorithmⅡ)[8]，PAESⅡ Pareto Envelop-based Selection Algorithm Ⅱ)[9]和SPEA2(Strength Pareto Evolution Algorithm 2)[10]等。

元胞遺傳算法(Cellular Genetic Algorithm，CGA)是融合CA與GA優(yōu)點整合而成的一種新GA，算法的核心思想是將遺傳算法的種群分布在二維細胞網(wǎng)格上，每個個體都占據(jù)一個特定的元胞并定義該元胞的狀態(tài)[11-12]。許多學者在這方面開展了卓有成效的研究和探索。Kirley[13]提出了一種基于災變機制的CGA，改變了原有種群分布，提高了種群的多樣性。文獻[14-15]從元胞的種群結構出發(fā)對算法進行改進分別提出分層CGA和自適應種群鄰居的CGA。Alba等[16]提出了元胞多目標遺傳算法(Cellular Multi-Objective Genetic Algorithm，CMOGA)。Nebro等[7]對CMOGA其進行改進，增加了外部種群的反饋機制，提出了MOCell，提升了算法局部尋優(yōu)能力。之后，Durillo等[17-18]把差分進化算法(Differential Evolution，DE)與MOCell進行了耦合，并提出了用于解決多目標復雜工程問題的元胞差分算法(Celluar Differential Evolution, CellDE)，并取得了不錯的效果。文獻[19-20]將CellDE分別用于求解機組排班多目標問題和移動自組織網(wǎng)絡，進一步驗證了CellDE兼具MOCell和DE的優(yōu)點。張屹等[21]利用CellDE算法求解車間布局優(yōu)化問題的Pareto解集，詹騰等[22]提出基于多策略差分進化的元胞多目標遺傳算法，驗證了CellDE結合了MOCell和DE的優(yōu)點。王亞良等[23]提出外部種群完全反饋的元胞差分(New Cellular Differential Evolution, NCe11DE)算法。Azizipour等[24]提出了一種新的遺傳算法與元胞機相結合的混合算法，用遺傳算法處理問題的可靠性部分，用CA方法解決問題的可操作性部分。GAN等[25]在元胞機基礎上提出了雙向進化優(yōu)化的混合元胞機算法，具有計算效率高和穩(wěn)定性好的特性。Redjepov等[26]提出了二維元胞機的可逆性算法。

CA是描述自然界復雜現(xiàn)象的數(shù)學模型，它主要由元胞、元胞空間、鄰居和演化規(guī)則構成。目前將CA應用于GA的研究大體分為兩類：第一類用CA豐富的演化規(guī)則來替代傳統(tǒng)GA中的某些遺傳操作；第二類則以復雜系統(tǒng)理論為基礎，它將種群中的個體分配到元胞空間中，借助CA模型的鄰居結構來實現(xiàn)GA的操作。CA理論研究主要包括前向問題即元胞機的分析和反向問題即元胞機的綜合，CA模型屬于“微觀”模型，需要融合其他方法才能取得較為理想的解決方案。

為此，本文將智能體(Agent)機制引入元胞種群，并通過對元胞機個體鄰居結構進行調(diào)整，實現(xiàn)進化種群由結構化種群過渡至非結構化種群，采用兩階段的外部種群多樣性維護方法，將擾動因子引入變異操作避免陷入局部最優(yōu)，引入多智能體方法和差分演化策略等來彌補CA的不足，提出一種外部種群充分引導的兩階段動態(tài)差分智能元胞機算法(Dynamic Differential Evolution Agent Cellular Automata，DDEACA)。通過三目標WFG系列函數(shù)對算法進行測試和分析，驗證了DDEACA算法的有效性，能較好地兼顧全局搜索和局部尋優(yōu)之間的協(xié)同問題。

1 元胞差分及其改進算法

Durillo等[18]在MOCell中引入差分進化操作，提出了基本的多目標元胞差分算法(CellDE)，CellDE在解決三目標優(yōu)化問題時獲得了質(zhì)量較好的Pareto前端。CellDE采用近似DE/rand/1的變異方式，其基向量不是隨機選擇的，而是當前進化個體，故DE的父本由當前個體和兩個鄰居構成。設種群規(guī)模為N，d為解空間的維數(shù)。Xr1、Xr2、Xr3為3個父本向量，Vi為變異向量，Ui為子代向量，其主要內(nèi)容如下。

(1)變異操作

Vi.j=Xr1.j+F(Xr2.j-Xr3.j),i∈[1,N],

j∈[1,d]。

(1)

式中F為介于[0,1]間的縮放因子。

(2)交叉操作

(2)

式中：randi.j為[0,1]之間均勻分布的隨機數(shù)，CR為介于[0,1]間的交叉常量，randj(i)∈[1,2,…,d]。

外部種群完全反饋的元胞差分算法(NCellDE)作為元胞差分算法的典型改進算法，與傳統(tǒng)的CellDE相比，在外部種群的多樣維護機制、種群個體優(yōu)劣評判標準和外部種群反饋機制都進行優(yōu)化和改進，取得較好的效果[23]。

2 兩階段動態(tài)差分智能元胞機算法(DDEACA)

DDEACA是基于NCellDE算法而提出的，同時將Agent機制引入CA空間封裝并擴展為具有自主性的智能型元胞機，充分利用Agent的自治特性，并結合結構化種群(元胞種群結構)和非結構化種群的優(yōu)點，對個體(元胞)的鄰居結構進行變化，將個體的鄰居結構(如Moore型)擴大至整個進化種群，通過對個體的鄰居結構進行調(diào)整，實現(xiàn)進化種群由結構化種群過渡到非結構化種群的效果，更好地實現(xiàn)全局尋優(yōu)和局部尋優(yōu)之間的平衡；同時為了減少算法對外部種群的維護時間開銷，并提高算法的收斂速度，對外部種群保留的對象進行調(diào)整及完全反饋。鄰居結構的變化將整個進化過程分成兩個階

段。在進化的第一個階段，外部種群并不一定要保留非支配解；在進化的第二階段，外部種群保留非支配解，同時一旦外部種群中的非支配個體超過預定規(guī)模，就立刻對外部種群進行修剪。鄰居結構和外部種群保留對象角色的變化賦予算法在兩階段尋優(yōu)中具備不同的側重點。算法的第一階段側重全局探索，第二階段側重局部挖掘，如圖1所示。

DDEACA算法的流程如圖2所示，算法步驟如表1所示。

表1 算法步驟

DDEACA算法偽代碼如下：

1:population←create_Population() //創(chuàng)建初始種群

2:archive←create_Archive(population) //創(chuàng)建外部種群

3:while!terminationCondition()

4: if first-stage

5: for individual:1 to populationSize

6: neighborhood←get_Neighbours(population, position(individual));

7: parent1←select(neighbourhood);

8: parent2←select(neighbourhood);

9: while parent1=parent2

10: parent2←select(neighbourhood);

11: end while

12: offspring←DifferentialEvolution(individual, parent1, parent2);

13: evaluateFitness(offspring);

14: insert(position(individual), offspring, population);

15: add_Archive(individual); //加入外部種群

16: end for

17: population←replace_Individuals(population, archive); //反饋

18: else

19: if first gen of second-stage//第二階段第一代

20: archive←change_Archive(archive)//外部種群保留非支配個體

21: end if

22: population←change_Population(archive) //外部種群作為進化種群

23: for individual:1 to populationSize

24: neighborhood←get_Neighbours(population, position(individual));

25: parent1←select(neighbourhood);

26: parent2←select(neighbourhood);

27: while parent1=parent2

28: parent2←select(neighbourhood);

29: end while

30: offspring←DifferentialEvolution(individual, parent1, parent2);

31: evaluateFitness(offspring);

32: add_Archive(individual); //加入外部種群

33: end for

34: end if

35:end while

2.1 算法第一階段外部種群多樣性維護

DDEACA算法的第一階段外部種群多樣性維護與NCellDE算法類似，首先對外部種群進行非支配排序，然后按表2中的規(guī)則對其進行維護篩選，設外部種群中秩為1的個體數(shù)量為a，外部種群規(guī)模為b，具體篩選過程如圖3。

表2 外部種群多樣性維護規(guī)則

2.2 算法第一階段外部種群完全反饋

CellDE采用精英保留策略，其個體進入外部種群的標準非常嚴格。DDEACA算法在第一階段進化時其外部種群需具備兩方面功能：其一保留進化結束后的優(yōu)良個體，其二收集當前進化過程中的優(yōu)秀子代。在當代進化結束后，根據(jù)外部種群多樣性維護規(guī)則進行處理，將剩余的所有個體作為下一代的父本，并將它們隨機分配到二維環(huán)形網(wǎng)狀結構中，如圖4所示。

2.3 算法第二階段外部種群和鄰居結構變化

DDEACA在第二階段進化時，外部種群的保留的不再是優(yōu)秀個體，而是采取CellDE的外部種群保留策略，即外部種群只保留非支配個體，同時非支配個體的數(shù)目一旦超過外部種群規(guī)模，則立刻對外部種群進行修剪。與第一階段不同，第二階段下一代進化的種群實際上是上一代外部種群中保留的非支配個體。同時為了進一步調(diào)高算法的選擇壓力，加快算法的收斂速度。在第二階段進化時，個體的鄰居不再局限于局部范圍，而是將整個外部種群中的其他個體都作為其鄰居。如圖5所示為外部種群和鄰居結構變化的比較示意圖。

2.4 實驗參數(shù)設置

在WFG系列問題上，將DDEACA同NSGA-Ⅱ、SPEA2、CellDE、NCellDE四種算法進行對比，考慮到運行時間等情況，其參數(shù)設置如表3所示。

表3 實驗參數(shù)設置表

NSGA-Ⅱ、SPEA2采用模擬二進制交叉，多項式

變異，交叉概率為0.9，變異概率為1/v(v為變量的個數(shù))。在CellDE、NCellDE和DDEACA中，F(xiàn)=0.5，CR=0.1。每種算法獨自運行50次。

2.5 DDEACA算法混合進化代數(shù)分配

DDEACA算法具有兩階段性，涉及第一階段和第二階段如何合理配置的問題，即第二階段何時開始？本文以第二階段與總進化代數(shù)的比值作為控制變量P，觀察P對算法的性能影響和算法運行時間的影響。選取具有欺騙性和多峰的WFG9函數(shù)為測試函數(shù)(3個目標，24個決策變量)。DDEACA算法的運行參數(shù)如下：進化代數(shù)N=1 000，分別取縮放因子F=0.5、交叉因子CR=0.1，在不同的控制變量P下，算法運行15次。選取世代距離GD、超體積HV對算法性能進行分析評估。表4給出了實驗結果。

表4 P對算法的性能影響

由表4的數(shù)據(jù)可知，當P值越大，即第二階段占總進化代數(shù)時間越長時，算法的超體積越大，收斂性越好。但隨著P值的增加，算法的運行時間也增加了。在算法能保持住多樣性的前提下，算法收斂性的提高與算法第二階段的運行最大進化代數(shù)的時間開銷是矛盾的，綜合考慮收斂性能和運行時間開銷兩個因素，取P=0.3，即最大進化代數(shù)的前0.7代為第一階段，后0.3代為第二階段。

3 基準函數(shù)測試

3.1 基準函數(shù)

選擇三目標的WFG系列函數(shù)對5種算法進行測試。WFG函數(shù)具有多峰性、偏好性、欺騙性和可分性等特性，其最優(yōu)Pareto前端形狀可以是凹/凸的、線性/非線性的、退化的及上述形狀特征的組合[28-29]。WFG函數(shù)的特征如表5所示，其三目標Pareto最優(yōu)邊界如圖6。

表5 測試函數(shù)特征

續(xù)表5

3.2 算法性能評價指標

性能度量指標如反向世代距離(Inverted Generational Distance, IGD)、ε[27]、世代距離(Generational Distance, GD)、分布指標(Spread, Δ)、超體積(Hypervolume, HV)[10]等。WFG函數(shù)由于最優(yōu)前端幅值不等且部分問題的形狀復雜[28]，本文采用GD和HV指標對算法性能進行測試分析。

(1)世代距離

世代距離是用來計算所得的Pareto前端收斂到最優(yōu)Pareto前端的程度：

(3)

式中：n為近似Pareto前端中個體的數(shù)目，di為第i個解的目標函數(shù)構成的向量與Pareto最優(yōu)前端之間的最近距離，GD大小與解的收斂性成反比。

(2)超體積

超體積用來計算獲得的Pareto前端在目標空間所覆蓋的體積：

(4)

超體積大小與Pareto前端的多樣性、收斂性成線性關系。在三維目標空間中，vi是由參考點W與解i的目標向量作為對角點所形成的空間(長方體)的體積。

4 測試結果分析

4.1 算法性能測試及分析

表6和表7分別給出了4種算法關于GD、HV性能指標的統(tǒng)計結果(各個指標的最優(yōu)值用深灰色標識，次優(yōu)值用淺灰色標識)。表8和表9是DDEACA分別與其他3種算法兩兩之間的Mann-Whitney秩檢驗結果。原假設為性能指標的均值相等，顯著性水平為0.05。

表6 收斂性指標GD

表7 覆蓋性指標HV

表8 GD指標Mann-Whitney檢驗

表9 HV指標Mann-Whitney檢驗

由表6的收斂性指標可知，DDEACA在WFG2～WFG4及WFG6～WFG8上取得了最優(yōu)值，在WFG1、WFG5和WFG9上收斂性未獲得最優(yōu)值。同時由表8可知，DDEACA與其他3種對比算法在收斂性指標上存在顯著差異。圖7和圖8分別給出了4種算法在WFG1、WFG2問題上獲得的Pareto前端。DDEACA算法中的P值會影響算法的收斂性，在P=0.3時DDEACA在WFG1的收斂性不如NSGA-Ⅱ和SPEA2，但DDEACA獲得的前端的多樣性比較好。WFG1問題的最優(yōu)Pareto前端由凹凸的曲面構成，DDEACA獲得前端與最優(yōu)前端有很好的一致性，而其他算法無法完全搜索出所有的凹面和凸面。另外，圖8也證明了DDEACA能在求解時較好地保持前端多樣性。WFG2的最優(yōu)Pareto前端由斷開的凹面構成，與其他算法相比，DDEACA獲得的前端能較好地逼近所有凹面。

由表7的覆蓋性指標可知，DDEACA在WFG2～WFG8上取得了最優(yōu)值。同時由表9可知，除了WFG7問題外，DDEACA與其他對比算法在HV指標上存在顯著差異。在WFG5問題上，盡管DDEACA的收斂性略遜色于NSGA-Ⅱ和SPEA2，但是DDEACA獲得的前端多樣性較好，其HV值優(yōu)于NSGA-Ⅱ和SPEA2。圖9給出了4種算法在WFG5問題上獲得的Pareto前端，由圖可知DDEACA獲得的前端分布均勻性優(yōu)于NSGA-Ⅱ和SPEA2。上述內(nèi)容進一步證明了DDEACA對外部種群多樣性維護方法的有效性。

4.2 WFG問題性能指標統(tǒng)計分析

圖10和圖11為4種算法在WFG問題上的性能指標統(tǒng)計盒圖。在收斂性指標分布上，DDEACA算法在WFG3、WFG5、WFG7出現(xiàn)了超過兩個異常值，在這些問題上，算法的穩(wěn)定性稍差些，而在其余測試問題上，DDEACA具有較好的穩(wěn)定性。

5 結束語

本文將智能體機制引入元胞種群并采用兩階段的外部種群多樣性維護方法，將擾動因子引入變異操作避免陷入局部最優(yōu)，提出一種外部種群充分引導的DDEACA算法。鄰居結構和外部種群個體角色的變化可以調(diào)節(jié)算法的選擇壓力，可以較好地實現(xiàn)算法全局探索和局部尋優(yōu)的平衡；第二階段外部種群保留非支配個體可以減少算法對外部種群的維護時間開銷。用WFG系列函數(shù)對算法進行測試和分析，驗證了DDEACA算法的有效性，較好地兼顧全局搜索和局部尋優(yōu)之間的協(xié)同問題，能獲得更好的Pareto前端和競爭性的收斂結果。

本文僅對DDEACA算法本身進行了研究和測試，并對算法的兩階段性進行了探索和分析，未來將研究把算法應用于工程MOP，以期實現(xiàn)混合進化代數(shù)控制變量P與具體MOP問題的自適應調(diào)節(jié)，達到算法與MOP的協(xié)同優(yōu)化。