多項(xiàng)學(xué)習(xí)免疫優(yōu)化算法

張偉偉，林靜靜，景紅蕾，林雪潔

(1.鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院，河南 鄭州 450000；

?

多項(xiàng)學(xué)習(xí)免疫優(yōu)化算法

張偉偉1，林靜靜1，景紅蕾1，林雪潔2

(1.鄭州輕工業(yè)學(xué)院 計(jì)算機(jī)與通信工程學(xué)院，河南 鄭州 450000；

2.鄭州大學(xué) 電氣工程學(xué)院，河南 鄭州 450000)

提出了多項(xiàng)學(xué)習(xí)免疫優(yōu)化算法OL-CAIS求解全局優(yōu)化問(wèn)題.將混沌優(yōu)化理論加入到免疫算法中，同時(shí)在算法中引入一個(gè)類(lèi)雜交算子的搜索方程，更注重整個(gè)群體的交互信息，重新定義了搜索方式，然后，通過(guò)正交實(shí)驗(yàn)構(gòu)造一個(gè)正交學(xué)習(xí)策略充分利用了搜索空間中的有用信息、正交設(shè)計(jì)小樣本特性，產(chǎn)生更優(yōu)秀的子代，保證多樣化的有效搜索.

人工免疫；混沌優(yōu)化；雜交算子；正交學(xué)習(xí)

1986年Farmer發(fā)表的論文“The immune system,adaptation and machine learning”[1]中提出了一個(gè)基于Jerne的網(wǎng)絡(luò)假說(shuō)動(dòng)態(tài)免疫系統(tǒng)模型，并探討了免疫系統(tǒng)與其他智能方式的關(guān)聯(lián).由人體免疫系統(tǒng)的進(jìn)化理論，De Castor提出了人工免疫網(wǎng)絡(luò)模型(aiNet)，并為解決多模態(tài)函數(shù)優(yōu)化問(wèn)題作了進(jìn)一步的改進(jìn)，傳統(tǒng)aiNet優(yōu)化算法[2]由此誕生.李春華等[3]對(duì)親和力閾值、相似度閾值等幾個(gè)參數(shù)做了研究，提出了基于參數(shù)優(yōu)化的自適應(yīng)人工免疫算法.受微粒群優(yōu)化算法[4]啟發(fā)，引入精英學(xué)習(xí)機(jī)制，提出用于優(yōu)化問(wèn)題的高效人工免疫網(wǎng)絡(luò)算法(EaiNet)[5]，每個(gè)獨(dú)立的個(gè)體總是向種群中最優(yōu)秀的個(gè)體學(xué)習(xí)，從而提高了算法的收斂速度.但大量的研究也表明免疫算法也存在早熟收斂、搜索能力差、計(jì)算量大等諸多不足和缺憾.

基于前述的研究成果和存在的問(wèn)題，本文將對(duì)免疫系統(tǒng)主要的進(jìn)化算子進(jìn)行改進(jìn)，提出一種全新的具有基于多項(xiàng)學(xué)習(xí)的免疫優(yōu)化算法(OL-CAIS)，目的在于加快收斂速率、提高求解質(zhì)量.

1 相關(guān)基礎(chǔ)理論

1.1 全局優(yōu)化

全局優(yōu)化問(wèn)題是工程領(lǐng)域普遍存在的一類(lèi)數(shù)學(xué)規(guī)劃問(wèn)題，具有重要的研究意義.一般的全局優(yōu)化問(wèn)題可以描述為:

其中：N表示決策變量個(gè)數(shù)，f(x)為目標(biāo)函數(shù)，[lb,ub]為可行解空間.人工免疫算法是受生物免疫系統(tǒng)啟發(fā)而設(shè)計(jì)的一種新型智能優(yōu)化算法，采用群體搜索策略，在搜索過(guò)程中能夠更好的收斂到全局最優(yōu)解.

1.2 免疫系統(tǒng)

克隆選擇算法[6]是生物免疫算法中的基本算法之一.在克隆選擇算法中，需要解決的問(wèn)題被映射為抗原，問(wèn)題的解被映射為抗體.免疫克隆選擇算法的主要流程如算法1所示.

算法1 免疫克隆選擇算法Algorithm 1 Immune clonal selection computation

2 多項(xiàng)學(xué)習(xí)免疫優(yōu)化算法

2.1 混沌初始化種群

混沌(Chaos)變量看似雜論無(wú)章卻內(nèi)含規(guī)律.混沌理論可以用于免疫算法在解空間產(chǎn)生出均勻分布的初始種群，以提高免疫算法的計(jì)算精度和收斂速度[7].常用混沌動(dòng)力學(xué)映射分岔圖如下：

圖1 Logistic映射分岔圖Fig.1 Mapping bifurcation diagram of Logistic

圖2 Tent映射分岔圖Fig.2 Mapping bifurcation diagram of Tent

圖3 Cat映射分岔圖Fig.3 Mapping bifurcation diagram of Cat

圖4 三種映射取值分布曲線Fig.4 Mapping values distribution curve of Three kinds

圖5 Cat映射產(chǎn)生初始種群在解空間的分布Fig.5 Initial population distribution of Cat in the solution space

比較而言，Cat映射具有更好的均勻性且混沌優(yōu)化過(guò)程中不易陷入小循環(huán)，故采用經(jīng)典Cat映射模型來(lái)產(chǎn)生用于混沌免疫算法的初始種群.Cat映射模型計(jì)算公式如式1所示：

(1)

式中：n表示混沌變量的序號(hào)；i表示種群序號(hào)；(xn,yn)表示一個(gè)二維混沌變量. 設(shè)定種群規(guī)模為100，用式(1)混沌產(chǎn)生初始種群.圖5為初始種群在解空間的分布.

2.2 雜交算子的搜索方程

一些經(jīng)典免疫算法如opt-aiNet、IA-AIS使用的是單個(gè)種群，所有的抗體獨(dú)立進(jìn)化，這將降低收斂速度，引入學(xué)習(xí)機(jī)制，CAIS將免疫分為獲得性免疫和固有免疫，一個(gè)進(jìn)化后的子代不僅承載來(lái)自父代的變異信息，更注重整個(gè)群體的交互信息，同時(shí)為解決人工免疫算法在實(shí)際應(yīng)用中存在的缺點(diǎn)，如算法后期收斂速度較慢，搜索過(guò)程也可能出現(xiàn)早熟，最重要缺少交叉操作，這時(shí)候增加類(lèi)似交叉操作的雜交算子更能維持種群的多樣性.即:

Abi(t+1)=Abi(t)+G1·λi(t),innate and Abi(t+1)=Abr1(t)+φi,j(Abr1(t)-Abr2(t)),adaptive

(2)

2.3 OL策略

由于AIS算法較弱的學(xué)習(xí)機(jī)制，不能很好地執(zhí)行系統(tǒng)的搜索，故本文采用正交設(shè)計(jì)的方法形成一個(gè)正交學(xué)習(xí)(OL)策略來(lái)產(chǎn)生一個(gè)更優(yōu)秀的候選解.為了增加搜索的多樣性，當(dāng)執(zhí)行OL策略時(shí)，傳遞向量Ti通過(guò)下式產(chǎn)生：

Ti=Xk+rand(0,1)(Xbest-Xk),

(3)

每一維對(duì)實(shí)驗(yàn)的影響定義如下：

(4)

其中，fm表示第m次實(shí)驗(yàn)的結(jié)果；當(dāng)?shù)趍次實(shí)驗(yàn)中因素n的水平為q時(shí)，zmnq=1，否則，zmnq=0.

