基于ELECTRE-III法的高維多目標(biāo)調(diào)和進(jìn)化算法

易高明 耿秀榮

摘 要：針對基于Pareto支配的低維多目標(biāo)進(jìn)化算法在求解3個(gè)以上目標(biāo)的高維多目標(biāo)時(shí)出現(xiàn)收斂壓力不足等問題，將調(diào)和模型中面向排序的ELECTRE-III引入高維多目標(biāo)進(jìn)化方法中，提出一種新的錦標(biāo)賽選擇算子。該算子包含兩層操作，分別是快速非支配分層操作和同一非劣層中的賦值級別高于關(guān)系排序操作。將這種賦值級別高于關(guān)系構(gòu)造的ELECRE-III排序法嵌入NSGA-II中并應(yīng)用于高維多目標(biāo)進(jìn)化個(gè)體的優(yōu)劣排序。對典型高維測試集WFG函數(shù)進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證該高維多目標(biāo)調(diào)和進(jìn)化算法的有效性。

關(guān)鍵詞：ELECTRE III方法;多目標(biāo)進(jìn)化算法;高維多目標(biāo);錦標(biāo)賽選擇;賦值級別高于關(guān)系

DOI：10. 11907/rjdk. 201488 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP312文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2020）008-0089-06

Abstract： Aiming at the insufficient convergence pressure of low-dimensional and multi-objective evolutionary algorithms based on Pareto domination in solving three or more high-dimensional and multi-objective evolutionary algorithms， we introduce the ranking-oriented ELECTRE-III in the harmonic model into the high-dimensional and multi-objective evolutionary methods， and propose a new tournament selection operator. The operator consists of two layers of operations. The assignment level of fast non-dominated hierarchical operation and the same non-inferior layer is higher than that of relational sorting operation. The ELECRE-III ranking method with higher assignment level than relation construction is embedded in NSGA-II and applied to the ranking of evolutionary individuals in high-dimensional multi-objective problems. The simulation results of typical high-dimensional test set WFG function verify the effectiveness of the proposed harmonic evolutionary algorithm.

Key Words： ELECTRE III method;multi-objective evolution algorithm;many-objectives;competition selection;valued outranking relation

0 引言

多目標(biāo)進(jìn)化算法可有效求解2～3個(gè)目標(biāo)優(yōu)化問題，然而當(dāng)目標(biāo)個(gè)數(shù)超過3時(shí)，這類問題就變成高維多目標(biāo)問題[1]。傳統(tǒng)基于Pareto占優(yōu)機(jī)制的多目標(biāo)進(jìn)化優(yōu)化方法選擇非支配解的壓力極大降低，導(dǎo)致逼近真實(shí)Pareto前沿所需進(jìn)化個(gè)體數(shù)量呈指數(shù)級增加。因此，基于絕對Pareto機(jī)制占優(yōu)的多目標(biāo)進(jìn)化方法難以有效解決高維多目標(biāo)問題[2]。

為了解決高維多目標(biāo)優(yōu)化問題，Ahmed [3]提出格支配占優(yōu)的高維多目標(biāo)進(jìn)化算法，這是一類非常典型的細(xì)粒度Pareto占優(yōu)方法。同時(shí)，研究者們開始關(guān)注第二級MOEs選擇算子，即多樣性保持算子，寄希望于在這個(gè)第二級算子上實(shí)施選擇壓力。Deb等[4]在NSGA-II基礎(chǔ)上提出其改進(jìn)版本NSGA-III，替換了NSGA-II中的擁擠距離算子;Ren等[5]提出對目標(biāo)函數(shù)直線擬合并計(jì)算擬合函數(shù)的坡度差值，找出坡度差中最小目標(biāo)，然后剔除對應(yīng)的目標(biāo)函數(shù)，達(dá)到目標(biāo)降維目的;Beume等[6]提出S測度選擇進(jìn)化算法;Igel[7]設(shè)計(jì)多目標(biāo)協(xié)方差矩陣進(jìn)化方法等;Moen[8]提出TC-SEA，采取曼哈頓距離自動生成一系列分布均勻的參考點(diǎn)。然而上述方法依然是基于絕對Pareto選擇壓力以逼近真實(shí)前沿面，存在收斂性不足和分布性不均勻等問題。

本文提出一種新的高維多目標(biāo)調(diào)和進(jìn)化算法，可以有效克服Pareto關(guān)系下高維進(jìn)化個(gè)體間存在的互不支配難題，并與具有代表性的兩類高維多目標(biāo)進(jìn)化優(yōu)化算法作對比，以驗(yàn)證本文算法有效性。

1 高維多目標(biāo)優(yōu)化問題

步驟2：考慮方案集中的全部方案對，根據(jù)方案[a]流出的有向弧數(shù)量和流入的有向弧數(shù)量之差[δ（a）]確定方案[a]的好壞，將最大[δ（a）]對應(yīng)的[a]分到第一非劣集[D1]中。

步驟3：如果第一非劣集[D1]只包含一個(gè)方案，則可以刪除第一層非劣集并在剩下的方案集[A]/[D1]上執(zhí)行步驟2;否則，繼續(xù)對第一非劣集[D1]執(zhí)行與步驟2同樣的操作，直到對[D1]中的各方案作出優(yōu)劣排序。重復(fù)步驟2和步驟3排序全部方案。

上述排序方法為降序蒸餾法，也稱正向排序法[14]。同樣地，可采用反向排序法得到另一個(gè)方案集排序。之后，采用ELECTRE-II中的綜合正向排序和反向排序方法給出方案的全部排序。