生物地理學(xué)優(yōu)化算法中基于Zoutendijk可行方向法的變異算子設(shè)計(jì)

王月嬌，劉三陽(yáng)(西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 陜西 西安 710126)

生物地理學(xué)優(yōu)化算法中基于Zoutendijk可行方向法的變異算子設(shè)計(jì)

王月嬌，劉三陽(yáng)
(西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 陜西 西安 710126)

根據(jù)約束優(yōu)化問(wèn)題的全局收斂性要求，基于傳統(tǒng)優(yōu)化與智能優(yōu)化,設(shè)計(jì)了一種基于Zoutendijk可行方向法的新型變異算子，并將其應(yīng)用于生物地理學(xué)優(yōu)化算法，構(gòu)建了一種用混合優(yōu)化算法求解優(yōu)化問(wèn)題的方法.通過(guò)算子設(shè)計(jì)策略的理論驗(yàn)證、智能算法的收斂性分析及6個(gè)不同類型算例的仿真試驗(yàn)，證明此自適應(yīng)求解優(yōu)化問(wèn)題機(jī)制具有實(shí)效性.

約束優(yōu)化；Zoutendijk可行方向法；變異算子；生物地理學(xué)優(yōu)化算法

約束優(yōu)化模型：

(1)

其中，x∈X∈Rn,y∈Y∈Rm是決策變量，X與Y為變量的上下界約束.F：Rn×Rm→R1和G：Rn×Rm→R1分別為目標(biāo)函數(shù)和約束函數(shù).求解此優(yōu)化模型，常用基于梯度的傳統(tǒng)優(yōu)化算法，雖然收斂速度較快，但對(duì)于目標(biāo)函數(shù)的可微和凸性要求較高，易陷入局部最優(yōu)，因而大多不太適合全局性優(yōu)化問(wèn)題求解.而智能算法對(duì)優(yōu)化函數(shù)的連續(xù)、可微等性質(zhì)要求較低，具有對(duì)函數(shù)性態(tài)的依賴性較小、不需要使用梯度以及適用范圍廣、魯棒性好等優(yōu)點(diǎn)，故具有廣闊的應(yīng)用前景.

美國(guó)Cleveland 州立大學(xué)Dan Simon 教授于2008年提出了一種新型的基于種群的全局智能進(jìn)化算法[1-2]——生物地理學(xué)優(yōu)化算法 (biogeography-based optimization，BBO)，用于求解無(wú)約束優(yōu)化問(wèn)題.該算法作為一種模擬生物進(jìn)化過(guò)程的隨機(jī)化搜索算法[3]與其他智能算法(如ACO、PSO、DE、GA等)相比具有良好的收斂性和穩(wěn)定性，且算法結(jié)構(gòu)簡(jiǎn)單、易于實(shí)現(xiàn)，近年來(lái)因其獨(dú)特的搜索機(jī)制和較好的性能在傳感器選擇、電力系統(tǒng)優(yōu)化和動(dòng)態(tài)網(wǎng)絡(luò)的社區(qū)監(jiān)測(cè)等領(lǐng)域得到了廣泛應(yīng)用[4-5].

BBO算法由ps個(gè)棲息地組成，每個(gè)棲息地由n維適宜度指數(shù)向量SIV(suitable index vector)組成[6]，用向量xi=(xi1,xi2，…，xin)，i=1,2，…，ps表示優(yōu)化問(wèn)題在n維搜索空間的一個(gè)潛在可行解.

約束優(yōu)化問(wèn)題的應(yīng)用非常廣泛，其解法形式多樣，但目前尚無(wú)對(duì)所有問(wèn)題都普遍有效的算法，而且求得的解多是局部最優(yōu)解.主流的求解方法主要包括內(nèi)點(diǎn)法、外點(diǎn)法、可行方向法及梯度投影法等，而智能算法能在對(duì)目標(biāo)函數(shù)性質(zhì)要求較少的情況下，從不同角度用不同策略對(duì)算法進(jìn)行改進(jìn)，取得了較好的全局最優(yōu)解.但是，對(duì)于約束優(yōu)化問(wèn)題，僅用智能算法對(duì)變量進(jìn)行搜索，計(jì)算量大且難以驗(yàn)證進(jìn)化得到的點(diǎn)是否滿足最優(yōu)性約束.受多種改進(jìn)算法的啟發(fā)[7-9]，將傳統(tǒng)算法與智能算法[10-11]相結(jié)合，設(shè)計(jì)了一種新型的自適應(yīng)求解優(yōu)化問(wèn)題的機(jī)制.

1 基于Zoutendijk可行方向法的變異算子設(shè)計(jì)

