一種融入小生境技術(shù)的遺傳禁忌算法

摘要:針對(duì)遺傳算法在全局優(yōu)化問(wèn)題中容易出現(xiàn)早熟和收斂速度慢，禁忌搜索強(qiáng)烈依賴于初始解等問(wèn)題，根據(jù)遺傳算法和禁忌搜索算法自身的特點(diǎn)，分析兩者的優(yōu)勢(shì)和不足，提出了一種融入小生境技術(shù)的遺傳禁忌算法.該算法采用融入了小生境技術(shù)的遺傳算法作全局搜索，用禁忌搜索算法作局部搜索，可以加快收斂速度，同時(shí)可以抑制早熟現(xiàn)象，避免過(guò)早收斂到局部最優(yōu).分析和實(shí)驗(yàn)結(jié)果表明，該算法能很好地抑制早熟收斂，同時(shí)在計(jì)算速度和計(jì)算結(jié)果方面都有改進(jìn)，是一種快速有效的優(yōu)化算法.

關(guān)鍵詞:遺傳算法;禁忌搜索;小生境;全局優(yōu)化

中圖分類號(hào):TP391.72;TH162文獻(xiàn)標(biāo)識(shí)碼:A

AHybridStrategyBasedonGeneticAlgorithmandTabuSearchImportingNiches

LIZhiyong1，CHENYouwen1，2

(1.CollegeofComputerandCommunication，HunanUniv，Changsha，Hunan410082，China;

2.DepartmentofComputer，HunanInternationalEconomicsUniv，Changsha，Hunan410205，China)

Abstract:GeneticalgorithmandTabusearchalgorithmarepowerfultoolstosolvecomplicatedlargescaleoptimizationproblems.TodealwiththeprematurityandlowconvergencespeedwhenthegeneticalgorithmareusedforglobaloptimizationandTabusearchdependsstronglyonitsinitialsolution，ahybridoptimizationalgorithmwasintroducedthroughcomprehensivecontrastandcomparisonbetweentheabovetwoalgorithmstoimprovethelocalsearchabilityofGeneticalgorithm.Inthisalgorithm，Tabusearchalgorithmwasusedforlocalsearchandgeneticalgorithmwasusedforglobalsearchinordertospeedupconvergenceforsatisfactoryresults.Meanwhile，nichewasimportedtocontrolprematurityandtoavoidconvergingtolocaloptimum.Thetestresultsshowthatbothcalculatingspeedandoutputareimproved，soitisafastandeffectivealgorithm.

Keywords:geneticalgorithm;tabusearchalgorithm;niche;globaloptimization

遺傳算法(GeneticAlgorithm，GA)源于生物遺傳學(xué)，是模擬自然界生物的優(yōu)勝劣汰、適者生存過(guò)程的一種隨機(jī)優(yōu)化方法[1].禁忌搜索(TabuSearch，TS)算法是模擬人類智力過(guò)程，對(duì)局部領(lǐng)域搜索的一種擴(kuò)展方法.將這二者結(jié)合起來(lái)的遺傳禁忌算法，具有較好的通用性與優(yōu)化性，適合處理一些復(fù)雜、大規(guī)模的優(yōu)化問(wèn)題，是一種有效的全局搜索魯棒算法[2].目前，國(guó)內(nèi)外研究學(xué)者對(duì)GA和TS算法的混合策略大致分為2種[3]:一是用禁忌變異算子取代一般的變異算子;二是遺傳進(jìn)化過(guò)程中每次變異操作結(jié)束后，都調(diào)用TS算法對(duì)群體中的每個(gè)個(gè)體進(jìn)行局部搜索.這2種策略都利用TS算法來(lái)有效地彌補(bǔ)GA較差的局部搜索能力，但是TS的頻繁調(diào)用顯然大大增加了算法的計(jì)算復(fù)雜度，另外這種策略仍然無(wú)法完全有效地克服傳統(tǒng)GA中的“早熟”收斂現(xiàn)象.針對(duì)以上不足，本文首先對(duì)GA和TS算法進(jìn)行了分析比較，并結(jié)合它們各自的優(yōu)勢(shì)，提出了一種新的GA和TS算法的混合策略.同時(shí)為了克服GA的早熟現(xiàn)象，在算法中引入了小生境技術(shù).針對(duì)典型多峰優(yōu)化函數(shù)的實(shí)驗(yàn)測(cè)試，結(jié)果表明本算法具有更好的全局搜索與局部?jī)?yōu)化能力，是一種有效的通用優(yōu)化算法.

