趙嘉，陳丹丹，肖人彬，樊棠懷

（1.南昌工程學院 信息工程學院, 江西 南昌 330099; 2.華中科技大學 人工智能與自動化學院, 湖北 武漢430074）

現(xiàn)實生活中許多優(yōu)化問題涉及多個相互制約且相互沖突的目標，這類問題稱為多目標優(yōu)化問題(multi-objective optimization problem, MOP)[1]。解決MOP的難點在于改進其中一個目標必然會導致另一個或多個剩余目標的退化，因此針對MOP求解并不能同單目標優(yōu)化問題一樣找到一個唯一的最優(yōu)解使得各個目標同時取得最優(yōu)值，而是通過各個目標函數(shù)的相互協(xié)調，得到一組權衡最優(yōu)解，即Pareto最優(yōu)解集[2]。為盡可能的趨近于真實的Pareto最優(yōu)解集，通常采用多目標進化算法(multi-objective evolutionary algorithms,MOEA)[3]求解 MOP。

近30年來，MOEA研究成果豐富，種類繁多，主要包括基于Pareto支配關系的MOEA、基于精英保留機制的MOEA、基于分解的MOEA、基于指標的MOEA、混合機制的MOEA以及新型進化機制的MOEA，不同種類的MOEA表現(xiàn)出不同的優(yōu)劣勢與差異性?；赑areto支配關系的MOEA原理簡單，參數(shù)少，易于理解，代表算法有非支配排序遺傳算法(nondominated sorting genetic algorithm, NSGA)[4]及其改進版本NSGA-II[5]、NSGAIII[6]和多目標遺傳算法(multi-objective genetic algorithm, MOGA)[7]等?；诰⒈Ａ魴C制的MOEA通過建立外部檔案(external archive, EA)[8]來存儲精英解以增加解群的多樣性從而獲得優(yōu)良的Pareto前沿，代表算法有強度Pareto進化算法(strength pareto evolutionary algorithm, SPEA)[9]及其改進版本SPEA2[10]、Pareto存檔進化策略算法(pareto archived evolution strategy, PAES)[8]及其改進版本PESA和PESA-II[11]等。基于分解的MOEA將MOP轉化為一組單目標優(yōu)化問題，在此基礎上進行子問題鄰域信息協(xié)同求解，代表算法有基于分解的多目標進化算法(multi-objective evolutionary algorithm based on decomposition, MOEA/D)[12]以及在此基礎上改進的基于多層交互偏好的多目標分解進化算法(multi-layer interaction preference based multi-objective evolutionary algorithm through decomposition, MLIP-MOEA/D)[13]等?；谥笜说腗OEA運用性能評價指標來引導搜索及對解進行選擇，使算法能夠找到針對評價指標好的解，代表算法有多目標搜索中基于指標的選擇算法(indicator-based selection in multi-objective search,IBEA)[14]和基于超體積的多目標快速優(yōu)化算法(algorithm for fast hypervolume-based many-objective optimization, HypE)[15]等?；旌蠙C制的MOEA通過結合每個MOEA和元啟發(fā)式算法的優(yōu)點以克服單個MOEA或元啟發(fā)式算法的固有局限性，從而進一步提高解空間搜索的有效性，代表算法有超多目標進化算法(hyper multi-objective evolutionary algorithm, HMOEA)[16]和自適應多種群混合進化算法(hybrid evolutionary algorithm with adaptive multi-population strategy, HMOEAAMP)[17]等。近年來，基于新型進化機制的MOEA在多目標優(yōu)化領域嶄露頭角，如多目標粒子群算法(multi-objective particle swarm optimization,MOPSO)[18]，多目標灰狼算法(multi-objective grey wolf optimizer, MOGWO)[19]等，這類算法通過引入元啟發(fā)式算法和新型進化機制來求解多目標優(yōu)化問題，提供了研究MOP的新思路，在多目標優(yōu)化領域廣受關注。

