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

謝秋紅

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

一、引言

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

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

對(duì)多目標(biāo)優(yōu)化算法近幾年的改進(jìn)算法進(jìn)行梳理，并進(jìn)行簡(jiǎn)單的介紹和述評(píng)。

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

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

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

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

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

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

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

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

（五）大規(guī)模并行加速M(fèi)PSO算法

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

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

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

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

三、總結(jié)

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