算法2 正交學(xué)習(xí)策略Algorithm 2 Orthogonal learning strategies

2.4 算法框架

本文提出了基于多項(xiàng)學(xué)習(xí)的免疫優(yōu)化算法OL-CAIS.利用免疫算法各環(huán)節(jié)具有很強(qiáng)的獨(dú)立性和擴(kuò)展性，提出將混沌優(yōu)化理論加入到免疫算法中，在算法中引入精英類(lèi)雜交算子的搜索方程，重新定義了搜索方式，為了充分利用搜索空間中的有用信息，通過(guò)正交設(shè)計(jì)構(gòu)造一個(gè)正交學(xué)習(xí)策略.正交學(xué)習(xí)策略利用正交設(shè)計(jì)小樣本特性，產(chǎn)生更優(yōu)秀的子代，保證多樣化的有效搜索.OL-CAIS算法的整體框架如算法3所示.

算法3 多項(xiàng)學(xué)習(xí)的免疫優(yōu)化算法OL-CAISAlgorithm 3 Multiple learning immune optimization algorithm

3 仿真實(shí)驗(yàn)

為了測(cè)試所提出算法的性能，本節(jié)通過(guò)解決6個(gè)常用的全局優(yōu)化問(wèn)題[8]進(jìn)行實(shí)驗(yàn)評(píng)估OL-CAIS的性能.與傳統(tǒng)的進(jìn)化算法模型比較,并分析OL-CAIS的性能.