Yang[20]通過對螢火蟲種群行為的模擬和簡化，提出了螢火蟲算法(firefly algorithm, FA)。FA與其他進化算法相比，前者在概念、過程、涉及的參數(shù)和適用性方面具有優(yōu)勢[21-22]，鑒于FA的種群搜索特性以及良好的優(yōu)化性能，Yang[23]將其應用于求解多目標優(yōu)化問題，提出了多目標螢火蟲算法(multi-objective firefly algorithm, MOFA）。MOFA改進了FA中的移動公式，使公式的隨機項隨迭代次數(shù)呈非線性遞減，并采用權重比策略確定當前最好解，但螢火蟲的移動僅受制于支配解或者當前最好解，算法的搜索范圍具有局限性，勘探能力有待增強，導致MOFA易早熟且收斂性能差。

為了提升MOFA的勘探能力，增強算法的優(yōu)化性能，Tsai等[24]提出了一種基于非支配排序的多目標螢火蟲算法(non-dominated sorting firefly algorithm for multi-objective optimization, MONSFA)，MONSFA中提供了兩種隨機搜索策略供螢火蟲選擇移動，通過隨機改變螢火蟲的搜索方向來提高算法的勘探能力，同時運用NSGA-II的非支配排序和擁擠距離策略實現(xiàn)種群再生和檔案維護以提高算法的全局搜索能力。謝承旺等[25]提出了一種多策略協(xié)同的多目標螢火蟲算法(multi-objective firefly algorithm based on multiply cooperative strategies, MOFA-MCS)，該算法改進了MOFA的學習公式，通過隨機選取檔案精英解作為引導者指引粒子學習來間接阻止種群向局部區(qū)域靠攏，拓寬種群的搜索范圍以達到提升算法勘探能力的目的。LYU等[26]提出了一種基于補償因子與精英學習的多目標螢火蟲算法(multi-objective firefly algorithm based on compensation factor and elite learning, CFMOFA)，CFMOFA中通過精英學習來擴大螢火蟲的探測范圍，以此來提高Pareto最優(yōu)解集的多樣性和準確性。

上述提到的各改進算法在一定程度上均提升了算法的勘探能力，但大都是對算法的局部進行改進，算法的整體性能并未取得大的突破，且學習策略單一，具有一定的局限性，一方面，螢火蟲移動的方向過于片面，種群的勘探能力有待進一步提高，解集覆蓋域不夠廣泛；另一方面，算法的尋優(yōu)性能差，難以收斂到真實的Pareto最優(yōu)解?；诖?，為提升算法的勘探能力，增強算法的全局搜索能力，本文提出了一種基于最大最小策略和非均勻變異的螢火蟲算法(heterogeneous variation firefly algorithm with maximin strategy, HVFAM)。HVFA-M具有如下特點：1)引入Maximin策略[27]，一方面用于維護檔案群體的多樣性，以獲得分布性較好的解集，另一方面用于從外部檔案中隨機挑選精英解，參與種群進化；2)精英解[19]配合當前最好解引導螢火蟲移動，以擴大種群的搜索范圍，增大Pareto最優(yōu)解所在區(qū)域被探測到的可能性，使得解集覆蓋域更廣，有利于提高解集分布的廣泛性；3)螢火蟲位置更新后進行非均勻變異[28]，促使算法進行局部搜索，在提高算法全局探索能力的同時兼顧算法的局部開采能力，有利于收斂到真實的Pareto最優(yōu)解。以上3種策略分工明確，協(xié)同實施，作用于HVFA-M的不同階段，顯著增強了算法的勘探能力和尋優(yōu)能力，提高了多目標螢火蟲算法的收斂性及多樣性。

1 基礎知識

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

以最小化問題為例，MOP的數(shù)學模型通?？梢悦枋鰹橐韵滦问剑?/p>

式中：x表示決策向量；n為決策向量的維數(shù)；X是n維決策空間；y表示目標向量；m為目標函數(shù)的個數(shù)；Y是m維目標空間。對于任意兩個決策向量xi,xj∈X，當且僅當成立時，稱xiPareto支配xj，記為xi?xj。若 ? ?x∈X，使得x?x?成立，則稱x?為非支配解個體，種群中所有非支配解個體組成的集合稱為Pareto最優(yōu)解集(pareto-optimal set, PS)，其在目標空間的投影稱為Pareto最優(yōu)前沿(pareto-optimal front, PF)。

1.2 多目標螢火蟲算法

