多策略融合的多目標螢火蟲算法

黃建平, 陳 謠,邢文來, 康 平, 趙 嘉

(南昌工程學院信息工程學院, 330099,南昌)

0 引言

近年來,人工智能技術得到了研究者們越來越多的關注,并取得了一系列重要突破。人工智能技術的發展正在慢慢改變著我們生活。深度學習技術可通過構建神經網絡實現對復雜數據的分析和計算,從而實現高效的數據預測和決策。程鵬宇等[1]提出一種雙向多尺度跳躍的短時溫度預測模型應用于天氣預測。群智能算法則是一種在自然界生物群體所表現出來的智能現象啟發下提出的智能方法,具有自組織、自學習、自適應和內在并行性等特征,實現更加高效的信息處理和優化。張曦等[2]提出一種隨機學習螢火蟲算法優化的模糊軟子空間聚類算法,使群智能技術和數據挖掘技術相結合,提高了聚類算法的性能。由此可見,人工智能已經成為當今科技領域最為熱門的話題之一。隨著計算機性能、存儲容量和數據可用性的提高,人工智能可以處理和分析比以往任何時候都要大得多的數據集。其中,多目標優化問題(Multi-objective Optimization Problem, MOP)[3]出現在生活中的方方面面,而多目標問題的解決對于多種領域和應用非常重要和關鍵,例如在工業制造、環境保護、資源配置、城市規劃等方面均存在大量的多目標問題。

多目標問題是指需要在多個目標之間進行權衡和選擇的一類優化問題,即存在多個可能的解決方案,對其中一個子目標進行優化,可能會引起其他目標性能的降低,因此只能對多個目標進行折中處理,得到一組由非支配解組成的Pareto最優解[4]。傳統的數學優化方法常常因為無法構造精確的數學公式而難以求解此類問題[5]。為了解決該問題,一種受生物啟發求解MOP問題的算法——多目標進化算法(Multi-objective Evolutionary Algorithms,MOEAs)[6]應運而生,該類方法被認為是解決MOP問題的有效方法,并在各個領域獲得廣泛應用。

Yang[7]受自然界中螢火蟲發光傳遞信息行為的啟發,提出了螢火蟲算法(Fireflyalgorithm,FA),該算法具有操作簡單、參數少、收斂速度快及性能出色等特點,但也有易陷入局部最優、過早收斂等缺陷。為了提升FA的算法性能,諸多學者基于標準的FA做出改進。趙嘉等[8]提出一種深度學習螢火蟲算法(Firefly Algorithm with Deep Learning,DLFA),該算法將最優螢火蟲引入深度學習策略,采用隨機吸引模型代替全吸引模型以防止螢火蟲在移動過程中出現震蕩,兼顧探索和開采平衡。趙嘉等[9]提出一種自主學習螢火蟲算法(firefly algorithm based on self-learning, SLFA),該算法將粒子種群按適應度劃分為自主學習粒子和普通粒子,在面臨多峰優化問題時可有效地提升算法的尋優精度和多極值空間的探索能力。賀朝等[10]提出一種多策略集成螢火蟲算法,該算法引入基于注意力機制的慣性權重結合鄰域搜索策略修改了螢火蟲的移動公式,優化了螢火蟲在前期的勘探能力和后期的局部探索能力。鑒于FA的特性和優勢,Yang[11]對標準FA進行了拓展,提出了多目標螢火蟲算法(Multi-Objective Firefly Algorithm, MOFA)。MOFA算法中,筆者對螢火蟲的移動公式進行了改進,螢火蟲的移動依賴當前的Pareto最優解,使得算法的搜尋范圍小,容易陷入局部最優,且算法在收斂性和分布性上效果均有所欠缺。針對此缺陷,LV等[12]提出了一種基于補償因子與精英學習的多目標螢火蟲算法(multi-objective firefly algorithm based on compensation factor and elite learning, CFMOFA),該算法引入補償因子改進螢火蟲的學習公式提高螢火蟲全局尋優能力,采用精英個體學習擴大螢火蟲的探索范圍,提高了Pareto最優解集的多樣性和準確性。趙嘉等[13]提出一種基于最大最小策略和非均勻變異的螢火蟲算法(heterogeneous variation firefly algorithm with-maximinstrategy,HVFA-M),該算法引入Maximin策略添加改進學習策略提高算法的勘探能力和結合非均勻變異算子提高算法的尋優精度。

