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

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

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