基于環(huán)形拓?fù)浣Y(jié)構(gòu)和動(dòng)態(tài)鄰域的多模態(tài)多目標(biāo)粒子群優(yōu)化算法

章恩澤, 趙哲萱, 韋靜月, 葛 蕤, 蔣 超

(揚(yáng)州大學(xué)信息工程學(xué)院, 江蘇 揚(yáng)州 225127)

在工程實(shí)際中廣泛存在著一類具有多模態(tài)特性的多目標(biāo)優(yōu)化問題, 其決策空間存在2個(gè)或以上Pareto最優(yōu)解集對應(yīng)于目標(biāo)空間同一Pareto前沿, 該類問題被稱為多模態(tài)多目標(biāo)優(yōu)化問題(multimodal multi-objective optimization problems, MMOPs), 如路徑規(guī)劃問題[1]、建筑選址問題[2]或結(jié)構(gòu)優(yōu)化設(shè)計(jì)[3]等．由于大多數(shù)已有的多目標(biāo)優(yōu)化算法鮮少關(guān)注解在決策空間中的多樣性, 所以在求解MMOPs時(shí)通常難以得到分布性良好的Pareto最優(yōu)解集．近年來, 一些改進(jìn)的MMOPs求解算法被相繼提出．Yue等[1]提出基于環(huán)形拓?fù)浜吞厥鈸頂D距離的多目標(biāo)粒子群優(yōu)化算法(multi-objective particle swarm optimization algorithm with ring topology and special crowding distance, MO_Ring_PSO_SCD), 通過環(huán)形拓?fù)浣Y(jié)構(gòu)限制種群內(nèi)的信息傳遞速度, 使得種群在搜索過程中逐漸形成穩(wěn)定的小生境, 從而找到更多的Pareto最優(yōu)解; Hu等[4]在多模態(tài)多目標(biāo)鴿群算法(multimodal multi-objective pigeon-inspired optimization, MMOPIO)中采用映射方法將原始決策空間轉(zhuǎn)化到映射空間, 并根據(jù)粒子在映射空間的分布確定其鄰域關(guān)系, 使得種群在映射空間鄰域內(nèi)進(jìn)化; Zhang等[5]通過決策空間聚類方法將整個(gè)種群分為多個(gè)子種群, 子種群內(nèi)的粒子根據(jù)全局最優(yōu)位置更新位置和速度, 不同種群之間采用環(huán)形拓?fù)浣Y(jié)構(gòu)進(jìn)行信息傳遞; Qu等[6]采用自組織方法將種群劃分為多個(gè)子種群進(jìn)行并行搜索, 提出了自組織多目標(biāo)粒子群優(yōu)化算法(self-organized speciation based multi-objective particle swarm optimizer, SS-MOPSO); Zou等[7]采用改進(jìn)的差分進(jìn)化策略擴(kuò)大搜索范圍, 并利用近鄰移動(dòng)策略使粒子向最優(yōu)解逼近且在局部范圍內(nèi)進(jìn)行優(yōu)化．上述MMOPs求解算法均難以獲得完整的Pareto最優(yōu)解集, 且種群多樣性仍有待提高．為更有效地求解MMOPs, 本文基于無重疊環(huán)形拓?fù)浣Y(jié)構(gòu)構(gòu)造粒子鄰域, 采用鄰域最優(yōu)位置替代種群的全局最優(yōu)位置進(jìn)行粒子更新, 并引入周期重組(periodic recombination, PR)和一種全局最優(yōu)位置更新(global best position updating, GBPU)策略, 擬提出一種新的多模態(tài)多目標(biāo)粒子群優(yōu)化算法(ring topology and dynamic neighborhood based multi-objective particle swarm optimizer using periodic recombination and global best position updating, RDNMOPSO-PR-GBPU)．

1 RDNMOPSO-PR-GBPU算法

1.1 采用鄰域最優(yōu)位置的粒子群算法

(1)

(2)

PSO算法的收斂性雖較強(qiáng), 但容易陷入局部最優(yōu), 故將式(1)中的全局最優(yōu)位置替換為鄰域最優(yōu)位置nbest, 進(jìn)行PSO更新[8]:

(3)

1.2 基于空間距離的無重疊環(huán)形拓?fù)浣Y(jié)構(gòu)

粒子群的拓?fù)浣Y(jié)構(gòu)決定了種群中粒子間的信息交換方式, 從而直接影響算法的收斂速度．在環(huán)形拓?fù)浣Y(jié)構(gòu)中, 粒子僅與其相鄰的兩個(gè)粒子共享信息, 并根據(jù)各自鄰域最優(yōu)位置進(jìn)行更新,因而能夠發(fā)現(xiàn)更多最優(yōu)解[8]．常見的環(huán)形拓?fù)浣Y(jié)構(gòu)一般根據(jù)粒子的索引構(gòu)建鄰域, 如圖1所示, 其中1號(hào)、2號(hào)粒子編號(hào)雖相鄰, 但在決策空間中距離卻較遠(yuǎn), 因此該類鄰域關(guān)系并不能反映粒子在決策空間中的真實(shí)分布, 導(dǎo)致搜索效率下降．

