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

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

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

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