求解TSP的改進遺傳算法.pdf

1、遺傳算法是模擬自然環(huán)境中生物的遺傳和進化過程而形成的一種優(yōu)化算法。它具有全局搜索能力、隱并行性、魯棒性、操作簡單等特點，常被用于解決一些傳統(tǒng)優(yōu)化方法難以解決的問題。旅行商問題TSP)是組合優(yōu)化領域中一個典型的NP難問題，它陳述起來簡單，求解卻很困難。但旅行商問題的求解不僅為其他算法提供了思想方法平臺，同時也被廣泛地應用于交通、物流、大規(guī)模生產(chǎn)、基因測序等領域，具有較高的理論和應用價值。本文主要針對對稱型TSP，研究了TSP的遺傳算法求解

2、，主要工作如下：
　　 ⑴結合旅行商問題的特點，設計了一個新的遺傳交叉算子，在此基礎上提出了一種新的遺傳算法，并且證明了算法的收斂性。
　　 ⑵針對一類特殊的大規(guī)模旅行商問題，首先，提出了一種新的聚類策略，將距離較近的點聚成一類，從而將大規(guī)模的TSP轉化為若干個小規(guī)模問題；其次，給出了一種類的連接方法；最后，構造了求解這類特殊的大規(guī)模旅行商問題的有效算法。
　　 ⑶對提出的算法進行了數(shù)值模擬實驗，得出了較為理想的