混合擇優的多目標免疫粒子群優化算法

仲昭明，李向陽，逄珊

ZHONG Zhaoming1,LI Xiangyang2,PANG Shan3

1.魯東大學 物理與光電工程學院，山東 煙臺 264025 2.煙臺聯通信息化支撐中心，山東 煙臺 264001

3.魯東大學 信息科學與工程學院，山東 煙臺 264025

混合擇優的多目標免疫粒子群優化算法

仲昭明1，李向陽2，逄珊3

ZHONG Zhaoming1,LI Xiangyang2,PANG Shan3

1.魯東大學 物理與光電工程學院，山東 煙臺 264025 2.煙臺聯通信息化支撐中心，山東 煙臺 264001

3.魯東大學 信息科學與工程學院，山東 煙臺 264025

1 引言

很多實際工程問題需要同時優化多個目標，這類問題稱為多目標優化問題。由于存在多個相互沖突的目標，此類問題不存在單個解滿足所有目標，而存在一個折衷解的集合，稱為Pareto最優解集或非支配解集[1]。

進化算法是基于種群的智能優化算法，一次運行能夠求得問題的多個解，很適合求解多目標優化問題。目前已被成功應用于多目標優化領域，并發展成為一個新的研究方向：進化多目標優化[2-3]。近年來，一些新的智能算法被引入多目標優化問題的求解，其中基于粒子群的多目標優化是近年來逐步發展起來的一個新興研究方向。同進化算法相比，粒子群算法由于具有控制參數少以及收斂速度快等優點得到迅速發展。

但由于粒子群的單項信息共享機制。算法在多目標優化過程中經常會遇到早熟收斂等問題[4]。并且群中每個粒子都在解集中各自的全局極值的指導下搜索，如果最優解的選取不當，難以獲得均布性好的解。因此如何選擇粒子的全局極值是十分重要的，對于多目標優化算法解的收斂性和多樣性都有很大影響。

為此本文提出一種基于解集信息熵和Sigma值[5]的混合擇優機制：種群的粒子以一定概率，根據解集中解的信息熵值或Sigma值選擇其全局極值，并且在迭代不同階段側重不同的選擇原則。該機制充分利用信息熵的密度定義能更好地描述解集分布情況[6]以及Sigma值有助于加速收斂的優點，兼顧了算法的全局和局部搜索能力，有效地改善了解的分布性和收斂性。同時，引入免疫理論中的克隆選擇機制直接對解集進行選擇搜索，進一步提高了算法的分布性。

2 基于信息熵和Sigma值的混合選擇機制

2.1 典型的選擇機制分析

粒子全局極值的選取對多目標粒子群優化算法解集的收斂性和分布性都有很大的影響。早期，由Coello[7]等提出的MOPSO借用了PAES[8]等進化多目標優化算法的檔案進化策略，將自適應網格法用于解集的維護。把解集劃分為網格，根據網格內解的個數設定解的適應度值，網格內解越多其適應度值越小，對所有網格應用輪盤賭方法選擇粒子的全局極值。這種方法比較簡單，但由于解是隨機選擇的，因此算法的收斂性有待提高。Raquel[9]等人將NSGA-II中的擁擠距離的概念引入，得到CD-MOPSO。對解集中解的擁擠距離進行排序，據此選擇全局極值，其解的分布性較好，但收斂性仍有待提高。此外應用較為廣泛的選擇機制還包括支配樹機制和Sigma機制。支配樹機制通過設計支配樹的數據結構存儲精英解，為粒子選取最優經驗，指導粒子飛行。這種機制比Coello的網格機制在解的收斂性上有所提高，但其自身也存在不足：未考慮解的分布情況。Sigma機制則引入參數“σ”來比較粒子和解在空間上的位置關系。如圖1所示的二維情況為例，參數σ的定義為：

圖1 Sigma機制示意圖

通過比較群中粒子和解集中解的σ值，選取二者差值最小的解為全局極值。被選擇的全局極值指導粒子沿著直線方向直接逼近Pareto前沿，收斂性較好。但由于Sigma機制未考慮到解的密度信息，在解集中粒子分布不均勻的情況下，容易出現早熟收斂現象，其全局搜索能力有待提高。

