遺傳算法報告

1、傳統(tǒng)優(yōu)化算法可以解決一些比較簡單的問題，但對于一些非線性的復(fù)雜問題，往往優(yōu)化時間很長，并且經(jīng)常不能得到最優(yōu)解，甚至無法知道所得解同最優(yōu)解的近似程度，而一些現(xiàn)代優(yōu)化算法就能很好地解決這些問題。2 0 世紀(jì)6 0 年代學(xué)者開始對遺傳進(jìn)化感興趣，進(jìn)而形成了遺傳算法。遺傳算法(GA)是由美國Michigan大學(xué)的Holland教授于1975年首先提出的。它源于達(dá)爾文的進(jìn)化論、孟德爾的群體遺傳學(xué)說和魏茨曼的物種選擇學(xué)說;其基本思想是模擬自然界遺傳機(jī)制和生物進(jìn)化論而形成的一種過程搜索最優(yōu)解的算法。從公開發(fā)表的論文看,我國首先開始研究應(yīng)用遺傳算法的有趙改善和華中理工大學(xué)的師漢民等人。遺傳算法最早應(yīng)用于一維地

2、震波形反演中,其特點(diǎn)是處理的對象是參數(shù)的編碼集而不是問題參數(shù)本身,搜索過程既不受優(yōu)化函數(shù)聯(lián)系性的約束,也不要求優(yōu)化函數(shù)可導(dǎo),具有較好的全局搜索能力;算法的基本思想簡單,運(yùn)行方式和實(shí)現(xiàn)步驟規(guī)范,具有全局并行搜索、簡單通用、魯棒性強(qiáng)等優(yōu)點(diǎn),但其局部搜索能力差,容易出現(xiàn)早熟現(xiàn)象。自1985年起,國際遺傳算法會議每兩年召開一次,在歐洲,從1990年開始每隔一年也舉辦一次類似的會議。 1993年,國際上第一本以遺傳算法和進(jìn)化計算為核心內(nèi)容的學(xué)術(shù)期刊EvolutionaryComputation(進(jìn)化計算)在MIT創(chuàng)刊; 1994年,在美國奧蘭多召開的IEEE WorldCongressonComputa

3、tionntelligence(IEEE全球計算智能大會)上,進(jìn)化計算與模糊邏輯、神經(jīng)網(wǎng)絡(luò)一起統(tǒng)稱為計算智能; 1997年,IEEE Transac-tionsonEvolutionaryComputation創(chuàng)刊。這些刊物及時全面地報道了近年來遺傳算法的最新研究成果。目前,與遺傳算法有關(guān)的學(xué)術(shù)會議包括ICGA、PPSN、ICEC、ANNGA、EP、FOGA、COGANN、EC、GP、SEAL等。遺傳算法是模擬生物在自然環(huán)境中優(yōu)勝劣汰、適者生存的遺傳和進(jìn)化過程而形成的一種具有自適應(yīng)能力的、全局性的概率搜索算法。它是從代表問題可能潛在解集的一個種群開始,首先將表現(xiàn)型映射到基因型即編碼,從而將解空

4、間映射到編碼空間,每個編碼對應(yīng)問題的一個解,稱為染色體或個體。初始種群產(chǎn)生之后,按照適者生存和優(yōu)勝劣汰的原理,逐代演化產(chǎn)生出越來越好的近似解。在每一代,根據(jù)問題域中個體的適應(yīng)度大小選擇個體,并借助自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異,產(chǎn)生出代表新的解集的種群。這個過程使種群像自然進(jìn)化一樣,后代種群比前代更加適應(yīng)于環(huán)境,末代種群中的最優(yōu)個體經(jīng)過解碼可以作為問題近似最優(yōu)解。利用遺傳算法求解問題的流程如下。a)建立數(shù)學(xué)模型。b)編碼,即用設(shè)計好的算法將表現(xiàn)型映射到個體基因型。c)解碼,遺傳算子只對編碼后的染色體起作用,由個體表現(xiàn)型計算目標(biāo)函數(shù)值后就可以判斷染色體的優(yōu)劣。d)確定適應(yīng)度轉(zhuǎn)換規(guī)則,染色

