一種改進(jìn)的遺傳算法及其在TSP求解中的應(yīng)用.pdf

1、　　遺傳算法(Genetic Algorithm,簡稱GA)由John Holland于1975年提出,對于傳統(tǒng)方法難于求解的組合優(yōu)化、模式識別、圖像處理等復(fù)雜問題,使用該算法求解能得到令人較為滿意的解。近年來,遺傳算法在解決連續(xù)變量的函數(shù)最優(yōu)化問題和離散變量的組合最優(yōu)化問題時表現(xiàn)出的魯棒性、全局性、隱并行性和自適應(yīng)性使其成為一種應(yīng)用日益廣泛的智能優(yōu)化算法。
　　TSP是組合優(yōu)化中最為著名的問題,它綜合了一大類組合優(yōu)化問題的典型特

2、征,并以不同的形式存在于超大規(guī)模集成芯片制造、印刷電路板設(shè)計、X—射線結(jié)晶學(xué)、機(jī)器人控制等高科技領(lǐng)域。
　　由NP完全理論可知,TSP屬于NP難問題,用常規(guī)的搜索方法無法有效地求解。但如今正迅速發(fā)展的按自然法則計算的思想在求解大規(guī)模組合優(yōu)化問題時表現(xiàn)出非凡的潛力,其中的一個分枝—遺傳算法以其獨有的魅力吸引了越來越多的研究者。
　　經(jīng)典遺傳算法的主要特點在于它的簡單性和魯棒性,幾乎不需要知道所求問題的任何知識,但也正是由于這一

3、點,遺傳算法不能利用問題本身的信息,影響了求解具體問題時的效率。因此,在研究利用遺傳算法求解TSP問題上我們存在很大的改進(jìn)空間。
　　本文對遺傳算法的理論與應(yīng)用進(jìn)行了一些研究和分析工作。首先介紹了遺傳算法的理論和它在組合優(yōu)化問題中的應(yīng)用,然后針對TSP問題的求解進(jìn)一步指出遺傳算法存在易陷入早熟收斂和后期收斂速度慢的缺點,最后本文在原有遺傳算法的基礎(chǔ)上提出了一種改進(jìn)的遺傳算法。由于考慮到交叉算子和變異算子對算法的多樣性影響,因此交叉