基于改進(jìn)人工蜂群算法的高維多目標(biāo)優(yōu)化

王艷嬌，肖婧

?

基于改進(jìn)人工蜂群算法的高維多目標(biāo)優(yōu)化

王艷嬌1, 2，肖婧2, 3

(1. 東北電力大學(xué)信息工程學(xué)院，吉林吉林，132002 2. 哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江哈爾濱，150001 3. 遼寧省交通高等?？茖W(xué)校信息工程系，遼寧沈陽，110122)

為了提高高維多目標(biāo)優(yōu)化算法的收斂性和分布性，提出基于改進(jìn)人工蜂群算法的高維多目標(biāo)優(yōu)化算法。首先，利用一種改進(jìn)的適應(yīng)值評價(jià)方式定量比較高維多目標(biāo)中個(gè)體的優(yōu)劣；其次，改進(jìn)人工蜂群算法，使種群迅速收斂于最優(yōu)的非支配前沿；最后，建立新的分布性維護(hù)機(jī)制使所獲得的非支配解分布均勻、覆蓋整個(gè)最優(yōu)前沿。研究結(jié)果表明：對于3~8個(gè)目標(biāo)的DTLZ系列測試函數(shù)，與PISA算法等幾種較流行的高維多目標(biāo)算法相比，本文方法收斂性好，解集覆蓋范圍廣且分布均勻.

高維多目標(biāo)優(yōu)化；人工蜂群算法；適應(yīng)值評價(jià)方式；分布性維護(hù)方法

高維多目標(biāo)優(yōu)化問題通過協(xié)調(diào)權(quán)衡和折中處理的方法，使不少于3個(gè)目標(biāo)的問題盡可能同時(shí)達(dá)到最優(yōu)，是目前世界公認(rèn)的優(yōu)化難題和研究熱點(diǎn)，其主要研究方向大致可分為以下幾個(gè)方面：引入新型優(yōu)化算法或其他機(jī)制、提出合適的適應(yīng)值評價(jià)方式及精英選擇策略、建立合理的分布性保持機(jī)制以及可視化技術(shù)。PISA算法(preference rank immune memory clone selection algorithm)[1]，LbsNSGA-II(light beam search based non-dominated sorting genetic algorithm II)[2]和NSGA-II(non-dominated sorting genetic algorithm II)[3]是目前較流行并有代表性的高維多目標(biāo)算法，但隨著目標(biāo)數(shù)的增加，這些算法的優(yōu)化效果都有所下降，存在計(jì)算復(fù)雜、所得近似Pareto前沿點(diǎn)不夠多、分布不均勻以及覆蓋不完整等問題。Karaboga等[4]于2005年提出的人工蜂群算法(artificial bee colony algorithm，ABC)是一種新型群集智能優(yōu)化算法，該算法操作簡單，無需設(shè)置很多參數(shù)，具有強(qiáng)大的搜索能力，在函數(shù)優(yōu)化問題、人工神經(jīng)網(wǎng)絡(luò)訓(xùn)練、濾波器設(shè)計(jì)、網(wǎng)絡(luò)優(yōu)化、機(jī)器人路徑規(guī)劃等眾多領(lǐng)域應(yīng)用廣泛[5]。文獻(xiàn)[6]以NSGA-II算法為基本框架，將人工蜂群算法用于二目標(biāo)優(yōu)化問題，收效較好，證實(shí)該算法可以解決多目標(biāo)優(yōu)化問題，但未涉及高維多目標(biāo)優(yōu)化問題。本文作者將這種新型優(yōu)化算法應(yīng)用到高維多目標(biāo)優(yōu)化中，為此更改人工蜂群算法中跟隨蜂的選擇方式、偵查蜂的行為，同時(shí)根據(jù)高維多目標(biāo)優(yōu)化問題的特點(diǎn)，提出新的適應(yīng)值評價(jià)方式和新的分布性維護(hù)機(jī)制，以便實(shí)現(xiàn)基于改進(jìn)人工蜂群算法的高維多目標(biāo)優(yōu)化算法，并對3~8個(gè)目標(biāo)的DTLZ2和DTLZ3基準(zhǔn)函數(shù)進(jìn)行測試。

1 人工蜂群算法

人工蜂群算法是受蜜蜂采蜜機(jī)制啟發(fā)而提出的一種群智能進(jìn)化算法，在ABC算法中將蜂群分為引領(lǐng)蜂、跟隨蜂和偵察蜂3類，它們在優(yōu)化過程中所起的作用各不相同。

1) 引領(lǐng)蜂。它的數(shù)量為蜜源數(shù)量的一半，并總是處于較好一半蜜源的位置上，它們在自身所在蜜源左、右按下式開采新蜜源：

其中：V為新蜜源的位置；x和x分別為蜜源和蜜源(隨機(jī)選擇但不等于)的第維位置；R為[?1，1]間的隨機(jī)數(shù)。

2) 跟隨蜂。選擇較優(yōu)蜜源并在其附近按下式搜索新蜜源：

其中：為按輪盤賭方式選擇的較優(yōu)蜜源；為隨機(jī)選取的不等于的數(shù)。通常將引領(lǐng)蜂、跟隨蜂所在的位置稱為本代蜜源。

3) 偵察蜂。若某一蜜源連續(xù)代不變，則啟動(dòng)偵查蜂，隨機(jī)產(chǎn)生新蜜源代替原蜜源。

