多目標(biāo)優(yōu)化算法改進綜述

謝秋紅

(陸軍特種作戰(zhàn)學(xué)院，廣東 廣州 510000)

一、引言

在工程和科學(xué)上的許多問題都可以抽象為多目標(biāo)優(yōu)化問題，比如廢水處理工藝、水的分配系統(tǒng)和空氣動力學(xué)設(shè)計問題等，這些問題需要同時滿足多個目標(biāo)。為了解決多目標(biāo)優(yōu)化問題，多目標(biāo)進化算法(Multi-objective Evolutionary Algorithms，MOEAs)應(yīng)運而生。1975年，Holland教授提出了遺傳算法。Schaffer于1985年首次將多目標(biāo)優(yōu)化算法與遺傳算法結(jié)合，提出向量評估遺傳算法。1989年，Goldberg使用Pareto理論解決多目標(biāo)優(yōu)化問題，從此，多目標(biāo)優(yōu)化算法研究成為熱門研究方向。常見的算法包括：非支配排序遺傳算法(NSGA和NSGA-II) 、多目標(biāo)優(yōu)化粒子群算法(MOPSO)、帕累托強度進化算法(SPEA和SPEA2)等等。其中，MOPSO算法收斂速度快、容易實現(xiàn)、低計算代價，容易覆蓋基準(zhǔn)函數(shù)的帕累托陣面。但是MOPSO存在兩個問題：如何更新gbest和pbest；如何快速收斂到最優(yōu)解的帕累托陣面。下面從傳統(tǒng)算法和最新研究兩個角度梳理多目標(biāo)優(yōu)化算法。

二、多目標(biāo)優(yōu)化算法近幾年改進成果

對多目標(biāo)優(yōu)化算法近幾年的改進算法進行梳理，并進行簡單的介紹和述評。

（一）適應(yīng)性AMPSO算法

文獻[1]新提出一種適應(yīng)性的多目標(biāo)優(yōu)化算法(AdaptiveMultiobject ivePSO，AMPSO)。該算法的工作集中在兩點：基于解空間分布熵提出一種適應(yīng)性的gbest搜索機制；基于種群間距信息(SP)提出一種適應(yīng)性的飛行參數(shù)機制來平衡全局搜索和粒子的局部搜索能力。在這兩點的改造下，算法不僅具有了較高的精度，而且搜索出的最優(yōu)解有很好的多樣性。

（二）自適應(yīng)梯度AGMOPSO算法

文獻[2]提出一種自適應(yīng)梯度的多目標(biāo)粒子群優(yōu)化（AGMOPSO）算法、基于多目標(biāo)梯度(stocktickerMOG)方法和自適應(yīng)參數(shù)的機制，提高了計算性能。算法中，多目標(biāo)梯度方法用來更新檔案提高了算法的收斂速度和進化過程中的局部查找。同時，根據(jù)粒子的多樣性信息建立了飛行參數(shù)的自適應(yīng)機制，用來平衡算法的收斂性和多樣性，可以找到更好的傳播解決方案。多目標(biāo)梯度法和自適應(yīng)飛行參數(shù)的機制使得算法的解決方案有更好的多樣性，具有更快的收斂到真正的帕累托最優(yōu)前沿。此外，作者討論了AGMOPSO任何成功應(yīng)用的前提條件。最后，該算法與其他的多目標(biāo)粒子群優(yōu)化算法和兩個國家的最先進的多目標(biāo)算法的比較來驗證計算性能。

（三）存儲導(dǎo)向的MOPS算法

文獻[3]提出了一種新的外部檔案引導(dǎo)MOPSO算法(AgMOPSO)，其中用于速度更新的領(lǐng)袖是從外部存檔中選擇。群體領(lǐng)袖pbest和gbest的選擇多目標(biāo)粒子群優(yōu)化算法的設(shè)計是很重要的。這些領(lǐng)袖有望有效地引導(dǎo)蜂群接近真正的帕累托最優(yōu)前沿。本文創(chuàng)新點體現(xiàn)在三個方面：(1)作者通過分解方法將多目標(biāo)優(yōu)化問題（MOPS）轉(zhuǎn)化為一系列子問題，每個粒子是由三個從外部存檔選擇的領(lǐng)袖決定，轉(zhuǎn)化為相應(yīng)的優(yōu)化子問題；(2)作者在外部存檔上運行基于免疫的進化策略，因為領(lǐng)袖都選取自外部存檔，使用克隆選擇范式有助于加速收斂。因此，在外部存檔中對個體進行改進，將有助于指導(dǎo)基于粒子群算法的搜索，從而為真實的遺傳算法提供快速逼近；(3)新的pbest和gbest的更新方式。一般來說，個體極值、局部最好并進行分別訪問每個粒子、當(dāng)?shù)厝骸⒄麄€群。然而在AgMOPSO算法中，作為分解的方法是利用變換將MOPs轉(zhuǎn)化為一組子問題，同時優(yōu)化各子問題，加快AgMOPSO收斂。