Zoutendijk可行方向法已發(fā)展成為求解約束優(yōu)化問(wèn)題的一類重要方法[12]，其基本思想是： 在給定一個(gè)可行點(diǎn)x(k)之后，用求解線性規(guī)劃問(wèn)題的方法來(lái)確定改進(jìn)的可行方向dk，然后沿方向dk求解有約束的線搜索問(wèn)題，得到極小點(diǎn)λk，令x(k+1)=x(k)+λkdk，如果x(k+1)仍不是最優(yōu)解，則重復(fù)上述步驟.

利用Zoutendijk可行方向法設(shè)計(jì)變異算子，并將其移植到BBO中，從而建立一種新型混合算法，對(duì)優(yōu)化問(wèn)題進(jìn)行求解.

1.1 變異算子設(shè)計(jì)

算法1基于Zoutendijk可行方向法的變異算子.

Step1更新每個(gè)棲息地i容納si種生物種群的概率p(si)，計(jì)算每個(gè)棲息地的突變率m(si)(參考算法2).對(duì)于k個(gè)精英棲息地，令m(si)=0，然后突變每一個(gè)非精英棲息地 ，用m(si)判斷棲息地i的某個(gè)特征分量是否發(fā)生了突變.

Step3對(duì)于最小適宜度函數(shù)模型

(2)

(3)

下面通過(guò)具體算例來(lái)描述當(dāng)前個(gè)體是如何進(jìn)化為下一個(gè)個(gè)體的.

此處將求取積極約束的系數(shù)矩陣，判斷個(gè)體是否在可行域內(nèi)部轉(zhuǎn)化為確定指標(biāo)集，即I(x(k))={i|gi(x(k))=0}是否為空集，若I(x(k))≠?，則變異的個(gè)體在某些約束的邊界上，此時(shí)可以通過(guò)求解構(gòu)造的線性規(guī)劃問(wèn)題的最優(yōu)解得到改進(jìn)的可行方向，即d(k)，若I(x(k))=?，則個(gè)體在可行域的內(nèi)部，令d(k)=-f(x(k)).

1.2 混合BBO算法構(gòu)建

算法2基于新型變異算子的混合BBO算法.

Step1初始化.設(shè)定棲息地?cái)?shù)量ps，優(yōu)化問(wèn)題的維數(shù)n， 最大種群數(shù)量Smax，最大突變率mmax和最大迭代次數(shù).隨機(jī)生成初始種群xi=(xi1,xi2,…，xin)，i=1,2,…,ps.令k=0.

Step3映射Cost(xi,yi)到種群數(shù)量Si，計(jì)算遷入率λ(si)、遷出率μ(si) 和棲息地i容納si種生物種群的概率p(si)，i=1,2,…,ps.

Step4遷移操作：

對(duì)i=1,2,…,ps，利用Pmod選取棲息地對(duì)i執(zhí)行遷入操作.

對(duì)j=1,2,…,n，若rand(ps,n)<λi，選取棲息地i的特征分量(x,y)ij執(zhí)行遷入操作.

若rand(ps,n)<λi，則利用其他棲息地的遷出率進(jìn)行輪盤選擇，選出棲息地k，令 (x,y)ij=(x,y)k,j.

Step5變異操作：

對(duì)i=ps/2 tops，計(jì)算

Step6是否滿足停止條件，如不滿足，令k=k+1，轉(zhuǎn)回Step2，否則輸出迭代過(guò)程中的最優(yōu)解.

2 算法的理論分析

算法1的理論驗(yàn)證：

與式(2)等價(jià)的最小化適宜度函數(shù)模型：

(4)

然后,求解以下與式(3)等價(jià)的一般最小化問(wèn)題：

(5)

下面給出1)和2)的證明.

證明假設(shè) (x,y)是式(4)的K-T點(diǎn)，則存在(wpq)Τ>0滿足

非線性不等式組：

根據(jù)Farkas 擇一性定理，知

無(wú)解.即

無(wú)解.

算法2的全局收斂性分析見(jiàn)文獻(xiàn)[13-15]中的解釋.

3 數(shù)值仿真與分析

為驗(yàn)證算法的有效性，從文獻(xiàn)[16-19]中選取6個(gè)算例進(jìn)行數(shù)值試驗(yàn)，使用Matlab編制仿真程序，并在CPU 為3.20 GHz ，RAM為2.00 GB 的PC機(jī)上進(jìn)行測(cè)試.在算法中取系統(tǒng)遷移率Pmod=1，系統(tǒng)突變率mmax=0.005，精英個(gè)體留存數(shù)k=2，種群數(shù)量ps=50，最大迭代次數(shù)10 000，精確度ε=1.0e-006.