ABC算法通過這3種蜜蜂的反復(fù)搜索、轉(zhuǎn)換求取最優(yōu)解，具體過程如下：隨機(jī)產(chǎn)生一定數(shù)量的初始蜜源，將引領(lǐng)蜂置于適應(yīng)度較優(yōu)的一半蜜源的位置上，按式(1)搜索產(chǎn)生新蜜源，與對應(yīng)的初始蜜源比較，若優(yōu)于初始蜜源，則將新蜜源作為標(biāo)記蜜源，否則，以初始蜜源作為標(biāo)記蜜源。跟隨蜂按輪盤賭方式挑選較優(yōu)的標(biāo)記蜜源并在其附近按式(2)探索新蜜源。將標(biāo)記蜜源和跟隨蜂產(chǎn)生的蜜源作為本代的蜜源，最后判斷是否出現(xiàn)偵察蜂，若出現(xiàn)，則隨機(jī)產(chǎn)生新蜜源代替相應(yīng)蜜源。

2 高維多目標(biāo)優(yōu)化

高維多目標(biāo)優(yōu)化算法的最終目標(biāo)是：使最優(yōu)解集接近于真實(shí)的非支配前沿、覆蓋整個(gè)前沿區(qū)域且分布均勻。傳統(tǒng)的二目標(biāo)優(yōu)化算法一般都不適合解決高維多目標(biāo)問題，這是由于迫使二目標(biāo)優(yōu)化算法收斂至最優(yōu)非支配前沿的進(jìn)化壓力為Pareto支配等級的差異，而隨著目標(biāo)維數(shù)增大，基于Pareto支配的非支配解急劇增加，種群中大部分解都處于最優(yōu)排序等級，由于幾乎所有解都是平等的，因此，無法選擇出較好解，使得原有算法只能收斂至局部最優(yōu)非支配前沿。

為增大高維多目標(biāo)優(yōu)化算法的選擇壓力，目前主要采取的措施如下。

1) 增加種群數(shù)目。這雖然在一定程度上增大了算法的選擇壓力，但未從本質(zhì)上改變壓力的產(chǎn)生方式，結(jié)果有所改善但很難收斂至最優(yōu)非支配前沿，也大大減低了算法的運(yùn)行效率。

2) 改進(jìn)原有的Pareto排序機(jī)制，如引入偏好信息的支配，這些方法隨著維數(shù)的增加，改進(jìn)效果越來越不明顯，不適合處理維數(shù)較高的多目標(biāo)優(yōu)化問題[7]。

3) 建立新的排序機(jī)制，如MSOPS(multiple single objective Pareto sampling)[8]和MSOPS-II(multiple single objective Pareto sampling II)[9]算法，但當(dāng)目標(biāo)維數(shù)較高時(shí)，由于難于設(shè)置合適權(quán)重或者預(yù)先不知道最優(yōu)結(jié)果使得上述的方法受到限制。

4) 將高維多目標(biāo)優(yōu)化問題轉(zhuǎn)化為低維問題處理，如主成分分析法[10]和MDMOEA算法(MOEA based on new selection schemes for dealing with many-objective problems)[11]，這是加大選擇壓力的最有效方式，但極易聚集于某一區(qū)域。

MDMOEA算法是解決高維多目標(biāo)優(yōu)化問題的新算法，它不同于傳統(tǒng)的多目標(biāo)算法，是以排序等級為第一標(biāo)準(zhǔn)，以多樣性測度如擁擠距離為第二標(biāo)準(zhǔn)建立的一種平衡算法的收斂性和分布性的新適應(yīng)值評價(jià)方法，定量比較個(gè)體的優(yōu)劣程度，使其可以較快收斂至最優(yōu)的非支配前沿，但該算法的解集覆蓋性和分布性都較差。本文借鑒并改進(jìn)該算法的適應(yīng)值評價(jià)方法，實(shí)現(xiàn)基于改進(jìn)人工蜂群算法的高維多目標(biāo)優(yōu)化。下面簡要介紹MDMOEA算法的適應(yīng)值評價(jià)方法和高維多目標(biāo)優(yōu)化的CAO操作(convergence acceleration operator)[12]。

2.1 MDMOEA算法

MDMOEA算法為高維多目標(biāo)優(yōu)化問題的求解提供了一種思路，其核心思想是建立了一種以占優(yōu)(L-optimality)為基礎(chǔ)的適應(yīng)值評價(jià)方法(其中，為個(gè)體表現(xiàn)好的目標(biāo)數(shù)與表現(xiàn)差的目標(biāo)數(shù)之差)。占優(yōu)的定義如下。

設(shè)解1和2滿足：

其中：N+和分別為自然數(shù)集合和目標(biāo)數(shù)目，滿足 0＜t＜，0＜q＜，0＜s＜，正則化目標(biāo)值為

f()為在目標(biāo)上的歸一化適應(yīng)度，為人為設(shè)定參數(shù)。若

則稱1占優(yōu)于2。

從上述定義可以看出：在個(gè)體進(jìn)行比較時(shí)，與要求個(gè)體在所有目標(biāo)上的表現(xiàn)不低于其他個(gè)體的Pareto占優(yōu)相比，條件更寬松，加大了算法的選擇壓力。

MDMOEA算法給出的適應(yīng)值評價(jià)公式為

其中：R()為個(gè)體的L排序值，相當(dāng)于L占優(yōu)于解的數(shù)目；d()為NSGA-II[3]中個(gè)體間的擁擠距離；

