基于三支決策的多目標優(yōu)化自然計算策略研究

張心茹， 季偉東， 岳玉麒， 殷曾祥

(哈爾濱師范大學 計算機科學與信息工程學院， 哈爾濱 150025)

0 引 言

多目標優(yōu)化問題(MOP)在工程實踐與理論研究等領域廣泛存在并持續(xù)發(fā)展，多目標優(yōu)化問題具體是指各目標之間相互沖突與協(xié)同，傳統(tǒng)的自然計算方法難以找到最優(yōu)解。國內(nèi)外諸多學者對傳統(tǒng)自然計算方法進行改進，提出以多目標進化算法(MOEA)、非支配排序遺傳算法(NSGA)等經(jīng)典算法為首的諸多衍生算法，從而適應多目標優(yōu)化問題的求解。Deb等[1]提出一種帶精英策略的快速非支配排序算法NSGA-II，依據(jù)快速非支配排序，對種群分層，降低算法的計算復雜度；Zhang等[2]將數(shù)學規(guī)劃和進化算法相結(jié)合，提出基于分解的多目標優(yōu)化算法(MOEA/D)，提高算法的計算速度；2002年，Coello等[3]提出多目標粒子群算法(MOPSO)，首次將標準粒子群優(yōu)化算法應用于多目標領域；2016年，Mirjalili等[4]提出多目標灰狼算法(MOGWO)，具有參數(shù)少、實現(xiàn)簡單、魯棒性強等優(yōu)點；Yen等[5]提出一種基于動態(tài)多子群的多目標粒子群優(yōu)化算法(DSMOPSO)，充分平衡探索開發(fā)能力；Martinez等[6]提出重新初始化策略，提高種群多樣性；魏文紅[7]等人通過泛化反向?qū)W習機制，引導種群個體向最優(yōu)帕累托前沿逼近；2018年，謝承旺[8]等提出混合型多目標螢火蟲算法，融入檔案精英個體引導策略及三點最短路徑技術，提高算法的整體性能；2020年，張偉等[9]提出基于種群分區(qū)的多策略粒子選取，平衡算法的收斂性和多樣性；徐航等[10]利用小孔成像反向?qū)W習策略增加尋優(yōu)的多樣性，提高跳脫局部最優(yōu)的能力；2022年，季偉東等[11]利用局部線性嵌入(LLE)降維思想解決大規(guī)模多目標優(yōu)化領域問題；王旭等[12]利用多指標的精英個體博弈機制，融合K-means 聚類，平衡算法性能。

國內(nèi)外學者雖以不同視角和背景針對收斂精度、速度、分布性等多方面進行改進和創(chuàng)新，但大多針對于某一單獨算法，其策略不具有通用性和普適性。對于多目標優(yōu)化領域，尋找一種通用的優(yōu)化策略具有重要的意義。針對上述問題，本文基于三支決策理論思想，結(jié)合三支分域及異域分治策略，提出應用于自然計算領域的三支決策多目標優(yōu)化策略(Natural computing strategy for multi-objective optimization based on three-way decision, 3WD-MNC)，通過分段Tent映射改變種群初始化，提高算法的多樣性；結(jié)合三支決策思想，提出三支分域策略，對子域種群進行異域分治策略尋優(yōu)，從而指導種群進化。

將該方法分別應用于兩種不同的自然計算方法中，從整體和局部兩方面提升算法收斂性、分布性、高效性，綜合提升算法平均性能，并與這兩個代表性算法在6個經(jīng)典測試函數(shù)上進行對比，驗證其有效性和普適性。

1 多目標優(yōu)化問題

設在目標空間Rm中，多目標優(yōu)化問題的數(shù)學描述可表示為式(1)：

minF(x)=(f1(x),f2(x), …,fm(x))

(1)

滿足條件：

其中，x=(x1,x2,…,xn)為決策空間Ω中的一個決策變量，gi(x)和hj(x)為約束函數(shù)，分別表示MOP的p個不等式約束和q個等式約束條件，共同確定滿足所有條件的可行域。

2 基于三支決策的多目標優(yōu)化自然計算策略(3WD-MNC)

2.1 Tent混沌種群初始化

初始種群的優(yōu)劣在一定程度上會影響算法的收斂速度和解的精度[13]。隨機產(chǎn)生的數(shù)據(jù)初始化種群信息難以保留種群的多樣性。因此本文采用迭代速度快，且遍歷均勻性較好的Tent混沌映射，設初始化種群的種群規(guī)模為n，在[0,1]內(nèi)隨機產(chǎn)生初始值X0，利用公式(2)進行迭代并生成n-1個新個體，最后將全部個體映射到變量的取值范圍內(nèi)，生成Tent混沌初始化種群。在保證種群多樣性的前提下，提高收斂速度，縮短尋優(yōu)時間。