5、體所對應(yīng)的解空間的值可能相差很大,需要一定的轉(zhuǎn)換使其適合定量評估個體的優(yōu)劣。e)設(shè)計遺傳算子,即設(shè)計交叉、變異和選擇算子等。遺傳算子與待優(yōu)化問題、染色體的編碼方案有很大的關(guān)系。f)確定運(yùn)行參數(shù),運(yùn)行參數(shù)包括交叉概率、變異概率和種群數(shù)目等。遺傳算法本身的參數(shù)還缺乏定量的標(biāo)準(zhǔn),目前采用的多是經(jīng)驗(yàn)數(shù)值,并且遺傳參數(shù)的選取與編碼和遺傳算子的設(shè)計有很大關(guān)系。目前在遺傳算法的應(yīng)用中,最突出的問題是局部搜索能力差和容易出現(xiàn)早熟現(xiàn)象。近年來,眾多學(xué)者圍繞這兩個核心問題發(fā)表了大量有價值的學(xué)術(shù)論文,從各方面對遺傳算法進(jìn)行了改進(jìn)。在遺傳算子方面,Pan等人提出自適應(yīng)變異算子,使得變異能夠根據(jù)解的質(zhì)量自適應(yīng)地調(diào)整搜索

6、區(qū)域,較明顯地提高了搜索能力。Louis等人根據(jù)個體之間的海明距離進(jìn)行非均勻的交叉和變異,在保持群體多樣性的同時還防止了早熟。夏虎等人提出了一種考慮環(huán)境作用的協(xié)同免疫遺傳算法,在該算法中,設(shè)計了克隆環(huán)境演化算子和自適應(yīng)探索算子,并構(gòu)造了三個子種群協(xié)同進(jìn)化來發(fā)揮克隆環(huán)境演化算子的作用,從而提高了算法的全局搜索能力。蔡良偉等人提出一種改進(jìn)的交叉操作,根據(jù)種群的多樣性和個體的相關(guān)性選擇不同的交叉策略以減少無效的交叉操作,從而提高了交叉操作的效率并改善了算法的收斂性能。江雷等人提出的基于并行遺傳算法求解TSP,對遺傳算法的雜交算子進(jìn)行改進(jìn),探討了使用彈性策略來維持群體的多樣性,使得算法跨過局部收斂的障

7、礙,向全局最優(yōu)解方向進(jìn)化。Whitley等人提出了自適應(yīng)和有指導(dǎo)的變異,這種方法對改進(jìn)遺傳算法的性能起了一定的作用。一些學(xué)者提出了基于多種群的遺傳算法,將一個大的種群分成多個小的種群,每個小種群獨(dú)立地進(jìn)行進(jìn)化,進(jìn)化一定代數(shù)后進(jìn)行種群間的通信。由于這種方式可以采用并行計算的模式,取得了較好的效果。賀新等人介紹了一種基于新的變異算子多種群的新遺傳算法,該算法引入一種基于主群、附屬子群的結(jié)構(gòu),可避免傳統(tǒng)遺傳算法難以克服的早熟收斂問題。葉在福等人引入多種群,對不同種群賦予不同的控制參數(shù),實(shí)現(xiàn)不同的搜索目的,通過移民算子聯(lián)系各種群,通過人工選擇算子保存各種群每個進(jìn)化代中的最優(yōu)個體,對遺傳算法的早熟現(xiàn)象有

8、了很大的改進(jìn)。朱燦等人提出了一種考慮性別特征的遺傳算法,該方法模擬生物系統(tǒng)多物種同時進(jìn)化,指出最優(yōu)種子的獲得不但需要一個好的個體(父體),而且需要一個好的進(jìn)化方向(母體),通過增加母體的方法加速最優(yōu)物種的進(jìn)化,從而提高了算法的效率。遺傳算法的控制參數(shù)主要有種群數(shù)目Npop、交叉概率Pc和變異概率Pm,不同的參數(shù)組合對遺傳算法的運(yùn)行性能影響很大。DeJong首先系統(tǒng)地研究了不同的參數(shù)組合對遺傳算法的性能影響,他對五個函數(shù)進(jìn)行測試后,提出了一組參數(shù)選擇范圍:Npop= 50,Pc= 0.6,Pm= 0.001,這一組參數(shù)值后來被作為標(biāo)準(zhǔn)參數(shù)廣泛使用。丁承明等人提出了利用正交試驗(yàn)法去優(yōu)化選取控制參數(shù)

9、,這種方法利用正交試驗(yàn)的均衡分散性,使得通過較少的試驗(yàn)次數(shù)就能搜索大部分參數(shù)組合空間,而且還可以確定哪個參數(shù)對結(jié)果影響最顯著,然后有針對性地進(jìn)行精確的搜索,從而使得參數(shù)問題得到圓滿解決。李康順等人提出的改進(jìn)遺傳算法能夠根據(jù)個體適應(yīng)度大小和群體的分散程度自動調(diào)整遺傳控制參數(shù),從而能夠在保持群體多樣性的同時加快收斂速度,克服了傳統(tǒng)遺傳算法的收斂性差、易早熟等問題。還有許多學(xué)者從其他方面對遺傳算法進(jìn)行了改進(jìn),如設(shè)計交互式遺傳算法、引入量子理論等。這些改進(jìn)都在某種程度上提高了遺傳算法的性能,然而這些改進(jìn)都具有一定的局限性。因此,提高遺傳算法的收斂速度、克服早熟現(xiàn)象將是一個永恒的目標(biāo)。由于遺傳算法具有全

