基于 Pareto 熵的多目標粒子群優化算法

發布時間：2022-01-23所屬分類：科技論文瀏覽：1次

摘 要： 摘 要: 粒子群優化算法因形式簡潔、收斂快速和參數調節機制靈活等優點,同時一次運行可得到多個解,且能逼近非凸或不連續的 Pareto 最優前端,因而被認為是求解多目標優化問題最具潛力的方法之一.但當粒子群優化算法從單目標問題擴展到多目標問題時,Pareto 最優解集的存儲

　　摘 要: 粒子群優化算法因形式簡潔、收斂快速和參數調節機制靈活等優點,同時一次運行可得到多個解,且能逼近非凸或不連續的 Pareto 最優前端,因而被認為是求解多目標優化問題最具潛力的方法之一.但當粒子群優化算法從單目標問題擴展到多目標問題時,Pareto 最優解集的存儲與維護、全局和個體最優解的選擇以及開發與開采的平衡等問題亦隨之出現.通過目標空間變換方法,采用 Pareto 前端在被稱為平行格坐標系統的新目標空間中的分布熵及差熵評估種群的多樣性及進化狀態,并以此為反饋信息來設計進化策略,使得算法能夠兼顧近似 Pareto 前端的收斂性和多樣性.同時,引入格占優和格距離密度的概念來評估 Pareto 最優解的個體環境適應度,以此建立外部檔案更新方法和全局最優解選擇機制,最終形成了基于 Pareto 熵的多目標粒子群優化算法.實驗結果表明:在 IGD 性能指標上,與另外 8 種對等算法相比,該算法在由 ZDT 和 DTLZ 系列組成的 12 個多目標測試問題集中表現出了顯著的性能優勢.

　　關鍵詞: 多目標優化問題;粒子群優化;平行格坐標系統;Pareto 熵;自適應參數

　　大多數工程和科學問題都可以歸結為多目標優化問題(multiobjective optimization problem,簡稱 MOP),其求解方法一直都是學術界和工程界共同關注的焦點.多目標優化問題通常存在多個彼此沖突的目標,其優化結果為 Pareto 最優解集.與數學規劃方法相比,進化算法因一次運行可得到多個解,且能逼近非凸或不連續的 Pareto 最優前端,從而被認為是更適合求解多目標優化問題的智能方法.

　　粒子群優化算法(particle swarm optimization,簡稱 PSO)[1]是由 Kennedy 和 Eberhart 在 1995 年提出的仿生算法,它是受到飛鳥集群活動規律的啟發,根據社會學和心理學而建立的群體智能模型.粒子群優化算法是一種具有形式簡潔、收斂快速和參數調節機制靈活等優點的進化算法,并且已經成功應用于單目標優化問題,被認為是求解多目標優化問題最具潛力的方法之一.但當粒子群優化算法從單目標問題擴展到多目標問題而形成多目標粒子群優化(multiple objective particle swarm optimization,簡稱 MOPSO)時,新的技術問題隨之出現.多目標優化問題的 Pareto 最優解集特征和粒子群優化算法的快速收斂特征,使得多目標粒子群優化算法面臨以下技術挑戰:① 維護存儲 Pareto最優解集的檔案,使算法最終輸出的 Pareto前端能夠兼顧收斂性和多樣性,這是第二代進化多目標算法的共性問題;② 從群體和個體的 Pareto 最優解集中分別選舉全局最優解(gBest)和個體最優 解 (pBest),使這兩個最優解引導粒子盡最大可能地發現高質量的新解 ;③ 平衡進化過程中的開采 (exploration)和開發(exploitation),使得種群既保持快速收斂的優點,但又盡可能地避免陷入局部 Pareto 前端或者收斂到單一解.后面兩個挑戰是多目標粒子群優化算法區別于其他多目標進化算法的特有問題.

　　本文將根據多目標優化問題和粒子群優化算法的特征,采用近似 Pareto 前端的分布熵及其變化來估計種群進化狀態,并依據這些進化過程反饋信息設計具有動態平衡開采和開發能力的進化策略,形成基于 Pareto 熵的多目標粒子群優化算法.

　　為了內容相對獨立以及統一本文術語和符號,本文第 1 節簡要介紹多目標優化問題和粒子群優化算法的基本概念.第 2 節綜述與本文內容相關的多目標粒子群優化算法的研究現狀和存在的問題.第 3 節闡述 Pareto 熵的計算方法以及基于 Pareto 熵的種群進化狀態檢測方法.第 4 節描述本文算法的主要進化策略和完整的算法流程.第 5 節分析對比實驗結果.最后,在第 6 節中給出全文結論.

