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

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

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

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