上述提到的算法雖然在一定程度上提升算法的性能,但是在收斂到真實的Pareto最優解的能力和解集覆蓋域等方面仍存在不足。鑒于此,本文提出了多策略融合的多目標螢火蟲算法(Multi-objective firefly algorithm based on multi-strategy fusion,MOFA-MSF)。MOFA-MSF具有如下特點:1)引入隨機化與均勻化相結合的方法初始化種群,以此生成均勻分布的初始種群;2)設置外部檔案,在外部檔案中選擇精英解來引導螢火蟲移動,并在搜索過程中,根據當前外部檔案中解的數量采用不同的方式選擇精英解;3)引入變異算子和萊維飛行,使算法能夠以較快的速度收斂的同時避免陷入局部最優;4)使用擁擠距離機制篩選精英解,以獲得均勻分布的Pareto前沿。以上多種策略作用在算法的不同階段,提升了MOFA各方面的性能。

1 多目標螢火蟲算法

螢火蟲算法是Yang根據螢火蟲利用發光來傳遞信息的生物特性,提出的一種新的多目標優化算法。其核心思想是:亮度低的螢火蟲受亮度強的螢火蟲吸引,并向其靠近完成位置迭代,而亮度高的螢火蟲不受任何螢火蟲吸引,進行隨機移動。

螢火蟲i對螢火蟲j的吸引力定義為:

(1)

式中,β0表示螢火蟲的最大吸引力,通常取β0=1;γ表示光吸收系數,一般取γ∈[0.01,100];rij為螢火蟲i到螢火蟲j的歐氏距離,計算公式為:

(2)

若螢火蟲j的亮度低于螢火蟲i的亮度,螢火蟲j會向著螢火蟲i移動,其位置更新公式為:

xj(t+1)=xj(t)+βij(rij)(xi(t)-xj(t))+αε

(3)

式中,t是算法當前的迭代次數,xi為螢火蟲i在搜索空間中的位置,α是步長系數,一般取α∈[0,1]。ε是服從正態分布、均勻分布或者其他分布的隨機數向量。

若不存在亮度高于螢火蟲j的個體,即螢火蟲j不被任何螢火蟲吸引,其位置更新公式為:

xj(t+1)=g*+αε

(4)

式中,g*是以隨機加權和的方式將多目標函數轉換為單目標函數得到的當前最優解。對于求解最小值問題,若不存在螢火蟲u使得ψ(xu)<ψ(xv),則當前的最優解g*即為螢火蟲v。ψ(xv)定義為:

(5)

式中,E表示目標函數的個數,we為(0,1)之間的隨機數。

2 MOFA-MSF算法

2.1 種群初始化策略

大部分多目標螢火蟲算法采用隨機初始化的方式生成初始種群,隨機初始化方式的缺點在于僅考慮了生成種群的隨機性而沒有考慮初始種群在決策空間中的分布問題。針對這一問題,引入均勻化與隨機化相結合的初始化方法[14]產生初始種群。該方法有如下優勢:1)保持了選取子區間和在區間中生成位置的隨機性;2)使初始種群均勻分布在決策空間中。以這種方式獲得均勻的分布的初始種群,為MOFA-MSF算法的全局搜索奠定了良好的開端。該初始化方法的流程為:

輸入:種群數量N,決策向量的維數D,每個決策變量xd(d∈[1:D])的范圍[ad,bd]。

輸出:初始化種群。

步驟1:d= 1,j= 1。d和j分別表示當前遍歷的維度和螢火蟲。

步驟2:當d<=D時,重復步驟3～步驟9。

步驟3:對決策變量xd的范圍區間[ad,bd]進行劃分,計算ωd=(bd-ad)/N。

步驟4:得到θd={[ad,ad+ωd],[ad+ωd,ad+2ωd],…,[ad+(N-1)ωd,bd]}。

步驟5:當j<=N時,重復步驟6～步驟8。

步驟7:從集合θd中刪除步驟6所選中的區間。

步驟8:j=j+1。

步驟9:d=d+1。

