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

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

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

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