　　2 相關研究工作

　　自 Coello 等人[2]于 2002 年提出采用粒子群算法來求解多目標優化問題以來,多目標進化領域中的成功經驗被迅速借鑒到多目標粒子群優化算法中,出現了大量的階段性研究成果,其中以 Coello 等人[3]采用超網格和變異方法的多目標粒子群優化算法最為經典.Reyes-Sierra[4]對 2006 年之前的多目標粒子群優化算法做了綜述總結,隨后,Padhye[5,6]做了一些專題比較研究.關于多目標進化算法的最新綜述可參見文獻[7,8].

　　對多目標粒子群優化算法的研究主要集中檔案維護、全局最優解選擇和種群多樣性增加等方面,也有少部分工作對個體最優解選擇和粒子變異方面進行了研究.

　　在外部檔案維護策略方面,主要借鑒多目標遺傳算法中檔案維護的有效策略,如采用聚類、擁擠距離 (crowding distance)、自適應超網格(adaptive grid)、-占優(-dominance)、最大化最小適應度(maximin fitness)、值等形成相應的多目標粒子群優化算法中的檔案維護策略[9,10].這些不同的策略都是直接或間接地評估檔案中每個個體的密度(擁擠度)或者占優強度.當檔案中的 Pareto 最優解個數超出容量限制時,通常直接將個體適應度較好的新解來更新個體適應度較差的舊解,從而使得 Pareto 前端具有更好的分布性能.

　　在全局最優解選擇策略方面,基于隨機選擇、值、擁擠距離、動態鄰居、自適應超網格、聚類、占優樹、非占優排序(non-dominated sorting)、Pareto 占優、超體積(hyper-volume)、最大化最小適應度、小生境(niche)、綜合學習(comprehensive learning)等策略多目標粒子群優化算法被相繼提出來[912].在這些方法中,大多數通過評估外部檔案中的個體密度來選擇那些處于相對稀疏區域的 Pareto 最優解作為全局最優解以降低選擇壓力, 避免收斂到單一解,以及增加 Pareto 前端的多樣性;而另一部分基于“占優”概念的最優解選擇策略則偏重算法的收斂性能,但容易導致過高的選擇壓力而容易收斂到局部極值.

　　在個體最優解選擇策略方面,雖然絕大部分算法為了降低計算開銷而僅保留一個 Pareto 最優解,但僅一個個體最優解不足以描述個體 Pareto 最優前端.Branke[13]和 Abido[14]分別研究了采用個體外部檔案保存個體 Pareto 最優解的方法(類似種群外部檔案保存種群 Pareto 最優解),獲得了比單一個體 Pareto 最優解更好的性能. 另外,最大化最小個體間距離和加權和[13]等策略被用來作為選擇個體最優解的標準.

　　在平衡開發與開采策略方面,如果不合理利用粒子群算法快速收斂的優點,則容易導致早熟而陷入局部極值.一些算法從種群角度提出平衡策略,如動態調整種群大小策略[15]和子群策略[1618];一些算法采用文化進化框架提出平衡策略[19,20];一些算法從粒子運動參數選擇角度提出平衡策略,如線性下降慣性權重參數和自適應參數等[21];一些算法從粒子擾動(變異)角度提出平衡策略,自 Coello[3]在多目標粒子群算法中提出變異方法后, 后續多目標粒子群優化算法幾乎都采用變異方法來增強種群多樣性;還有一些算法采用混合平衡策略[22,23].

　　但是,多目標粒子群優化算法仍然面臨一些技術挑戰: 

　　一方面,個體適應度評估決定了多目標粒子群優化算法中選擇全局最優解和維護檔案這兩個關鍵策略.但當前的個體適應度都是單一度量標準,要么是基于密度的評估來考察個體的多樣性潛力,要么是基于 Pareto 占優關系的評估來考察個體的收斂性潛力.因而導致在維護外部檔案時不能兼顧 Pareto 最優前端的多樣性和收斂性,而在選擇全局最優解時不能兼顧平衡開發和開采. 

　　另一方面,全局最優解頻繁更換和快速收斂特征,使得開發與開采的平衡問題在多目標粒子群優化算法中更為突出:過度地開發將會導致收斂性不足而影響優化精度,而過度地開采將會導致多樣性匱乏而陷入局部極值.雖然已經存在自適應單目標粒子群優化算法[24],但多目標問題的 Pareto 最優解集特征,使得在多目標空間中監測種群進化環境更為復雜.而當前已經存在的多目標粒子群優化算法缺乏種群進化環境的動態監測機制來獲取反饋信息,難以決定算法“在何時調節何種進化策略到何種程度”.