步驟10:輸出初始種群{x1,x2,…,xN-1,xN}。

2.2 隨機擾動策略

多目標螢火蟲算法的步長依賴于步長系數α,且α會隨著迭代次數的增加而減小,這使得螢火蟲之間的步長差別越來越小。這種情況不利于多目標螢火蟲算法求解具有復雜Pareto前沿的MOP問題。因此,本文引入Lévy flight隨機擾動代替原有的隨機步長,以平衡算法的局部搜索和全局勘探能力,提升算法求解復雜MOP問題的能力。

萊維飛行(Lévy flight)[15]是法國數學家Lévy提出的一類非高斯隨機過程,是一種具有概率分布步長的隨機游走,是隨機游走模型中最好的策略之一。

萊維飛行的隨機步長s的計算公式為:

(6)

式中,v和μ均為服從正態分布的隨機數,它們的定義為:

(7)

上式中,σv和σμ的計算公式為:

(8)

式中,通常取φ(1,3),本文取φ=1.5;Γ為標準的Gamma函數。

2.3 變異算子

螢火蟲之間的個體差異會隨著算法的進行和種群的不斷更新變得越來越小,這可能會使螢火蟲之間出現嚴重的聚集現象。為了避免種群陷入局部最優,本文引入變異算子[16],螢火蟲k在每次進行位置更新之后,按照變異概率pm隨機對螢火蟲k的一個分量進行擾動,pm的計算方式為:

(9)

式中,t是當前迭代的次數,maxT為最大迭代次數。

若隨機選中的是第j維度分量,螢火蟲k的變異公式為:

(10)

式中,xk(j)為螢火蟲k第j維度的值,lj和uj分別代表螢火蟲k在第j維度上的下限和上限,pm表示變異的概率,rand(1)表示0到1之間的隨機數。下限lj和上限uj的計算方式為:

(11)

式中,u和l分別表示螢火蟲在解空間內的上界和下界。

算法前期,螢火蟲的變異概率和擾動幅度較大,算子能夠充分發揮算法的全局搜索能力,使種群具有更好的分布性。算法后期,螢火蟲變異的概率變小且擾動的幅度也隨之減少,算子更加注重局部搜索,使得產生后的解有著更大的概率靠近真實的Pareto前沿,維護了種群的收斂性。

2.4 檔案精英解引導螢火蟲移動

MOFA-MSF算法迭代過程中,外部檔案始終不為空集,所以,當螢火蟲i與j因互相吸引而更新位置時,算法將從檔案中選取一個精英解A*引導螢火蟲進行移動。區別于MOFA算法,螢火蟲i和螢火蟲j之間相互移動存在2種情況:

1)當螢火蟲i和螢火蟲j互不吸引,彼此非劣時,i和j都將在精英解A*的引導下進行位置更新,移動公式[11]為:

(12)

2)若螢火蟲i和螢火蟲j之間存在吸引關系,假設螢火蟲i吸引j,那么螢火蟲j將同時向著精英解A*和螢火蟲i移動,移動公式為:

(13)

區別于隨機選取,本文在選取精英解A*時,根據外部檔案中解的數量采取不同的選擇方式。大致思想為:1)若外部檔案未滿,則從外部檔案中隨機選取解作為精英解;2)若外部檔案已滿,優先選取外部檔案中擁擠度大的解作為精英解,例如,對外部檔案中的解由擁擠度從大到小排序,從檔案的前50%的個體中選取精英解。在上述選取的精英解引導下,本文算法會優先搜索擁擠距離大的區域,能夠在一定程度上使得獲得的解集分布更加均勻且加快種群的收斂速度。

2.5 擁擠距離策略維護外部檔案

多目標螢火蟲算法通常采用容量有限的外部檔案來存儲迭代過程中獲得的非劣解,當非劣解數量超出檔案規模時,要對檔案進行裁剪來維持檔案中解的多樣性。為了獲得均勻分布的Pareto前沿,提高MOFA-MSF算法的性能,本文引入擁擠距離策略。

擁擠距離策略[17]是多目標優化算法中常用的一種選擇壓制性策略,其主要思想是在選擇解的過程中不但要考慮目標值函數,還要考慮解的擁擠度,從而保證選擇的解具有良好的多樣性和分布性。擁擠距離策略的優勢在于,其實現簡單,易與各種優化算法相結合。

