遺傳算法在TSP問題上的應(yīng)用.pdf

1、旅行商問題(Traveling Salesman Problem，TSP)是一個經(jīng)典的組合優(yōu)化問題，是多種復(fù)雜問題的一種簡化形式。TSP問題的搜索空間隨著城市數(shù)的增加而增大，在龐大的空間中尋找最優(yōu)解，往往需要大量的求解時間，因此需尋求一種求解時間短且精度較高的算法來解決此問題。 遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法，其簡單通用、魯棒性強、適于并行處理等，借助遺傳算法解決TSP問題是

2、一個自然的想法。 本文針對遺傳算法求解TSP問題進行了研究。首先分析了遺傳算法的基本原理，遺傳算法的研究及應(yīng)用，接著對TSP問題的應(yīng)用價值及其研究現(xiàn)狀作了相應(yīng)的分析，并結(jié)合遺傳算法及TSP問題的特點，在對基本遺傳算法改進的基礎(chǔ)上，設(shè)計了一個新的算法，并通過實驗驗證了算法的有效性，本文主要研究工作如下： 1．針對遺傳算法求解TSP問題，提出了基于適應(yīng)度對種群進行分級，采用小種群并行育種的方式。讓適應(yīng)度較高的個體用于實現(xiàn)最優(yōu)

3、解的開采以保證算法的收斂性；適應(yīng)度較低的個體產(chǎn)生較多的個體對搜索空間進行探索，以保證種群的多樣性，避免陷入局部最優(yōu)解。而且在每級內(nèi)使用了精英保留策略。 2．基于遺傳算法的交叉策略，使用混合交叉算子，即PMX和一種啟發(fā)式交叉算子，既可保留父代中相同的模式，又可以較大概率生成優(yōu)于父體的個體。 3．改進了變異算子，提出了對種群使用混合變異算子，即2-opt和一種貪婪倒位變異算子。 4．將本文算法進行了數(shù)值實驗和相關(guān)比較