　　熵在熱力學中表示系統混亂狀態,而在生態學中表示生物的多樣性.本文將通過對目標空間變換來獲得 Pareto 前端的熵,以此來度量多目標粒子群優化算法中種群的多樣性,并利用差熵來估計種群的進化狀態,從而為算法提供實時的進化環境反饋信息.同時,在變換后的目標空間中評估 Pareto 最優解的個體密度和格占優強度,為算法中外部檔案更新和全局最優解選擇提供決策依據.

　　3 Pareto 熵及進化狀態檢測

　　本節先介紹 Pareto 熵的計算方法,包括將采用平行格坐標系統映射目標空間映射的方法和 Pareto 熵及差熵的定義;然后,根據外部檔案更新算法中 Pareto 熵的變化情況,分析不同進化狀態的臨界閾值;最后,歸納出種群進化狀態的判定條件.

　　3.1 平行格坐標系統

　　平行坐標(parallel coordinates)[25]是一種廣泛使用的多維數據分析和可視化方法.多目標優化問題的目標向量正是一種多維數據(在進化多目標優化計算社區中,通常將 2~3 個目標的優化問題稱為 multi-objective optimization problem,簡稱 MOP,而將 4 個以上目標的優化問題稱為 many-objective optimization problem,簡稱 MaOP).受這一方法啟發,將存儲在外部檔案中的多維 Pareto 前端按照平行坐標方式轉化到二維平面中,并將 Pareto 前端的笛卡爾坐標值映射成整數值坐標,從而多維 Pareto 前端被轉換成一張二維平面網格.對應于笛卡爾坐標系統,在此將這種二維平面網格稱為平行格坐標系統(parallel cell coordinates system,簡稱 PCCS).下面采用采用數學形式來描述這種映射方法.

　　3.2 Pareto熵及其差熵

　　熵是一種度量微觀分布均勻性的方法.在熱力學中,熵表示系統混亂狀態,而在生態學中熵表示物種的多樣性.當存儲在外部檔案中的近似 Pareto 前端被映射到 PCCS 后,可以采用熵來度量近似 Pareto 前端的分布均勻性,間接地表達當前種群的多樣性特征.如果近似 Pareto 前端發生變化,則會引起 PCCS 中的對應的格坐標分量重新分布,從而引起熵發生變化.因此,可以采用差熵來表示近似 Pareto 前端在相鄰迭代時刻的熵的變化大小: 

　　差熵越大,意味著近似 Pareto 前端重新分布的范圍越大,這可能由于:① 算法生成的新解占優了大量的舊解而引起 Pareto 前端發生大范圍變化;② 新解引起了 max mf 或者 min mf 發生變化而導致第 k 列上的格坐標分量重新分布. 

　　相反,差熵越小,近似Pareto前端重新分布的范圍越小,這是因為在外部檔案維護過程中,質量更好(如個體密度較小)的新解替換了質量較差(個體密度較大)的舊解而引起個別格坐標分量的重新分布. 從而,通過差熵可以推測當前種群的發現新解的潛力,進而估計種群所處的進化狀態,如收斂狀態、多樣化狀態和停滯狀態.這種進化狀態是設計開發和開采進化策略的依據. 由于采用熵來度量近似 Pareto 前端的分布特征,間接地評估對應的 Pareto 最優解集的性能.本文為了強調在 PCCS 中這種分布熵評估的對象是近似 Pareto 最優解集所對應的近似 Pareto 前端,故將其稱為 Pareto 熵.

　　Pareto 熵及其差熵在進化過程中的變化趨勢與待優化多目標問題的性質和優化算法的求解能力緊密相關. 對于單模態多目標優化問題,在進化過程的前期,優化算法通過發現的新解占優較多的舊解而推動種群向真實 Pareto 前端方向收斂,從而引起 Pareto 熵及其差熵發生較大變化;而在進化過程的后期,當種群逼近真實 Pareto 前端后,算法發現的新解只能占優其鄰近的個別舊解,或者替換個別適應度較差(如個體密度較大)的舊解,僅能引起 Pareto 熵及其差熵發生很小的變化.但對于多模態多目標優化問題,當優化算法發現的新解跳出局部極值時,新解將會占優處于局部 Pareto 前端上的大量舊解,從而引起 Pareto 熵及其差熵發生急劇變化,直到種群重新聚集在新的局部 Pareto 前端附近為止.根據這一特點,利用 Pareto 熵及其差熵可以識別待優化問題的模態性質和估計種群所處的進化狀態,從而動態地調整優化算法的進化策略.