為改善算法的性能，一些學者提出將上述機制混合使用，如Junjie[10]等人提出的混合機制，在Sigma機制的基礎上綜合考慮解的密度信息，在保持算法收斂性的前提下提高了解集的分布性。但該機制中的關于解的密度定義過于簡單，有些情況下難以體現解的實際分布情況，并且在每次迭代過程都要進行混合適應度計算，計算量較大。

2.2 混合選擇機制

通過對現有選擇機制的分析可知：好的選擇機制應該能夠選擇合適的全局極值引導粒子迅速向Pareto前沿飛行，同時還應考慮算法的分布性，盡量選擇那些分布比較稀疏的解，使粒子向解空間更廣泛的區域進行探索。

為此本文提出一種全局極值的混合選取機制：在每次迭代中粒子依一定概率，根據解集中解的信息熵或者Sigma值選擇全局極值。而該選擇概率則隨著迭代的進行而不斷調整：在迭代初期基于信息熵的選擇概率較大，選擇分布性好的解作為全局極值，以使粒子盡量在解空間全面的探索，提高解集分布性；而在迭代后期則加大基于Sigma值的選擇概率，使得種群快速向Pareto前沿逼近，提高解集的收斂性。本文的選擇概率如下：

其中，Rand為[0，1]間的隨機數，max_iteration為最大迭代次數，iteration為當前迭代次數。

對于種群中的每次迭代，在種群的N個粒子中，隨機選擇Nσ個粒子按照Sigma機制，從解集中選擇Sigma值最為接近的作為全局極值。而剩余粒子則按照信息熵值，利用輪盤賭的方法選擇全局極值。其中Nσ按照下式計算：

信息熵的計算：為了保持解集的分布性，許多基于密度或分布的全局極值選擇機制被提出，然而這些機制對于解集中解的密度定義過于簡單，某個解的密度只取決于直接相鄰的解，而沒有考慮到更遠處解的分布情況。信息熵比傳統的擁擠距離等密度定義能更好地描述某個解對于解集分布情況的貢獻。因此，為了更準確地反映解集中解的實際分布情況，本文引入信息熵的概念，采用Parzen窗估計法來計算熵值。熵值量化每一個解對Pareto解集分布的貢獻。

Pareto解集可表示為Y={yi|i=0，1，…，|Y}，用pyi=P (yi∈Y)表示解集中每個解yi的概率。其熵值為：

其概率計算采用Parzen窗函數計算。Parzen窗估計法是一種具有堅實理論基礎和優秀性能的非參數函數估計方法，它能夠較好地描述多維數據的分布狀態，其基本思想就是利用一定范圍內各點密度的平均值對總體密度函數進行估計。Parzen窗定義如下。

解的概率密度估計為：

其中K是核函數，基于正態函數的平滑性將使得估計函數變化平滑，本文采用正態窗核函數：

其中m為目標空間維度，σ是核寬，σ∈Rm。核寬的設置對Parzen窗計算影響較大，這里根據解空間的大小做適應性變化：

其中maxj和minj分別表示解集中第j維的最大、最小值。

計算完解集的信息熵后，粒子用輪盤賭的方法選擇其全局極值，信息熵越大，密度分布越好，被選為粒子全局極值的概率就越大。

3 克隆選擇機制

為了改善粒子群的搜索能力，文獻[11-12]將人工免疫系統中的克隆選擇機制應用到標準的粒子群算法當中，其基本思想是：在粒子群進化的每一代，選擇最好的若干粒子作為抗體，抗體的適應度函數越大，產生的克隆體越多。這樣粒子群算法在縱向完成對整個解空間搜索的同時，克隆選擇算子橫向地進行局部搜索，提高算法的局部搜索能力。

