王艷嬌，肖婧

?

基于改進人工蜂群算法的高維多目標優(yōu)化

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

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

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

高維多目標優(yōu)化；人工蜂群算法；適應值評價方式；分布性維護方法

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

1 人工蜂群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 MDMOEA算法

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

設解1和2滿足：

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

f()為在目標上的歸一化適應度，為人為設定參數(shù)。若

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

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

MDMOEA算法給出的適應值評價公式為

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

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

2.2 CAO操作

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

1) 局部搜索改善舊解。設維目標優(yōu)化問題的一個前沿點為(1，2，…，f)。

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

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

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

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

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

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

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

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

3.1 適應度評價方式的改進

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

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

3.2 人工蜂群算法的改進

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

3.2.1 跟隨蜂選擇方式的調整

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

1) 按下式計算個體的信息素()：

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

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

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

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

3.2.2 偵察蜂行為的替代

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

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

3.3 分布性維護策略

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

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

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

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

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

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

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

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

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

步驟4 選擇引領蜂搜索前后的一半蜜源為本代的初始標記蜜源。

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

步驟6 對跟隨蜂產(chǎn)生的/2個個體進行強變異操作。

步驟7 將步驟4和步驟6中的個體結合為1個種群。

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

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

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

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

步驟12 判斷是否達到預設的迭代次數(shù)max2，若是則輸出結果，否則，轉至步驟10。

3.5 高維多目標人工蜂群算法復雜度分析

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

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

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

4 性能仿真和分析

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

4.1 測試函數(shù)及性能評價標準

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

為評價和對比各算法性能，選取目前國內外常用的收斂性和分布性準則——世代距離GD和間距度量標準S作為性能評價標準[1]。

4.2 實驗仿真結果及分析

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

4.2.1 各種改進措施的有效性

為驗證本文提出的基于人工蜂群算法的多目標優(yōu)化方法各項改進措施的有效性，將本文最終確定的多目標算法與單獨改進項的算法進行比較，分別稱加入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)算法。此外，為驗證本文算法外加的CAO操作的有效性，將本文最終確定的多目標算法與未加入CAO操作的算法MABC4(improved artificial bee colony algorithm4)也進行比較。

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

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

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

綜上證實本文提出的各種改進措施的有效性。

4.2.2 本文方法的有效性

高維多目標優(yōu)化算法的效果與所選取的優(yōu)化算法、適應值評價方式及多樣性維護措施息息相關，為充分驗證本文算法的優(yōu)勢，這里進行如下實驗。

實驗一：與MDMOEA算法的比較。

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

表1 2種算法在各目標上的覆蓋范圍

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

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

實驗二：與其他高維多目標算法的比較。

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

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

表2 各種算法對3~8個目標的DTLZ2問題的測試結果

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

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

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

(a) 5個目標；(b) 8個目標

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

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

5 結論

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

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

[1] 楊咚咚, 焦李成, 公茂果, 等.求解偏好多目標優(yōu)化的克隆選擇算法[J]. 軟件學報, 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] 暴勵, 曾建潮. 一種雙種群差分蜂群算法[J]. 控制理論與應用, 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

國家自然科學基金資助項目(61175126)；教育部博士點基金資助項目(20112304110009)；東北電力大學博士科研啟動基金資助項目(BSJXM-201320)；遼寧省博士科研啟動基金資助項目(201205118)；遼寧省教育廳科學技術研究一般項目(L2012458)；黑龍江省博士后基金資助項目(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)

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