改進(jìn)的TSP進(jìn)化求解算法研究.pdf

1、遺傳算法是一種模擬自然界生物進(jìn)化的搜索算法,粒子群算法是群體智能的體現(xiàn),模仿魚群和鳥群覓食行為發(fā)展起來的,均屬于進(jìn)化算法。兩者之間有很多相似之處,均簡單易行、魯棒性強(qiáng),不需要專門的領(lǐng)域知識(shí)而僅用適應(yīng)度函數(shù)做評(píng)價(jià)來指導(dǎo)搜索過程,從而得到了廣泛的應(yīng)用,引起了專家學(xué)者的廣泛關(guān)注,得到了很多顯著的成果。
　　TSP問題是一個(gè)典型的NP難題,它的思想在生活生產(chǎn)中運(yùn)用很廣,提高TSP問題的解決效率有著現(xiàn)實(shí)的意義。因?yàn)镹P問題不能在多項(xiàng)式時(shí)間內(nèi)

2、得到最優(yōu)解。因此設(shè)計(jì)出相應(yīng)的算法盡快的得到近似解和滿意解是很現(xiàn)實(shí)的。智能算法就是在這樣的思想指導(dǎo)下被運(yùn)用于TSP問題的。
　　本文對(duì)遺傳算法和粒子群算法的理論與運(yùn)用做了一些探討。首先介紹了兩種算法的原理和應(yīng)用,其次分析了TSP問題的研究現(xiàn)狀、數(shù)學(xué)模型和解決方案。接著介紹了兩種算法在求解 TSP問題中的應(yīng)用和發(fā)展。在此基礎(chǔ)上,針對(duì) TSP問題、遺傳算法和粒子群算法進(jìn)化求解的特點(diǎn),提出了環(huán)路插入方法生成初始種群。并從遺傳算法和粒子群算