一種從目標空間反向引導種群進化的進化算法

楊祉祺 姚亦飛 于繁華 李曉寧 蘇小麗

摘? 要： 目前進化算法大多是通過解從決策空間到目標空間的映射，來判斷解的質量。針對約束多目標優(yōu)化問題，將極限學習機代理模型與不可行解存檔方法相結合，提出一種通過目標向量反向預測來引導決策空間種群進化的算法。在CTP和TYPE系列的測試問題上進行了HV度量、IGD度量的性能測試。與幾種經典的算法比較，該算法在大多情況下都表現出具有競爭力的性能，且在高難度問題下比其他算法表現更好。

關鍵詞： 引導解； 代理模型； 不可行解； 約束優(yōu)化問題； 進化算法

中圖分類號：TP311.5? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2023）04-58-04

Abstract： Most of the current evolutionary algorithms judge the quality of the solution by mapping the solution from the decision space to the objective space. For the constrained multi-objective optimization problem， combining the extreme learning machine surrogate model with the infeasible solution archiving method，an algorithm to guide the evolution of the decision space according to backward prediction of the objective vector is proposed. The comparison of HV indicators and IGD indicators on CTP and TYPE test series shows that the proposed algorithm performs better than other classical algorithms in most cases， especially in high complexity problems.

Key words： guidance solution; surrogate model; infeasible solution; constraint optimization problem; evolutionary algorithms

0 引言

現實世界中的優(yōu)化問題往往存在相互沖突的多個目標，這樣的問題被稱為多目標優(yōu)化問題（multi-objective optimization problem，MOP）。一個MOP中原則上會產生一組帕累托最優(yōu)解。所有帕累托最優(yōu)解組成的集合稱為帕累托集（Pareto set，PS），PS在目標空間的映射即帕累托前沿（Pareto front，PF）。優(yōu)化問題往往還涉及不等式和/或等式約束，約束處理是現實世界問題的關鍵組成部分。約束多目標優(yōu)化問題（constrained multi-objective optimization problems，CMOP）根據其種類、約束強度、約束數量等屬性，難度通常比普通的MOP更大，應用也更加廣泛。一個CMOP可以在數學上表述為

其中，有[m]個目標函數需要同時進行優(yōu)化，一個解[m]個目標函數上的函數值共同構成這個解在一個[m]維目標空間（objective space，OS）的目標向量（objective director，OD）。每個目標函數[fix]都是在決策空間（decision space，DS）[S?Xd]上定義的。通常，DS是一個在[Xd]上的[d]維超空間。DS的每個維度都有其上界（[xmaxi]）、下界[（xmini）]的限制，每個解也在DS中存在一個對應的[d]維決策向量（decision director，DD）。[gj（x）]是[d]維的不等式約束，[hj（x）]是[d]維的等式約束?？偣灿衃p]個約束，[q]個不等式約束和[p-q]個等式約束。約束的存在將解限制在DS上的一個區(qū)域[F?S]中，稱作可行域，所有未越界但不屬于可行域的區(qū)域稱為不可行域[1，2]。

目前對于約束多目標優(yōu)化算法（constrained multi-objective evolutionary algorithms，CMOEAs）的研究深度不及傳統(tǒng)的MOEAs。針對CMOEAs高維情況收斂速度慢和陷入局部最優(yōu)這兩個問題，本文中提出了一種在主要循環(huán)之外直接生成優(yōu)秀的OD來引導優(yōu)化過程的新方法。并將這種方法與另一種不可行解存檔方法相結合，對基于差分進化的分解算法進行了改進，形成了一種目標空間反向引導算法（Objective space reverse guiding algorithm，ORGA）。

ORGA能夠處理高收斂壓力和不規(guī)則PF問題，彌補了目前此方向研究的空白。更重要的是，反向引導策略生成解的新思路，對EA研究的意義所在。

1 ORGA框架

1.1 反向引導策略

1.1.1 理論基礎

MOP中的解通常對應兩個向量。目標向量OD，一般記作[Fi（f1，…，fm）]（[m]為目標數）；決策向量DD，一般記作[Xi（x1，…， xd）]（[d]為決策變量數）。[Fi（f1，…，fm）]與[Xi（x1，…， xd）]之間有函數關系[fj=fj（xj，1，…，xj，d）（j∈1，…，m）]，即某個解OD的各分量可由其DD的各分量經過指定的函數運算得到。為了降低使用復雜真實函數的次數，很多研究者使用了從DS到OS的代理模型，用于替代真實函數[3]。或者是使用代理模型作為分類器，直接進行后代篩選[4]。既然可以使用代理模型來依據DD計算OD，對于本質上存在某種函數映射關系的DD和OD，理論上，也可以通過OD和訓練好的代理模型來計算精度有所損失的DD。