螢火蟲算法中，亮度和吸引力是兩個關鍵要素。亮度表征了螢火蟲所處位置的優(yōu)劣，吸引力決定了螢火蟲移動的方向，所有螢火蟲根據(jù)位置更新公式移動到新的位置后，更新自身亮度，并根據(jù)吸引規(guī)則進行下一次移動。通常將螢火蟲xi的絕對亮度I(xi)表示為I(xi)?f(xi)，即用螢火蟲xi所在位置解的目標函數(shù)值表征xi的絕對亮度。吸引力 β是一個相對參數(shù)，取決于每一只螢火蟲所處的相對位置，根據(jù)螢火蟲之間的吸引力與它們的亮度成正比，而與它們的距離成反比的特性[22]，螢火蟲j對螢火蟲i的吸引力可定義為

式中： β0為最大吸引力，即在光源處rij=0螢火蟲的吸引力(通常取值為1)；γ為光吸收系數(shù)，用來體現(xiàn)光強隨距離增加和傳播媒質的吸收而逐漸減弱的特性，從而描述出吸引力的變化，一般取γ ∈[0.01,100]；rij為螢火蟲i到螢火蟲j之間的空間距離，一般采用歐氏距離計算，但不僅僅局限于歐氏距離。

對于任意給定的兩只螢火蟲，螢火蟲i被螢火蟲j吸引并朝著j所在的方向移動，其位置更新公式為

式中：第2部分是學習部分，取決于吸引力的大?。坏?部分是隨機部分，是帶有特定系數(shù)的隨機項。其中t為算法的迭代次數(shù)，xi(t)和xj(t)分別為算法在第t次迭代時，螢火蟲i和螢火蟲j的空間位置；α為步長因子，取值為 [0 ,1]內(nèi)均勻分布的隨機數(shù)，εi為服從均勻分布、高斯分布或者其他分布得到的隨機數(shù)向量。

多目標螢火蟲算法中，根據(jù)Pareto 支配的定義確定任意兩只螢火蟲之間是否存在吸引關系，以螢火蟲i作為研究對象，若螢火蟲j?i，i被j吸引，并按照式(3)朝著螢火蟲j所在的位置和方向移動。若螢火蟲i不被其他任何螢火蟲支配，則根據(jù)式(4)進行位置更新[21]：

其中，g?表示當前最好解，α和 εi的含義同式(3)，其取值可參考文獻[23]。g?是由式(5)將多目標函數(shù)以隨機加權和的方式轉換成一個組合的單目標函數(shù)而取得的最優(yōu)值，若求取的是最小化問題，則g?是令單目標函數(shù)最小化得到的針對給定的多目標優(yōu)化問題的當前最小解。

式中：K表示目標函數(shù)的個數(shù)；wk∈(0,1)，權重wk應該在每次迭代中隨機選擇，以便非支配解沿著帕累托前沿進行不同的采樣。

1.3 Maximin 策略

Maximin策略起源于游戲理論，由Balling[29]首次將其應用于求解多目標優(yōu)化問題，并得出其在不使用其他多樣性維護機制的條件下可以實現(xiàn)非劣解前沿均勻分布的目標。Maximin策略中，運用Maximin適應值函數(shù)計算出每只螢火蟲的Maximin適應值，借助Maximin適應值的大小區(qū)分每只螢火蟲的優(yōu)劣，螢火蟲 的Maximin適應值函數(shù)定義為

式中：l=1,2,···,m，m為目標函數(shù)的個數(shù)；npop為種群大小。首先計算出螢火蟲i與其他螢火蟲對應不同目標函數(shù)上的差值，從中選取最小值 m in(xi)，再從i與其他所有螢火蟲計算所得的所有min(xi)中選取最大值 m ax(min(xi))作為i的Maximin適應值。顯然，非劣解的Maximin適應值均小于零，即在解群中根據(jù)Maximin適應值的正負便可辨別非劣解，同時，Maximin策略可用于“獎勵”分散的非劣解和“懲罰”聚集的非劣解[27]，即分散解的Maximin適應值更小，聚集解的Maximin適應值較大。Maximin策略憑借這兩個獨特的性質成為求解MOP的一個有效工具，一方面，區(qū)分了非劣解的優(yōu)劣；另一方面，根據(jù)這一區(qū)分可以保留種群中Maximin適應值小且分散的解，保證了解集之間分布的均勻性。