10、局并行搜索、簡單通用、魯棒性強(qiáng)等優(yōu)點(diǎn),使得遺傳算法廣泛地應(yīng)用于各個領(lǐng)域。在計算機(jī)科學(xué)與人工智能方面遺傳算法在計算機(jī)科學(xué)與人工智能領(lǐng)域中的應(yīng)用包括數(shù)據(jù)庫查詢優(yōu)化、數(shù)據(jù)挖掘與知識獲取、人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)與參數(shù)優(yōu)化、模式識別、專家系統(tǒng)等。另外,遺傳算法在軟件測試用例自動生成方面也作出了很大的貢獻(xiàn)。組合優(yōu)化(combinatorialoptimization)研究那些含有有限個可行解的、日常生活中大量存在的問題。這其中一個重要并且普遍的應(yīng)用領(lǐng)域就是考慮如何有效利用稀缺資源來提高生產(chǎn)力。GA在組合優(yōu)化問題中的應(yīng)用包括路徑覆蓋、裝箱、背包、確定最小生成樹、機(jī)器調(diào)度排序與平衡、車輛路徑、網(wǎng)絡(luò)設(shè)計與路徑、旅行推

11、銷員分配等。將遺傳算法用于知識獲取,構(gòu)成以遺傳算法為核心的機(jī)器學(xué)習(xí)系統(tǒng)。比較經(jīng)典的是Holland設(shè)計的用于序列決策學(xué)習(xí)的桶鏈算法(bucketbrigade)反饋機(jī)制(該系統(tǒng)被稱為分類器系統(tǒng)),以及機(jī)器人規(guī)則、概念學(xué)習(xí)、模式識別等。早期的經(jīng)濟(jì)學(xué)研究采用遺傳算法來求解數(shù)學(xué)公式,取得了不錯的效果,但離機(jī)器學(xué)習(xí)還差得很遠(yuǎn)。例如,Lettau在1997年建立的一個簡單的主體模型中就使用了這種方法;Bauer對遺傳算法在經(jīng)濟(jì)與投資中的應(yīng)用進(jìn)行了全面分析。近年來,商業(yè)、金融領(lǐng)域已經(jīng)成為遺傳算法應(yīng)用熱點(diǎn),目前已經(jīng)有許多基于遺傳算法的軟件包應(yīng)用于金融系統(tǒng)和股票投資分析。遺傳算法的研究歸納起來可分為理論與技術(shù)

12、研究和應(yīng)用研究兩個方面?？梢哉f,遺傳算法的應(yīng)用已經(jīng)滲透到了各個領(lǐng)域。但目前遺傳算法的算法分析和理論分析還沒有跟上,還有很多富有挑戰(zhàn)性的課題亟待完善與解決,主要有:a)算法規(guī)模小。雖然遺傳算法模擬了生物的進(jìn)化過程,但目前遺傳算法的運(yùn)行規(guī)模還遠(yuǎn)小于生物的進(jìn)化規(guī)模。隨著計算機(jī)系統(tǒng)性能的不斷提高,人們將有可能實(shí)現(xiàn)模擬更接近于自然的進(jìn)化系統(tǒng),從而充分利用遺傳算法的并行性解決更復(fù)雜、更有價值的問題。b)遺傳算法的編碼問題。編碼是遺傳算法求解問題的前提,最基本的是二進(jìn)制編碼。其他的編碼方法有格雷碼、實(shí)數(shù)編碼、符號編碼、多參數(shù)編碼和DNA編碼等。不同的應(yīng)用應(yīng)該采用不同的編碼方式,因此基于不同的應(yīng)用,遺傳算法的編碼還有待改進(jìn)與完善。c)遺傳算法控制參數(shù)的選擇問題。遺傳算法中控制參數(shù)的不同選取會對遺傳算法的性能產(chǎn)生較大的影響,將影響到整個算法的收斂性。這些參數(shù)包括交叉概率(pc)、變異概率(pm)和種群數(shù)目(Npop)等。d)早熟收斂和局部搜索能力差問題。早熟收斂和局部搜索能力差是遺傳算法最突出的兩個