每個(gè)問(wèn)題獨(dú)立運(yùn)行30次，記錄其中的最優(yōu)解、最差解以及對(duì)應(yīng)的目標(biāo)函數(shù)值，并記錄得到最優(yōu)解的運(yùn)行時(shí)間.獨(dú)立運(yùn)行30次，每個(gè)算例的最優(yōu)結(jié)果與文獻(xiàn)值的對(duì)比情況列于表1.

表1 測(cè)試結(jié)果Table 1 Test result

從表1中不難得到，自適應(yīng)算法能夠得到問(wèn)題的已知最優(yōu)解，算例1和4得到的結(jié)果與文獻(xiàn)的最優(yōu)解和最優(yōu)值非常吻合；算例2在初始化時(shí)就已經(jīng)收斂到最優(yōu)解，可知具有很好的收斂穩(wěn)定性；算例3得到的最優(yōu)解不在下層問(wèn)題的可行域內(nèi)，但與文獻(xiàn)的最優(yōu)解和最優(yōu)值很接近，這可能由算法本身的缺陷所致.算例5和6的最優(yōu)解雖然與文獻(xiàn)最優(yōu)解相差較大，但其最優(yōu)值卻比較相近.由此可知，本文算法具有較優(yōu)的運(yùn)行結(jié)果和較短的運(yùn)行時(shí)間.

表中數(shù)據(jù)雖未與主流算法的性能進(jìn)行比較，但文獻(xiàn)的最優(yōu)值已經(jīng)能夠代表當(dāng)前約束優(yōu)化問(wèn)題的求解程度，同時(shí)主流算法的計(jì)算過(guò)程并不都適用本算例.另外，本文將智能算法和可行方向法相結(jié)合的模式，從理論上已經(jīng)體現(xiàn)了其優(yōu)點(diǎn)，顯然本文算法在變異算子的選擇上較單純使用智能算法具有更多優(yōu)勢(shì)，也更合理.

4 結(jié) 論

生物地理學(xué)優(yōu)化算法作為一種新穎的優(yōu)化方法，憑借其可靠有效的性能在求解一般優(yōu)化問(wèn)題上已超越傳統(tǒng)優(yōu)化算法.將經(jīng)典Zoutendijk可行方向法的變異算子設(shè)計(jì)為智能算法求解約束優(yōu)化問(wèn)題.理論驗(yàn)證和收斂性分析為進(jìn)一步的仿真實(shí)驗(yàn)提供了理論基礎(chǔ)，數(shù)值實(shí)驗(yàn)有效論證了本自適應(yīng)算法機(jī)制具有一定的實(shí)效性.

因BBO算法的研究剛剛起步，有很多問(wèn)題需要探索和解決： 比如棲息地的數(shù)量，即種群規(guī)模和遷移模型對(duì)算法性能和效率的影響；將BBO算法與其他傳統(tǒng)優(yōu)化算法進(jìn)行不同程度的組合；為構(gòu)建更有效的算法機(jī)制提供正確合理的算法理論研究等.本研究并未將BBO與其他優(yōu)化算法相結(jié)合，從而形成正面的直接的對(duì)比，但所提方法已為后續(xù)研究構(gòu)建了一個(gè)將智能算法與傳統(tǒng)優(yōu)化算法有效結(jié)合的框架，這也是筆者今后重點(diǎn)研究的方向.

[1] SIMON D.Biogeography-based optimization[J].IEEETransactionsonEvolutionaryComputation,2008,12(6)： 702-713.

[2] 王存睿，王楠楠，段曉東,等.生物地理學(xué)優(yōu)化算法綜述[J]．計(jì)算機(jī)科學(xué),2010,37(7)： 34-38．

WANG C R,WANG N N,DUAN X D,et al.Survey of biogeography-based optimization[J].ComputerScience,2010,37(7)： 34-38.

[3] 封全喜.生物地理學(xué)優(yōu)化算法研究及其應(yīng)用[D].西安： 西安電子科技大學(xué)，2014.

FENG Q X.ResearchonBiogeography-BasedOptimizationandItsApplication[D].Xi’an： Xidian University,2014.

[4] ZHOU X,LIU Y H,LI B,et al.Multiobjective biogeography based optimization algorithm with decomposition for community detection in dynamic networks[J].PhysicaAStatisticalMechanicsandItsApplications,2015,436： 430-442.

[5] GOLAFSHANI E M.Introduction of biogeography-based programming as a new algorithm for solving problems[J].AppliedMathematicsandComputation,2015,270(C)： 1-12.

[6] 張建科.生物地理學(xué)優(yōu)化算法研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2011,32(7)： 2497-2500.