以最小化問題為例,對于螢火蟲j,其擁擠距離distj的計算公式為:

(14)

擁擠距離大的解,周圍的解越稀疏,擁擠距離小的解,周圍的解越密集。在外部檔案超出規模時,通過擁擠距離對非支配解排序,保留擁擠距離大的解,以此來獲得均勻分布的Pareto解集。

2.6 算法流程

結合上述多種策略,給出MOFA-MSF算法的流程:

輸入:種群規模N,外部檔案Arc的規模ArcNum,最大迭代次數maxT,螢火蟲的最大吸引力β0,光吸收系數γ,步長系數α。

輸出:Pareto最優解集。

步驟1:利用隨機化均勻化初始化策略生成規模為N的初始種群,迭代次數t=0。

步驟2:計算每只螢火蟲的適應度值。

步驟3:對初始種群進行快速非支配排序,篩選得到初始非支配解集并將前ArcNum個個體存儲在外部檔案Arc中。

步驟4:當t

步驟5:遍歷螢火蟲,重復步驟6～步驟8。

步驟6:根據檔案中解的數量用不同的方式從外部檔案中挑選出精英解A*。

步驟7:判斷螢火蟲i和螢火蟲j之間是否存在吸引關系。若是,被吸引螢火蟲按照公式(13)更新位置,否則,2只螢火蟲均按照公式(12)更新位置。

步驟8:采用變異算子對更新后的螢火蟲進行變異,若變異后的位置優于變異前,則進行位置更新,否則,不進行任何操作。

步驟9:更新種群的適應度值。

步驟10:更新外部檔案Arc,若外部檔案中解的數量超出規模,利用擁擠距離策略刪除多余解。

步驟11:t=t+1。

步驟12:輸出Pareto最優解集。

3 實驗與結果

為驗證MOFA-MSF的性能,整個實驗包括2個部分:1)MOFA-MSF與經典多目標優化算法對比;2)MOFA-MSF與新近多目標優化算法對比。

3.1 與經典多目標優化算法對比

本節將MOFA-MSF與5種不同的經典多目標優化算法:MOPSO[18],PESA-I[19],MOEA/D[20],NSGA-III[21]和MOFA[11]在7個測試函數上進行對比。MOPSO、NSGA-III、MOFA、MOEA/D和PESA-II的實驗結果均取自文獻[13]。本文采用反轉世代距離(Inverted GenerationalDistance,IGD)[22]評判算法的優劣。為確保算法比較的公平性,MOFA-MSF和這5種經典算法的參數設置如表1所示,和其他算法的參數一樣,本文設置最大迭代次數maxT為300,種群大小為N為50,外部檔案大小ArcNum設置為200。為克服隨機因素的干擾,每個算法在每個函數上均獨立運行30次,取算法獨立運行30次的平均值作為評價指標。

表1 各經典算法的參數設置

表2列出了MOFA-MSF與其他5種經典算法在7個測試函數上的IGD的標準差(std)和均值(mean)及每個算法在所有測試函數上獲得的最優值的總數(total),表2中加黑的數據代表這6種算法在同一個測試函數上的最優值。從表2可知,MOFA-MSF算法在實驗中,除Vinnent1之外的其他測試函數均取得最優值,說明MOFA-MSF的收斂性和勘探能力相較于這些經典優化算法有了較大提升。在測試函數Viennet1下,PESA-II算法在IGD的均值上優于其他幾種算法,但MOFA-MSF在數量級上與其相同且系數差別很小,與此同時MOFA-MSF具有更小的IGD標準差,說明在這個測試函數上二者相差很小。綜上所述,相較于這幾種經典優化算法,MOFA-MSF算法在收斂性和多樣性方面體現了較強的優勢。

表2 MOFA-MSF與經典優化算法在IGD上的對比結果

表3給出了在IGD上基于Friedman校驗的各多目標優化算法結果的秩平均值和平均排名,可以看出MOFA-MSF排名第1,隨后分別是MOFA、PESA-II、NSGA-III、MOPSO,其中NSGA-III和MOPSO擁有相同的秩,排名并列第4,最差的是MOEA/D。表3的結果表明,MOFA-MSF相較于其他5種經典算法,求解精度更高,收斂性更好,綜合性能更強。