為模擬退火溫度。在式(3)中，R()綜合考慮了個(gè)體在各目標(biāo)上的優(yōu)劣，與Pareto排序一樣迫使種群靠近最優(yōu)前沿，而d()依據(jù)擁擠距離進(jìn)行計(jì)算，S()依據(jù)的是排序值并以模擬退火方式計(jì)算所得，增加了種群多樣性，平衡了算法的分布性。式(3)綜合考慮了收斂性和分布性，決定了算法的進(jìn)化方向，這與NSGA-II算法中精英種群的作用其實(shí)是相同的。但精英種群首先考慮收斂度，其次才考慮分布性，而MDMOEA算法通過退火溫度協(xié)調(diào)收斂性和分布性的重要程度。實(shí)驗(yàn)結(jié)果證實(shí)對于高維多目標(biāo)問題，這種權(quán)衡考慮收斂性和分布性的思想是合理、有效的。

2.2 CAO操作

大多數(shù)高維多目標(biāo)優(yōu)化算法都只能收斂于局部最優(yōu)非支配前沿，文獻(xiàn)[12]提出一種適用于高維多目標(biāo)的CAO操作，可以加速算法收斂并在一定程度上避免陷入局部最優(yōu)。操作步驟如下。

1) 局部搜索改善舊解。設(shè)維目標(biāo)優(yōu)化問題的一個(gè)前沿點(diǎn)為(1，2，…，f)。

①對所有個(gè)體在各目標(biāo)上進(jìn)行排序，判斷個(gè)體在各目標(biāo)上屬于邊界個(gè)體(沒有比個(gè)體本身更好的位置)還是中間個(gè)體，對于邊界個(gè)體保持不變，對中間個(gè)體按下式進(jìn)行改進(jìn)：

其中：f,1表示個(gè)體1在目標(biāo)上的函數(shù)值；f,2為比個(gè)體1更優(yōu)且與之距離最近的個(gè)體2的函數(shù)值；為竄改的步長因子。

②自適應(yīng)調(diào)整步長因子。步長因子決定了局部改善解與原解的距離，在一定程度上決定了算法的效率。

設(shè)CAO操作的成功率為：s=e/×100%。其中：e為由CAO操作成功引入到下一代進(jìn)化中的解；為種群數(shù)目。當(dāng)成功率下降到閾值時(shí)，通過冷卻因子增大為。

2) 從目標(biāo)空間映射到?jīng)Q策空間。由第1步操作得到可能的改善目標(biāo)值，由于種群是在決策空間進(jìn)化，故需將其從目標(biāo)空間映射到?jīng)Q策空間，這里采用人工神經(jīng)網(wǎng)絡(luò)映射方式，具體操作過程如下。

人工神經(jīng)網(wǎng)絡(luò)選用徑向基網(wǎng)絡(luò)，將真實(shí)未經(jīng)改善的目標(biāo)值和相應(yīng)的決策變量作為神經(jīng)網(wǎng)絡(luò)的輸入和輸出，訓(xùn)練該網(wǎng)絡(luò)，然后以式(4)的結(jié)果作為該網(wǎng)絡(luò)的輸入，利用已訓(xùn)練好的網(wǎng)絡(luò)求出相應(yīng)的輸出，即為對應(yīng)的決策變量；若超出范圍，則在定義域內(nèi)隨機(jī)產(chǎn)生新值，形成新解；若這一新解與相應(yīng)舊解相比在各目標(biāo)上都沒有退后，則用新解取代舊解。

3 基于人工蜂群算法的高維多目標(biāo)優(yōu)化

為更好解決高維多目標(biāo)優(yōu)化問題，改進(jìn)MDMOEA算法的適應(yīng)值評價(jià)方式及人工蜂群算法，使其能夠迅速收斂至最優(yōu)的非劣前沿，并建立新的分布性保持機(jī)制。

3.1 適應(yīng)度評價(jià)方式的改進(jìn)

MDMOEA算法的適應(yīng)度評價(jià)公式中d()和S()是依據(jù)NSGA-II算法中的擁擠距離進(jìn)行計(jì)算的，它的作用是避免種群收斂于某一點(diǎn)，使獲得的非支配解盡量分布均勻，但該擁擠距離在高維多目標(biāo)問題中不能很好地評估個(gè)體間的密度。與NSGA-II算法中的擁擠距離相比，Harmonic平均距離能夠更準(zhǔn)確地評價(jià)個(gè)體間的擁擠程度，會(huì)取得更好的優(yōu)化效果[13]，為此，本文采用Harmonic平均距離，即

其中：通常取2(?1)，為目標(biāo)數(shù)；d為距離個(gè)體最近的第個(gè)個(gè)體的歐式距離?？梢?，本文提出的改進(jìn)適應(yīng)值評價(jià)方式仍為式(3)的形式，只是其中d()的計(jì)算采用如式(5)所示的Harmonic平均距離。

3.2 人工蜂群算法的改進(jìn)

將人工蜂群算法與改進(jìn)適應(yīng)度評價(jià)方式相結(jié)合直接用于解決高維多目標(biāo)問題時(shí)容易收斂于局部最優(yōu)非支配前沿，并且收斂速度不夠快，為此進(jìn)行如下改進(jìn)。

3.2.1 跟隨蜂選擇方式的調(diào)整

通過多次仿真實(shí)驗(yàn)發(fā)現(xiàn)，跟隨蜂使用輪盤賭方式選擇較優(yōu)蜜源，較貪婪，雖然加快了算法的收斂速度，但降低了種群的多樣性也容易早熟收斂。在自由搜索算法[14]中，提出了一個(gè)重要模型——靈敏度與信息素配合模型，個(gè)體選擇某一區(qū)域(其靈敏度與信息素能夠匹配)進(jìn)行搜索，步驟如下。