ZHANG J K.Research on optimization algorithm for biogeography[J].ComputerEngineeringandDesign,2011,32(7)： 2497-2500.

[7] YOU X M,HAO F C,MA Y H.A hybrid differential evolution algorithm solving complex multimodal optimization problems[J].JournalofInformationandComputationalScience,2015,12(13)： 5175-5182.

[8] ZHANG S,LIU S Y.Artificial bee colony algorithm with improved search equations[J].JournalofInformationandComputationalScience,2015,12(10)： 4069-4076.

[9] WAN Z P,WANG G M,SUN B.A hybrid intelligent algorithm by combining particle swarm optimization with chaos searching technique for solving nonlinear bilevel programming problems[J].Compstat2006-ProceedingsinComputationalStatistics,2013(8)： 26-32.

[10] LI H C.An evolutionary algorithm for multi-criteria inverse optimal value problems using a bilevel optimization model[J].AppliedSoftComputing,2014,23(23)： 308-318.

[11] KUO R J,LEE Y H,ZULVIA F E,et al. Solving bi-level linear programming problem through hybrid of immune genetic algorithm and particle swarm optimization algorithm[J].AppliedMathematicsandComputation,2015,266(C)： 1013-1026.

[12] 唐煥文，秦學(xué)志.實(shí)用最優(yōu)化方法[M].第3版.大連： 大連理工大學(xué)出版社，2004.

TANG H W,QIN X Z.PracticalMethodsofOptimization[M].3rd ed. Dalian： Dalian University of Technology Press,2004.

[13] 李和成.非線性雙層規(guī)劃問(wèn)題的遺傳算法研究[D].西安： 西安電子科技大學(xué)，2009.

LI H C.ResearchonGeneticAlgorithmofNonlinearBilevelProgramming[D].Xi’an： Xidian University,2009.

[14] WANG Y P,DANG C Y.An evolutionary algorithm for global optimization based on level-set evolution and Latin squares[J].IEEETransactionsonEvolutionaryComputation,2007(11)： 579-595.

[15] WANG Y P,LI H,DANG C Y.A new evolutionary algorithm for a class of nonlinear bilevel programming problems and its global convergence[J].InformsJournalonComputing,2011,23(4)： 618-629.

[16] WANG Y P,JIAO Y C,LI H.An evolutionary algorithm for solving nonlinear bilevel programming based on a new constraint-handling scheme [J].IEEETransactionsonSystems,ManandCybernetics,2005,35(2)： 221-232.

[17] ZHONG W J,XU N R.Boltzmann machine approach of bilevel programming [J].JournalofSystemsEngineering,1995,10(1)： 7-13.

[18] ZHENG P E,LIUG H,LI R B.The solution of a class of bilevel programming based on hierarchical optimization algorithm [J].SystemsEngineeringandElectronics,2005,27(4)： 662-665.

[19] BJORNDAL M,JORNSTEN K.The deregulated electricity market viewed as a bilevel programming problem [J].JournalofGlobalOptimization,2005,33(3)： 465-475.

WANG Yuejiao,LIU Sanyang
(SchoolofMathematicsandStatistics,XidianUniversity,Xi’an710126,China)

The article deals with a class of nonlinear constraint programming problems， and a new hybrid biogeography-based optimization algorithm is proposed to search for the value of the variables. To meet the global convergence requirements of the constraint optimization problem， a new efficient mutation operator based on Zoutendijk feasible direction method is designed by integrating the advantages of traditional and intelligent optimization so that it can generate high quality potential offspring. Then, a hybrid biogeography-based optimization algorithm is constructed to search for the optimal solution of the constraint programming. Furthermore， a specific example is demonstrated which shows that our new mechanism can be easily used to force the individuals moving toward the feasible region and improve the feasible solutions gradually. The theoretical identification of operator design strategy， convergence analysis of intelligent algorithm and simulation experiment on six different types of numerical examples verify the effectiveness of the proposed adaptive mechanism in solving optimization problem．

constraint optimization; Zoutendijk feasible direction method; mutation operator; biogeography-based optimization

2016-06-28.

國(guó)家自然科學(xué)基金資助項(xiàng)目(61373174)； 中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(JB150716).

王月嬌(1991—)，ORCID： http： //orcid.org/0000-0001-5910-9439,女，碩士，主要從事最優(yōu)化理論與智能算法設(shè)計(jì)研究,E-mail： xd07101051@126.com.

10.3785/j.issn.1008-9497.2018.01.005

O 224; TP 393

A

1008-9497(2018)01-023-06

AnewmutationoperatordesignedbyZoutendijkfeasibledirectionmethodinbiogeography-basedoptimization.Journal of Zhejiang University (Science Edition),2018,45(1)： 023-028