本文借鑒這種思想，但是根據多目標優化的特點對克隆選擇機制進行調整：克隆選擇不是應用于種群，而是直接應用于解集，根據解集中解的信息熵而非適應度排序。針對信息熵值最高的前m個解，每個解的生成l個克隆體，然后對所有的克隆體進行變異。算法采用的是與適應度值有關的變異算子[13]。

其中N(0，1)是均值為0，標準差為1的Guass隨機變量；β是用于控制指數函數衰減的變量，是經過規范化處理的克隆的各維度適應度值。

對每個解和其克隆體進行比較，如果出現支配原解的克隆體，則用克隆體代替原解。這樣經過對解集的克隆選擇可以獲得更為接近Pareto前沿的解集，并且克隆是針對解集中分布較好的若干解直接進行，比對種群進行克隆的效果更為直接。

基于混合擇優和克隆選擇的多目標粒子群可由以下步驟描述：

（1）初始化粒子群P，確定種群規模為N，初始Pareto解集置空。

（2）計算每個粒子的適應度。

（3）根據Pareto支配關系對解集進行更新，若超出數量限制則進行修剪。

（4）利用混合機制，根據每個粒子的選擇概率基于Sigma值或者信息熵值選擇全局極值值。

（5）對粒子群中每個粒子的速度和位置進行更新。

（6）更新粒子歷史最優值。

（7）Pareto解集進行克隆選擇，用支配占優的克隆代替原來的解。

（8）判斷是否達到最大迭代次數，若是，結束，輸出Pareto最優解集；否則，令iter=iter+1，轉（2）。

4 算法驗證

4.1 實驗設置和性能評價指標

為比較所提出算法（Es-MOPSO）的性能，選擇Sigma機制的σ-MOPSO和文獻[10]的Nv-MOPSO算法進行對比。為了比較的公平性，三種算法的種群、Pareto解集的規模和迭代次數均相同。其中種群和解集的規模均設置為100，最大迭代次數為200；算法速度更新公式中，慣性權重ω=0.6，c1=c2=2。本文算法指數衰減控制系數β取100，在解集粒子克隆選擇個數m取15（即種群粒子數的15%）。

性能仿真實驗選取較為常用的測試函數：ZDT1～ZDT4[14]，DTLZ1和DTLZ2[15]。這些測試函數均有已知的Pareto前沿。本文ZDT1～ZDT3測試函數的決策數n取20，ZDT4的n取10。對于DTLZ函數n=k+|xk|-1，本文中取k=3，|xk|=5。

性能評價指標如下所示。

收斂性指標Generational Distance（GD）[16]：

其中n是解集中解的數目，di是每個解距離已知Pareto前沿的最小歐幾里得距離。GD值越小說明算法的解集越靠近Pareto前沿。

分布指標SP（Spacing）[17]：

最大展布指標MS（Maximum Spread）[14]（該度量指標用于衡量所得解對Pareto前沿的覆蓋程度）：

4.2 實驗結果分析

為減少隨機因素的影響，三種算法對每個測試函數均獨立運行20次。表1和表2分別是三種算法對各測試函數運算結果的收斂性指標、分布指標的平均值和標準差值的比較。

從表1中可以發現，對于收斂性指標GD，本文算法對所有測試函數的結果都明顯優于Nv-MOPSO算法。和σ-MOPSO相比，除了測試函數ZDT1和ZDT3是σ-MOPSO取得了最優結果，其余測試函數則是本文算法取得最優結果，但是和σ-MOPSO算法差別不大。從表2中可以發現，對于分布指標SP，本文算法所有的測試函數均得到了最優結果，較另外兩種算法有較為明顯的提高。對于最大展布指標，如表3所示，除了測試函數ZDT1外，本文算法對于其他測試函數均獲得了最優結果，說明混合擇優機制有助于發現邊界的解，提高解集的最大分布。

表1 三種算法計算得到GD指標平均值和標準差值

表2 三種算法計算得到SP指標平均值和標準差值

表3 三種算法計算得到MS指標平均值和標準差值