3.1 平臺(tái)選定和參數(shù)設(shè)定

表1給出了實(shí)驗(yàn)中使用的測(cè)試函數(shù).它們可以分為四種類(lèi)型:f1是單峰函數(shù)，f2～f6是多峰函數(shù).

表1 測(cè)試函數(shù)Tab.1 Test function

比較OL-AIS與Opt-aiNet，CSA算法在上述6個(gè)測(cè)試問(wèn)題的10維和30維，此外與其他7個(gè)最先進(jìn)的進(jìn)化算法比較.列出了7個(gè)代表進(jìn)化算法：差分進(jìn)化算法 (SaDE)[9]；基于正交交叉微分進(jìn)化(OXDE)[10]；量化正交遺傳算法(OGA/Q)[11]；全面學(xué)習(xí)粒子群優(yōu)化(CLPSO)[12]；進(jìn)化策略與協(xié)方差矩陣適應(yīng)(CMA-ES)[13]；全局和局部的實(shí)數(shù)編碼遺傳算法(GL-25)[14]；混合學(xué)習(xí)克隆選擇算法(HLCSA)[15].種群大小設(shè)置為30，最大運(yùn)行次數(shù)(mFES)設(shè)置為10 000×D.所有的實(shí)驗(yàn)都是獨(dú)立運(yùn)行30次.

3.2 實(shí)驗(yàn)結(jié)果和討論

表2 改進(jìn)前后算法的性能比較D=10,30Tab.2 Performance comparison of improvement algorithm D=10 and D=30

表3介紹OL-CAIS與其他7個(gè)最先進(jìn)的進(jìn)化算法在平均值和標(biāo)準(zhǔn)差的比較，維數(shù)為10，最好的結(jié)果以粗體顯示.表4顯示了OL-CAIS與其他7個(gè)最先進(jìn)的進(jìn)化算法在平均值和標(biāo)準(zhǔn)差的比較，維數(shù)為30，最好的結(jié)果以粗體顯示.可以觀察到，這些測(cè)試實(shí)例，顯示OL-CAIS的可伸縮性很好處理高維優(yōu)化問(wèn)題.

表3 7種算法的性能比較 D=10Tab.3 Performance comparison of seven kinds of algorithm D=10

4 結(jié)果與討論

雖然傳統(tǒng)免疫優(yōu)化算法的優(yōu)點(diǎn)在于搜索出全局最優(yōu)解，但是它不能滿足人們對(duì)搜索效率和求解質(zhì)量的要求.相比之下，本文提出的OL-CAIS優(yōu)化算法，不僅引入了學(xué)習(xí)思想和類(lèi)雜交算子的搜索方程, 更注重整個(gè)群體的交互信息,通過(guò)正交設(shè)計(jì)構(gòu)造一個(gè)正交學(xué)習(xí)策略，利用其正交設(shè)計(jì)小樣本特性,可以產(chǎn)生更優(yōu)秀的子代,保證多樣化的有效搜索致力于平衡算法的搜索能力和開(kāi)發(fā)能力.因此，OL-CAIS優(yōu)化算法在最優(yōu)解質(zhì)量和收斂速度上比傳統(tǒng)優(yōu)化算法表現(xiàn)出更好的性能.

表4 7種算法的性能比較 D=30Tab.4 Performance comparison of seven kinds of algorithm D=30

[1]JDFARMER,NHPACKARD,ASPERELSON.Theimmunesystem,adaptation,andmachinelearning[J].PhysicaD:NonlinearPhenomena,1986,22(1):187-204.

[2]DECASTROLN,TIMMISJ.Anartificialimmunenetworkformultionfunctionoptimization[C]//ProceedingsofIEEECongressonEvolutionaryComputation.NewYork:IEEEPress,2002(1):699-674.

[3] 李春華,朱燕飛,毛宗源.一種新型的自適應(yīng)人工免疫算法[J].計(jì)算機(jī)工程與應(yīng)用,2004,40(22):84-87.

