一種改進的多目標蜻蜓優化算法

韓 鵬，陳 鋒

(中國科學技術大學 自動化系，安徽 合肥 230000)

一種改進的多目標蜻蜓優化算法

韓 鵬，陳 鋒

(中國科學技術大學 自動化系，安徽 合肥 230000)

提出了一種改進的多目標蜻蜓優化算法。通過引入混合變異算子增加種群的多樣性，避免算法早熟現象的發生；采用基于擁擠距離的外部檔案動態維護策略，使獲得的Pareto最優解集具有更好的分布性。最后，使用多目標基準函數進行測試，并與基本多目標蜻蜓算法和基本多目標粒子群算法進行性能比較。實驗結果表明，改進后的多目標蜻蜓優化算法提高了Pareto最優解集的收斂性和分布性。

多目標優化；蜻蜓算法；多樣性；分布性

0 引言

工程實踐和系統設計中的許多優化問題都是多目標優化問題，如城市交通交叉口信號配時，系統的軟硬件設計等。傳統的處理多目標優化問題的方法是通過加權求和將多目標轉化為單目標問題來進行處理。但是，這要求對優化問題有很強的先驗認識，難以應用到真正的多目標優化中。又由于多目標優化問題幾乎都不存在唯一的全局最優解，因此多目標優化問題通常是要尋找一組非劣解[1](Pareto最優解集)。

蜻蜓算法[2]是美國學者MIRJALILI S在2015年提出的一種基于種群的啟發式智能算法，其易于理解和實現。蜻蜓算法在一些系統優化方面比粒子群算法更有效果，并且已得到成功應用。傅軍棟等人[3]提出了基于蜻蜓算法和支持向量機的變壓器故障診斷方法，相對于GA-SVM和PSO-SVM方法，具有準確率高、收斂速度快以及穩定性好的優點。SAMBANDAM R K等人[4]提出一種自適應蜻蜓算法解決圖像多級分割問題，并成功應用在醫學圖像領域。然而，與其他基于種群的啟發式算法類似，基本多目標蜻蜓算法同樣存在容易陷入局部最優且非劣解分布不均勻的缺陷。為此本文提出一種改進的多目標蜻蜓優化算法(IMODA)。

本文首先在多目標蜻蜓優化算法中引入混合變異算子，提高種群多樣性，減小種群陷入局部最優的可能性；然后采用基于擁擠距離的動態檔案維護策略，使Pareto解集具有更好的分布性。最后，通過對多目標基準函數的測試，并與基本多目標粒子群算法和基本多目標蜻蜓算法進行世代距離(GD)、覆蓋率(MS)、分布均勻度(SP)三種性能指標[5]的比較分析。

1 多目標蜻蜓算法原理

蜻蜓算法的靈感來源于蜻蜓的靜態和動態群體行為，在靜態群體行為中，群體進行捕食；在動態群體行為中，群體進行遷移。這兩種行為非常類似于啟發式優化算法中的兩個重要階段：探索和開發。為模擬蜻蜓的群體行為，MIRJALILI S借鑒了。SAMBANDAM R K在描述昆蟲行為中提出的三種基本原則：分離度、對齊度和內聚度，以及另外兩個新概念(食物吸引力和天敵排斥力)。具體意義和數學表達方法如下：

(1)分離度指蜻蜓與相鄰個體之間避免碰撞。

(1)

(2)對齊度是指相鄰個體之間傾向于保持相同的速度。

(2)

(3)內聚度是指蜻蜓傾向于向相鄰個體中心聚攏。

(3)

(4)食物吸引力指食物對蜻蜓的吸引力。

Fi=X+-X

(4)

(5)天敵排斥力指蜻蜓對天敵的排斥力。

Ei=X-+X

(5)

式中X表示當前蜻蜓個體的位置；Xj表示第j個相鄰蜻蜓個體的位置；Vj表示第j個相鄰蜻蜓個體的速度；N表示與第i個蜻蜓個體相鄰的個體數量；X+表示食物源位置；X-表示天敵位置。

根據上述5種蜻蜓行為，下一代蜻蜓的步長和位置計算如下：

ΔXt+1=(sSi+aAi+cCi+fFi+eEi)+wΔXt

(6)

Xt+1=Xt+ΔXt+1

(7)

式(6)和(7)中t表示當前迭代次數；i表示第i個蜻蜓個體；Xt表示當前第t代種群個體位置；ΔXt+1表示下一代種群位置更新步長；Xt+1表示下一代種群個體位置；s表示分離度權重；a表示對齊度權重；c表示內聚度權重；f表示食物因子；e表示天敵因子；w表示慣性權重。