圖2是三種算法對測試函數DTLZ2獨立運行的某次運行結果，其中，圖（a）、（b）、（c）分別對應Es-MOPSO、Nv-MOPSO和σ-MOPSO。從圖2可以發現，對于三維的測試函數DTLZ2，本文算法由于利用了信息熵表示解的分布情況，得到解集分布明顯比其他兩種算法的解集更為均勻。

5 算法的參數分析

Es-MOPSO算法的參數有初始種群規模，粒子群的加速系數c1、c2，慣性權重ω，克隆選擇機制中指數衰減控制系數β和克隆比例等。其中后兩個參數是本文引入的，因此重點針對這兩個參數對算法的影響進行分析。

5.1 指數衰減控制系數β的影響

為研究β對算法性能的影響，分別取β為25～150，其他參數設置同前文。圖3為對ZDT4函數計算的GD和SP值的變化曲線。如圖可見，隨著β的增加，GD值減小，收斂性能得到改善，但是SP值增大，分布性變差（對DTLZ1等其他測試函數的驗證也可以得到相同的結論，受篇幅限制未列出計算結果）。因此，綜合分析兩個性能的變化曲線，β值取100左右較為合適。

圖2 三種算法對DTLZ2函數計算得到Pareto解集分布情況

圖3 控制系數對算法收斂性和分布性指標的影響

圖4 克隆比例對算法收斂性和分布性指標的影響

5.2 克隆比例的影響

為研究克隆比例對算法性能的影響，m分別取5%～25%，其他參數設置同前文，對ZDT4進行計算，計算得到的GD和SP值隨m的變化如圖4所示。從圖中可見，隨著m的增加，算法的收斂性和分布性都有所提高（對DTLZ1等其他測試函數的驗證也可以得到相同的結論，受篇幅限制未列出計算結果）。當m值達到15%～20%左右時，算法的收斂性能和分布性能較好，如果再提高m，算法性能則沒有明顯提高且計算量增大，因此m值取15%～20%較為合理。

6 結論

針對多目標粒子群優化算法在解的收斂性和分布性方面的存在的不足，設計了一種全局極值的混合選取機制：按照一定概率，根據解集中解的信息熵或σ值確定粒子的全局極值，選擇概率則隨迭代進行變化，有效兼顧了解的分布性和收斂性。將免疫算法中克隆選擇機制引入算法，直接對解集中信息熵值高的解進行克隆選擇，在增強局部搜索性能的同時，進一步提高了解集的分布性。在多個典型測試函數上進行實驗，結果證明本文算法在保持較為優越收斂性的同時，顯著提高了解集的分布性。對混合擇優的多目標免疫粒子群算法進行進一步的理論分析和改進，并用于實際工程問題求解，擴展其應用范圍，將是下一步的研究內容。

[1]公茂果，焦李成，楊咚咚，等.進化多目標優化算法研究[J].軟件學報，2009，20（2）：271-289.

[2]Deb K.Multi-objective optimization using evolutionary algorithms[M].Chichester：John Wiley&Sons，2001.

[3]Srinivas N，Deb K.Multiobjective optimization using non-dominated sortingingeneticalgorithms[J].EvolutionaryComputation，1994，2（3）：221-248.

[4]Fieldsend J E，Sing S.A multi-objective algorithm based upon particle swarm optimization，an efficient data structure and turbulence[C]//Proceedings of the UK Workshop on Computational Intelligence，Birmingham，2002：37-44.

[5]Mostaghim S，Teich J.Strategies for ending good local guides in Multi-Objective Particle Swarm Optimization（MOPSO）[C]// Proceedings of IEEE Swarm Intelligence Symposium.Indianapolis，USA：IEEE Press，2003：26-33.

[6]Tan K C，Goh C K，Mamun A A，et al.An evolutionary immune system for multi-objective optimization[J].European Journal of Operational Research，2008，187：371-392.

[7]Coello Coello C A，Pulido G T，Lechuga M S.Handling multiple objectives with particle swarm optimization[J].IEEE Transactions on Evolutionary Computation，2004，8（3）：256-279.

[8]Knowles J D，Corner D W.Approximating the non-dominated front using the Pareto archive evolutionary strategy[J].Evolutionary Computation，2000，8（2）：149-172.

