資源描述：
《一種改進的遺傳算法及其在tsp中的應用》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。
1、一種改進的遺傳算法及其在TSP中的實現(xiàn)摘要文章針對TSP問題，提出了一種改進的遺傳算法。在遺傳算法中引入進化算法的思想，在此基礎上提出頂端培育策略和分階段策略，以求在保證群體多樣性的同時加快收斂速度。算法的仿真和測試表明，該算法對遺傳算法的改進是有效的。關鍵詞TSP遺傳算法進化算法1引言TSP問題是典型的NP完全問題。目前求解TSP問題的主要方法有啟發(fā)式搜索法、模擬退火算法、遺傳算法、Hopfield神經(jīng)網(wǎng)絡算法、二叉樹描述算法，遺傳算法是求解此類NP完全問題的一種比較有效的全局搜索方法。但遺傳算法中一個較難解決的問題是提高收斂速度的同時取得最優(yōu)
2、解或較優(yōu)解。文獻一中提出的思維進化算法在對TSP問題的求解中取得了較好的結果，本文在遺傳算法的基礎上，引入思維進化算法加強收斂性。此外，本文提出的分階段策略和頂端培育策略有利于保持群體多樣性的同時加快收斂速度。2思維進化算法簡介[1]對于思維進化算法(原名Mind-Evolution-BasedMachineLearning，現(xiàn)更名為MindEvolutionaryComputation)，據(jù)文獻1介紹如下：群體中共有n個子群體。在每個子群體中包含m個體和一個局部標志矩陣，用于記錄子群體進化時的信息。在整個環(huán)境中有一個全局標志矩陣，用于記錄群體中
3、優(yōu)勝個體的基因信息。首先，在子群體內部進行競爭，淘汰部分較差個體，提取優(yōu)勝者信息并記錄到局部標志矩陣，其中的最優(yōu)個體代表該子種群；另外，將每個子種群的最優(yōu)個體信息記入全局標志矩陣，并用末位淘汰制淘汰最差的子群體，該子群體的新個體由全局標志矩陣指導產(chǎn)生，而在各子群體內部則據(jù)局部標志矩陣產(chǎn)生新個體來補充被淘汰的個體。因為全局標志矩陣記錄了各代各子群中最優(yōu)個體的信息，所以據(jù)它所產(chǎn)生的新個體以較大概率成為較優(yōu)個體，有利于加強收斂速度。而局部標志矩陣記錄了各子群內部部分較優(yōu)個體的信息，所以，據(jù)它所產(chǎn)生的新個體以較大概率在局部（子群內部）成為較優(yōu)個體。這樣也
4、有利于保持群體的多樣性。3算法綜述3.1主要思想：本算法在遺傳算法的基礎上引入進化思想的方法，將遺傳算法與思維進化算法有機結合起來。即利用傳統(tǒng)的遺傳算子（選擇、交叉、變異）來產(chǎn)生優(yōu)良的一部分個體后代，而另一部分個體后代則依據(jù)已產(chǎn)生各輩的優(yōu)良基因記錄（標志矩陣）來生成。另外，本文提出了“頂端培育策略”和“分階段策略”以加快收斂速度?！绊敹伺嘤呗浴笔侵笇敹耍ㄈ后w中優(yōu)勝個體）加大培育力度（增加變異概率和變異方式）；“分階段策略”是指對迭代的不同時期采取不同變異概率和變異方式。3.2頂端培育策略：“一母生九子，九子各不同”，在生物學中，這是遺傳中客觀
5、存在的生理現(xiàn)象。針對TSP問題，通常需求的是全局最優(yōu)解。因此，對同一代中不同個體應采取不同培育力度：即對于優(yōu)勝個體應該加大培育力度?；谶@一生理現(xiàn)象，“頂端修改策略”即對當前群體內（或子群）的最優(yōu)個體作為重點培育種子，加大對它的變異概率和方式。因為當前群體內（或子群）的最優(yōu)個體是當前目標值最小的個體，它的基因通常較接近全局最優(yōu)解的基因，通過它的成功變異能提高收斂速度。3.3分階段策略：對于不同進化階段，群體間個體之間的差異性有明顯不同，初始群體由隨機生成，個體差異很大，進化了一定的代數(shù)之后（尤其是較為接近最優(yōu)解時），個體之間差異較小，即群體內的大
6、部分個體（尤其是那些優(yōu)勝個體）的基因趨同。種群的多樣性大為降低，易陷入“早熟”而停止收斂。所以，應該加大變異操作的概率或增加變異的方式來增強后期的收斂速度。3.4算法框架：<1>初始化：Generation=0;//初始化進化代數(shù)InitialPop(Pop);//初始化種群Pop(n,m,N)MaxNumber=constMax;//定義常量最大循環(huán)次數(shù)X=constX;//定義常量系數(shù)（分階段策略）PublicRecord(N,N)=1;//全局標志矩陣賦初值SubRecord(n,N,N)=1；//局部標志矩陣賦初值BestRecord(n
7、,2)=0;//記錄最優(yōu)個體矩陣賦初值While(Generation選擇：Select(N,Pop,PublicRecord,SubRecord);//選擇UpdateBestRecord(BestRecord);//記錄子種群的最優(yōu)個體UpdatePublicRecord(PublicRecord);//記錄全局優(yōu)勝個體UpdateSubRecord(SubRecord);//記錄局部優(yōu)勝個體<3>交叉：Xover(N,Pop)；//交叉<4>生成：Complete(N,Pop,PublicRecord,SubR
8、ecord);//據(jù)標志矩陣生成新個體<5>變異：ifGeneration>X*MaxNumberAddMutateProbabilit