表3 各個算法在IGD上基于Friedman校驗的平均排名

為了更加直觀地體現MOFA-MSF的優勢,圖1列出了MOFA-MSF在2個測試函數上與5種經典算法上的Pareto前沿圖,其中黑色實線表示真實Pareto前沿,紅色圓圈表示算法所求得的Pareto前沿?？梢钥闯鯩OFA-MSF相較于經典算法在均勻性分布性上均有較強的優勢。

3.2 與新近多目標優化算法對比

為了進一步驗證MOFA-MSF的性能表現,本節將MOFA-MSF與7種新近的多目標優化算法:HVFA-M[13]、TVMOPSO[23]、NSLS[24]、CFMOFA[12]、MOEA/IGD-NS[25]、SMSE-MOA[26]和DMSPSO[27]進行對比。表4給出了MOFA-MSF與這7種新近算法的相關參數。

表4 MOFA-MSF與7種新近算法的參數設置

為確保實驗的公平性,除TVMOPSO、SMSE-MOA和DMSPSO的迭代次數保留原有的設置外,其余算法在2目標問題上迭代次數均設置為250,3目標問題設置為500。外部檔案大小ArcNum均設置為100。本算法的其余參數設置與3.2節相同。為克服隨機因素的干擾,每個算法在每個函數上均獨立運行30次,取IGD平均值(Mean IGD)作為評價指標。

表5列出了MOFA-MSF與這7種算法的對比結果,表中最后一行的total表示各個算法獲得最優值的次數,加黑的數據代表這8種算法在同一個測試函數上的最優值。從表5知,MOFA-MSF算法在6個測試函數上共取得4次最優。TVMOPSO和MOEA/IGD-NS分別在ZDT6和DTLZ4測試函數上各取得一次最優,其余算法未取得最優。表6是MOFA-MSF與這7種新近算法基于Friedman校驗的結果的秩平均值和平均排名,可以看出MOFA-MSF排名第一,隨后依次是HVFA-M、MOEA/IGD-NS、CFMOFA、TVMOPSO、SMSE-MOA、NSLS,最差的是DMSPSO。綜上所述,MOFA-MSF算法相較于這些新近多目標優化算法,依舊表現出較強的性能,且在收斂性和多樣性仍具有較強的優勢。

表5 MOFA-MSF與7種新近多目標優化算法在IGD上的對比結果

表6 各個算法在IGD上基于Friedman校驗的平均排名

經過兩輪的對比實驗可知,MOFA-MSF是一種有效且可行的多目標優化算法,在收斂性、分布性和勘探能力方面均表現出較強的優勢。原因在于,MOFA-MSF針對MOFA算法的缺陷,使用隨機化均勻化相結合的方法初始種群,再根據檔案中解的數量采用不同方式選取精英解并利用該精英解引導螢火蟲移動,引入變異算子提升算法的局部探索能力,在螢火蟲移動公式中加入萊維飛行隨機擾動代替原有隨機步長,采用擁擠距離策略維護外部檔案,以上多種策略融合在一定程度上優化了MOFA的收斂性差、分布性差和勘探能力弱等特點。

4 結論

針對MOFA所表現的問題,本文提出了多策略融合的多目標螢火蟲算法。首先,利用均勻化與隨機化相結合的初始化方法產生均勻分布的初始種群,為全局探索奠定了基礎;采用檔案精英配合萊維飛行隨機擾動引導螢火蟲的移動,在選擇檔案精英時,根據檔案中解的數量,采用不同的方式選擇精英解;引入變異算子,對進行過移動的螢火蟲的分量進行一個擾動,提升了種群的局部探索能力;最后,采用擁擠距離機制對外部檔案進行更新維護,以獲得最接近真實Pareto前沿的均勻分布的最優解集。本文使用MOFA-MSF在7個測試函數上與5種經典優化算法進行對比、在6個測試函數上與7種新近算法進行對比。實驗表明,MOFA-MSF在各個測試函數上均具有較為出色的性能。通過與這些經典算法和新近算法的對比,證實了本文多策略融合的有效性,提升了MOFA算法的性能。