一種約束多目標優化問題的改進蟻群遺傳算法

摘要：該文針對多目標蟻群遺傳算法（MOAGA）解集邊界分布不均的問題，提出改進算法，解決了連續空間中帶約束條件多目標優化問題。改進算法在基本MOAGA算法的基礎上，在選擇中引入一定比例的邊界決策、單目標最優決策，并提高邊界決策的交叉率。實驗證明，改進算法解決了基本算法解集分布邊界疏中間密的問題，并且能更快的獲得散布性較好的Pareto最優解集。

關鍵詞：約束多目標優化問題，改進蟻群遺傳算法，散布性，Pareto前沿

中圖分類號：TP18文獻標識碼：A文章編號：1009-3044(2008)36-2830-03

An Improved Multi-Objective Ant-Genetic Algorithm In Constrained Problem

WU Ai-hua

(Changsha Social Work College，Changsha 410004，China)

Abstract: An improved Multi-Objective Ant-Genetic Algorithm is presented in this paper， it can be used to solve Constrained Multi-Objective Optimization Problem on continuous space. Go farther than the basic MOAGA， we introduce some scale of boundary-decision and single-objective excellent-decision in choosing， and enhance ratio of intercrossing of boundary-decision. In the end， an example was listed to prove that the improved algorithm can solve the problem of the solution-set distributing uneven on the boundary in basic one， and can obtain the Pareto optimality set faster and better.

Key words: Constrained Multi-Objective Optimization Problem; Improved Multi-Objective Ant-Genetic Algorithms; diffusion performance; Pareto front

1 引言

在實際問題中，許多控制和決策問題需同時考慮多個目標優化，即約束多目標優化問題。不失一般性，以最小化問題為例，約束多目標優化問題可定義如下：

但對多目標優化問題的求解至今還是一個難點，通常很難求出其最優解，只能求出Pareto解。近年來，出現了一系列用來解決此問題的算法，如遺傳算法(GA)、粒子群優化（PSO）、蟻群算法（ACA）等，這些算法雖然在過程控制、工程優化等方面取得了成功，但在求解多目標函數優化問題時存在一些困難。就目前來說，由于蟻群算法具有并行性、正反饋機制以及求解效率高等特性，但其全局搜索能力較差，容易陷入局部解[1]。而遺傳算法盡管具有快速性、隨機性、全局收斂性等優點，但是運行到一定程度后，由于沒有有效利用系統中的反饋信息而作大量無謂的冗余迭代，另外該算法對所選參數比較敏感，其收斂速率還得不到非常有效的保證，有時會出現收斂停滯現象[2]。考慮到蟻群算法和遺傳算法的特性，因此有學者考慮研究蟻群算法與遺傳算法的融合[3]（GAAA），但該算法只是簡單地先后運用兩種算法進行求解，并不是實質的融合，盡管在一定程度上提高了求解的精度，但是算法效率降低了。多目標蟻群遺傳算法（MOAGA）很好的解決了這一問題，但是由于該算法采用是線性交叉算子，解集的分布是中間密，靠近邊界的部分比較稀疏。因此為了解決解分布的均勻散布性，本文提出基于MOAGA的改進算法，在選擇過程中時，按一定比例加入邊界決策（特別是邊界最優決策），同時使得部分單目標最優決策直接成為父代；在交叉過程中，提高邊界決策的繁殖能力。這樣，就能更快地獲得散布性較好的解集。

2 改進的多目標蟻群遺傳算法

2.1 信息素操作

首先將決策向量空間均勻分解為M=M1×M2×…×Mn個子空間Ej1j2…ji（ji=1，2，…，Mi）。然后在每個子空間中隨機產生一個決策形成第1代——初始決策集A(1*)。 對初始決策用約束條件判斷，剔除非可行決策得可行決策集A(1)。

則第k代編號為j1j2…jn的子空間上第i個目標函數對應的信息量Phi，j1j2…ji(k)為：

其中Phi，j1j2…ji(k)=0，且Ph'i，j1j2…ji(k)為第k代子空間j1j2…jn上由于新決策引入所產生的信息量增量，ρ為揮發系數。

具體計算過程為：不妨設在子空間j1j2…jn上，第k代的Pareto最優決策集為P{p1，p2， …，pk}。

若P≠Φ，則

若P=Φ，則Phi，j1j2…ji(k)=0；其中i=1，2， …，m。

2.2 優秀決策集更新

第 代進化結束得到第 代初始決策集A(k*)，根據一個定義的相似度對A(k*)去掉相似決策（以提高決策的散布范圍），并用約束條件處理后得到第 代可行決策集A(k)。 接著對A(k)進行Pareto分級，取A(k*)的第1級Pareto決策集與優秀決策集D（對于第一代，令D=Φ）取并，得到決策集B，再對B又一次進行Pareto分級，則B的第1級Pareto決策集即更新后的D。