1GA與TS混合優(yōu)化算法及小生境策略

11GA與TS算法的混合優(yōu)化算法

遺傳算法是由Holland于1975年首次提出，它作為一種搜索算法已經(jīng)被成功地應(yīng)用于復(fù)雜函數(shù)優(yōu)化問(wèn)題，尤其適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜問(wèn)題和非線性問(wèn)題.該算法通過(guò)選擇、交叉、變異3個(gè)算子的作用逐步求取問(wèn)題的最優(yōu)解.其主要特點(diǎn)是:①對(duì)參數(shù)的編碼進(jìn)行操作，而不是參數(shù)本身;②同時(shí)對(duì)多個(gè)點(diǎn)進(jìn)行搜索;③主要用到目標(biāo)函數(shù)的信息;④采用隨機(jī)轉(zhuǎn)換規(guī)則，而非確定性規(guī)則.其缺點(diǎn)是由于“爬山”能力和局部搜索能力差，常導(dǎo)致提前收斂于局部最優(yōu).研究發(fā)現(xiàn)，GA求解到一定范圍時(shí)往往做大量無(wú)為的冗余迭代，求精確解效率低[4].

禁忌搜索算法最早是由GloverF于1986年提出的，它是一種“局部搜索”的修正方法.它通過(guò)一個(gè)靈活的記憶功能和藐視準(zhǔn)則達(dá)到搜索解空間的目的.與傳統(tǒng)的優(yōu)化算法相比，TS算法的主要特點(diǎn)是:①在搜索過(guò)程中可以接受劣解，所以具有較強(qiáng)的“爬山”能力;②新解不是在當(dāng)前解的領(lǐng)域中隨機(jī)產(chǎn)生，而是從中選取最好解，即最好解的產(chǎn)生概率遠(yuǎn)遠(yuǎn)大于其他解.禁忌搜索算法的缺陷是對(duì)于初始解具有較強(qiáng)的依賴性，一個(gè)較好的初始解可使禁忌搜索在解空間中搜索到更好的解，而一個(gè)較差的初始解則會(huì)降低禁忌搜索的收斂速度，搜索到的解也相對(duì)較差;此外，其搜索只是單對(duì)單操作，即在搜索過(guò)程中初始解只能有一個(gè)，在每代也只是把一個(gè)解移動(dòng)到另一解.

Glover等人[5]從廣義的角度對(duì)遺傳算法和禁忌搜索法進(jìn)行了比較和分析，指出了兩者結(jié)合的可能性，為遺傳算法和禁忌搜索法的結(jié)合應(yīng)用提供了理論基礎(chǔ).為了保持GA和TS算法的優(yōu)點(diǎn)，提高算法的計(jì)算效率，在實(shí)際應(yīng)用時(shí)人們提出各種改進(jìn)策略[6-7].文獻(xiàn)[6]把TS作為GA的變異算子，變異算子作用于染色體個(gè)體，對(duì)每個(gè)個(gè)體進(jìn)行獨(dú)立尋優(yōu).該算法利用TS算法有效地彌補(bǔ)了GA較差的局部搜索能力，但是TS的頻繁調(diào)用顯然大大增加了算法的計(jì)算復(fù)雜度，另外這種策略仍然無(wú)法完全有效地克服傳統(tǒng)GA中的“早熟”收斂現(xiàn)象.

12融入小生境技術(shù)的GA算法

由于遺傳算法采用根據(jù)適應(yīng)度值的大小來(lái)決定個(gè)體是否被復(fù)制的選擇機(jī)制，這樣容易出現(xiàn)來(lái)源于同一種群的個(gè)體被大量繁衍的情況，形成近親繁殖，造成算法過(guò)早收斂，從而導(dǎo)致全局尋優(yōu)過(guò)程失敗，特別是對(duì)于多峰值函數(shù)容易出現(xiàn)這種現(xiàn)象[8].為了避免GA陷入局部最優(yōu)，引入小生境技術(shù)是有效的策略之一.

湖南大學(xué)學(xué)報(bào)(自然科學(xué)版)2010年

第4期李智勇等:一種融入小生境技術(shù)的遺傳禁忌算法