標準的Maximin策略計算不在同一數(shù)量級的目標值時，得到的Maximin適應值具有偏向性，其次，支配解的存在會影響非支配解的Maximin適應值。針對Maximin策略存在的缺陷，徐鳴等[30]提出應先對所有目標值進行規(guī)范化處理，Gong等[31]提出應僅計算非劣解的Maximin適應值，此外，賈樹晉等[27]提出為了獲得廣泛的Pareto最優(yōu)端，應令邊界解的Maximin適應值最小以避免其丟失。因此在本文算法中運用改進的Maximin策略[27]，定義為

式中：l=1,2,···,m；fl(xi)指螢火蟲i進行規(guī)范化后第l維目標值；xbs表示非支配解集的邊界解。

2 HVFA-M算法

2.1 Maximin策略維護種群多樣性和選取精英解

MOEA 通常采用設置一定大小的外部檔案來儲存算法在迭代過程中產(chǎn)生的非劣解，為避免資源贅余，引入 Maximin 策略[27]。Maximin 策略作為一種多樣性維護策略，常用于多目標優(yōu)化算法中維護種群的多樣性，本文算法中，Maximin策略不僅作為外部檔案更新策略，還作為精英選擇策略，一方面用以維持解群的多樣性，另一方面用以區(qū)分精英解之間的優(yōu)劣信息，便于選擇較優(yōu)的精英解參與種群進化。當外部檔案EA 中非劣解的數(shù)量超過算法限制的最大容量時，運用Maximin策略刪除多余的非劣解。具體步驟為：

1) 根據(jù)式(7) 計算EA 中每個非劣解的Maximin 適應值；

2) 將EA 中所有的非劣解按照Maximin 適應值進行升序排序；

3) 刪除Maximin 適應值最大的解，重復此步驟，直到檔案中的容量達到其限定值。

2.2 學習策略的改進

從式(3)、(4) 可以看出，標準MOFA中被支配的螢火蟲僅僅受到支配它的螢火蟲和隨機項的影響，不受任何支配的螢火蟲僅僅受到當前最好解和隨機項的影響，而存儲在外部檔案中的非劣解，也就是精英解，也沒有得到充分的利用，這導致種群進化緩慢，使得算法的勘探能力弱，不利于解集逼近并廣泛完整的表達真實的Pareto前沿。基于外部檔案中的精英解攜帶了優(yōu)良的種群信息，可以指導種群進化，本文對學習公式進行了改進，引入精英解結合當前最好解共同引導螢火蟲移動，合理的繼承了解群中的優(yōu)良基因，擴大了算法的搜索范圍，有利于算法獲得位置更為優(yōu)異，分布更為均勻，覆蓋范圍更為廣泛的Pareto最優(yōu)解集。改進如下：

1) 當螢火蟲i被j支配時，螢火蟲i的位置更新公式為

2) 當螢火蟲i不被其他任何螢火蟲支配時，螢火蟲i的位置更新公式為

以存在支配關系的螢火蟲的位置更新公式為例，求解二目標最小化問題，給出MOFA和HVFA-M兩種算法搜索范圍的簡化模型，如圖1所示。圖1中，黑色曲線為Pareto最優(yōu)前沿，紅色五角星代表外部檔案中的精英解，紅色圓點代表當前最好解g?，黑色圓點表示螢火蟲，橙色圓圈為螢火蟲的搜索范圍。MOFA中，若螢火蟲j

圖1 MOFA與HVFA-M搜索范圍的差異性Fig.1 Differences in search scope between MOFA and HVFA-M

2.3 非均勻變異機制

螢火蟲算法收斂速度較快，導致多目標螢火蟲算法后期在尋優(yōu)過程中易陷入早熟收斂，很難收斂于真實的Pareto 前沿，通常通過引入變異算子解決這一問題。非均勻變異算子[28]作為一種動態(tài)變異算子，在初始階段能夠均勻的搜索空間，具備一定的全局搜索能力；在后期則具備一定的局部搜索能力，有利于尋找到更好的非支配解，進一步提高解的質量?；诖耍敕蔷鶆蜃儺愃阕?，每一代螢火蟲i進行位置更新后，按照一種隨迭代次數(shù)動態(tài)遞減的變異概率pm隨機對i的向量進行擾動，這里若選中的是第k維分量（1 ≤k≤n，n為向量的維數(shù)），變異操作可定義為[26]

