求解TSP的改進(jìn)遺傳算法.pdf

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

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