1) 按下式計(jì)算個(gè)體的信息素()：

其中：()為個(gè)體適應(yīng)度；max和min分別為所有個(gè)體的最大和最小適應(yīng)度。

2) 靈敏度與信息素配合模型。以最小化問題為例，靈敏度與信息素滿足下式稱為相互配合：

其中：第個(gè)個(gè)體的靈敏度()為0~1的隨機(jī)數(shù)。與輪盤賭方式類似，本文方法也是從多個(gè)符合式(7)的個(gè)體中隨機(jī)選擇1個(gè)作為。

從這種模型可以看出：每個(gè)個(gè)體都可以搜索任何區(qū)域，這就避免了陷入局部最優(yōu)；所搜索區(qū)域的信息素必須適應(yīng)其靈敏度，這就使算法有導(dǎo)向作用，決定了算法在搜索空間中的收斂和發(fā)散。所以，跟隨蜂選擇蜜源的方式可以被上述“信息素?靈敏度”配合選擇的方式代替，方式如下：按式(6)計(jì)算各蜜源的信息素，跟隨蜂產(chǎn)生1個(gè)靈敏度(0~1的隨機(jī)數(shù))，選擇滿足式(7)的蜜源為較優(yōu)蜜源。

3.2.2 偵察蜂行為的替代

在ABC算法中，偵察蜂的作用是為避免算法陷入局部最優(yōu)，但由于本文在解決高維多目標(biāo)優(yōu)化問題時(shí)，1個(gè)個(gè)體的位置變化會(huì)導(dǎo)致所有個(gè)體的擁擠距離變化，這樣蜜源幾乎每代都在變化，很難啟動(dòng)偵察蜂，導(dǎo)致算法易于陷入局部最優(yōu)。為此，本文設(shè)計(jì)在跟隨蜂產(chǎn)生1個(gè)新解后加入強(qiáng)變異操作，代替?zhèn)刹旆涞男袨?，起到避免算法陷入局部最?yōu)的作用。強(qiáng)變異操作具體公式為

其中：′為隨機(jī)產(chǎn)生的變異位。若該變異位超出變量定義域范圍，則隨機(jī)產(chǎn)生1點(diǎn)代替該值；若變異后個(gè)體在各目標(biāo)上的表現(xiàn)都不遜于舊個(gè)體，則用新個(gè)體代替舊個(gè)體。這樣的個(gè)體接收準(zhǔn)則只與個(gè)體的適應(yīng)度有關(guān)，計(jì)算量很少，又可以保證算法的進(jìn)化方向。

3.3 分布性維護(hù)策略

實(shí)驗(yàn)結(jié)果表明，綜合考慮收斂性和多樣性建立新的適應(yīng)值評價(jià)公式可以收斂至最優(yōu)的非支配前沿，但獲得的解較集中地聚集于某一區(qū)域，分布性較差。而高維多目標(biāo)優(yōu)化算法希望解集覆蓋廣泛、分布均勻，上述方法無法滿足這一要求，為此，本文提出后期分布性維護(hù)措施。

在二目標(biāo)優(yōu)化問題中，精英種群是確保種群進(jìn)化的原因。進(jìn)化后期在確保所有個(gè)體都處于最優(yōu)非支配排序的前提下，依擁擠距離可使個(gè)體均勻分布。同樣地，在高維多目標(biāo)優(yōu)化中，可利用擁擠距離使聚集于某一區(qū)域的個(gè)體分散，但需確保個(gè)體處于最優(yōu)的非支配排序。為此，本文在算法后期建立基于擁擠距離的新型適應(yīng)值評價(jià)標(biāo)準(zhǔn)，具體計(jì)算式為

其中：()為個(gè)體的適應(yīng)度；()和X()分別為個(gè)體的Harmonic距離及其Pareto支配排序值。依Harmonic距離計(jì)算得到的擁擠距離為0~1之間的數(shù)，而個(gè)體的最優(yōu)排序等級為1，擁擠距離的作用被充分重視。

在式(9)中，由于Pareto排序越低、Harmonic距離越大的個(gè)體越好，可以保證在一直處于最優(yōu)非支配前沿的前提下，促使種群進(jìn)化，增大種群多樣性，令集中于最優(yōu)非支配前沿某一區(qū)域的種群依Harmonic距離均勻分布于整個(gè)的非支配前沿。

3.4 高維多目標(biāo)人工蜂群算法實(shí)現(xiàn)流程

歸納本文提出的高維多目標(biāo)優(yōu)化算法，首先采用適應(yīng)值評價(jià)方式將高維多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，改進(jìn)有強(qiáng)大搜索能力的人工蜂群算法，使種群迅速收斂至最優(yōu)的非支配前沿；然后，利用分布性維護(hù)措施使得聚集于某一區(qū)域的解集分散至整個(gè)前沿并均勻分布。為了避免混淆，這里稱利用前面的適應(yīng)值評價(jià)方式解決高維多目標(biāo)的過程為第1階段，分布性維護(hù)過程為第2階段。本文提出的基于人工蜂群算法的高維多目標(biāo)優(yōu)化算法的具體操作流程如下。

步驟1 初始化。給出算法相關(guān)參數(shù)，其中包括種群數(shù)目；2個(gè)階段的迭代次數(shù)分別為max1和max2；2個(gè)階段計(jì)算適應(yīng)值所需參數(shù)和；并隨機(jī)產(chǎn)生數(shù)目為的初始種群。

步驟2 按3.1節(jié)方式評價(jià)個(gè)體。

