基于TSP的遺傳算法優(yōu)化研究.pdf

1、在人工智能領(lǐng)域中，研究在搜索過(guò)程中自動(dòng)獲取和積累有關(guān)搜索空間的知識(shí)并自適應(yīng)地控制搜索過(guò)程從而得到最優(yōu)解的通用搜索一直是令人矚目的課題。旅行商(TSP)問(wèn)題是組合優(yōu)化領(lǐng)域中的一個(gè)典型問(wèn)題，雖然它陳述起來(lái)很簡(jiǎn)單，但求解卻很困難，并且已經(jīng)被證明是NP完全問(wèn)題。遺傳算法是借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來(lái)的全局的概率搜索算法。在眾多解決TSP問(wèn)題的方法中，遺傳算法有著其他方法不具備的很多優(yōu)點(diǎn)，對(duì)于中小規(guī)模TSP問(wèn)題，遺傳算法可以得到最優(yōu)解，對(duì)

2、于大規(guī)模TSP問(wèn)題，可以得到近似最優(yōu)解。 本文通過(guò)對(duì)遺傳算法常見(jiàn)的各選擇算子，交叉算子，變異算子進(jìn)行比較，確定了以效果較好的錦標(biāo)賽精英選擇、部分映射交叉，移位變異和插入變異為基礎(chǔ)的算子進(jìn)行優(yōu)化。針對(duì)錦標(biāo)賽精英選擇過(guò)于集中在少數(shù)優(yōu)良個(gè)體的現(xiàn)象，提出了一種新的選擇方法：差異雙親錦標(biāo)賽精英選擇法。針對(duì)于倒置變異和插入變異各自的優(yōu)缺點(diǎn)，提出了一種新的變異方法：倒置.插入混合變異法。 對(duì)已有的算法和改進(jìn)的算法進(jìn)行了比較，采用隨機(jī)生