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

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

關(guān)鍵詞： 引導(dǎo)解； 代理模型； 不可行解； 約束優(yōu)化問題； 進(jìn)化算法

中圖分類號(hào)：TP311.5? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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 引言

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

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

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

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

1 ORGA框架

1.1 反向引導(dǎo)策略

1.1.1 理論基礎(chǔ)

MOP中的解通常對(duì)應(yīng)兩個(gè)向量。目標(biāo)向量OD，一般記作[Fi（f1，…，fm）]（[m]為目標(biāo)數(shù)）；決策向量DD，一般記作[Xi（x1，…， xd）]（[d]為決策變量數(shù)）。[Fi（f1，…，fm）]與[Xi（x1，…， xd）]之間有函數(shù)關(guān)系[fj=fj（xj，1，…，xj，d）（j∈1，…，m）]，即某個(gè)解OD的各分量可由其DD的各分量經(jīng)過指定的函數(shù)運(yùn)算得到。為了降低使用復(fù)雜真實(shí)函數(shù)的次數(shù)，很多研究者使用了從DS到OS的代理模型，用于替代真實(shí)函數(shù)[3]?；蛘呤鞘褂么砟Ｐ妥鳛榉诸惼?，直接進(jìn)行后代篩選[4]。既然可以使用代理模型來依據(jù)DD計(jì)算OD，對(duì)于本質(zhì)上存在某種函數(shù)映射關(guān)系的DD和OD，理論上，也可以通過OD和訓(xùn)練好的代理模型來計(jì)算精度有所損失的DD。

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

1.1.2 目標(biāo)空間引導(dǎo)解的生成方法

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

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

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

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

其中，[k]為收斂系數(shù)（[k>1]，本文中[k]設(shè)置為2），控制引導(dǎo)解的收縮速度;

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

第五步 用極限學(xué)習(xí)機(jī)[5]來預(yù)測(cè)引導(dǎo)解的DD；

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

1.1.3 反向引導(dǎo)策略

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

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

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

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

1.2 不可行解存檔

不可行解不滿足約束條件，但在某些測(cè)試問題中，優(yōu)秀的不可行解反而是進(jìn)化過程中的先進(jìn)個(gè)體。因此適當(dāng)?shù)乇Ａ魞?yōu)秀的不可行解，可能有助于種群進(jìn)化。為此研究者提出了由不可行算子引導(dǎo)差分進(jìn)化的方法[6]。此方法在種群之外獨(dú)立建立了一個(gè)優(yōu)秀不可行解的存檔[z]，存檔[z]與種群[x]和參考向量[ω]一一對(duì)應(yīng)。

1.3 不可行解引導(dǎo)方法

差分進(jìn)化算法[7]的子代產(chǎn)生，使用式⑹

將式中的[xj]替換為不可行存檔解[zj]即可得到需要的不可行算子引導(dǎo)進(jìn)化公式⑺。

2 實(shí)驗(yàn)部分

2.1 實(shí)驗(yàn)設(shè)置

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

2.2 實(shí)驗(yàn)結(jié)果

2.2.1 收斂情況

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

2.2.2 可靠性實(shí)驗(yàn)

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

2.2.3 小結(jié)

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

3 結(jié)論

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

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

參考文獻(xiàn)（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

*基金項(xiàng)目：本研究由中國自然科學(xué)基金（Grant No.42105144）； 吉林省教育廳（Grant No.JJKH20220840-KJ）； 遼寧省科技廳和國家機(jī)器人重點(diǎn)實(shí)驗(yàn)室聯(lián)合基金（Grant No.2020-KF-22-08）

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

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