　　為了說明 Pareto熵及差熵在不同模態下的變化特征,圖 2給出了本文算法(詳細內容見第4節)采集的 Pareto 熵及差熵變化曲線.其中,存儲 Pareto 最優解集的外部檔案的最大容量設定為 100.圖 2(a)是由具有 3 個目標的單模態測試問題 DTLZ2 產生的 Pareto 熵及差熵變化曲線,圖 2(b)是由具有 2 個目標的多模態測試問題 ZDT4 產生的 Pareto 熵及差熵變化曲線.在圖 2(a)中的進化前期階段(大約 Iteration<40,不同算法對同一優化問題可能會有不同的分界值),Pareto 熵及差熵發生較大幅度變化,表明算法產生的新解在不斷占優外部檔案中的舊解,導致近似 Pareto 前端發生大范圍變化;而在圖 2(a)中的進化后期階段(Iteration>40),Pareto 熵及差熵僅發生小幅度變化,表明近似 Pareto 前端只發生局部小范圍變化,算法產生的新解僅占優個別就解或替換個別質量較低的舊解. 對于單模態多目標優化問題,Pareto 熵及差熵在進化過程中只經歷了一個周期的劇烈變化.而在圖 2(b)中的進化前期階段(約 Iteration<100),Pareto 熵及差熵經歷了大約 8 個周期的較為明顯的劇烈變化,表明算法在前期階段產生的新解頻繁地跳出局部 Pareto 前端,反映了算法具有很好的發現高質量新解的能力.

　　需要特別指出的是,Pareto 熵及差熵的劇烈變化周期個數并不等同于局部 Pareto 前端的個數,因為一個高質量的新解有時可以跳過多個局部 Pareto 前端;同時,具有極端邊界值的新解有時可能引起 PCCS 的對應目標列中大量格坐標分量重新分布,而使 Pareto 熵及差熵產生一個劇烈變化周期.

　　3.3 進化狀態檢測

　　收斂速度和優化精度是基于概率尋優的進化算法的兩個相互沖突目標:過分強調收斂速度往往會引起算法早熟而陷入局部極值;相反,過分注重收斂精度將會增加大量的函數評估次數而使得算法復雜度急劇提高.因此,需要有效地設計開發與開采的平衡策略來控制進化算法的多樣性和收斂性.但在設計這種平衡策略之前,算法研究者需要回答“在何時采用何種策略到何種程度”的問題.然而在算法設計之前,通常缺乏對待優化問題的先驗知識,并且算法還需要兼顧不同類型的待優化問題.這要求具有平衡開發與開采能力的算法在迭代進化過程中能夠檢測算法自身所處狀態,如收斂狀態(convergence status)、多樣化狀態(diversity status)和停滯狀態 (stagnation status),然后根據不同進化狀態來動態調節進化策略,使得算法能夠適應不同特征的待優化問題,并在收斂速度和優化精度之間達到最佳平衡.

　　本質上,檢測進化狀態就是從種群所處的進化環境中獲得實時反饋信息,從而為控制進化過程提供決策依據,并形成“檢測調節檢測…”的閉環控制過程.由于多目標優化問題的優化結果不再是單一解,而是由一組非占優解構成的 Pareto 最優解集,因此,多目標優化問題比單目標優化問題具有更加復雜的進化環境,不能簡單地通過比較目標值的大小來判斷進化狀態,從而使具有自適應進化環境的多目標優化算法設計變得更加困難.有的多目標進化算法通過性能評估指標(如 hyper-volume)來評估進化環境,但這類綜合性度量指標難以反映進化迭代中的占優與多樣化過程細節.

　　通過上一小節的分析可知,Pareto 熵的變化是由于進化算法獲得的新解占優了 Pareto 前端上的舊解,或者替換了質量較差的舊解而引起的.在采用外部檔案存儲 Pareto 最優解集的多目標進化算法中,通常認為個體密度較大的 Pareto 解的質量較差,在外部檔案更新過程中,往往采用個體密度較小的 Pareto 新解替換個體密度較大的 Pareto 舊解,從而增強近似 Pareto 前端的多樣性,包括分布均勻性和延展性.因此,通過評估進化過程中的 Pareto 差熵可以推測進化迭代過程中的占優與多樣化細節,從而估計多目標進化算法所處的進化狀態,為動態調整進化策略提供反饋信息.但是劃分不同進化狀態的 Pareto 差熵的分界值是這種方法的關鍵因素,不合理的分界值會導致進化狀態的誤判,從而可能誘導進化算法采用相反的進化策略.在此,本小節將從理論上分析劃分進化狀態的 Pareto 差熵臨界閾值. ——論文作者：胡 旺 1,2, Gary G. YEN2 , 張 鑫 1