圖1 基于索引的環(huán)形拓?fù)浣Y(jié)構(gòu)Fig.1 An index-based ring topology structure

為更好地體現(xiàn)粒子在決策空間中的分布, 本文充分考慮粒子在決策空間和目標(biāo)空間的多樣性, 提出一種基于空間距離的無重疊環(huán)形拓?fù)浣Y(jié)構(gòu), 如圖2所示．對種群中所有粒子按照非支配關(guān)系和特殊擁擠距離[1]進(jìn)行優(yōu)劣排序, 將排名前Ndms個(gè)粒子歸類為小型子種群, 其余Ndisad個(gè)粒子歸入劣勢子種群．由于各子種群相互獨(dú)立且進(jìn)行并行搜索, 所以種群的多樣性可進(jìn)一步得以提升．以圖2中種群規(guī)模為10的粒子群為例, 根據(jù)基于特殊擁擠距離的非支配排序方法[1]對粒子進(jìn)行排序, 將編號(hào)為1、4、3的粒子置于第一個(gè)小型子種群Dss1, 將編號(hào)為2、6、5的粒子置于第二個(gè)小型子種群Dss2,Dss1和Dss2分別追隨拓?fù)浣Y(jié)構(gòu)中粒子的鄰域最優(yōu)位置進(jìn)行并行搜索．剩余編號(hào)為7、8、9、10的粒子在決策空間中分布較松散且距離鄰域最優(yōu)解較遠(yuǎn), 為了提升搜索效率, 將此類粒子并入劣勢子種群Ndisad, 利用全局最優(yōu)位置引導(dǎo)其向更好的區(qū)域進(jìn)行搜索．

圖2 基于空間距離的無重疊環(huán)形拓?fù)浣Y(jié)構(gòu)Fig.2 A non-overlapping ring topology based on the distance structure

1.3 全局最優(yōu)位置更新策略

對于PSO算法,全局最優(yōu)位置的選擇直接影響整個(gè)種群的搜索方向和最終解集的質(zhì)量,因而在利用PSO算法求解多目標(biāo)優(yōu)化問題時(shí),為每個(gè)粒子選擇合適的全局最優(yōu)位置成為算法設(shè)計(jì)的關(guān)鍵[9]．針對多模態(tài)多目標(biāo)優(yōu)化問題,本文通過在已有鄰域最優(yōu)位置的周圍進(jìn)行局部搜索,以獲得潛在的分布性更優(yōu)的全局最優(yōu)位置,從而在引導(dǎo)種群逼近Pareto最優(yōu)解集的同時(shí)維護(hù)其多樣性．本文設(shè)計(jì)的全局最優(yōu)位置更新策略的步驟如下:

2) 在所有小型子種群的鄰域最優(yōu)位置附近生成一個(gè)新的粒子, 并計(jì)算其目標(biāo)函數(shù)值;

1.4 周期重組

小型子種群采用無重疊環(huán)形拓?fù)浣Y(jié)構(gòu), 增加了搜尋到最優(yōu)解的可能性, 但由于粒子間信息流動(dòng)過于單一, 粒子可能表現(xiàn)出“趨同性”, 即一旦某一粒子陷入局部最優(yōu), 則可能導(dǎo)致與之處于同一鄰域的其他粒子處于停滯狀態(tài)．為引導(dǎo)粒子跳出局部最優(yōu), 現(xiàn)引入周期重組策略, 以增強(qiáng)算法的探索力度和開拓搜索范圍．周期重組策略的具體步驟如下:

2) 保存Dss i中所有粒子的個(gè)體最優(yōu)檔案(personal best archive, PBA)和鄰域最優(yōu)檔案(neighborhood best archive, NBA);

3) 對Dss i中粒子重新進(jìn)行初始化操作, 將隨機(jī)新生成的粒子加入下一代種群中;

4) 根據(jù)式(2)(3)更新Dss i中粒子, 并將更新后的粒子加入到下一代種群中．

2 仿真結(jié)果與分析

為驗(yàn)證本文算法的有效性, 現(xiàn)設(shè)置3組對比實(shí)驗(yàn)進(jìn)行仿真分析: 比較參數(shù)Ndms和Ndisad取值對算法優(yōu)化結(jié)果的影響; 對比引入周期重組和全局最優(yōu)位置更新策略前后算法性能的有效性; 對比本文算法與5種已有多目標(biāo)優(yōu)化算法的性能．所有實(shí)驗(yàn)均通過MATLAB 2020b編程實(shí)現(xiàn), 計(jì)算機(jī)配置為Intel(R) Core(TM) i5-9400F@2.90 GHz, 16 GB RAM．采用8個(gè)多模態(tài)多目標(biāo)優(yōu)化測試函數(shù)MMF1～MMF8[1]綜合測試算法的性能．