步驟3 選取適應(yīng)值較優(yōu)的/2個(gè)個(gè)體作為引領(lǐng)蜂的位置，按式(1)搜索產(chǎn)生新個(gè)體，若有超出邊界的個(gè)體，則將其置于邊界上。

步驟4 選擇引領(lǐng)蜂搜索前后的一半蜜源為本代的初始標(biāo)記蜜源。

步驟5 跟隨蜂按3.2.1節(jié)中的方式選擇較優(yōu)個(gè)體，按式(2)進(jìn)行搜索，產(chǎn)生/2個(gè)個(gè)體。

步驟6 對跟隨蜂產(chǎn)生的/2個(gè)個(gè)體進(jìn)行強(qiáng)變異操作。

步驟7 將步驟4和步驟6中的個(gè)體結(jié)合為1個(gè)種群。

步驟8 實(shí)施CAO操作，得到下一次迭代種群。

步驟9 判斷是否達(dá)到預(yù)設(shè)的迭代次數(shù)max1，若是則轉(zhuǎn)至下一步；否則，轉(zhuǎn)至步驟2。

步驟10 按式(9)評價(jià)種群。

步驟11 執(zhí)行步驟3~7。

步驟12 判斷是否達(dá)到預(yù)設(shè)的迭代次數(shù)max2，若是則輸出結(jié)果，否則，轉(zhuǎn)至步驟10。

3.5 高維多目標(biāo)人工蜂群算法復(fù)雜度分析

為分析本文算法的復(fù)雜度，這里給出種群數(shù)目和目標(biāo)數(shù)。

算法迭代過程依據(jù)適應(yīng)度評價(jià)方式的不同分為2個(gè)階段。以3.1節(jié)中的適應(yīng)度評價(jià)方式計(jì)算更加復(fù)雜，時(shí)間復(fù)雜度更大，所以，以第1階段的時(shí)間復(fù)雜度為算法每代的最壞時(shí)間復(fù)雜度。算法在步驟3、步驟5和步驟6搜索新蜜源的過程中，其時(shí)間復(fù)雜度都為(/2)；步驟2和步驟4都需根據(jù)提出的改進(jìn)適應(yīng)度評價(jià)方式評價(jià)個(gè)體優(yōu)劣，需計(jì)算L排序值和Harmonic距離，其中L排序的時(shí)間復(fù)雜度與Pareto排序的時(shí)間復(fù)雜度相當(dāng)，都為(2)，Harmonic距離的時(shí)間復(fù)雜度為((2)lg(2)。步驟8中的CAO操作的時(shí)間復(fù)雜度為()。因此，在每一代的最壞時(shí)間復(fù)雜度為

根據(jù)復(fù)雜度“”的比較關(guān)系，上式可以簡化為(2)，這表明個(gè)體評價(jià)的時(shí)間復(fù)雜度在整個(gè)算法的時(shí)間復(fù)雜度中占主導(dǎo)地位，且本文算法的時(shí)間復(fù)雜度與現(xiàn)在主流的多目標(biāo)算法NSGA-II算法的時(shí)間復(fù)雜度相當(dāng)。

4 性能仿真和分析

為驗(yàn)證本文算法的有效性和先進(jìn)性，進(jìn)行一系列仿真實(shí)驗(yàn)，并與目前較優(yōu)秀的3種算法[1-3]進(jìn)行比較。實(shí)驗(yàn)仿真是在Intel Centrino Duo(CPUT 7250，1G內(nèi)存、2.0 GHz主頻)的計(jì)算機(jī)上實(shí)現(xiàn)，程序采用Matlab7.5語言實(shí)現(xiàn)。

4.1 測試函數(shù)及性能評價(jià)標(biāo)準(zhǔn)

測試函數(shù)選用目前常用的可擴(kuò)展為任意目標(biāo)維數(shù)和自變量維數(shù)的DTLZ1，DTLZ2和DTLZ3問題[15]，其中DTLZ1的|x|=7，其最優(yōu)前沿面為線性超平面，包括11|x|?1個(gè)局部最優(yōu)前沿，一般算法很難收斂于最優(yōu)非支配前沿，故很難用于判斷算法跳出局部最優(yōu)的能力；DTLZ2的|x|=10，最優(yōu)前沿為，常用以檢測算法的分布效果；DTLZ3的|x|=7，含有3|xk|?1個(gè)非支配前沿，函數(shù)十分復(fù)雜，是DTLZ系列問題中最難的問題，一般算法很難收斂至最優(yōu)的非支配前沿，故常用此函數(shù)評價(jià)算法的收斂性。

為評價(jià)和對比各算法性能，選取目前國內(nèi)外常用的收斂性和分布性準(zhǔn)則——世代距離GD和間距度量標(biāo)準(zhǔn)S作為性能評價(jià)標(biāo)準(zhǔn)[1]。

4.2 實(shí)驗(yàn)仿真結(jié)果及分析

為充分驗(yàn)證本文方法的有效性，這里進(jìn)行2部分實(shí)驗(yàn)：1) 驗(yàn)證各種改進(jìn)措施的有效性；2) 驗(yàn)證綜合改進(jìn)后本文方法的有效性.

4.2.1 各種改進(jìn)措施的有效性

