改進(jìn)的遺傳算法求解TSP問題的應(yīng)用與研究.pdf

1、旅行商問題是一個(gè)經(jīng)典組合優(yōu)化方面的問題。隨著城市集群的規(guī)模迅猛增長，旅行商問題在搜索空間里變得越來越難尋找最優(yōu)解。同時(shí)，過于冗余的改進(jìn)算法給程序帶來更多的負(fù)面影響。因此，尋找一個(gè)高效和便捷的遺傳算法計(jì)算框架成了眾多學(xué)者的研究重點(diǎn)。
　　對于旅行商問題這類完全問題，遺傳算法具有全局搜索的優(yōu)勢，而它的局部搜索能力不足以及收斂速度緩慢。在傳統(tǒng)精確算法中，它們多為局部搜索算法，一般得到局部較優(yōu)解，即對小范圍的城市群能夠準(zhǔn)確求出近似解。因此

2、，近年來不斷改進(jìn)的遺傳算法有通過和傳統(tǒng)算法相結(jié)合成混合算法來改進(jìn)，以便達(dá)到優(yōu)勢互補(bǔ)。除此之外，它也有借助相關(guān)策略的改進(jìn)來提高遺傳算法的性能。在改進(jìn)算法中，鮮有人突出提出對于城市信息預(yù)處理來克服那些不足，有的是基于數(shù)據(jù)挖掘算法中的k均值聚類算法與遺傳算法的混合算法的提出。聚類算法是以迭代時(shí)間的巨大代價(jià)來換取遺傳算法處理能力的提高。
　　本文出發(fā)點(diǎn)依然是圍繞傳統(tǒng)遺傳算法解決旅行商問題所遇到的兩大問題，采取一種直接劃分地圖而形成區(qū)域網(wǎng)格

3、的簡單方式，通過劃分處理城市信息數(shù)據(jù)進(jìn)而改進(jìn)路徑編碼。改進(jìn)的遺傳算法是將原來城市群的坐標(biāo)數(shù)據(jù)根據(jù)地圖區(qū)域網(wǎng)格單位的劃分進(jìn)行數(shù)據(jù)信息預(yù)處理而達(dá)到地圖壓縮和提煉有用信息的目的。改進(jìn)的遺傳算法基于對于原始數(shù)據(jù)進(jìn)行域規(guī)則的數(shù)據(jù)預(yù)處理，提出了一種對傳統(tǒng)路徑編碼，以及諸算子改進(jìn)的遺傳算法。改進(jìn)的遺傳算法的數(shù)據(jù)預(yù)處理將根據(jù)地圖區(qū)域化特點(diǎn)進(jìn)行網(wǎng)格區(qū)域劃分處理，且采用提前培育的局部優(yōu)秀基因塊,再與整體相結(jié)合完成分階段初始化。同時(shí)，區(qū)域劃分必然存在鄰近區(qū)域