基于遺傳算法與模擬退火算法的旅行商問題研究畢業(yè)論文(完整版)
【正文】 用概率算法，用來在一個大的搜尋空間內(nèi)找問題的最優(yōu)解。旅行商問題在軍事通訊電路板的設(shè)計大規(guī)模集成電路基因排序等領(lǐng)域具有廣泛的應(yīng)用。這個過程將導(dǎo)致種群像自然進化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼（decoding），可以作為問題近似最優(yōu)解。適應(yīng)度越大，生存能力越強，越能夠在競爭中獲勝而生存或者參與配對產(chǎn)生下一代。A：優(yōu)勝劣汰（精英策略）進化的目的是為了讓種群的適應(yīng)能力更強，必須留下適應(yīng)能力最強的染色體參與到下一代。需要在時間和解的質(zhì)量上找到平衡點。 3）判斷新解是否被接受，判斷的依據(jù)是一個接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropolis準(zhǔn)則: 若Δt′0則接受S′作為新的當(dāng)前解S，否則以概率exp(Δt′/T)接受S′作為新的當(dāng)前解S。 8 else X ← X39。圖31 X軸為退火迭代次數(shù)，Y軸為解的權(quán)值，紅色的線模擬了退火求解過程，綠色線為最優(yōu)解，本實例設(shè)置退火初始溫度為1000，終止條件為T，退火函數(shù)為T=T**delta，其中delta由運行狀態(tài)獲得。致謝 感謝張老師一個學(xué)期以來對我們的關(guān)心愛護，張老師能夠盡職盡責(zé)的給我們上課，經(jīng)常給予我們啟發(fā)，并且指導(dǎo)我們學(xué)習(xí)論文的撰寫。為結(jié)合二者的優(yōu)勢，考慮設(shè)計同時具有模擬退火算法和遺傳算法思想的模擬退火遺傳算法，即SA_GA算法。缺點是為了尋找到全局最優(yōu)解，需要慢慢的退火，因此所花的時間長，特別是有關(guān)冷卻機制的參數(shù)難以控制。此時，當(dāng)前的解完成一次迭代。紅色粗線表示解的權(quán)值，綠線表示通過確定性算法得到的最優(yōu)解，上圖反應(yīng)了經(jīng)過世代繁衍，染色體所具有的權(quán)值越來越接近最優(yōu)解，上圖為種群的大小399，繁殖的世代數(shù)為300，滿足以上參數(shù)的N=20的實例模擬退火算法原理和金屬退火的原理相似：我們將熱力學(xué)的理論套用到統(tǒng)計學(xué)上，將搜尋空間內(nèi)每一點作為成空氣內(nèi)的分子；分子的能量，就是它本身的動能；而搜尋空間內(nèi)的每一點，也像空氣分子一樣帶有“能量”，以表示該點對命題的合適程度。B：交叉配對種群進化的動力是交叉配對，通過從舊的種群中選取雙親，雙親染色體交叉，產(chǎn)生具有新的適應(yīng)能力的下一代，并且通過多次染色體交叉盡量產(chǎn)生適應(yīng)能力強的下一代。染色體編碼為：{H，fitness}， 其中H為哈密頓回路，亦可認(rèn)為是染色體編碼，fitness為染色體適應(yīng)度。 initialize Pop(t) with N chromosomes Popi(t)2 while not (terminating condition) do3 for i ←1 to N do fi← f(Popi(t))4 for i ←1 to N do 5 NewPopi(t+1)←randomly choose Popi(t)∈Pop(t) with pj=fj/(∑kfk)6 CrossPop(t+1) ← rebine(NewPo
物理相關(guān)推薦
鄂ICP備17016276號-1