為驗(yàn)證本文提出的基于人工蜂群算法的多目標(biāo)優(yōu)化方法各項(xiàng)改進(jìn)措施的有效性，將本文最終確定的多目標(biāo)算法與單獨(dú)改進(jìn)項(xiàng)的算法進(jìn)行比較，分別稱加入3.1，3.2，3.3節(jié)中部分操作的算法為MABC1(improved artificial bee colony algorithm1)，MABC2(improved artificial bee colony algorithm2)和MABC3(improved artificial bee colony algorithm3)算法。此外，為驗(yàn)證本文算法外加的CAO操作的有效性，將本文最終確定的多目標(biāo)算法與未加入CAO操作的算法MABC4(improved artificial bee colony algorithm4)也進(jìn)行比較。

各算法參數(shù)設(shè)置如下：種群數(shù)目為200，即引領(lǐng)蜂、跟隨蜂數(shù)目都為100，第1階段迭代次數(shù)為180次，第2階段多樣性維護(hù)的迭代次數(shù)為20次，=1，=1 0000。為直觀對比改進(jìn)效果，對3個(gè)目標(biāo)的DTLZ1問題進(jìn)行測試，隨機(jī)運(yùn)行1次，結(jié)果如圖1所示。

(a) 本文算法；(b) MABC1算法；(c) MABC2算法；(d) MABC3算法；(e) MABC4算法

從圖1可以看出：MABC1算法與本文算法相比僅改變了擁擠距離的計(jì)算方式，但在規(guī)定代數(shù)內(nèi)無法收斂到最優(yōu)前沿且分布較離散，證明基于改進(jìn)擁擠距離的適應(yīng)值評價(jià)方式的有效性；MABC2算法在求解具有多個(gè)非支配前沿的DTLZ1問題時(shí)收斂到局部最優(yōu)非支配前沿，1+2+3=8，即跟隨蜂的新的選擇方式和偵察蜂的行為，有利于算法跳出局部最優(yōu)；MABC3算法可以收斂到最優(yōu)的非支配前沿，但是聚集于某一區(qū)域，即解集覆蓋性很差，這證明本文提出的第二階段的分布性維護(hù)措施在種群多樣性維護(hù)、提高解集覆蓋性上優(yōu)勢明顯；MABC4算法在固定迭代次數(shù)內(nèi)并未收斂至最優(yōu)前沿但較接近，說明CAO操作可有效提高收斂速度。

綜上證實(shí)本文提出的各種改進(jìn)措施的有效性。

4.2.2 本文方法的有效性

高維多目標(biāo)優(yōu)化算法的效果與所選取的優(yōu)化算法、適應(yīng)值評價(jià)方式及多樣性維護(hù)措施息息相關(guān)，為充分驗(yàn)證本文算法的優(yōu)勢，這里進(jìn)行如下實(shí)驗(yàn)。

實(shí)驗(yàn)一：與MDMOEA算法的比較。

本文算法主要借鑒MDMOEA算法處理高維多目標(biāo)問題的思想，所以，首先將本文算法與文獻(xiàn)[11]中的MDMOEA算法進(jìn)行比較，對5個(gè)目標(biāo)的DTLZ1和DTLZ3問題進(jìn)行測試。種群數(shù)目等參數(shù)設(shè)置與文獻(xiàn)[11]中相同，本文方法保證第二階段的迭代次數(shù)為20次。表1所示為本文算法和MDMOEA算法在各目標(biāo)上的覆蓋范圍。

表1 2種算法在各目標(biāo)上的覆蓋范圍

實(shí)驗(yàn)結(jié)果證實(shí)：對于上述2個(gè)測試問題，這2種方法都可以收斂至最優(yōu)的非支配前沿；MDMOEA算法的函數(shù)評價(jià)次數(shù)為30 000次，而本文算法的函數(shù)評價(jià)次數(shù)僅為20 000次，即本文算法在收斂速度方面有較大提高，這也就證明對于高維多目標(biāo)優(yōu)化問題與遺傳算法相比，人工蜂群算法與L支配適應(yīng)值相結(jié)合的方式可使收斂速度顯著提高；另外，從表1可以看出：對于上述2個(gè)測試函數(shù)，MDMOEA算法在第2和第3個(gè)目標(biāo)上的覆蓋范圍都很小，即其最優(yōu)非支配解集較集中，而本文算法分布在整個(gè)平面空間中，在解集覆蓋性上優(yōu)勢明顯。

綜上所述，經(jīng)過上述綜合改進(jìn)，與MDMOEA算法相比，在保證收斂效果相當(dāng)?shù)那疤嵯?，本文算法在收斂速度、解集分布性和解集覆蓋性上都得到大幅度提高。

實(shí)驗(yàn)二：與其他高維多目標(biāo)算法的比較。

從MDMOEA算法的實(shí)驗(yàn)結(jié)果可以看出：綜合考慮收斂效果和分布效果并不是解決高維多目標(biāo)問題的最好算法。為表明本文算法的先進(jìn)性，將本文算法與目前最有代表性的高維多目標(biāo)算法即PISA算法[1]、LbsNSGA-II[2]和NSGA-II[3]進(jìn)行對比。為使這4種算法的對比更具科學(xué)性，相同參數(shù)皆采用文獻(xiàn)設(shè)置的參數(shù)值。本文算法設(shè)置的參數(shù)來自于多次實(shí)驗(yàn)獲得的較理想?yún)?shù)值：種群數(shù)目為200，即引領(lǐng)蜂、跟隨蜂數(shù)目都為100；第1階段迭代次數(shù)為480次，第2階段多樣性維護(hù)的迭代次數(shù)為20次；=1，=10 000。

