遺傳算法求解TSP的研究.pdf

1、作為一種模擬生物自然遺傳與進(jìn)化過程的優(yōu)化方法，遺傳算法(GA)因其具有隱并行性、不需目標(biāo)函數(shù)可微等特點(diǎn)，常被用于解決一些傳統(tǒng)優(yōu)化方法難以解決的問題。旅行商問題(TSP)是典型的NP難題組合優(yōu)化問題之一，且被廣泛應(yīng)用于許多領(lǐng)域，所以研究遺傳算法求解TSP具有重要的理論意義和應(yīng)用價(jià)值。具有量子計(jì)算諸多特點(diǎn)的量子遺傳算法(QGA)作為一新的概率進(jìn)化算法，在解決實(shí)際問題時(shí)，其高度并行性能極大地提高計(jì)算效率，因而研究QGA求解TSP同樣有重要的價(jià)

2、值；而將具有遍歷性和隨機(jī)性的“混沌”概念引入量子遺傳算法求解較復(fù)雜的組合優(yōu)化問題又為求解優(yōu)化問題開拓了一個(gè)新的思路。 首先，本文用一種改進(jìn)的基本遺傳算法求解TSP，由先驗(yàn)知識(shí)+隨機(jī)的方法產(chǎn)生初始群體，采用啟發(fā)式交叉和邊重組交叉相結(jié)合的交叉算子及GA的初期和后期采用不同適應(yīng)度的方法。然后，著重研究了改進(jìn)的QGA求解TSP，即采用適合TSP的矩陣編碼及有效性修復(fù)的方法，在基本QGA的基礎(chǔ)上運(yùn)用可控旋轉(zhuǎn)門，引入使算法收斂速度更快的模糊