2.3 遺傳操作

選擇：為了保證決策的多樣性及不縮小散布范圍，把以下幾種決策直接作為父代參與遺傳交叉：部分邊界決策、少量父代決策中的Pareto 優秀決策、少量單目標最優決策、少量優秀決策集D中的決策。注意：以上決策總個數不能超過父代決策的20%（經驗值，一般建議5%~15%），否則將會很快收斂于局部最優。接著按概率進行選擇，第 代可行決策集Aj(k*)（j=1，2， …，kM）被選中的概率為：

其中j'表示第j個決策所處的子空間坐標。然后依照輪盤賭的方式，選取決策直到A(k)規模為M，得到第k代可行決策集A(k)。

1) 交叉

一般來說，大量的約束多目標優化問題都是基于實數空間的，因此本文采用線性交叉算子。由于實數線性交叉的特點，在數次交叉后，不可避免后代不斷趨近于空間的中心，從而形成空間中心較密、邊界稀疏甚至沒有的情況。前面進行父代選擇時進行了一定的處理，但是為了保證解集的散布性，在主體交叉完畢后進行邊界強制性交叉。邊界強制性交叉的特點是，在兩個父代個體中，隨機確定其中一個為邊界決策，另一個在其余決策中隨機選擇。

2) 變異

變異操作是產生新個體的輔助方法，同時也決定了蟻群遺傳算法的局部搜索能力。每個個體的每個變量都有均等的變異機會，先選定一個個體的一個變量，然后產生一個隨機數，如果該數大于變異概率，則不執行變異操作；否則在該個體相應變量的定義域范圍進行變異操作。本文選擇的變異方法是決策突變，即若某決策被選定執行變異，則在其定義域范圍內進行突變。

3 收斂性驗證

3.1 間距評估

間距評估是由Shott于1995年提出的[4]，通過計算相鄰解之間的相對距離，來對解的多樣性進行評估。若設Pareto最優決策的個數為 ，則分布性能可用最近解歐氏距離的標準差來表示：

3.2最大散布范圍

這種評價方式是由Zitzle and Kalyanmony Deb于1999年提出的[5]，用來計算解集中的所有極值解構成的多面體的周長，具體定義如下：

的值越大表示解的散布范圍越廣。

3.3收斂速度

這里我們用一級Pareto最優決策集的改變百分比序列來反應收斂速度：

其中X為本次迭代的一級Pareto最優決策最優集，X'為上次迭代的一級Pareto最優決策最優集，“ ”為近似減法（表示把集合X中與X'相同或相似的決策去掉）。從表達是可以看出，若隨著迭代的進行，Mi序列迅速穩定趨向于0（實際是一個很小的數），則表示算法收斂較快。

3.4數值實驗

為說明MOAGA在解決連續空間中帶約束多目標優化問題的優越性，本文以兩變量約束問題BNH問題為例來測試算法的性能。

BNH問題

BNH問題是一個兩變量約束問題，它的Pareto前沿是連通的，便于求解。由下表可以看出，改進算法比MOAGA算法搜索到的解的數量更多，分布也更加均勻，而且解散布的范圍更廣。

4 結束語

本文提出了一種基于蟻群算法和遺傳算法的改進多目標蟻群遺傳算法[6]，用來求解約束多目標優化問題。本算法先將解空間分解成子區域，信息素對遺傳搜索進行指導，在搜索中更新信息素，同時采用了最優決策集的更新策略和搜索收斂退出機制，從而提高求解效率，降低算法復雜度。實驗證明，與以往算法相比，此算法解決了解集分布邊界疏的問題，并且能更快更精確地逼近Pareto前沿。

參考文獻：

[1] T.Stutzle， M.Dorigo. A Short Convergence Proof for a class of Ant Colony Optimization Algorithm. IEEE Transaction on Evolutionary Computation.2002， 6(4):358-365.

[2] B.Roy. Problems and Methods with Multiple Objective function. Mathematical Programming.1971，1(2):239-201.

[3] S.Christine. Ants Can Solve Constrain Satisfaction Problem. IEEE Transactions on Evolutionary Computation.2002，6(4):347-357.

[4] Deb K. Multi-objective Optimization Using Evolutionary Algorithms， New York: JohnWileysons，2001.

[5] Van Veldhuizen D.A.， Lamont GB. On Measuring Multiobjective Evolutionary Algorithm Performance. In Proceeding sof the 2000 Congress on Evolutionary Computation. 2000: 204-211.

[6] 伍愛華，李智勇. 多目標優化的蟻群遺傳算法[J].計算機工程，2008，34(8):200-202.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文?！?/p>