式中：uk和lk分別為向量取值范圍的最大值與最小值；γ隨機的取0或1；t為當前迭代次數(shù)；Gmax為最大迭代次數(shù)；r為 [0 ,1]內(nèi)的隨機數(shù)；b為系統(tǒng)參數(shù)，決定了隨機數(shù)擾動對迭代次數(shù)t的依賴程度，取值一般為2到5，本文中取b=3。算法前期，t較小，該算子均勻的搜索空間，充分發(fā)揮螢火蟲算法的全局搜索能力；算法后期，隨著t增大，該算子的搜索變得局部化，使得變異后產(chǎn)生的新解以更大的概率逼近真實的Pareto 最優(yōu)解，如圖2所示。非均勻變異算子的引入平衡了算法全局搜索和局部開采的能力，進一步提高了算法的尋優(yōu)能力，有效增強了算法的收斂性。

圖2 非均勻變異算子下螢火蟲的局部搜索Fig.2 Local search of firefly under heterogeneous variation

2.4 算法流程

結合Maximin 策略、學習公式改進及非均勻變異機制3種策略，給出HVFA-M 的算法流程，如算法1所示。

算法1基于最大最小策略和非均勻變異的螢火蟲算法

輸入決策向量的維數(shù)n，決策變量的區(qū)間范圍 [a,b]，種群規(guī)模npop，外部檔案容量nrep，最大迭代次數(shù)Gmax，光吸收系數(shù) γ，最大吸引度 β0，以及初始步長α。

輸出Pareto最優(yōu)解集

1)螢火蟲種群初始化。產(chǎn)生規(guī)模為npop的初始群體，nrep=0，迭代次數(shù)t= 0。

2)計算螢火蟲在每一個目標函數(shù)上的適應值，并根據(jù)Pareto關系進行評價，將非支配解復制到nrep中。

3)根據(jù)式(7)計算所有非支配螢火蟲的Maximin適應值。

4) 當t

5) 對螢火蟲進行遍歷，重復6)~8)。

6) 螢火蟲i與螢火蟲j進行比較，重復7)~8)。

7)螢火蟲之間進行相互學習。若螢火蟲j

8)非均勻變異。對位置更新后的螢火蟲進行變異，若變異后的螢火蟲優(yōu)于變異前的螢火蟲，則將該位置替換為變異后的螢火蟲，否則不做任何操作。

9)更新所有非支配螢火蟲的Maximin適應值。

10)外部檔案更新與維護。若外部檔案中非支配解的數(shù)量超出其最大容量nrep，按照Maximin適應值的大小對檔案中的所有非支配解進行排序，通過刪去Maximin適應值最大的解來實現(xiàn)外部檔案動態(tài)調整的目的，直到滿足條件為止

11)t=t+1

2.5 算法時間復雜度分析