為了消除隨機(jī)性對算法評價(jià)的不良影響，獨(dú)立運(yùn)行10次取平均值，改變目標(biāo)數(shù)目，得到各算法的收斂性和分布性的統(tǒng)計(jì)結(jié)果，見表2。將本文算法簡記為DMABC算法(deal with many objectives based on an improved artificial bee colony algorithm)。

表2 各種算法對3~8個(gè)目標(biāo)的DTLZ2問題的測試結(jié)果

注：為目標(biāo)數(shù)目；各目標(biāo)第1行數(shù)值表示均值，第2行數(shù)值表示方差，黑體數(shù)為每個(gè)測試函數(shù)所得最優(yōu)結(jié)果。

從表2可以看出：對于3~8個(gè)目標(biāo)的DTLZ2和DTLZ3問題，本文算法的世代距離均值遠(yuǎn)遠(yuǎn)比其他3種算法的小，說明本文算法更可以收斂至最優(yōu)的非支配前沿，其收斂性對各測試函數(shù)都優(yōu)于其他3種對比算法，且GD的方差很小，表明本文算法具有很高的穩(wěn)定性，能在各次測試中均收斂至理想非支配前沿；在5個(gè)目標(biāo)以上的DTLZ2問題上，NSGA-II的均值較大，表明它極易陷入局部Pareto前沿，收斂性較差，而對3個(gè)目標(biāo)以上的DTLZ3問題，所獲方差較大，證明該算法并不穩(wěn)定；PISA和LbsNSGA-II算法所獲GD均值、方差均比NSGA-II的小，表明PISA和LbsNSGA-II的收斂性優(yōu)于NSGA-II，但比本文算法的收斂性差很多。對于3~8個(gè)目標(biāo)的DTLZ3問題可得出類似結(jié)論。

從表2可以看出：除在6個(gè)目標(biāo)的DTLZ2問題和8個(gè)目標(biāo)的DTLZ3問題上，PISA算法的分布性均值最小外，本文算法的均值都最小。這表明本文算法在大多測試問題上都可以獲得最佳的分布效果，對高維多目標(biāo)優(yōu)化具有良好的分布性能，且所獲方差較小，表明本文算法的穩(wěn)定性較好。對于3~8個(gè)目標(biāo)的DTLZ3問題可得出類似結(jié)論。分布性指標(biāo)只能反映解集的分布是否均勻，但不能直觀反映解集是否覆蓋整個(gè)Pareto前沿，為此這里又給出5個(gè)目標(biāo)和8個(gè)目標(biāo)DTLZ2問題的優(yōu)化結(jié)果分布圖，可以直觀顯示解集覆蓋能力，如圖2所示。

(a) 5個(gè)目標(biāo)；(b) 8個(gè)目標(biāo)

圖2中縱坐標(biāo)表示在各目標(biāo)上可以取得的數(shù)據(jù)范圍，數(shù)據(jù)范圍越寬，表明解集覆蓋范圍越大。由于PISA算法的收斂效果和分布效果都優(yōu)于LbsNSGA-II和NSGA-II算法，這里僅給出與PISA算法的對比結(jié)果。對于5個(gè)目標(biāo)的DTLZ2問題，PISA算法在前4個(gè)目標(biāo)上的覆蓋范圍均為0.3~0.5，在第5個(gè)目標(biāo)上的覆蓋范圍為0.2~0.5，而本文算法在各目標(biāo)上的覆蓋范圍都可達(dá)到理論范圍0~1；對于8個(gè)目標(biāo)的DTLZ2問題，PISA算法在各目標(biāo)上的分布范圍都為0~0.5，而本文算法在各目標(biāo)上的覆蓋范圍接近理論范圍0~1，這說明與PISA算法相比，本文算法所獲得的解集覆蓋范圍更寬。

上述實(shí)驗(yàn)從收斂效果、分布效果、解集覆蓋能力方面證明本文提出方法可以較好地解決高維多目標(biāo)優(yōu)化問題。這是由于本文采用一種新的適應(yīng)值評價(jià)方式、改進(jìn)人工蜂群算法并綜合使用CAO操作增大種群向最優(yōu)前沿進(jìn)化的壓力、加快算法收斂速度并在一定程度上避免收斂于局部最優(yōu)非支配前沿，使種群迅速收斂到最優(yōu)的Pareto前沿，而后期使用分布性維護(hù)策略使聚集于某一區(qū)域的種群依靠Harmnic距離分散，獲得很好的覆蓋和分布效果。

5 結(jié)論

1) 借鑒并改進(jìn)了MDMOEA算法中的適應(yīng)值評價(jià)方式，并對人工蜂群算法進(jìn)行改進(jìn)，迫使種群迅速收斂于最優(yōu)的非支配前沿。

2) 為避免算法獲得的最優(yōu)解聚集于某一區(qū)域，提出分布性維護(hù)措施.通過對3~8個(gè)目標(biāo)的DTLZ2和DTLZ3問題進(jìn)行測試，并與其他幾種多目標(biāo)優(yōu)化算法對比，本文方法獲得的非支配解更接近于真實(shí)的Pareto前沿，分布更加均勻、寬廣。這表明本文方法是一種有效的高維多目標(biāo)優(yōu)化方法，不僅在實(shí)際應(yīng)用中具有廣泛的推廣價(jià)值，而且擴(kuò)展了人工蜂群算法的應(yīng)用領(lǐng)域。

[1] 楊咚咚, 焦李成, 公茂果, 等.求解偏好多目標(biāo)優(yōu)化的克隆選擇算法[J]. 軟件學(xué)報(bào), 2010, 21(1): 14?33. YANG Dongdong, JIAO Licheng, GONG Maoguo, et al. Clone selection algorithm to solve preference multi-objective optimization[J]. Journal of Software, 2010, 21(1): 14?33.

