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

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

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

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

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

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

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

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

1 基礎(chǔ)知識(shí)

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

以最小化問題為例，MOP的數(shù)學(xué)模型通常可以描述為以下形式：

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

1.2 多目標(biāo)螢火蟲算法

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

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

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

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

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

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

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

1.3 Maximin 策略

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

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

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

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

2 HVFA-M算法

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

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

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

2) 將EA 中所有的非劣解按照Maximin 適應(yīng)值進(jìn)行升序排序；

3) 刪除Maximin 適應(yīng)值最大的解，重復(fù)此步驟，直到檔案中的容量達(dá)到其限定值。

2.2 學(xué)習(xí)策略的改進(jìn)

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

1) 當(dāng)螢火蟲i被j支配時(shí)，螢火蟲i的位置更新公式為

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

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

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

2.3 非均勻變異機(jī)制

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

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

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

2.4 算法流程

結(jié)合Maximin 策略、學(xué)習(xí)公式改進(jìn)及非均勻變異機(jī)制3種策略，給出HVFA-M 的算法流程，如算法1所示。

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

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

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

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

2)計(jì)算螢火蟲在每一個(gè)目標(biāo)函數(shù)上的適應(yīng)值，并根據(jù)Pareto關(guān)系進(jìn)行評(píng)價(jià)，將非支配解復(fù)制到nrep中。

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

4) 當(dāng)t

5) 對(duì)螢火蟲進(jìn)行遍歷，重復(fù)6)~8)。

6) 螢火蟲i與螢火蟲j進(jìn)行比較，重復(fù)7)~8)。

7)螢火蟲之間進(jìn)行相互學(xué)習(xí)。若螢火蟲j

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

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

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

11)t=t+1

2.5 算法時(shí)間復(fù)雜度分析

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

3 實(shí)驗(yàn)與結(jié)果

3.1 測(cè)試函數(shù)

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

表1 2-目標(biāo)測(cè)試函數(shù)集Table 1 2-objective test function

表2 3-目標(biāo)測(cè)試函數(shù)集Table 2 3-objective test function

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

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

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

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

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

續(xù)表4

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

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

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

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

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

從表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檢驗(yàn)結(jié)果表明HVFAM較其他5種對(duì)比算法求解的精確度更高、覆蓋率更廣、綜合性能顯著。

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

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

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

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

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

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

表10 HVFA-M與6種新近算法的IGD實(shí)驗(yàn)結(jié)果Table 10 Experimental results of HVFA-M and six recent algorithms on IGD

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

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

3.4 3種改進(jìn)策略的有效性分析

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

MOFA：標(biāo)準(zhǔn)MOFA不添加任何策略。

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

MOFA+K1+K2： 添加Maximin多樣性維護(hù)策略和改進(jìn)學(xué)習(xí)策略的MOFA。

MOFA+K3：添加非均勻變異機(jī)制的MOFA。

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

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

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

表12 算法策略分析的IGD實(shí)驗(yàn)結(jié)果Table 12 Experimental results of algorithm strategy analysis on IGD

續(xù)表12

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

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

4 結(jié)論

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