仲昭明,李向陽,逄珊
ZHONG Zhaoming1,LI Xiangyang2,PANG Shan3
1.魯東大學(xué) 物理與光電工程學(xué)院,山東 煙臺(tái) 264025 2.煙臺(tái)聯(lián)通信息化支撐中心,山東 煙臺(tái) 264001
3.魯東大學(xué) 信息科學(xué)與工程學(xué)院,山東 煙臺(tái) 264025
混合擇優(yōu)的多目標(biāo)免疫粒子群優(yōu)化算法
仲昭明1,李向陽2,逄珊3
ZHONG Zhaoming1,LI Xiangyang2,PANG Shan3
1.魯東大學(xué) 物理與光電工程學(xué)院,山東 煙臺(tái) 264025 2.煙臺(tái)聯(lián)通信息化支撐中心,山東 煙臺(tái) 264001
3.魯東大學(xué) 信息科學(xué)與工程學(xué)院,山東 煙臺(tái) 264025
很多實(shí)際工程問題需要同時(shí)優(yōu)化多個(gè)目標(biāo),這類問題稱為多目標(biāo)優(yōu)化問題。由于存在多個(gè)相互沖突的目標(biāo),此類問題不存在單個(gè)解滿足所有目標(biāo),而存在一個(gè)折衷解的集合,稱為Pareto最優(yōu)解集或非支配解集[1]。
進(jìn)化算法是基于種群的智能優(yōu)化算法,一次運(yùn)行能夠求得問題的多個(gè)解,很適合求解多目標(biāo)優(yōu)化問題。目前已被成功應(yīng)用于多目標(biāo)優(yōu)化領(lǐng)域,并發(fā)展成為一個(gè)新的研究方向:進(jìn)化多目標(biāo)優(yōu)化[2-3]。近年來,一些新的智能算法被引入多目標(biāo)優(yōu)化問題的求解,其中基于粒子群的多目標(biāo)優(yōu)化是近年來逐步發(fā)展起來的一個(gè)新興研究方向。同進(jìn)化算法相比,粒子群算法由于具有控制參數(shù)少以及收斂速度快等優(yōu)點(diǎn)得到迅速發(fā)展。
但由于粒子群的單項(xiàng)信息共享機(jī)制。算法在多目標(biāo)優(yōu)化過程中經(jīng)常會(huì)遇到早熟收斂等問題[4]。并且群中每個(gè)粒子都在解集中各自的全局極值的指導(dǎo)下搜索,如果最優(yōu)解的選取不當(dāng),難以獲得均布性好的解。因此如何選擇粒子的全局極值是十分重要的,對于多目標(biāo)優(yōu)化算法解的收斂性和多樣性都有很大影響。
為此本文提出一種基于解集信息熵和Sigma值[5]的混合擇優(yōu)機(jī)制:種群的粒子以一定概率,根據(jù)解集中解的信息熵值或Sigma值選擇其全局極值,并且在迭代不同階段側(cè)重不同的選擇原則。該機(jī)制充分利用信息熵的密度定義能更好地描述解集分布情況[6]以及Sigma值有助于加速收斂的優(yōu)點(diǎn),兼顧了算法的全局和局部搜索能力,有效地改善了解的分布性和收斂性。同時(shí),引入免疫理論中的克隆選擇機(jī)制直接對解集進(jìn)行選擇搜索,進(jìn)一步提高了算法的分布性。
2.1 典型的選擇機(jī)制分析
粒子全局極值的選取對多目標(biāo)粒子群優(yōu)化算法解集的收斂性和分布性都有很大的影響。早期,由Coello[7]等提出的MOPSO借用了PAES[8]等進(jìn)化多目標(biāo)優(yōu)化算法的檔案進(jìn)化策略,將自適應(yīng)網(wǎng)格法用于解集的維護(hù)。把解集劃分為網(wǎng)格,根據(jù)網(wǎng)格內(nèi)解的個(gè)數(shù)設(shè)定解的適應(yīng)度值,網(wǎng)格內(nèi)解越多其適應(yīng)度值越小,對所有網(wǎng)格應(yīng)用輪盤賭方法選擇粒子的全局極值。這種方法比較簡單,但由于解是隨機(jī)選擇的,因此算法的收斂性有待提高。Raquel[9]等人將NSGA-II中的擁擠距離的概念引入,得到CD-MOPSO。對解集中解的擁擠距離進(jìn)行排序,據(jù)此選擇全局極值,其解的分布性較好,但收斂性仍有待提高。此外應(yīng)用較為廣泛的選擇機(jī)制還包括支配樹機(jī)制和Sigma機(jī)制。支配樹機(jī)制通過設(shè)計(jì)支配樹的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)精英解,為粒子選取最優(yōu)經(jīng)驗(yàn),指導(dǎo)粒子飛行。這種機(jī)制比Coello的網(wǎng)格機(jī)制在解的收斂性上有所提高,但其自身也存在不足:未考慮解的分布情況。Sigma機(jī)制則引入?yún)?shù)“σ”來比較粒子和解在空間上的位置關(guān)系。如圖1所示的二維情況為例,參數(shù)σ的定義為:
圖1 Sigma機(jī)制示意圖
通過比較群中粒子和解集中解的σ值,選取二者差值最小的解為全局極值。被選擇的全局極值指導(dǎo)粒子沿著直線方向直接逼近Pareto前沿,收斂性較好。但由于Sigma機(jī)制未考慮到解的密度信息,在解集中粒子分布不均勻的情況下,容易出現(xiàn)早熟收斂現(xiàn)象,其全局搜索能力有待提高。
為改善算法的性能,一些學(xué)者提出將上述機(jī)制混合使用,如Junjie[10]等人提出的混合機(jī)制,在Sigma機(jī)制的基礎(chǔ)上綜合考慮解的密度信息,在保持算法收斂性的前提下提高了解集的分布性。但該機(jī)制中的關(guān)于解的密度定義過于簡單,有些情況下難以體現(xiàn)解的實(shí)際分布情況,并且在每次迭代過程都要進(jìn)行混合適應(yīng)度計(jì)算,計(jì)算量較大。
2.2 混合選擇機(jī)制
通過對現(xiàn)有選擇機(jī)制的分析可知:好的選擇機(jī)制應(yīng)該能夠選擇合適的全局極值引導(dǎo)粒子迅速向Pareto前沿飛行,同時(shí)還應(yīng)考慮算法的分布性,盡量選擇那些分布比較稀疏的解,使粒子向解空間更廣泛的區(qū)域進(jìn)行探索。
為此本文提出一種全局極值的混合選取機(jī)制:在每次迭代中粒子依一定概率,根據(jù)解集中解的信息熵或者Sigma值選擇全局極值。而該選擇概率則隨著迭代的進(jìn)行而不斷調(diào)整:在迭代初期基于信息熵的選擇概率較大,選擇分布性好的解作為全局極值,以使粒子盡量在解空間全面的探索,提高解集分布性;而在迭代后期則加大基于Sigma值的選擇概率,使得種群快速向Pareto前沿逼近,提高解集的收斂性。本文的選擇概率如下:
其中,Rand為[0,1]間的隨機(jī)數(shù),max_iteration為最大迭代次數(shù),iteration為當(dāng)前迭代次數(shù)。
對于種群中的每次迭代,在種群的N個(gè)粒子中,隨機(jī)選擇Nσ個(gè)粒子按照Sigma機(jī)制,從解集中選擇Sigma值最為接近的作為全局極值。而剩余粒子則按照信息熵值,利用輪盤賭的方法選擇全局極值。其中Nσ按照下式計(jì)算:
信息熵的計(jì)算:為了保持解集的分布性,許多基于密度或分布的全局極值選擇機(jī)制被提出,然而這些機(jī)制對于解集中解的密度定義過于簡單,某個(gè)解的密度只取決于直接相鄰的解,而沒有考慮到更遠(yuǎn)處解的分布情況。信息熵比傳統(tǒng)的擁擠距離等密度定義能更好地描述某個(gè)解對于解集分布情況的貢獻(xiàn)。因此,為了更準(zhǔn)確地反映解集中解的實(shí)際分布情況,本文引入信息熵的概念,采用Parzen窗估計(jì)法來計(jì)算熵值。熵值量化每一個(gè)解對Pareto解集分布的貢獻(xiàn)。
Pareto解集可表示為Y={yi|i=0,1,…,|Y},用pyi=P (yi∈Y)表示解集中每個(gè)解yi的概率。其熵值為:
其概率計(jì)算采用Parzen窗函數(shù)計(jì)算。Parzen窗估計(jì)法是一種具有堅(jiān)實(shí)理論基礎(chǔ)和優(yōu)秀性能的非參數(shù)函數(shù)估計(jì)方法,它能夠較好地描述多維數(shù)據(jù)的分布狀態(tài),其基本思想就是利用一定范圍內(nèi)各點(diǎn)密度的平均值對總體密度函數(shù)進(jìn)行估計(jì)。Parzen窗定義如下。
解的概率密度估計(jì)為:
其中K是核函數(shù),基于正態(tài)函數(shù)的平滑性將使得估計(jì)函數(shù)變化平滑,本文采用正態(tài)窗核函數(shù):
其中m為目標(biāo)空間維度,σ是核寬,σ∈Rm。核寬的設(shè)置對Parzen窗計(jì)算影響較大,這里根據(jù)解空間的大小做適應(yīng)性變化:
其中maxj和minj分別表示解集中第j維的最大、最小值。
計(jì)算完解集的信息熵后,粒子用輪盤賭的方法選擇其全局極值,信息熵越大,密度分布越好,被選為粒子全局極值的概率就越大。
為了改善粒子群的搜索能力,文獻(xiàn)[11-12]將人工免疫系統(tǒng)中的克隆選擇機(jī)制應(yīng)用到標(biāo)準(zhǔn)的粒子群算法當(dāng)中,其基本思想是:在粒子群進(jìn)化的每一代,選擇最好的若干粒子作為抗體,抗體的適應(yīng)度函數(shù)越大,產(chǎn)生的克隆體越多。這樣粒子群算法在縱向完成對整個(gè)解空間搜索的同時(shí),克隆選擇算子橫向地進(jìn)行局部搜索,提高算法的局部搜索能力。
本文借鑒這種思想,但是根據(jù)多目標(biāo)優(yōu)化的特點(diǎn)對克隆選擇機(jī)制進(jìn)行調(diào)整:克隆選擇不是應(yīng)用于種群,而是直接應(yīng)用于解集,根據(jù)解集中解的信息熵而非適應(yīng)度排序。針對信息熵值最高的前m個(gè)解,每個(gè)解的生成l個(gè)克隆體,然后對所有的克隆體進(jìn)行變異。算法采用的是與適應(yīng)度值有關(guān)的變異算子[13]。
其中N(0,1)是均值為0,標(biāo)準(zhǔn)差為1的Guass隨機(jī)變量;β是用于控制指數(shù)函數(shù)衰減的變量,是經(jīng)過規(guī)范化處理的克隆的各維度適應(yīng)度值。
對每個(gè)解和其克隆體進(jìn)行比較,如果出現(xiàn)支配原解的克隆體,則用克隆體代替原解。這樣經(jīng)過對解集的克隆選擇可以獲得更為接近Pareto前沿的解集,并且克隆是針對解集中分布較好的若干解直接進(jìn)行,比對種群進(jìn)行克隆的效果更為直接。
基于混合擇優(yōu)和克隆選擇的多目標(biāo)粒子群可由以下步驟描述:
(1)初始化粒子群P,確定種群規(guī)模為N,初始Pareto解集置空。
(2)計(jì)算每個(gè)粒子的適應(yīng)度。
(3)根據(jù)Pareto支配關(guān)系對解集進(jìn)行更新,若超出數(shù)量限制則進(jìn)行修剪。
(4)利用混合機(jī)制,根據(jù)每個(gè)粒子的選擇概率基于Sigma值或者信息熵值選擇全局極值值。
(5)對粒子群中每個(gè)粒子的速度和位置進(jìn)行更新。
(6)更新粒子歷史最優(yōu)值。
(7)Pareto解集進(jìn)行克隆選擇,用支配占優(yōu)的克隆代替原來的解。
(8)判斷是否達(dá)到最大迭代次數(shù),若是,結(jié)束,輸出Pareto最優(yōu)解集;否則,令iter=iter+1,轉(zhuǎn)(2)。
4.1 實(shí)驗(yàn)設(shè)置和性能評價(jià)指標(biāo)
為比較所提出算法(Es-MOPSO)的性能,選擇Sigma機(jī)制的σ-MOPSO和文獻(xiàn)[10]的Nv-MOPSO算法進(jìn)行對比。為了比較的公平性,三種算法的種群、Pareto解集的規(guī)模和迭代次數(shù)均相同。其中種群和解集的規(guī)模均設(shè)置為100,最大迭代次數(shù)為200;算法速度更新公式中,慣性權(quán)重ω=0.6,c1=c2=2。本文算法指數(shù)衰減控制系數(shù)β取100,在解集粒子克隆選擇個(gè)數(shù)m取15(即種群粒子數(shù)的15%)。
性能仿真實(shí)驗(yàn)選取較為常用的測試函數(shù):ZDT1~ZDT4[14],DTLZ1和DTLZ2[15]。這些測試函數(shù)均有已知的Pareto前沿。本文ZDT1~ZDT3測試函數(shù)的決策數(shù)n取20,ZDT4的n取10。對于DTLZ函數(shù)n=k+|xk|-1,本文中取k=3,|xk|=5。
性能評價(jià)指標(biāo)如下所示。
收斂性指標(biāo)Generational Distance(GD)[16]:
其中n是解集中解的數(shù)目,di是每個(gè)解距離已知Pareto前沿的最小歐幾里得距離。GD值越小說明算法的解集越靠近Pareto前沿。
分布指標(biāo)SP(Spacing)[17]:
最大展布指標(biāo)MS(Maximum Spread)[14](該度量指標(biāo)用于衡量所得解對Pareto前沿的覆蓋程度):
4.2 實(shí)驗(yàn)結(jié)果分析
為減少隨機(jī)因素的影響,三種算法對每個(gè)測試函數(shù)均獨(dú)立運(yùn)行20次。表1和表2分別是三種算法對各測試函數(shù)運(yùn)算結(jié)果的收斂性指標(biāo)、分布指標(biāo)的平均值和標(biāo)準(zhǔn)差值的比較。
從表1中可以發(fā)現(xiàn),對于收斂性指標(biāo)GD,本文算法對所有測試函數(shù)的結(jié)果都明顯優(yōu)于Nv-MOPSO算法。和σ-MOPSO相比,除了測試函數(shù)ZDT1和ZDT3是σ-MOPSO取得了最優(yōu)結(jié)果,其余測試函數(shù)則是本文算法取得最優(yōu)結(jié)果,但是和σ-MOPSO算法差別不大。從表2中可以發(fā)現(xiàn),對于分布指標(biāo)SP,本文算法所有的測試函數(shù)均得到了最優(yōu)結(jié)果,較另外兩種算法有較為明顯的提高。對于最大展布指標(biāo),如表3所示,除了測試函數(shù)ZDT1外,本文算法對于其他測試函數(shù)均獲得了最優(yōu)結(jié)果,說明混合擇優(yōu)機(jī)制有助于發(fā)現(xiàn)邊界的解,提高解集的最大分布。
表1 三種算法計(jì)算得到GD指標(biāo)平均值和標(biāo)準(zhǔn)差值
表2 三種算法計(jì)算得到SP指標(biāo)平均值和標(biāo)準(zhǔn)差值
表3 三種算法計(jì)算得到MS指標(biāo)平均值和標(biāo)準(zhǔn)差值
圖2是三種算法對測試函數(shù)DTLZ2獨(dú)立運(yùn)行的某次運(yùn)行結(jié)果,其中,圖(a)、(b)、(c)分別對應(yīng)Es-MOPSO、Nv-MOPSO和σ-MOPSO。從圖2可以發(fā)現(xiàn),對于三維的測試函數(shù)DTLZ2,本文算法由于利用了信息熵表示解的分布情況,得到解集分布明顯比其他兩種算法的解集更為均勻。
Es-MOPSO算法的參數(shù)有初始種群規(guī)模,粒子群的加速系數(shù)c1、c2,慣性權(quán)重ω,克隆選擇機(jī)制中指數(shù)衰減控制系數(shù)β和克隆比例等。其中后兩個(gè)參數(shù)是本文引入的,因此重點(diǎn)針對這兩個(gè)參數(shù)對算法的影響進(jìn)行分析。
5.1 指數(shù)衰減控制系數(shù)β的影響
為研究β對算法性能的影響,分別取β為25~150,其他參數(shù)設(shè)置同前文。圖3為對ZDT4函數(shù)計(jì)算的GD和SP值的變化曲線。如圖可見,隨著β的增加,GD值減小,收斂性能得到改善,但是SP值增大,分布性變差(對DTLZ1等其他測試函數(shù)的驗(yàn)證也可以得到相同的結(jié)論,受篇幅限制未列出計(jì)算結(jié)果)。因此,綜合分析兩個(gè)性能的變化曲線,β值取100左右較為合適。
圖2 三種算法對DTLZ2函數(shù)計(jì)算得到Pareto解集分布情況
圖3 控制系數(shù)對算法收斂性和分布性指標(biāo)的影響
圖4 克隆比例對算法收斂性和分布性指標(biāo)的影響
5.2 克隆比例的影響
為研究克隆比例對算法性能的影響,m分別取5%~25%,其他參數(shù)設(shè)置同前文,對ZDT4進(jìn)行計(jì)算,計(jì)算得到的GD和SP值隨m的變化如圖4所示。從圖中可見,隨著m的增加,算法的收斂性和分布性都有所提高(對DTLZ1等其他測試函數(shù)的驗(yàn)證也可以得到相同的結(jié)論,受篇幅限制未列出計(jì)算結(jié)果)。當(dāng)m值達(dá)到15%~20%左右時(shí),算法的收斂性能和分布性能較好,如果再提高m,算法性能則沒有明顯提高且計(jì)算量增大,因此m值取15%~20%較為合理。
針對多目標(biāo)粒子群優(yōu)化算法在解的收斂性和分布性方面的存在的不足,設(shè)計(jì)了一種全局極值的混合選取機(jī)制:按照一定概率,根據(jù)解集中解的信息熵或σ值確定粒子的全局極值,選擇概率則隨迭代進(jìn)行變化,有效兼顧了解的分布性和收斂性。將免疫算法中克隆選擇機(jī)制引入算法,直接對解集中信息熵值高的解進(jìn)行克隆選擇,在增強(qiáng)局部搜索性能的同時(shí),進(jìn)一步提高了解集的分布性。在多個(gè)典型測試函數(shù)上進(jìn)行實(shí)驗(yàn),結(jié)果證明本文算法在保持較為優(yōu)越收斂性的同時(shí),顯著提高了解集的分布性。對混合擇優(yōu)的多目標(biāo)免疫粒子群算法進(jìn)行進(jìn)一步的理論分析和改進(jìn),并用于實(shí)際工程問題求解,擴(kuò)展其應(yīng)用范圍,將是下一步的研究內(nèi)容。
[1]公茂果,焦李成,楊咚咚,等.進(jìn)化多目標(biāo)優(yōu)化算法研究[J].軟件學(xué)報(bào),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]尚榮華,焦李成,公茂果,等.免疫克隆算法求解動(dòng)態(tài)多目標(biāo)優(yōu)化問題[J].軟件學(xué)報(bào),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
為解決多目標(biāo)粒子群優(yōu)化算法存在解的多樣性差、分布不均等問題,提出一種混合擇優(yōu)機(jī)制:在迭代過程中每個(gè)粒子依概率,根據(jù)解集信息熵或Sigma值確定其全局極值;并直接對解集進(jìn)行基于信息熵的克隆選擇,根據(jù)支配關(guān)系更新解集,充分發(fā)掘分布性更好的解。測試函數(shù)的仿真實(shí)驗(yàn)結(jié)果表明,該算法在保持較好的收斂性能的同時(shí),其求解的分布性指標(biāo)要明顯優(yōu)于其他算法,這說明混合擇優(yōu)機(jī)制能夠有效地提升多目標(biāo)粒子群優(yōu)化算法求解的多樣性和分布性。
多目標(biāo)優(yōu)化;粒子群;信息熵;克隆選擇
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.
國家自然科學(xué)青年基金(No.61102167);山東省科技發(fā)展計(jì)劃項(xiàng)目(No.2011YD04049)。
仲昭明(1963—),男,副教授,研究方向?yàn)橹悄芩惴皯?yīng)用。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