每個蜻蜓處于半徑為r的圓的圓心，當兩個蜻蜓之間的歐氏距離小于r時，則認為兩者相鄰，同時為了加快算法的收斂速度，半徑r隨著迭代次數的增加而線性增加，直至整個群體全部相鄰。

在多目標蜻蜓算法中，MIRJALILI S采用在群體智能算法中廣泛使用的外部檔案來存儲優化過程中得到的非劣解，并使用Coello提出的自適應網格法和輪盤賭法為蜻蜓個體從外部檔案中選擇食物源位置和天敵位置。

2 改進的多目標蜻蜓算法

為提高多目標蜻蜓優化算法的性能以更好地解決多目標優化問題，提出以下改進策略。

2.1 混合變異

COELLO C A C將變異算子[6]應用到多目標粒子群優化算法中，提高了算法的探索能力。在此基礎上，為提高MODA算法種群的多樣性，避免陷入局部最優，在算法中加入變異操作。由于均勻變異容易引起退化現象，本文采用一種基于隨機平均變異和高斯變異的混合變異算子，被選中個體的變異方法計算如下：

(8)

(9)

(10)

(11)

xt,d為個體變異前的位置；xmax,d為個體在第d維上的最大取值；xmin,d為個體在第d維上的最小取值；m為變異幅度，具體計算如下：

m=Pt(xmax,d-xmin,d)

(12)

(13)

Pt為第t次迭代的變異概率，T為最大迭代次數，η為變異速率因子，控制變異概率降低的速度。在算法初期，較大的變異概率使種群多樣性更高，有助于找到更多的非劣解，算法后期，較小的值有利于算法的收斂。將變異概率作用于變異幅度，使變異幅度隨著迭代次數的增大而減少，在算法前期能夠在整個搜索空間進行尋優，后期較小的變異幅度是為了保證算法在迭代后期的開發能力。

2.2 基于擁擠距離的外部檔案動態維護策略

DEB K等人[7]在NSGA-II算法中采用擁擠距離對非支配解進行密度估計,實驗結果證明該方法能使非支配解集保持較好的分布性。但是，該方法很可能因為一次性剔除很多密集區域的個體而導致Pareto前沿出現部分斷截。為此，本文采用一種基于擁擠距離的外部檔案動態維護策略，以保持Pareto解集的多樣性。

首先將所有最優解分別按照目標函數值從小到大進行排序，第k個目標維度上最優解x的排序號的位置信息表示為P(x,k)，與該最優解對應的目標函數值表示為fP(x,k)，由擁擠距離定義[7]可知，當第k個目標維度上位置信息為P(x,k)的最優解被刪除時，在第k個目標維度上只會影響位置信息為P(x,k)+1和P(x,k)-1的兩個最優解的擁擠距離分量，所以只需要重新計算相鄰的兩個受到影響的最優解在第k個目標維度上的擁擠距離分量，即：

IP(x,k)-1=|fP(x,k)+1-fP(x,k)-2|

(14)

IP(x,k)+1=|fP(x,k)+2-fP(x,k)-1|

(15)

其中IP(x,k)為第k個目標維度上位置信息為P(x,k)的最優解的擁擠距離分量。在動態維護過程中,每次只刪除擁擠距離最小的一個最優解,并根據被刪除最優解的位置信息找出在各目標維度上受影響的最優解；按式(14)和(15)重新計算受影響的最優解的擁擠距離分量,更新其擁擠距離,進而再基于新的擁擠距離對Pareto最優集進行維護,從而避免一次性刪除很多密集區域的個體，這樣不斷循環至Pareto最優解規模達到外部檔案最大容量。

2.3 IMODA算法步驟

IMODA算法步驟如下：

(1)初始化參數，隨機產生種群初始位置和初始速度，設定外部檔案最大容量、最大迭代次數、半徑以及各權重初始值。

(2)計算種群中各蜻蜓個體的目標函數值。

(3)選擇所有可行解，基于Pareto支配關系構造當前的Pareto最優解集，并加入外部檔案中。

(4)判斷外部檔案大小是否超過最大容量，如果是，則按照本文提出的基于擁擠距離的外部檔案動態維護策略剔除多余值；否則，執行下一步。

(5)從外部檔案中選擇食物源位置、天敵位置，并更新各權重因子和半徑參數。

(6)根據式(6)和式(7)以及本文提出的混合變異操作更新群體位置。

(7)終止條件判定：如果為達到最大迭代次數，迭代次數加1，并轉至(2)；否則執行下一步。

(8)輸出外部檔案中所有解。

3 實驗與分析