本文采用基于排擠機(jī)制的小生境遺傳算法，其基本思想是:首先兩兩比較群體中各個(gè)個(gè)體之間的距離，若這個(gè)距離在預(yù)先的距離L之內(nèi)，則對(duì)其中適應(yīng)值較低的個(gè)體施加一個(gè)較強(qiáng)的罰函數(shù)，極大地降低其適應(yīng)度，這樣，對(duì)于在預(yù)先指定的某一距離L之內(nèi)的2個(gè)個(gè)體，其中較差的個(gè)體經(jīng)處理后其適應(yīng)度變得更差，它在后面的進(jìn)化過(guò)程被淘汰的概率就極大.也就是說(shuō)，在距離L內(nèi)將只存在一個(gè)優(yōu)良個(gè)體，從而既維護(hù)了群體的多樣性，又使得各個(gè)個(gè)體之間保持一定的距離，并使得個(gè)體能夠在整個(gè)約束的空間中分散開來(lái)，避免大量重復(fù)的解充斥整個(gè)解空間.

2融入小生境的遺傳禁忌算法

21融入小生境的遺傳禁忌算法的設(shè)計(jì)思想及總體框架

針對(duì)傳統(tǒng)GA與TS混合方法的不足，本文提出一種新的GA和TS算法混合方法，并在其中引入小生境技術(shù)，使GA的種群保持較高的多樣性，從而避免GA陷入局部最優(yōu).其設(shè)計(jì)思想是二階段優(yōu)化策略:第一階段采用融入了小生境技術(shù)的GA進(jìn)行全局搜索，搜索工程中保持群體中的個(gè)體以較大概率分布在解空間中的大部分區(qū)域，待全局搜索收斂到一定程度后，各小生境中個(gè)體基本收斂，及時(shí)停止GA算法;第二階段用TS算法進(jìn)行局部搜索，在獲得良好初始解的情況下，充分利用TS算法的“爬山”能力強(qiáng)，求精解效率高等特點(diǎn)，使算法快速收斂到全局最優(yōu)解.本文將這種融入小生境策略(Niche)的遺傳(GA)禁忌(TS)算法簡(jiǎn)稱為NGATS(NichGeneticAlgorithmTabuSearch).其總體框架如圖1所示.

圖1NGATS算法總體框架

Fig.1NGATSalgorithmsgeneralstructure

22NGATS算法描述

NGATS算法的偽碼描述:

Begin

確定參數(shù)，包括種群規(guī)模N，最小海明距離L等;

t=0;

NGA-best=0;

P0=問(wèn)題空間中隨機(jī)產(chǎn)生N個(gè)個(gè)體;

While(GATermination_Condition=False)

t=t+1;

求出P(t)中每個(gè)個(gè)體ai的適應(yīng)度F(ai);

NGA-best=MAX(F(ai));

按概率進(jìn)行比例選擇;

根據(jù)交叉概率Pc，進(jìn)行交叉得P′(t);

根據(jù)變異概率Pm，進(jìn)行變異得P″(t);

求出P″(t)中每個(gè)個(gè)體bi的適應(yīng)度F(bi);

/*小生境淘汰技術(shù)*/