[9]Raquel C R，Naval P C.An effective use of crowding distance in multiobjective particle swarm optimization[C]//Proceedings of the Conference on Genetic and Evolutionary Computation. NY：ACM Press，2005：257-264.

[10]Yang J，Zhou J，Liu L，et al.A novel strategy of pareto-optimal solution searching in Multi-Objective Particle Swarm Optimization（MOPSO）[J].Computers and Mathematics with Applications，2009，57：1995-2000.

[11]尚榮華，焦李成，公茂果，等.免疫克隆算法求解動態多目標優化問題[J].軟件學報，2007，11（8）：2700-2711.

[12]Gong M G，Jiao L C，Du H F，et al.Multi-objective immune algorithmwithPareto-optimal neighbor-basedselection[J]. Evolutionary Computation，2008，16（2）：225-255.

[13]De Castro L N，Timmis J.Artificial immune systems：a new computational intelligence approach[M].Berlin：Springer-Verlag，2002.

[14]Zitzler E，Deb K，Thiele L.Comparison of multiobjective evolutionary algorithms：empirical results[J].Evolutionary Computation，2000（8）：173-195.

[15]Deb K，Thiele L，Laumanns M，et al.Scalable multi-objective optimization test problems[C]//Proceedings of the IEEE Congress on Evolutionary Computation（CEC 2002）.Piscataway：IEEE Service Center，2002：825-830.

[16]Veldhuizen D A V，Lamont G B.Multi objective evolutionary algorithmresearch：ahistoryandanalysis[R].AirForce Institute，Wright-Patterson AFB，OH，1998.

[17]Schott J R.Fault tolerant design using single and multi criteria genetic algorithm optimization[D].Massachusetts：Cambridge University，1995.

1.School of Physics and Optoelectronic Engineering,Ludong University,Yantai,Shandong 264025,China
2.Informatizatiion Support Center of China Unicom,Yantai,Shandong 264001,China
3.School of Information Science and Engineering,Ludong University,Yantai,Shandong 264025,China

In order to solve the problems of loss in diversity and poor distribution of Pareto solutions in Multi-Objective Particle Swarm Optimization（MOPSO）,a hybrid global best selecting strategy is proposed.Each particle’s global best is selected according to information entropy or Sigma value of solutions with a varying selecting probability.And clone selection strategy is used to update Pareto solution set according to dominance relationships.As a result,the better distributed solutions are exploited. Results on several benchmark functions show that the proposed algorithm has better distribution performance while maintains a good convergence.This indicates that the proposed hybrid strategy is effective in improving the diversity and distribution of MOPSO.

multi-objective optimization;particle swarm optimization;information entropy;clone selection

為解決多目標粒子群優化算法存在解的多樣性差、分布不均等問題，提出一種混合擇優機制：在迭代過程中每個粒子依概率，根據解集信息熵或Sigma值確定其全局極值；并直接對解集進行基于信息熵的克隆選擇，根據支配關系更新解集，充分發掘分布性更好的解。測試函數的仿真實驗結果表明，該算法在保持較好的收斂性能的同時，其求解的分布性指標要明顯優于其他算法，這說明混合擇優機制能夠有效地提升多目標粒子群優化算法求解的多樣性和分布性。

多目標優化；粒子群；信息熵；克隆選擇

A

TP301

10.3778/j.issn.1002-8331.1204-0086

ZHONG Zhaoming,LI Xiangyang,PANG Shan.Multi-objective immune particle swarm optimization algorithm with a hybird global best selecting strategy.Computer Engineering and Applications,2013,49（13）：43-47.

國家自然科學青年基金（No.61102167）；山東省科技發展計劃項目（No.2011YD04049）。

仲昭明（1963—），男，副教授，研究方向為智能算法及應用。E-mail：zzm2538@163.com

2012-04-09

2012-06-13

1002-8331（2013）13-0043-05

CNKI出版日期：2012-08-06http://www.cnki.net/kcms/detail/11.2127.TP.20120806.1442.020.html