MOPs中需要被優(yōu)化的是DD，但是解的質量直接取決于OD。這就導致了現在MOEAs的復雜流程——通過遺傳和變異增殖DD，使用真實函數計算OD，再將其用于DD的環(huán)境選擇。而如果能用代理模型來反向由OD計算出DD，就可以采取一種新的產生解的模式，即根據現有的OD，直接產生一個在OS可能更加優(yōu)秀的后代解的OD，之后再依據代理模型來計算它的DD。傳統(tǒng)方法使用現有解中的優(yōu)秀解引導種群進化，而這種新的產生解的模式可以使用現有解的優(yōu)化解來引導進化。

1.1.2 目標空間引導解的生成方法

受基于分解的評估方法啟發(fā)，本文提出了一種在OS產生引導解的方法。具體步驟如下：

第一步 在OS產生一組均勻分布的參考向量，并初始化一組和向量數量相同大小的零數組[Dmin]；

第二步 在父代中尋找模長最長的OD，然后取它的模記為[Dmax]；

第三步 以式（5）求出[Dmid]

其中，[k]為收斂系數（[k>1]，本文中[k]設置為2），控制引導解的收縮速度;

第四步 以[Dmid]確定長度，以參考向量確定方向，生成一組引導解；

第五步 用極限學習機[5]來預測引導解的DD；

第六步 將越界的引導解舍去，并以其[Dmid]更新其[Dmin]，對未越界的引導解再評估之后環(huán)境選擇。

1.1.3 反向引導策略

如圖1所示，假設用于預測DD的代理模型誤差足夠小，則[X']落在[X]的附近區(qū)域內。而OD由DD通過連續(xù)函數計算得出，則[F']應當也落于[F]在OS的附近區(qū)域內。換言之，通過預測得到[X']，再通過函數計算得到的[F']，在代理模型的誤差足夠小時，應當落在生成的引導解[F]的附近區(qū)域內。

本方法預測得到的一組解[X']和[F']，其PF能夠基本保持兩點優(yōu)秀特質：