For(i=0;i

{For(j=0;j!=ij

d(bi，bj)=‖bi-bj‖=∑chromlenk=1(bik-bik)2

if(d(bi，bj))

min(Fbi，F(xiàn)bj)=Penalty

}

EndWhile

s=NGA_best;/*s為TS的初始解*/

s*=s;/*s*是目前找到的最好解*/

T=Φ;/*T為禁忌表*/

InitializetheaspirationfunctionA;

iter=0;

best_iter=0;

While(iter

iter=iter+1;

generateasetV*ofsolutionsi=smisuchthateithermiTorf(si)>A(f(s));

choosethebestsolutions’inV*;

updatethetabulistTandtheaspirationfunctionA;

if(f(s’)>f(s*))then

s*=s’;

best_iter=iter;

endif

s=s’;

EndWhile

End

需要說(shuō)明的是:NGATS算法中第1階段和第2階段的銜接問(wèn)題，即遺傳算法終止規(guī)則.本文規(guī)定若連續(xù)代數(shù)Q內(nèi)都滿足|eval(Utmax)-eval(U(t-1)max)|≤ε，其中ε為一適當(dāng)小的正數(shù)，eval(Utmax)為第t代的最大適應(yīng)度值，eval(U(t-1)max)為t-1代的最大適應(yīng)度值，連續(xù)t代內(nèi)最大適應(yīng)度差值都小于ε，表明遺傳算法基本陷入“停滯”，則遺傳算法終止.

3仿真模擬實(shí)驗(yàn)分析

3.1實(shí)驗(yàn)1

以文獻(xiàn)[9]中多峰函數(shù)優(yōu)化(求最大值)為例來(lái)驗(yàn)證算法的有效性.

f1:10+sin(1/x)(x-0.16)2，0

對(duì)該算例采取二進(jìn)制編碼，求解精度為10-4，適應(yīng)度函數(shù)取為原函數(shù)的實(shí)際值，群體規(guī)模為5，交叉概率為0.8，變異概率為0.25，海明距離L為2，罰函數(shù)Penalty為10-10，連續(xù)代數(shù)Q為5，ε為0.01，最大迭代數(shù)為100.機(jī)器為Pentium(R)4CPU2.40MHz，512內(nèi)存，每項(xiàng)實(shí)驗(yàn)做100組.

由于標(biāo)準(zhǔn)遺傳算法在當(dāng)前條件下幾乎收斂不到全局最優(yōu)解，故本文采用改進(jìn)的遺傳算法(采用“精英保留”策略，即在選擇前保留當(dāng)前最優(yōu)解)作為文中的“改進(jìn)遺傳算法(improvedgeneticalgorithm，IGA)”進(jìn)行對(duì)比.對(duì)IGA，TS和NGATS進(jìn)行收斂性分析，得到不同進(jìn)化代最好解的靜態(tài)性能曲線(100次采樣的平均值)，如圖2所示.

遺傳代數(shù)

圖2目標(biāo)函數(shù)進(jìn)化曲線圖

Fig.2Objectivefunctionalevolutioncurve

由圖2可知，小生境技術(shù)和禁忌算法的融入對(duì)算法快速收斂到全局最優(yōu)值有顯著作用.在實(shí)驗(yàn)中，TS和IGA在100次迭代內(nèi)常常收斂不到全局最優(yōu)值，而改進(jìn)后的NGATS算法，在100次迭代內(nèi)都能收斂到全局最優(yōu)值(19.8949).

32實(shí)驗(yàn)2

從上面幾種算法的收斂代數(shù)來(lái)分析NGATS算法的性能.對(duì)于實(shí)驗(yàn)1的結(jié)果，從最小成功收斂代數(shù)、平均收斂代數(shù)、陷入局部最優(yōu)解的次數(shù)和成功率這幾方面來(lái)對(duì)IGA，TS和NGATS這3種算法作性能上的比較.結(jié)果見(jiàn)表1.

由表1可知，NGATS較IGA和TS在收斂性能和搜索能力上都有很大提高，只需較小的群體規(guī)模和較少的遺傳代數(shù)就可獲得全局最優(yōu)解.第1階段融入了小生境技術(shù)的GA使算法很快進(jìn)入到最優(yōu)解附近，第1階段的禁忌算法使算法快速收斂到最優(yōu)解.

33實(shí)驗(yàn)3

我們沿用文獻(xiàn)[10]的ANGA算法和文獻(xiàn)[6]的GATS算法和本文的NGATS算法做對(duì)比實(shí)驗(yàn).對(duì)如下所示的函數(shù)求最小值:

f2:sin2x21+x22-0.5[1+0.001(x21+x22)]2-0.5，

-4≤xi≤4，i={1，2}.

該函數(shù)的全局最優(yōu)值在(0，0).在全局最優(yōu)值附近有無(wú)窮個(gè)取值相同的局部最優(yōu)值，且形態(tài)震蕩強(qiáng)烈，一般的優(yōu)化算法很難找到其全局最優(yōu)解，因此常常被國(guó)內(nèi)外很多學(xué)者用于對(duì)優(yōu)化算法的測(cè)試.

對(duì)該問(wèn)題采用二進(jìn)制編碼，計(jì)算精度為10-4，群體規(guī)模為20，適應(yīng)度函數(shù)取為目標(biāo)函數(shù)f=exp(f)，全局最優(yōu)解為(f=0.3678，x1=0，x2=0).分別用ANGA，GATS和NGATS進(jìn)行優(yōu)化.各自隨即產(chǎn)生100組初始種群逐一測(cè)試，當(dāng)?shù)鷶?shù)達(dá)到20000代還沒(méi)有達(dá)到最優(yōu)解f=0.3678時(shí)，則認(rèn)為算法已陷入局部最優(yōu)解.運(yùn)行時(shí)間為100次重復(fù)實(shí)驗(yàn)中成功收斂的平均值.機(jī)器為Pentium(R)4CPU2.40MHz，512內(nèi)存.實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表2.

從表2可以看出，NGATS的速度和成功率都優(yōu)于其他2種算法.ANGA的成功率優(yōu)于GATS算法，但GATS在速度上要優(yōu)于ANGA算法.這是因?yàn)锳NGA引入了小生境技術(shù)，增加了種群的多樣性，使算法在更大的范圍內(nèi)搜索，提高了算法的成功率.GATS在GA中融入TS，在獲得良好初始解的情況下，TS算法較強(qiáng)的“爬山”能力，求精解效率高等特點(diǎn)，加快了算法收斂速度.而NGATS算法同時(shí)融合了小生境技術(shù)和TS算法的優(yōu)點(diǎn)，所以在速度和有效性上獲得了雙贏.