由于螢火蟲算法采用全吸引模型，MOFA算法采用兩層循環(huán)遍歷所有螢火蟲，故其時間復雜度為O(N2)。HVFA-M算法在MOFA的基礎上，添加了Maximin策略，在求解Maximin適應值時，新增兩個循環(huán)，第一個循環(huán)遍歷所有目標m，第二個循環(huán)遍歷了所有螢火蟲，故其時間復雜度為O(N2)+O(mN)。由于求解的目標個數(shù)較種群規(guī)模少(m

3 實驗與結果

3.1 測試函數(shù)

為評估HVFA-M的性能，本文使用9個經(jīng)典的MOP對HVFA-M進行性能測試[32-34]，這9個多目標測試函數(shù)由5個2-目標函數(shù)和4個3-目標函數(shù)組成。其定義及特征如表1、2所示。

表1 2-目標測試函數(shù)集Table 1 2-objective test function

表2 3-目標測試函數(shù)集Table 2 3-objective test function

3.2 與經(jīng)典多目標優(yōu)化算法進行比較

為驗證HVFA-M的性能，將HVFA-M 與MOPSO[18]，NSGA-III[6]，MOEA/D[12]，PESA-II[11]及MOFA[23]5種經(jīng)典多目標優(yōu)化算法進行比較，所有對比算法的參數(shù)設置均取自于相應文獻，如表3所示。為分別驗證HVFA-M 的收斂性和Pareto最優(yōu)解集的廣泛性，采用generation distance(GD)[35]、maximum spread(MS)[36]性能評價指標量化算法獲得的Pareto 最優(yōu)前沿的收斂性和廣泛性，其中GD反映了算法所得的近似Pareto 前沿對真實Pareto前沿的逼近程度，GD值越小，表示算法收斂性越好；MS 反映出算法所得的Pareto 最優(yōu)前沿在目標空間中分布的廣泛程度，MS值越大，表示解集的廣泛性越好。為評價HVFA-M的綜合性能，即避免算法收斂性差而導致的更廣泛的分布的影響，采用inverted generation distance(IGD)[37]評價指標來判斷算法的優(yōu)劣，IGD指標可同時評價算法的收斂性和多樣性，IGD值越小，算法的綜合性能越好。為保證所有算法比較的公平性，所有算法的最大迭代次數(shù)設置為300，種群大小設置為50，外部檔案EA 的[大小設置]為200；為減少隨機因素的干擾，所有算法在每個測試函數(shù)上均獨立運行30次，評價指標數(shù)據(jù)為算法獨立運行30次的平均值。

表3 各算法參數(shù)設置Table 3 Parameter setting of each algorithm

表4~6給出了HVFA-M 與其他5種經(jīng)典算法在9個測試函數(shù)上的GD 、MS、IGD 的均值和標準差，表格中加粗數(shù)據(jù)表示不同算法在同一測試函數(shù)上取得的最優(yōu)值。

表4 HVFA-M與5種經(jīng)典算法在GD上的實驗結果Table 4 Experimental results of HVFA-M and five classical algorithms on GD

續(xù)表4

根據(jù)表4，單方面考慮算法的收斂性看，HVFA-M在9個測試函數(shù)上有5次取得最優(yōu)，相對于其他5種對比算法獲得的最優(yōu)值的次數(shù)最多，尤其對于測試函數(shù)ZDT1—ZDT4，在收斂性上的優(yōu)勢更為突出，充分體現(xiàn)出其勘探能力強，收斂性能好的優(yōu)點。根據(jù)表5，從算法求取的Pareto 最優(yōu)解集的廣泛性角度分析，HVFA-M 在9個測試函數(shù)上有4次取得最優(yōu)值，且在剩余的5個測試函數(shù)上的取值與最優(yōu)值相差不大，充分凸顯出其搜索范圍廣、覆蓋面積大的特點。根據(jù)表6，綜合來看，HVFA-M 在9個測試函數(shù)上有4次取得最優(yōu)，且在ZDT6、Viennet1問題上，HVFA-M 與最優(yōu)值之間具有相同的數(shù)量級，表明二者之間差異性小，充分說明HVFA-M 在收斂性和多樣性方面具有較強的優(yōu)勢。

表5 HVFA-M與5種經(jīng)典算法在MS上的實驗結果Table 5 Experimental results of HVFA-M and five classical algorithms on MS

表6 HVFA-M與5種經(jīng)典算法在IGD上的實驗結果Table 6 Experimental results of HVFA-M and five classical algorithms on IGD

表7給出了各種算法在3種評價指標上分別取得最優(yōu)值的數(shù)目。表8采用Friedman檢驗給出6種對比算法在3種性能評價指標上的平均排名。

從表7給出的各算法優(yōu)勢解的總數(shù)統(tǒng)計來看，HVFA-M 在3種評價指標上共有13次取得了最優(yōu)值，排名第一，遠勝于其他5種對比算法，PESA-II次之，共取得5次最優(yōu)，最差的是MOFA，無一次取得最優(yōu)。綜合來看，HVFA-M相對于其他5種對等比較算法表現(xiàn)出顯著的性能優(yōu)勢。

從表8可以看出，HVFA-M 在GD、MS、IGD上的名次均是最好的，在GD上隨后依次是NSGA-III、PESA-II 、MOFA、和 MOPSO，最差的是MOEA/D；在MS上隨后依次是MOPSO、PESA-II 、MOFA和MOEA/D，最差的是NSGA-III；在IGD上隨后依次是 PESA-II、MOPSO、NSGA-III和 MOFA，最差的是MOEA/D。Friedman檢驗結果表明HVFAM較其他5種對比算法求解的精確度更高、覆蓋率更廣、綜合性能顯著。

為更加直觀的展現(xiàn)HVFA-M 的優(yōu)勢，圖3列出了HVFA-M 與5種經(jīng)典算法在9種測試函數(shù)上的Pareto前沿擬合曲線圖，其中黑線表示真實的Pareto前沿，紅色圓圈表示算法所得的Pareto前沿。該曲線圖清晰的呈現(xiàn)出各個算法在各個測試問題上求取的Pareto 前沿與真實Pareto 前沿的擬合情況，與表4~8給出的實驗結果保持一致，均表明HVFA-M 較其他5種算法具有最優(yōu)的GD、 MS和IGD 性能，即具有較好的收斂性和多樣性。

圖3 HVFA-M與5種經(jīng)典算法的Pareto前沿擬合曲線Fig.3 Fitting of Fareto fronts of HVFA-M and five classical algorithms

3.3 與新近的多目標優(yōu)化算法比較

為進一步驗證HVFA-M 的有效性，本部分將HVFA-M 與6種新近的多目標優(yōu)化算法 SMSEMOA[38]、 TVMOPSO[39]、DMSPSO[40]、 NSLS[41]、MOEA/IGD-NS[42]以及 CFMOFA[26]進行比較，所有對比算法的參數(shù)設置均取自于相應文獻，如表9所示。這里選取6個基準MOP 測試問題組成的測試集合，包括5個2-目標的ZDT 系列函數(shù)ZDT1、ZDT2、ZDT3、ZDT4和 ZDT6，以及 1個 3-目標的DTLZ 系列函數(shù)DTLZ4，并利用IGD評價指標來判斷算法的優(yōu)劣。實驗中，為了確保公平性，EA最大設為100，除SMSEMOA、TVMOPSO 以及DMSPSO 算法的評估次數(shù)維持其實驗原始設計外，其他所有算法的2-目標測試問題的最大迭代次數(shù)設置為250，3-目標測試問題的最大迭代次數(shù)設置為500；為平衡隨機性，算法獨立運行30次，結果取其平均值，實驗結果由表10 給出，其中加粗數(shù)據(jù)表示不同算法在同一測試函數(shù)上獲得的最優(yōu)值。

表9 各算法參數(shù)設置Table 9 Parameter setting of each algorithm

根據(jù)表10， HVFA-M在6個測試函數(shù)上取得了3次最優(yōu)的IGD均值，TVMOPSO、MOEA/IGDNS、CFMOFA僅僅各取得一次最優(yōu)，SMSEMOA、DMSPSO、NSLS在6個測試函數(shù)上均無一次能獲得最優(yōu)的IGD均值。表11采用Friedman檢驗給出了HVFA-M與6種新近算法基于IGD指標的平均排名，可以看出，HVFA-M排名第一，MOEA/IGD-NS次之，隨后依次是CFMOFA、TVMOPO、SMSE-MOA、NSLS，最差的是DMSPSO，F(xiàn)riedman檢驗的結果與表10中的IGD均值結果保持一致。綜合來看，HVFA-M較其他6種對比算法具有更強IGD性能，即表現(xiàn)出更強的收斂性與多樣性。

表10 HVFA-M與6種新近算法的IGD實驗結果Table 10 Experimental results of HVFA-M and six recent algorithms on IGD

表11 各算法在IGD上基于Friedman檢驗的平均排名Table 11 Average ranking of each algorithm based on Friedman test on IGD

經(jīng)過兩次實驗比較可知，HVFA-M 是一種可行且有效的多目標優(yōu)化算法，表現(xiàn)出很強的收斂性及多樣性。究其原因：首先，運用Maximin策略一方面有效維護了解群的多樣性，另一方面用于選擇精英解參與種群進化；其次，檔案精英解結合當前最好解指導螢火蟲移動，有利于提升算法的勘探能力，擴大種群搜索范圍，增強算法的收斂性和廣泛性；最后，引入非均勻變異算子平衡算法全局與局部搜索的能力，促進種群全局勘探的同時兼顧種群局部開發(fā)，進一步提高種群的尋優(yōu)能力，促進算法收斂。以上3種策略分工合作，相互結合，共同提高了HVFA-M收斂性、多樣性的綜合性能。

3.4 3種改進策略的有效性分析

本文提出的HVFA-M是MOFA與多種策略的融合，它將MOFA與3種策略融合在一起：Maximin多樣性維護策略(K1)、改進學習策略(K2)和非均勻變異機制(K3)。為了分析3種改進策略對算法性能產(chǎn)生的影響，將MOFA與每種策略融合進行測試。選取表1、2中的9個典型的多目標測試函數(shù)進行數(shù)值實驗，所涉及的算法描述如下。

MOFA：標準MOFA不添加任何策略。

MOFA+K1：添加Maximin多樣性維護策略的MOFA。

MOFA+K1+K2： 添加Maximin多樣性維護策略和改進學習策略的MOFA。

MOFA+K3：添加非均勻變異機制的MOFA。

MOFA+K1+K3：添加Maximin多樣性維護策略和非均勻變異機制的MOFA.

HVFA-M： K1、K2、K3的 3種策略融合的MOFA。

需要指出的是，由于策略K2是在添加策略K1的基礎上實現(xiàn)，因此無法單獨給出MOFA添加策略K2的實驗結果。表12給出了添加不同策略的MOFA9個測試問題上獲得的IGD均值和方差，算法的參數(shù)設置與3.2節(jié)相同，其中加粗數(shù)據(jù)為最好的測試結果。

表12 算法策略分析的IGD實驗結果Table 12 Experimental results of algorithm strategy analysis on IGD

續(xù)表12

根據(jù)表12可以看出，僅添加Maximin多樣性維護策略和僅添加非均勻變異機制對改進MOFA的幫助有限，而在Maximin策略的基礎上添加改進學習策略或非均勻變異機制均能有效改善算法的性能，特別是MOFA在Maximin多樣性維護策略的基礎上，添加通過Maximin適應值篩選出精英解來引導學習的改進學習公式策略，對算法的幫助更大。對于DTLZ7測試函數(shù)，由于其具有離散、混合和多模態(tài)的組合特征，使得3種策略均不適用于求解此類問題。從算法獲得的最優(yōu)值的數(shù)目上看，MOFA融合3種策略改進的HVFA-M，能夠顯著提高Pareto最優(yōu)解集的質量。表13給出了 HVFA-M與對比算法基于IGD指標的Friedman檢驗結果，可以看出，HVFA-M排名第一，其次是 MOFA+K1+K2、MOFA+K1+K3、MOFA+K3、MOFA+K1，最差的是MOFA。綜合來看，MOFA通過結合3種策略，獲得了更好的優(yōu)化性能。

表13 算法策略分析的IGD平均排名Table 13 Average ranking of algorithm strategy analysis on IGD

4 結論

多目標螢火蟲算法的勘探能力弱，求解精度差，本文針對這一問題，提出了一種新的多目標優(yōu)化方法?基于最大最小策略和非均勻變異的螢火蟲算法(HVFA-M)。首先，Maximin策略用作外部檔案的動態(tài)調整以保證目標空間中非劣解的良好覆蓋從而確保精英解參與種群進化；其次，檔案精英解配合當前最好解引導螢火蟲移動，使得螢火蟲移動的方向更全面，以提高算法的勘探能力從而增大解群尋找最優(yōu)解的概率；最后非均勻變異算子的引入使得算法融入了一定的局部搜索思想，以提高解的尋優(yōu)能力從而進一步加快算法收斂。在多目標領域廣泛使用的幾個基準測試函數(shù)上，將HVFA-M 與幾種經(jīng)典及新近算法進行比較研究，數(shù)值結果和圖形結果清晰地表明，本文所提出的HVFA-M 具有很強的競爭力，是解決多目標優(yōu)化問題的一種可行且有效的選擇。本文的研究重點是小規(guī)模多目標優(yōu)化問題，下一步，將驗證HVFA-M 在大規(guī)模多目標測試問題上的性能，并運用HVFA-M 求解工程實踐中的多目標優(yōu)化問題。