遺傳算法求解TSP問題的研究與改進(jìn).pdf

1、遺傳算法是模仿生物進(jìn)化和自然選擇機(jī)理，模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。近年來，遺傳算法由于在解決各類最優(yōu)化問題時(shí)表現(xiàn)出的魯棒性、全局性、隱含并行性和自適應(yīng)性而成為一種應(yīng)用日益廣泛的智能優(yōu)化算法。旅行商問題(TSP)是組合優(yōu)化領(lǐng)域中的一個(gè)典型NP完全問題，是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問題的集中概括和簡(jiǎn)化形式?？焖?、有效地解決TSP問題有著較高的理論意義和實(shí)際應(yīng)用價(jià)值。
　　 本文根據(jù)TSP

2、問題的特點(diǎn)和當(dāng)前研究情況，選用遺傳算法對(duì)它進(jìn)行求解。介紹了遺傳算法的原理及基本實(shí)現(xiàn)技術(shù)，著重闡述了遺傳算法的特性和影響遺傳算法性能的因素，針對(duì)TSP問題對(duì)遺傳算法進(jìn)行相應(yīng)的改進(jìn)。首先針對(duì)傳統(tǒng)遺傳算法中初始種群平均適度度低的缺點(diǎn)，設(shè)計(jì)了一種貪婪選擇策略代替隨機(jī)化生成初始種群，從而提高初始種群的質(zhì)量；然后根據(jù)TSP問題種群個(gè)體編碼的特點(diǎn)，結(jié)合貪婪算法，設(shè)計(jì)了一種貪婪交叉算子，使之既能有效地保留父代個(gè)體的優(yōu)良基因，又能以較大的概率產(chǎn)生新的優(yōu)良

3、個(gè)體；在變異算子設(shè)計(jì)上，采用了兩種變異算子相結(jié)合的方法，以提高種群的多樣性；此外，在進(jìn)化過程中算法引入了自適應(yīng)策略來控制遺傳參數(shù)的變化。本文使用改進(jìn)的遺傳算法對(duì)國際通用的TSP測(cè)試庫TSPLIB中不同城市規(guī)模的數(shù)據(jù)進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果表明了該算法具有較高的執(zhí)行效率。
　　 在以上改進(jìn)遺傳算法的基礎(chǔ)上，結(jié)合主從式并行程序設(shè)計(jì)的特點(diǎn)，提出了工作站機(jī)群環(huán)境中基于MPI求解TSP問題的并行遺傳算法。該算法采用按城市結(jié)點(diǎn)編號(hào)分配種群，并定期