表2對(duì)函數(shù)f2采用ANGA，GATS和NGATS算法的計(jì)算結(jié)果比較

Tab.2Differenceofcomputingresultsoffunctionf2withANGA，GATSandNGATS

f2運(yùn)行時(shí)間/s成功率/%

ANGA2.7891

GATS1.3671

NGATS0.78100

4結(jié)論

本文結(jié)合遺傳算法和禁忌搜索算法各自的優(yōu)點(diǎn)，提出了一種融入了小生境的遺傳禁忌算法NGATS.NGATS采用二階段優(yōu)化策略:第1階段采用融入了小生境技術(shù)的GA進(jìn)行全局搜索，搜索過(guò)程中保持群體的多樣性;第2階段用TS算法進(jìn)行局部搜索，加速算法的收斂.仿真實(shí)驗(yàn)證明，NGATS在有效性，收斂速度以及計(jì)算結(jié)果方面相對(duì)于簡(jiǎn)單GA和TS都有所提高.

參考文獻(xiàn)

[1]HOLLANDJ.Adaptationinnaturalandartificialsystems[M].Michigan:UniversityofMichiganPress，1975.

[2]徐寧，李春光，張健，等.幾種現(xiàn)代優(yōu)化算法的比較研究[J].系統(tǒng)工程與電子技術(shù)，2002，24(12):100-103.

XUNing，LIChunguang，ZHANGJian，etal.Studiesonsomemodernoptimizationalgorithms[J].SystemsEngineeringandElectronics，2002，24(12):100-103.(InChinese)

[3]蔣泰，楊海.定位—路線問(wèn)題的遺傳禁忌混合優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，2008，28(3):688-691.

JIANGTai，YANGHai.Genetic/tabuhybridoptimizationalgorithmforlocalroutingproblems[J].ComputerApplications，2008，28(3):688-691.(InChinese)

[4]丁建立，陳增強(qiáng)，袁著祉.遺傳算法與螞蟻算法的融合[J].計(jì)算機(jī)研究與發(fā)展，2003，40(9):1351-1356.

DINGJianli，CHENZengqiang，YUANZhuzhi.Onthecombinationofgeneticalgorithmandantalgorithm[J].JournalofComputerResearchandDevelopment，2003，40(9):1351-1356.(InChinese)

[5]GLOVERF，KELLYJ，LAGUNAM.Geneticalgorithmandtabusearch:hybridsforoptimizations[J].ComputersandOperationsResearch，1995，22(1):111-134.

[6]COSTAD.AnevolutionarytabusearchalgorithmandNHLschedulingproblem[J].InformationSystemsandOperationResearch，1995，33(3):161-178.

[7]JASZKIEWICZA.Geneticlocalsearchformultiobjectivecombinatorialoptimization[J].EuropeanJournalofOperationalResearch，2002，10(2):225-248.

[8]李明，黃平捷，周澤魁.基于小生境遺傳算法的矩形件優(yōu)化排樣[J].湖南大學(xué)學(xué)報(bào):自然科學(xué)版，2009，36(1):46-49.

LIMing，HUANGPingjie，ZHOUZekui.Optimallayoutofrectangularpartsbasedonnichegeneticalgorithm[J].JournalofHunanUniversity:NaturalSciences，2009，36(1):46-49.(InChinese)

[9]蘇小紅，楊博，王亞?wèn)|.基于進(jìn)化穩(wěn)定策略的遺傳算法[J].軟件學(xué)報(bào)，2003，14(11):1863-1868.

SUXiaohong，YANGBo，WANGYadong.Ageneticalgorithmbasedonevolutionarilystablestrategy[J].JournalofSoftware，2003，14(11):1863-1868.(InChinese)

[10]王淑佩，林亞平，易葉青.一種新的基于小生境的自適應(yīng)遺傳算法[J].蘭州理工大學(xué)學(xué)報(bào)，2006，32(5):83-87.

WANGShupei，LINYaping，YIYeqing.Anewselfadaptivegeneticalgorithmbasedonniches[J].JournalofLanzhouUniversityoftechnology，2006，32(5):83-87.(InChinese)