⑴ 由于生成的向量集[F]落于參考向量上，所以與[F]接近的[F']在OS大致分布均勻，即PF在多樣性上表現優(yōu)秀；

⑵ 由于[Dmax]是種群中距離原點最遠的解距離原點的距離，而生成的解[F]相對最遠解以指數級度量收斂，所以與[F]接近的[F']在收斂性上亦保持優(yōu)秀。

1.2 不可行解存檔

不可行解不滿足約束條件，但在某些測試問題中，優(yōu)秀的不可行解反而是進化過程中的先進個體。因此適當地保留優(yōu)秀的不可行解，可能有助于種群進化。為此研究者提出了由不可行算子引導差分進化的方法[6]。此方法在種群之外獨立建立了一個優(yōu)秀不可行解的存檔[z]，存檔[z]與種群[x]和參考向量[ω]一一對應。

1.3 不可行解引導方法

差分進化算法[7]的子代產生，使用式⑹

將式中的[xj]替換為不可行存檔解[zj]即可得到需要的不可行算子引導進化公式⑺。

2 實驗部分

2.1 實驗設置

對ORGA及有名的幾種算法SP-NSGA-II [8]， CDP-NSGA-II[1]，CMOEAD-DE-CDP和CMOEAD-DE-SR [9]分別在經典的CTP1-7問題[10]和Fan等人提出的TYPE1-3問題[11]上進行了測試。ORGA在反向引導時收斂系數[k]設置為2。對于CTP1-7約束問題，使用ZDT4作為測試問題。對于TYPE問題，使用其原測試約束問題。對于TYPE問題的參數設置。TYPE1問題，[η=0.5]。TYPE2問題，[ζ=0.01]。TYPE3問題，[γ=0.5]。在此設置下，TYPE系列的問題的PF和不可行域分布如圖2所示。

2.2 實驗結果

2.2.1 收斂情況

各算法在CTP6和TYPE系列問題上的最終迭代結果如圖3所示。對于CTP經典測試用例的1-5、7問題和TYPE1問題，各算法在這些問題上都表現較好。在TYPE2問題上，ORGA依然能完成收斂，而SP-NSGA-II和CDP-NSGA-II的表現均不佳，MOEAD-DE-CDP要優(yōu)于前二者，而MOEAD-DE-SR表現較好。在TYPE3問題上，SP-NSGA-II和CDP-NSGA-II表現不佳，MOEAD-DE-CDP和MOEAD-DE-SR并未跨過不可行域達到下半段PF，而ORGA能夠均勻地收斂到整個PF附近。在CTP6問題上，ORGA、SP-NSGA-II和CDP-NSGA-II三種算法均收斂到了PF附近，而MOEAD-DE-CDP和MOEAD-DE-SR未能完成收斂，沒有越過PF上方的一個可行域。

2.2.2 可靠性實驗

最后我們對TYPE和CTP兩系列的測試問題進行50次獨立重復實驗并記錄其進化結束后種群的IGD值和HV值。結果表明，在TYPE1、CTP1-5和CTP7問題上五種算法均表現良好；在TYPE2問題上MOEAD-DE-SR表現較好，ORGA僅在可靠性上略遜于它；在TYPE3問題上，ORGA、MOEAD-DE-CDP和MOEAD-DE-SR都可能達到較理想的IGD和HV值，但ORGA可靠性要更高；在CTP6問題上五種參與測試的算法均可能達到IGD值和HV值的較理想值，其中ORGA可靠性最高。

2.2.3 小結

從以上實驗結果可以看出，ORGA在所有問題上的表現都較為理想，兩種NSGA-Ⅱ在高維決策變量的TYPE系列問題上表現不佳。而MOEAD-DE-CDP和MOEAD-DE-SR在TYPE2、3問題上表現一般，在CTP6測試問題上表現較差。

3 結論

針對CMOPs，提出了一種通過目標向量反向預測來引導決策空間種群進化的方法。將極限學習機代理模型與不可行解存檔方法相結合，使得算法能夠高效地跨越不可行區(qū)域，在保持多樣性的同時迅速收斂。

ORGA的核心在于其使用的反向引導策略，該策略將EA原本面臨的DS尋解問題轉化為了一個OS尋解問題和一個代理模型的精確度問題。OS尋解的優(yōu)勢在于，其天然受到帕累托支配壓力的引導，而DS尋解并不直接受到收斂性指標上的引導。而該策略的OS尋解方法和代理模型選擇都仍有改進的空間。

參考文獻（References）：

[1] K. Deb. An efficient constraint handling method for genetic?algorithms. Computer methods in applied mechanics and engineering 186.2-4 （2000）：311-338

[2] K. Deb， et al. A fast and elitist multiobjective genetic algorithm： NSGA-II. IEEE transactions on evolutionary computation 6.2 （2002）：182-197

[3] B. Abbasi， T. Babaei， Z. Hosseinifard， K. Smith-Miles， M.Dehghani. Predicting solutions of large-scale optimization problems via machine learning： A case study in blood supply chain management. Computers & Operations Research 119（2020）：104941

[4] J.C. Xavier-Júnior， et al. An Evolutionary Algorithm for?Automated Machine Learning Focusing on Classifier Ensembles： an improved algorithm and extended results， Theoret. Comput. Sci. （2020）

[5] G.B. Huang， Q.Y. Zhu， C.K. Siew，Extreme learning machine： a new learning scheme of feedforward neural networks. 2004 IEEE international joint conference on neural networks （IEEE Cat. No. 04CH37541）. Vol. 2. Ieee，2004

[6] B. Xu， W. Duan， H. Zhang， Z. Li， Differential evolution with infeasible-guiding mutation operators for constrained multi-objective optimization. Applied Intelligence 50.12 （2020）：4459-4481

[7] H. Li， Q. Zhang，Multiobjective optimization problems with complicated Pareto sets， MOEA/D and NSGA-II. IEEE transactions on evolutionary computation 13.2 （2008）：284-302

[8] Y.G. Woldesenbet， G.G.Yen， B.G. Tessema，Constraint handling in multiobjective evolutionary optimization. IEEE Transactions on Evolutionary Computation 13.3 （2009）：514-525

[9] M.A. Jan， R.A. Khanum，A study of two penalty-parameterless constraint handling techniques in the framework of MOEA/D. Applied Soft Computing 13.1 （2013）：128-148

[10] K. Deb， A. Pratap， T. Meyarivan，Constrained test problems for multi-objective evolutionary optimization. International conference on evolutionary multi-criterion optimization. Springer， Berlin， Heidelberg，2001

[11] Z. Fan， W. Li， X. Cai， H. Li， C. Wei， Q. Zhang， E.Goodman，Difficulty adjustable and scalable constrained multiobjective test problem toolkit. Evolutionary computation 28.3（2020）：339-378

*基金項目：本研究由中國自然科學基金（Grant No.42105144）； 吉林省教育廳（Grant No.JJKH20220840-KJ）； 遼寧省科技廳和國家機器人重點實驗室聯合基金（Grant No.2020-KF-22-08）

作者簡介：楊祉祺（1997-），男，湖南長沙人，碩士研究生，主要研究方向：多目標優(yōu)化、元啟發(fā)算法。

通訊作者：姚亦飛（1981-），女，吉林長春人，博士，講師，主要研究方向：安全多方計算，私有信息保護。