(2)

2.2 基于三支思想的種群分域策略

三支決策是將不確定事物放入“待定區(qū)”的決策模式，將整體分為正域、負域、邊界域。正域代表接受，負域代表拒絕，邊界域代表無法做出接受或拒絕的判斷。三支決策可以很好劃分樣本間屬性的差異，將相似樣本劃分到同一區(qū)域，采用不同策略。受此思想影響，將初始化種群分為正域、負域、邊界域，對于可行解空間Ω，設定閾值因子r，構(gòu)造基于三支決策的自適應種群分域，式(3)：

(3)

其中，POS、NEG、BND分別為正域、負域、邊界域，F(xiàn)avg為平均適應度值，設定閾值因子r劃分域并區(qū)分優(yōu)劣個體。

2.3 異域分治策略

通過三支分域策略將初始種群分為三域后，對三域進行不同的尋優(yōu)更新操作。

在BND域，將候選解間的歐式距離，作為個體的分布性指標，d(x,y)為n維空間中任意兩個體之間的真實距離，式(4)：

(4)

利用式(5)將BND中最優(yōu)個體的d值與平均值相比較，若其大于平均歐氏距離，則對最優(yōu)個體進行高斯變異，反之反向?qū)W習變異，增強全局搜索，增加種群多樣性。

(5)

NEG域中，獲取隨機數(shù)rand，根據(jù)當前個體迭代次數(shù)t、最大迭代次數(shù)Tmax以及突變率mu，計算擾亂算子p，式(6)：

(6)

若rand>p，采用小孔成像變異策略，隨機向附近尋優(yōu)更新，變異計算公式(7)：

(7)

在POS域，同樣通過獲取隨機數(shù)rand，根據(jù)式(6)計算擾亂算子p。若rand

2.4 3WD-MNC在自然計算方法中的實現(xiàn)策略

本文將3WD思想以及異域分治策略結(jié)合，構(gòu)建3WD-MNC算法，并將其應用于自然計算領域的MOPSO和MOGWO中，其中，算法流程圖如圖1所示。

圖1 3WD-MNC算法流程圖

3 實驗結(jié)果與分析

為驗證所提策略有效性，選取ZDT1-ZDT4、ZDT6、DTLZ2作為測試函數(shù)，參數(shù)設置：雙目標種群規(guī)模N=100，迭代次數(shù)為100次；三目標種群規(guī)模N=300，迭代次數(shù)100次，測試30次；3WD策略中閾值因子r=0.1。

將所提策略應用于MOPSO和MOGWO中，得到3WD-MOPSO和3WD-MOGWO，與MOPSO、MOGWO經(jīng)典算法進行對比實驗，各對比算法在測試函數(shù)上的超體積指標(HV)、反世代距離指標(IGD)的結(jié)果見表1和表2，其中最優(yōu)結(jié)果加粗顯示。

表1 HV指標對比

表2 IGD指標對比

由表1可知，3WD-MOGWO和3WD-MOPSO均優(yōu)于MOPSO算法，說明本文所提3WD策略應用于MOPSO算法和MOGWO算法后的綜合性能相對較好。

由表2可知，在ZDT系列5個測試問題上，3WD-MOGWO算法和3WD-MOPSO算法的表現(xiàn)均優(yōu)于其他經(jīng)典算法，且相對于其他算法，平均值以及標準差也取得了較低的數(shù)值，表示本文所提算法在各測試函數(shù)上均有不錯的表現(xiàn)。ZDT1、ZDT4中，3WD-MOGWO算法普遍優(yōu)于MOPSO等算法，相對較好地收斂于真實帕累托前沿的附近，且分布較為均勻。

仿真結(jié)果表明，在6個測試函數(shù)中，與其他經(jīng)典優(yōu)化算法相比，本文所提出的3WD策略大多都能找到更好的解，說明本文所提策略在解決多目標問題能很大程度上提升算法的綜合性能，有效平衡算法的收斂性與多樣性。

4 結(jié)束語

本文提出基于三支決策的多目標優(yōu)化自然計算策略，充分利用三支決策三分而治的基本思想，將整體分為3個獨立域，分別對每個域進行異域分治策略，有效解決收斂速度過快導致陷入局部最優(yōu)的問題，保證前期多樣性，維持后期收斂速度的穩(wěn)定性，最終找到均勻分布且準確的前沿。綜合實驗結(jié)果表明，本文策略具有較好收斂性和多樣性，能夠有效提高解的精度。