基于遺傳算法與模擬退火算法的旅行商問題研究畢業(yè)論文-資料下載頁
2025-06-24 15:52本頁面
【正文】 愿接受較好的下一代，所以在上面停留了比較長的時間，而模擬退火遺傳算法不只是接受較好的下一代，而且具有一定概率的接受了不好的下一代，這正是模擬退火退一步海闊天空的思想，該方法減少了尋找較好的下一代所要花費的時間，而且，有可能不好的下一代可能在下一次繁衍中找到合適的對象，在下一次繁衍中發(fā)揮它的“潛質(zhì)”算法在退火和遺傳繁衍中尋找最優(yōu)解，兩種思想結(jié)合，在一定的程度上減少了單純用一種算法求解的所耗費的時間。算法的退火繁衍過程如下圖41所示：圖41 X軸表示種群的繁衍次數(shù)，Y軸表示染色體所具有的權(quán)值，和哈密頓回路的權(quán)值對應(yīng)。紅色粗線表示解的權(quán)值，綠線表示通過確定性算法得到的最優(yōu)解，上圖反應(yīng)了經(jīng)過世代繁衍，染色體所具有的權(quán)值越來越接近最優(yōu)解，上圖為種群的大小399，繁殖的世代數(shù)為300，，退火初始溫度T=1000，退火方程T=*T，滿足以上參數(shù)的N=20的實例，從上圖可以看到解的收斂更快。下面對解的質(zhì)量和求解的時間進行比較：NOptSAGAGA_SAEMINETEMINETEMINET8242242242242242242242102792832792792791537149737140537143737120349574403476394377表41 算法運行結(jié)果比較，其中N表示TSP的實例規(guī)模，OPT表示最優(yōu)解，SA為模擬退火算法，GA為遺傳算法，GA_SA為模擬退火遺傳算法，每個算法運行50次，E為平均解的質(zhì)量，MIN為50次中取得的最優(yōu)解，ET為算法每次平均執(zhí)行時間運行環(huán)境：內(nèi)存1G,CPU Celeron SA算法參數(shù)：T0=1000 T=T**delta 終止條件TGA算法參數(shù)：種群大小popSize=399 繁衍次數(shù)maxgen = 300 種群交叉率pc= 種群變異率pm=GA算法參數(shù)：T0=1000 T=T* 種群大小popSize=399 繁衍次數(shù)maxgen = 300 種群交叉率pc= 種群變異率pm=從表中可以看到，SA算法耗時最少，GA算法耗時最大；SA算法解的質(zhì)量較差，而GA算法解的質(zhì)量較好；采用SA_GA算法，取SA算法和GA算法的長處，一方面，算法的運行時間大大降低，另一方面，解的質(zhì)量又較接近GA的解，把GA的優(yōu)勢發(fā)揮出來，同時又把GA的耗時劣勢隱藏。從遺傳算法到模擬退火算法，再到模擬退火遺傳算法，啟發(fā)式算法一次又一次告訴我們，根據(jù)具體問題，結(jié)合各種啟發(fā)式算法的優(yōu)點，可以綜合出更加優(yōu)秀的啟發(fā)式算法，在問題規(guī)模較龐大的情況下，啟發(fā)式便能發(fā)揮它強大的作用。致謝 感謝張老師一個學期以來對我們的關(guān)心愛護，張老師能夠盡職盡責的給我們上課，經(jīng)常給予我們啟發(fā)，并且指導(dǎo)我們學習論文的撰寫。再次感謝張老師！References:[1] 張德富 算法設(shè)計與分析（高級教程
物理相關(guān)推薦
鄂ICP備17016276號-1