3.1 測試函數及參數選擇

圖1 MOPSO算法在MOP1和MOP2上的Pareto解

為了準確驗證改進后算法的性能，將本文算法與基本多目標粒子群和基本多目標蜻蜓算法進行對比分析。實驗選擇在多目標優化問題中廣泛使用的基準函數MOP1和MOP2進行測試分析。為了定量比較算法之間性能的差異，選擇世代距離(GD)、覆蓋率(MS)、分布均勻度量(SP)三種指標，以準確全面地反映算法的收斂性和多樣性。使用的基準測試函數具體表達式如下：

MOP1:

(16)

MOP2:

(17)

在相同硬件條件下，采用三種優化算法對測試函數分別獨立運行30次。三種優化算法在測試函數上的GD、SP和MS指標均值和標準差如表1所示。三種算法的種群個數均為100，外部檔案最大容量為100,最大迭代次數為500。

表1 3種算法測試結果對比

3.2 結果及分析

圖1～圖3為三種算法在MOP1和MOP2上的Pareto解。由圖2和圖3可以看出MODA和改進的MODA都能完全覆蓋Pareto前沿，但MODA的解的分布性較差，改進后的MODA的解分布較均勻。從表1中的數據也可以看出，改進的MODA算法的解具有更好的收斂性和分布性，性能表現也較為穩定。表明引入混合變異操作和基于擁擠距離的動態外部檔案維護策略能有效改善MODA算法的性能。

4 結論

本文提出了一種改進的多目標蜻蜓優化算法，該算法通過加入混合變異算子，以避免算法陷入局部最優；采用一種基于擁擠距離的動態檔案維護策略，提高了Pareto前沿的分布性。最后，通過對多目標基準函數的測試，驗證了本文提出的改進的多目標蜻蜓算法能夠獲得具有更好多樣性、分布性的Pareto前沿。下一步將利用更多、更復雜的多目標基準測試函數以及一些工程實踐中的多目標優化問題較全面地檢驗IMODA的性能。

圖2 MODA算法在MOP1和MOP2上的Pareto解

圖3 IMODA算法在MOP1和MOP2上的Pareto解

[1] DEB K, SINDHYA K, HAKANEN J. Multi-objective optimization[M].Decision Sciences: Theory and Practice. CRC Press, 2016.

[2] MIRJALILI S. Dragonfly algorithm: a new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems[J]. Neural Computing and Applications, 2016, 27(4): 1053-1073 .

[3] 傅軍棟，陳俐，康水華. 基于蜻蜓算法和支持向量機的變壓器故障診斷[J]. 華東交通大學學報，2016,33(4)：103-112.

[4] SAMBANDAM R K, JAYARAMAN S. Self-adaptive dragonfly based optimal thresholding for multilevel segmentation of digital images[J]. Journal of King Saud University-Computer and Information Sciences, 2016 23(6):123-132.

[5] Peng Guang, Fang Yangwang, Chai Dong, et al. Multi-objective particle swarm optimization algorithm based on sharing-learning and Cauchy mutation[C].Control Conference(CCC), 2016 35th Chinese. IEEE, 2016.

[6] COELLO C A C, PULIDO G T, LECHUGA M S. Handling multiple objectives with particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(3):256-279.

[7] DEB K, AGRAWAL S, PRATAP A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II[C].International Conference on Parallel Problem Solving From Nature. Springer Berlin Heidelberg, 2000: 849-858.

Improved multi-objective dragonfly optimization algorithm

Han Peng, Chen Feng

(Department of Automation, University of Science and Technology of China, Hefei 230000, China)

An improved multi-objective dragonfly optimization algorithm was proposed in this paper. A hybrid mutation operator was introduced to increase the diversity of the population and avoid the premature phenomenon. A strategy based on crowding distance strategy was used to maintain the external file dynamic, so as to obtain Pareto optimal solution set with better distribution. Finally, by multi-objective benchmark functions, it is compared with the basic multi-objective dragonfly algorithm and the multi-objective particle swarm optimization algorithm, and it turned out that the improved multi-objective dragonfly optimization algorithm improves the convergence and distribution of the Pareto optimal solution set.

multi-objective optimization; dragonfly algorithm; diversity; distribution

TP181

A

10.19358/j.issn.1674- 7720.2017.20.008

韓鵬，陳鋒.一種改進的多目標蜻蜓優化算法[J].微型機與應用，2017,36(20)：27-29,33.

2017-03-30)

韓鵬(1992-)，男，碩士研究生，主要研究方向：群智能理論。

陳鋒(1966-)，男，博士，副教授，主要研究方向：人工智能、智能交通。