【精彩文章推薦】東北大學 李飛等:基於分解和差分進化的多目標粒子群優化算法


點擊上方“控製與決策” 可以訂閱哦!


進入《控製與決策》公眾號首頁,點擊下方“微專欄”,可分類查閱曆史好文。

 

本文引用信息


李飛, 劉建昌, 石懷濤, 傅梓瑛. 基於分解和差分進化的多目標粒子群優化算法[J]. 控製與決策, 2017, 32(3): 403-410.

LI Fei, LIU Jianchang, SHI Huaitao, FU Ziying. Multi-objective particle swarm optimization algorithm based on decomposition and differential evolution[J]. Control and Decision, 2017, 32(3): 403-410.

DOI: 10.13195/j.kzyjc.2016.0186


 

基於分解和差分進化的多目標粒子群優化算法

李飛, 劉建昌, 石懷濤, 傅梓瑛

1研究背景

最優化問題是工程實踐和科學研究中主要的問題形式之一。其中如果需要同時處理的目標優化問題數目超過一個,且目標之間相互衝突的問題則被稱為多目標優化問題。多目標優化問題無處不在,如複雜係統的設計、規劃和建模,生產調度問題以及控製問題等都是典型的多目標優化問題。人們希望能夠在可行域內盡可能使每個目標都達到最優。一般來說,其中一個目標的改善往往會降低另外一個或其它多個目標的性能。因此,多目標優化問題沒有單個最優解, 而是多個最優解構成的最優解集(Pareto解集)。進化算法具有較好的全局搜索能力,且具備一次運行可以得到多個解的特性,因此進化多目標算法已被廣泛應用於解決多目標優化問題。

粒子群優化算法(PSO)是根據鳥群飛行覓食行為而提出的一種群智能優化算法。研究者發現鳥群在飛行過程中經常會突然改變方向,散開,聚集,其行為不可預測,但整體總保持一致性,個體與個體之間也保持著最適宜的距離。這是因為生物群體中存在著一種社會信息共享機製。PSO中每個粒子即為空間中的一個解,根據自己和整個群體在飛行過程中的最好位置,不斷更新自己的飛行速度與位置。由優化問題決定的適應函數值來評價粒子位置的優劣,每個粒子都將追隨當前最優粒子在解空間搜索。PSO結構簡單,收斂速度快,已被成功應用於求解單目標優化問題,是適合解決多目標優化問題的方法之一。

將多目標優化問題轉換為單目標優化問題是一種用線性規劃方法求解多目標優化問題的基本策略,將這種傳統的多目標求解策略與進化算法相結合構造了一種新穎的基於分解的多目標進化算法(MOEA/D),該算法自提出以來就引起了研究學者們的廣泛關注。MOEA/D主要將多目標優化問題分解為多個單目標優化問題協同求解,相對典型的基於Pareto支配關係的多目標優化算法NSGA-IISPEA-2有較低的計算複雜度。

2問題提出

因為PSO實現簡單並且收斂速度快,所以被廣泛地應用於求解單目標優化問題,而當粒子群優化算法從單目標問題擴展到多目標問題時,Pareto最優解集的存儲與維護、全局最優和個體最優的選擇以及收斂性和多樣性的平衡等問題亦隨之出現,因此PSO不能直接用於多目標優化問題的求解。要將PSO應用於求解多目標優化問題時,要選擇合適的全局最優和個體最優,使算法有合適的選擇壓力;並且要采用合適的檔案維護策略對Pareto 最優解集的進行存儲與修剪;同時要平衡種群的勘探和開發的能力。

dMOPSO算法使用PSO代替MOEA/D中的進化算法,並通過分解方法更新外部存檔和向導粒子,若個體最優粒子經過一定的代數沒有更新,則采用高斯分布重新初始化粒子,協助粒子跳出局部最優。然而該算法對於複雜的Pareto最優前沿,僅依靠分解策略,最終得到的解很難準確均勻的覆蓋完整的Pareto 最優前沿。為了提高dMOPSO算法的收斂性和多樣性,提出了一種基於分解和差分進化的多目標粒子群優化算法(dMOPSO-DE)

3dMOPSO-DE算法設計

在所提出的dMOPSO-DE算法中,首次提出了方向角的概念,通過方向角產生一組均勻分布的方向向量引導粒子飛行,然後通過分解策略和差分進化算法(DE)更新種群的全局最優粒子,並采用粒子重置策略維護種群多樣性

3.1均勻分布方向向量產生策略

均勻分布的方向向量可以引導算法產生均勻分布的解。本文首先生成均勻分布的方向向量,再通過此方向向量產生一組權重向量,實現解的均勻分布。但是要產生一組均勻分布的方向向量並不是那麼容易,本文提出方向角的概念,在此基礎上產生一組均勻分布的方向向量。

首先在1/4的超球麵上隨機產生n個點,然後計算每個點與其他點的位置關係,刪除位置最差的點,最後在超球麵上重新隨機產生一個點,重新計算每個點與其他點的位置關係,刪除位置最差的點,循環10000次就可以得到均勻分布的n個點,即可得到n個均勻分布的方向向量。

3.2全局最優粒子選擇

PSO算法中所有粒子都會跟隨全局最優粒子移動,全局最優粒子無論是從種群中隨機選取一個個體還是采取其它策略選取(如擁擠距離,網格)等,得到的全局最優粒子仍在局部Pareto最優前沿上。為了避免這種情況,dMOPSO-DE算法在分解策略的基礎上引入DE變異算子產生全局最優粒子。這種機製產生的全局最優粒子跳出局部Pareto前沿的可能性增大,因此能夠引導種群粒子跳出局部Pareto前沿。

其執行過程首先將新的種群與原種群合並,然後對於每個權重向量在合並後的種群中選擇分解函數值最小的一個個體,將這些個體合並成新的種群,最後采用DE操作產生全局最優粒子,選擇該粒子作為全局最優粒子。

3.3粒子重置策略

為了增加種群的多樣性,dMOPSO-DE采用了粒子的重置策略。當粒子的聚合函數值在一定的代數內一直好於新的粒子,即產生的新解的性能多次沒有更新,粒子可能陷入局部最優解,此時,可以通過高斯學習策略重置該粒子的位置。采用這種策略不僅讓粒子向優秀的個體學習,而且可以在優秀粒子陷入局部最優的時候,提高種群的勘探能力並避免在差的方向浪費時間。

3.4dMOPSO-DE算法整體流程

dMOPSO-DE算法首先初始化種群並通過均勻化方向角產生均勻化方向向量,然後采用粒子重置策略或者最基本的速度和位置更新公式更新種群信息,選取個體最優向導和全局最優向導,最後通過隱式精英保持策略,更新種群信息。

4