（四）多目標(biāo)大規(guī)模MPSO算法

文獻[3，4]設(shè)計了新的多目標(biāo)大規(guī)模優(yōu)化粒子群算法(Many-objective large-scale optimization problems，MaOLSOPs)。根據(jù)分布式并行計算的特點將現(xiàn)有研究成果分為三類：多目標(biāo)大規(guī)模優(yōu)化、多目標(biāo)優(yōu)化和分布式并行，并研究粒子群的并行屬性。算法步驟為：首先根據(jù)目標(biāo)將種群分為M+1個，多出的一個為針對所有目標(biāo)的種群；將種群中多個變量進行拆分分組，稱為類別；最后，類別中的多個個體可以進一步分解為多個集合，每個集合對應(yīng)一個單獨的計算資源。作者設(shè)計了并行框架，但沒有給出具體的實驗。

（五）大規(guī)模并行加速MPSO算法

文獻[5]針對具體的并行加速計算，提出一種基于異構(gòu)多核和GPU加速的粒子群法。具體是用英特爾的矢量協(xié)加速器(Intel Xeon Phicoprocessors)和圖形處理單元(Graphics Processing Units，GPUs)，而異構(gòu)的方法能減輕粒子群算法的時間復(fù)雜度。作者在定義的并行可分為函數(shù)層面、算法層面。在函數(shù)層面，復(fù)合函數(shù)可通過矩陣乘法并行操作，但是由于大量的條件限制，無法進行進一步并行優(yōu)化。但是復(fù)合函數(shù)的Weierstrass分量需要一定數(shù)量的計算資源，因此這部分可并行。CUDA提供了線性代數(shù)的工具包—— CUDA基本線性代數(shù)子程序，實現(xiàn)了用于GPU優(yōu)化的BLAS程序，因此可方便進行并行的矩陣乘法計算；在算法層面，PSO本身就是一個時間密集型任務(wù)，而APSO中定義的距離參數(shù)可通過距離矩陣的計算獲得。作者將矩陣拆分為多個子矩陣進行分別計算，每個子矩陣又交給多個線程并行計算。

（六）基于幾何結(jié)構(gòu)的MPSO算法

文獻[6]新提出一種基于幾何結(jié)構(gòu)的粒子群算法，具有快速搜索和魯棒性的特點，適用三個目標(biāo)以上的多目標(biāo)優(yōu)化問題。目標(biāo)問題之間的三種關(guān)聯(lián)關(guān)系：正相關(guān)、負(fù)相關(guān)、不相關(guān)?；诖?，作者進行了三個以上目標(biāo)的維度縮減操作。理想情況下，同一個簇內(nèi)的目標(biāo)是正相關(guān)的，但在目標(biāo)函數(shù)較多的情況下，很容易發(fā)生負(fù)相關(guān)情況。因此，提出一種模糊語義的方法進行簇調(diào)整，設(shè)置閾值決定關(guān)聯(lián)是否可以接受。

測試算法的兩種方法。(1)給定最大迭代次數(shù)，不限定精度地運行待測試算法，當(dāng)達到最大迭代次數(shù)時算法終止，比較測試函數(shù)運算結(jié)果。(2)給定最大迭代次數(shù)和精度，運行待測試算法，當(dāng)達到最大迭代次數(shù)或最優(yōu)值滿足所給定的精度時算法終止，比較各算法所需平均迭代次數(shù)。

三、總結(jié)

多目標(biāo)優(yōu)化算法的優(yōu)勢和局限可以通過評價方法進行評估，部分算法沿用了將多目標(biāo)優(yōu)化轉(zhuǎn)換為小目標(biāo)優(yōu)化問題的思想，并在收斂速度、計算性能、計算精度等其它方面進行改進，其中自適應(yīng)梯度AGMOPSO算法和存儲導(dǎo)向的MOPS算法加快了收斂速度，適應(yīng)性AMPSO算法提高了計算精度，并增加了最優(yōu)解的多樣性，大規(guī)模并行加速MPSO算法減輕了算法的時間復(fù)雜度。