[2] Deb K, Kumar A. Light beam search based multi-objective optimization using evolutionary algorithms[C]//2007 IEEE Congress on Evolutionary Computation(CEC' 2007). Singapore, 2007: 2125?2132.

[3] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE Trans on Evolutionary Computation, 2002, 6(2): 182?197.

[4] Karaboga D, Basturk B. On the performance of artificial bee colony (ABC) algorithm[J]. Applied Soft Computing, 2008, 8(1): 687?697.

[5] 暴勵(lì), 曾建潮. 一種雙種群差分蜂群算法[J]. 控制理論與應(yīng)用, 2011, 28(2): 266?272. BAO Li, ZENG Jianchao. A bi-group differential artificial bee colony algorithm[J]. Control Theory & Application, 2011, 28(2): 266?272.

[6] Ramin H, Bahareh H, Reza A, et al. A multi-objective artificial bee colony for optimizing multi-objective problems[C]//2010 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE). Chengdu, China: IEEE Press, 2010: 5277?5281.

[7] Sulflow A, Drechsler N, Drechsler R. Robust multi-objective optimization in high dimensional spaces[C]//Evolutionary Multi-Criterion Optimization: 4th International Conference EMO2007. New Yok: Springer?Verlag, 2007: 715?726.

[8] Hughes E J. Multiple single objective Pareto sampling[C]//2003 Congress on Evolutionary Computation. Canberra, Australia, 2003: 2678?2684.

[9] Hughes E J, MSOPS-II: A general-purpose many-objective optimizer[C]//2007 IEEE Congress on Evolutionary Computation (CEC’2007). Singapore, 2007: 3944?3951.

[10] Saxena D K, Deb K. Certain large-dimensional multi-objective optimization problems: Employing correntropy and a novel maximum variance unfolding[C]//Evolutionary Multi-Criterion Optimization: 4th International Conference, EMO2007. New York: Springer?Verlag, 2007: 772?787.

[11] ZOU Xiufen, CHEN Yu, LIU Minzhong, et al. A new evolutionary algorithm for solving many-objective optimization problems[J]. IEEE Transactions on Systems, MAN, and Cybernetics. Part B: Cybernetics, 2008, 38(5): 1402?1412.

[12] Salem F A, Tony J D, Griffin I A, et al. Convergence acceleration operator for multiobjective optimization[J]. IEEE transactions on Evolutionary Computation, 2009, 13(4): 825?847.

[13] HuangV L, SuganthanP N, Qin A K, et al. Multi-objective differential evolution with external archive and harmonic distance-based diversity measure[R]. Singapore: Technical Report of Nanyang Technological University, 2005: 1?24.

[14] Penev K, Littlefair G. Free search: A comparative analysis[J]. Information Sciences, 2005, 172(1): 173?193.

[15] ZHANG Bin, REN Weihua, ZHAO Lihua, et al. Immune system multiobjective optimization algorithm for DTLZ problems[C]//2009 Fifth International Conference on Natural Computation. Tianjin, China: IEEE, Press, 2009: 603?607.

(編輯 陳燦華)

Optimization of multi-objective problems based on artificial bee colony algorithm

WANG Yanjiao1, 2, XIAO Jing2, 3

(1. College of Information Engineering, Northeast Dianli University, Jilin 132002, China; 2. College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China; 3. College of Information Engineering, Liaoning Provincial College of Communications, Shenyang 110122, China)

In order to improve the convergence and diversity of large-dimensional multi-objective optimization algorithms, a novel large-dimensional multi-objective optimization algorithm based on an improved artificial bee colony algorithm was proposed. Firstly, an improved fitness evaluation method was employed to measure the superiority of every individual quantitatively. Secondly, artificial bee colony algorithm was improved to make the population converge reach the true Pareto front quickly. Finally, a novel diversity-maintaining scheme was established to make the solution set distribute uniformly and cover the whole Pareto front. The results show that the diversities and convergence of the proposed algorithm are better than other state-of-the-artlarge-dimensional multi-objective optimization algorithms such as PISA.

large-dimensional multi-objective optimization; artificial bee colony algorithm; fitness evaluation method; diversity-maintaining scheme

10.11817/j.issn.1672-7207.2015.06.019

TP393

A

1672?7207(2015)06?2109?09

2014?06?20；

2014?08?20

國家自然科學(xué)基金資助項(xiàng)目(61175126)；教育部博士點(diǎn)基金資助項(xiàng)目(20112304110009)；東北電力大學(xué)博士科研啟動(dòng)基金資助項(xiàng)目(BSJXM-201320)；遼寧省博士科研啟動(dòng)基金資助項(xiàng)目(201205118)；遼寧省教育廳科學(xué)技術(shù)研究一般項(xiàng)目(L2012458)；黑龍江省博士后基金資助項(xiàng)目(LBH-Z12073)(Project (61175126) supported by the National Natural Science Foundation of China; Project (20112304110009) supported by the Ministry of Education Doctoral Fund; Project (BSJXM-201320) supported by the PhD Research Funds of Northeast Dianli University; Project (201205118) supported by Scientific Research Foundation of Liaoning Province; Project (L2012458) supported by the General Project of Science and Technology of Education Department of Liaoning Province; Project (LBH-Z12073) supported by the Heilongjiang Postdoctoral Fund)

王艷嬌，博士，副教授，從事智能計(jì)算、智能信息處理研究；E-mail：wangyanjiao1028@126.com