一種改進(jìn)的遺傳算法及其在tsp中的應(yīng)用

《一種改進(jìn)的遺傳算法及其在tsp中的應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、一種改進(jìn)的遺傳算法及其在TSP中的實(shí)現(xiàn)摘要文章針對(duì)TSP問(wèn)題，提出了一種改進(jìn)的遺傳算法。在遺傳算法中引入進(jìn)化算法的思想，在此基礎(chǔ)上提出頂端培育策略和分階段策略，以求在保證群體多樣性的同時(shí)加快收斂速度。算法的仿真和測(cè)試表明，該算法對(duì)遺傳算法的改進(jìn)是有效的。關(guān)鍵詞TSP遺傳算法進(jìn)化算法1引言TSP問(wèn)題是典型的NP完全問(wèn)題。目前求解TSP問(wèn)題的主要方法有啟發(fā)式搜索法、模擬退火算法、遺傳算法、Hopfield神經(jīng)網(wǎng)絡(luò)算法、二叉樹(shù)描述算法，遺傳算法是求解此類(lèi)NP完全問(wèn)題的一種比較有效的全局搜索方法。但遺傳算法中一個(gè)較難解決的問(wèn)題是提高收斂速度的同時(shí)取得最優(yōu)

2、解或較優(yōu)解。文獻(xiàn)一中提出的思維進(jìn)化算法在對(duì)TSP問(wèn)題的求解中取得了較好的結(jié)果，本文在遺傳算法的基礎(chǔ)上，引入思維進(jìn)化算法加強(qiáng)收斂性。此外，本文提出的分階段策略和頂端培育策略有利于保持群體多樣性的同時(shí)加快收斂速度。2思維進(jìn)化算法簡(jiǎn)介[1]對(duì)于思維進(jìn)化算法(原名Mind-Evolution-BasedMachineLearning，現(xiàn)更名為MindEvolutionaryComputation)，據(jù)文獻(xiàn)1介紹如下：群體中共有n個(gè)子群體。在每個(gè)子群體中包含m個(gè)體和一個(gè)局部標(biāo)志矩陣，用于記錄子群體進(jìn)化時(shí)的信息。在整個(gè)環(huán)境中有一個(gè)全局標(biāo)志矩陣，用于記錄群體中

3、優(yōu)勝個(gè)體的基因信息。首先，在子群體內(nèi)部進(jìn)行競(jìng)爭(zhēng)，淘汰部分較差個(gè)體，提取優(yōu)勝者信息并記錄到局部標(biāo)志矩陣，其中的最優(yōu)個(gè)體代表該子種群；另外，將每個(gè)子種群的最優(yōu)個(gè)體信息記入全局標(biāo)志矩陣，并用末位淘汰制淘汰最差的子群體，該子群體的新個(gè)體由全局標(biāo)志矩陣指導(dǎo)產(chǎn)生，而在各子群體內(nèi)部則據(jù)局部標(biāo)志矩陣產(chǎn)生新個(gè)體來(lái)補(bǔ)充被淘汰的個(gè)體。因?yàn)槿謽?biāo)志矩陣記錄了各代各子群中最優(yōu)個(gè)體的信息，所以據(jù)它所產(chǎn)生的新個(gè)體以較大概率成為較優(yōu)個(gè)體，有利于加強(qiáng)收斂速度。而局部標(biāo)志矩陣記錄了各子群內(nèi)部部分較優(yōu)個(gè)體的信息，所以，據(jù)它所產(chǎn)生的新個(gè)體以較大概率在局部（子群內(nèi)部）成為較優(yōu)個(gè)體。這樣也

4、有利于保持群體的多樣性。3算法綜述3.1主要思想：本算法在遺傳算法的基礎(chǔ)上引入進(jìn)化思想的方法，將遺傳算法與思維進(jìn)化算法有機(jī)結(jié)合起來(lái)。即利用傳統(tǒng)的遺傳算子（選擇、交叉、變異）來(lái)產(chǎn)生優(yōu)良的一部分個(gè)體后代，而另一部分個(gè)體后代則依據(jù)已產(chǎn)生各輩的優(yōu)良基因記錄（標(biāo)志矩陣）來(lái)生成。另外，本文提出了“頂端培育策略”和“分階段策略”以加快收斂速度?！绊敹伺嘤呗浴笔侵笇?duì)頂端（群體中優(yōu)勝個(gè)體）加大培育力度（增加變異概率和變異方式）；“分階段策略”是指對(duì)迭代的不同時(shí)期采取不同變異概率和變異方式。3.2頂端培育策略：“一母生九子，九子各不同”，在生物學(xué)中，這是遺傳中客觀

5、存在的生理現(xiàn)象。針對(duì)TSP問(wèn)題，通常需求的是全局最優(yōu)解。因此，對(duì)同一代中不同個(gè)體應(yīng)采取不同培育力度：即對(duì)于優(yōu)勝個(gè)體應(yīng)該加大培育力度?；谶@一生理現(xiàn)象，“頂端修改策略”即對(duì)當(dāng)前群體內(nèi)（或子群）的最優(yōu)個(gè)體作為重點(diǎn)培育種子，加大對(duì)它的變異概率和方式。因?yàn)楫?dāng)前群體內(nèi)（或子群）的最優(yōu)個(gè)體是當(dāng)前目標(biāo)值最小的個(gè)體，它的基因通常較接近全局最優(yōu)解的基因，通過(guò)它的成功變異能提高收斂速度。3.3分階段策略：對(duì)于不同進(jìn)化階段，群體間個(gè)體之間的差異性有明顯不同，初始群體由隨機(jī)生成，個(gè)體差異很大，進(jìn)化了一定的代數(shù)之后（尤其是較為接近最優(yōu)解時(shí)），個(gè)體之間差異較小，即群體內(nèi)的大

6、部分個(gè)體（尤其是那些優(yōu)勝個(gè)體）的基因趨同。種群的多樣性大為降低，易陷入“早熟”而停止收斂。所以，應(yīng)該加大變異操作的概率或增加變異的方式來(lái)增強(qiáng)后期的收斂速度。3.4算法框架：<1>初始化：Generation=0;//初始化進(jìn)化代數(shù)InitialPop(Pop);//初始化種群Pop(n,m,N)MaxNumber=constMax;//定義常量最大循環(huán)次數(shù)X=constX;//定義常量系數(shù)（分階段策略）PublicRecord(N,N)=1;//全局標(biāo)志矩陣賦初值SubRecord(n,N,N)=1；//局部標(biāo)志矩陣賦初值BestRecord(n

7、,2)=0;//記錄最優(yōu)個(gè)體矩陣賦初值While(Generation選擇：Select(N,Pop,PublicRecord,SubRecord);//選擇UpdateBestRecord(BestRecord);//記錄子種群的最優(yōu)個(gè)體UpdatePublicRecord(PublicRecord);//記錄全局優(yōu)勝個(gè)體UpdateSubRecord(SubRecord);//記錄局部?jī)?yōu)勝個(gè)體<3>交叉：Xover(N,Pop)；//交叉<4>生成：Complete(N,Pop,PublicRecord,SubR

8、ecord);//據(jù)標(biāo)志矩陣生成新個(gè)體<5>變異：ifGeneration>X*MaxNumberAddMutateProbabilit