[4]BERGHF,ENGELBRECHTAP.Acooperativeapproachtoparticleswarmoptimization[C]//IEEETransactionsonEvolutionaryComputation.NewYork:IEEEPress,2004,8(3):225-239.

[5]LIZH,SHANGYN,TANHZ.Anefficientartificialimmunenetworkwithelite-learning[C]//Procdingsofthe3rdInternationalConferenceonNaturalComputation(ICNC9007).Haikou:IEEEPress,2007(4):213-217.

[6]LNDECASTRO,FJVONZUBEN.Theclonalselectionalgorithmwithengineeringapplications[C]//InProceedingsofGeneticandEvolutionaryComputationConference,2000:36-39.

[7]HEHONG,QIANFENG,DUWENLI.Achaoticimmunealgorithmwithfuzzyadaptivepara-meters[J].Asia-PacificJournalofChemicalEngineering,2008,3(6):695-705.

[8]JLIANG,PSUGANTHAN,KDEB.Novelcompositiontestfunctionsfornumericalglobaloptimization[C]//ProceedingsofIEEESwarmIntelligenceSymposium,2005:68-75.

[9]AKQIN,VLHUANG,PNSUGANTHAN.Differentialevolutionalgorithmwithstrategyadaptationforglobalnumericaloptimization[J].IEEETransEvolution,Comput,2009,13(2):398-417.

[10]YWANG,ZCAI,QZHANG.Enhancingthesearchabilityofdifferentialevolutionthroughorthogonalcrossover[J].InformSci,2012,185(1):153-177.

[11]YWLEUNG,YWANG.Anorthogonalgeneticalgorithmwithquantizationforglobalnumericaloptimization[J].IEEETransEvolutionComput,2001,5(1):41-53.

[12]JJLIANG,AKQIN,PNSUGANTHAN,etal.Comprehensivelearningparticleswa-rmoptimizerforglobaloptimizationofmultimodalfunctions[J].IEEETransEvolutionComput,2006,10(3):281-295.

[13]NHANSEN,AOSTERMEIER.Completelyderandomizedself-adaptationinevolutionstrategies[J].EvolutionComput,2001,9(2):159-195.

[14]CGARCíAMARTíNEZ,MLOZANO,FHERRERA,etal.Globalandlocalreal-codedgeneticalgorithmsbasedonparentcentriccrossoveroperators[J].EuroJOperatRes,2008,185(3):1088-1113.

[15]YONGPENG,BAOLIANGLU.Hybridlearningclonalselectionalgorithm[J].EvolutionInformationSciences,2015,296:128-146.

責(zé)任編輯：高 山

Multiple Learning Immune Optimization Algorithm

ZHANG Weiwei1,LIN Jingjing1,JING Honglei1,LIN Xuejie2

(1.College of Computer and Communication Engineering,Zhengzhou University of Light Industry,Zhengzhou 450000,China；2.College of Electrical Engineering,Zhengzhou University,Zhengzhou 450000,China)

This paper presents the immune optimization algorithm based on multiple learning OL-CAIS to solve global optimization problems.Chaos optimization theory is proposed to join the immune algorithm,and at the same time we introduced in the algorithm a class of hybrid operator search equation paying more attention to the interactive information of whole group.The search way is redefined and then,through the orthogonal experiment,an orthogonal learning strategy is formed which makes full use of the useful information in the search space and orthogonal design of small sample characteristics,to produce a better generation and ensure the effective of diverse search.

artificial immune;chaos optimization;hybrid operator;orthogonal learning

2016-10-10.

國(guó)家自然科學(xué)基金青年科學(xué)基金項(xiàng)目(61403349);河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目基礎(chǔ)研究計(jì)劃項(xiàng)目(14B520066；15A520033);鄭州輕工業(yè)學(xué)院博士基金項(xiàng)目(2013BSJJ044);鄭州輕工業(yè)學(xué)院研究生科技創(chuàng)新基金資助項(xiàng)目; 鄭州輕工業(yè)學(xué)院大學(xué)生科技活動(dòng)項(xiàng)目.

張偉偉(1986- ),女,博士，主要從事智能計(jì)算、優(yōu)化理論的研究.

1008-8423(2016)04-0424-06

10.13501/j.cnki.42-1569/n.2016.12.015

TP391

A