一種改進快速穩定的多目標優化算法

摘要：多目標優化問題屬于高維的搜索空間，用一些傳統方法來優化這些問題會導致較高的時間復雜性。為了解決該問題，使用了粒子群優化算法(PSO)，同時將εdominance的概念應用到PSO中。該方法在實驗過程中取得了良好的效果。其運算速度快，而且最終優化的點數可以得到控制。

關鍵詞：多目標優化； 粒子群算法； ε支配多目標優化

中圖分類號：TP3016文獻標志碼：A

文章編號：10013695(2007)04005202

優化問題是人們在改造世界時經常會遇到的一類普遍的問題。當人們考慮一個優化問題時，目的是求得目標的最優解。而多目標優化問題更是很普遍的問題^[1]。多目標優化問題起源于許多實際復雜系統的設計、建模和規劃問題。這些系統所在的領域包括工業制造、城市運輸、資本運算、森林管理、水庫管理、新城市的規劃和美化、能量分配等。幾乎每個現實生活中重要的決策問題都要在考慮不同約束的同時處理若干相互沖突的目標，這大大增加了問題的復雜程度^[2]。因此，研究一種快速、穩定、實用的多目標優化算法具有相當重要的現實意義。本文是使用粒子群優化算法(PSO)來解決多目標優化問題，同時將εdominance的概念應用到PSO中。粒子群優化是近幾年發展起來的群聚只能算法。該算法是基于群體中的各個粒子能夠從過去的經歷和其他粒子的經歷得到有效信息這個假設之上的。通過實驗發現，該算法與εdominance一起使用能使優化過程更加穩定、快速，而且實驗的效果也很理想。

1多目標優化的基本概念

1.1多目標優化問題

一個通常的多目標問題包括一個含有n個參數(自變量)的集合，一個k個目標函數的集合，一個m個約束的集合和目標函數和約束都是自變量的函數^[3]。

其中，x是自變量向量，y是目標向量，X是自變量空間，Y是目標空間，約束g(x）≤0確定了可行解。

1.2Pareto支配關系

對于任意兩個自變量向量a和b。

1.3εdominance概念^[4]

如果對于所有的i∈[1，2，…，m]均滿足(1+ε)×fi≥gi，則認為f εdominance支配g。表示形式為fεg。其中ε＞0。

1.4Pareto優化

根據目標域的偏序關系，就可以得出Pareto優化的定義：一個自變量向量x∈Xf考慮Xf的一個子集A。如果！a∈A∶ax，x被稱為是對應于集合A的Pareto最優。就是說，自變量向量a如果稱為對應于集合A的Pareto最優解或非劣最優解，那么，在任何一個目標上它都不能繼續得到優化而并沒有引起任何其他維目標的劣化。

2粒子群算法

粒子群優化(Particle Swarm Optimization， PSO)^[5，6]也是基于群體的方法，最早由Kennedy和Eberhart提出。它最初是由鳥類遷徙覓食的模型而得到的。在該模型中，群體中的每個個體都有給予一定的內部信息和外部信息而控制自己行為的能力。也就是說，每個個體都有一定的感知能力，能夠感知自己周圍的局部最好位置的個體和整個群體的全局最好位置的個體存在，并根據當前狀態和所獲得的信息，調整自己的下一步行為，從而使整個群體表現出一定的智能性。在解決優化問題時，每個個體的所在位置可被相應地看成一個潛在的解，經過反復迭代最終得到所需的全局最優解。下面給出粒子群算法的偽代碼:

創建并初始化一個n維空間的PSO：M

初始化r1和r2，每個粒子的x，v

其中，每個個體由當前位置x和速度v組成；其能感知的最優位置由p表示；pi，gj，t表示全局最優位置；pij，t表示局部最優位置。這里j=1，2，…，n，代表第j維搜索空間；i=1，2，…，M，代表第i個個體；t為迭代次數；λ是收縮因子；ω是慣性因子；c1和c2為兩個正常數；r1和r2為某個范圍中的隨機數。

3εMOPSO算法流程

在這個算法中關鍵的一步就是計算ε非支配解。其計算過程（圖1）的偽代碼如下：

4實驗結果

對該算法驗證其穩定性和快速性。在實驗過程中主要與CMOPSO^[7]多目標優化算法進行比較。在測試時，用到的測試函數是多目標算法測試比較常用的幾個測試函數，即ZDT1～ZDT6。這幾個測試函數是Deb在1998年指出多目標優化中比較困難的幾個問題：①收斂到Pareto最優陣面；②在群體中維持個體多樣性。對于問題①，在單目標演化優化中多峰函數、欺騙函數和孤立最優函數都是很著名的問題。為了獲得好的Pareto最優陣面的分布特性，問題②也是很重要的。然而，Pareto最優陣面的某些特征會不利于多目標優化演化算法找到各種各樣的Pareto最優解：凸或非凸的、離散的、非均勻分布的。針對具有這些特性的Pareto最優解，Deb設計出這六個相應的測試函數。其測試函數如表1所示。

表1測試函數

在這個算法中對于不同的測試函數ε取不同的值。在其他設置參數相同的情況下，ε的值不同計算時間就不同，得到的優化點個數就不同。ε的取值越大，得到的優化點就越少。這就是本算法的關鍵所在，而且最終得到的優化點的個數等于1/ε。

實驗參數的設置如表2所示。

表2實驗參數

εMOPSO算法中ε的取值，對于不同的測試函數取不同的值。如圖2所示ε=005時，比較的結果；當ε=0000 1時，其實驗結果如圖3所示。為了說明此算法的優越性，在以下幾個測試函數的驗證過程中就不再設ε=0000 1的情況了。

從圖2中可以明顯地看出來，當ε的取值很小時，其最終優化的點數就越多。如圖3當ε=0000 1時，其優化結果比CMOPSO算法的優化結果要好一些。這兩個圖是對ZDT1進行測試。

以下分別對策樹函數ZDT2、ZDT3、ZDT4和ZDT6進行測試。其測試結果分別如圖4、5所示。

對于ZDT2，ε＝003;對于ZDT3，ε＝0001;對于ZDT4，ε＝0065；對于ZDT6，ε＝0075。可以看出，對于不同ε的取值，實驗結果優化的點的數目就不同。

5結束語

多目標優化問題是一個比較熱門的研究課題。不同的優化算法有不同的效果，但最終的目的就是如何控制算法搜索的收斂性、解的多樣性和計算時間最小化。本文提出的εMOPSO算法能滿足上述要求，而且還能有效地控制優化解的個數。這就為決策者提供了一種很好的解決方法。因而，此算法具有有效的使用價值。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。