2.1 性能評價(jià)指標(biāo)

選擇決策空間反世代距離(the inverted generational distance in the decision space, IGDX)[10]和Pareto解集逼近度(Pareto sets proximity, PSP)[1]作為評價(jià)指標(biāo), 評價(jià)算法的性能．

IGDX可衡量獲得的解集與真實(shí)Pareto解集的近似程度．對于解集X, 有

其中D(x,y)為解x和解y的歐氏距離,X*為真實(shí)Pareto解集中的均勻采樣, |X*|為集合X*中解的總個(gè)數(shù)．IGDX的值越小, 表明解集的收斂性和多樣性越好．

2.2 參數(shù)取值的影響

設(shè)置種群規(guī)模為600, 當(dāng)小型子種群Ndms與劣勢子種群Ndisad之比r分別為2,4,6,8,10,12時(shí), 參數(shù)Ndms和Ndisad的取值如表1所示．

表1 不同r值下Ndms和Ndisad的取值

圖3給出了不同r值下算法運(yùn)行30次所得PSP均值．由圖3可見: 當(dāng)r=8時(shí), 在除MMF5和MMF6外的其余6個(gè)測試函數(shù)上PSP均值都最大, 表明該取值下小型子種群和劣勢子種群的數(shù)目使算法在探索和開發(fā)之間實(shí)現(xiàn)了更好的權(quán)衡, 從而獲得更好的綜合性能．

圖3 不同參數(shù)取值下算法所得PSP均值Fig.3 PSP mean values obtained by the algorithm under different values of parameter

2.3 周期重組和全局最優(yōu)位置更新策略的有效性

對比引入周期重組和全局最優(yōu)位置更新策略前后算法的有效性, PSP均值如表2所示．由表2可見: 本文算法在8個(gè)測試函數(shù)上都獲得了最優(yōu)結(jié)果, 且在全局和局部Pareto解集共存的測試函數(shù)MMF2和MMF3上優(yōu)勢較明顯, 說明周期重組和全局最優(yōu)位置更新策略有助于算法跳出局部最優(yōu)．

表2 引入周期重組和全局最優(yōu)位置更新策略前后算法的PSP 均值

2.4 幾種算法的性能對比

為進(jìn)一步驗(yàn)證本文算法的有效性, 現(xiàn)與基于分解的多目標(biāo)進(jìn)化算法(multi-objective evolutionary algorithm based on decomposition, MOEA/D)[11]、多目標(biāo)粒子群優(yōu)化算法(multi-objective particle swarm optimization algorithm, MOPSO)[12]、決策空間小生境多目標(biāo)遺傳優(yōu)化算法(decision space based niching nondominated sorting genetic algorithm Ⅱ, DN-NSGA Ⅱ)[13]、MO_Ring_PSO_SCD[1]和SS-MOPSO[6]等5種算法在8個(gè)測試函數(shù)上進(jìn)行對比．所有算法均設(shè)置最大評價(jià)次數(shù)為60 000, 種群規(guī)模為600, 每種算法在各測試函數(shù)上獨(dú)立運(yùn)行30次, 所得IGDX和PSP均值分別如表3～4所示．由表3～4可見: 1) 本文算法雖在MMF3和MMF7測試函數(shù)上的IGDX結(jié)果略遜于SS-MOPSO和DN-NSGAⅡ, 但在其他6個(gè)測試函數(shù)上獲得了IGDX的最小值; 2) 本文算法在除MMF5外的7個(gè)測試函數(shù)上PSP值均最大, 表明所提算法在大多數(shù)測試函數(shù)上獲得了更加逼近真實(shí)Pareto解集且分布性更好的最優(yōu)解集．其可能原因是, 作為傳統(tǒng)的多目標(biāo)優(yōu)化算法, MOEA/D和MOPSO未針對多模態(tài)情形進(jìn)行特殊處理; 相較于DN-NSGAⅡ和SS-MOPSO, MO_Ring_PSO_SCD和本文算法在信息傳遞時(shí)采用環(huán)形拓?fù)浣Y(jié)構(gòu), 在環(huán)境選擇中采用特殊擁擠度距離, 大大提高了解集在決策空間的分布性; 本文算法和MO_Ring_PSO_SCD雖然都采用基于擁擠距離的非支配排序方式, 但本文算法因引入周期重組和一種新的全局最優(yōu)位置更新策略, 故能幫助算法跳出局部最優(yōu), 找到更接近真實(shí)Pareto最優(yōu)解的解集．綜上, 本文算法在求解多模態(tài)多目標(biāo)優(yōu)化問題時(shí)更有效．

表3 不同算法的IGDX均值

表4 不同算法的PSP均值