遺傳算法的改進(jìn)及其應(yīng)用

遺傳算法的改進(jìn)及其應(yīng)用

隨著1975年新澤西州的horand教授首次提出了遺傳計(jì)算方法（ga）。它源于達(dá)爾文的進(jìn)化論、孟德?tīng)柕娜后w遺傳學(xué)說(shuō)和魏茨曼的物種選擇學(xué)說(shuō);其基本思想是模擬自然界遺傳機(jī)制和生物進(jìn)化論而形成的一種過(guò)程搜索最優(yōu)解的算法。從公開(kāi)發(fā)表的論文看,我國(guó)首先開(kāi)始研究應(yīng)用遺傳算法的有趙改善和華中理工大學(xué)的師漢民等人。遺傳算法最早應(yīng)用于一維地震波形反演中,其特點(diǎn)是處理的對(duì)象是參數(shù)的編碼集而不是問(wèn)題參數(shù)本身,搜索過(guò)程既不受優(yōu)化函數(shù)聯(lián)系性的約束,也不要求優(yōu)化函數(shù)可導(dǎo),具有較好的全局搜索能力;算法的基本思想簡(jiǎn)單,運(yùn)行方式和實(shí)現(xiàn)步驟規(guī)范,具有全局并行搜索、簡(jiǎn)單通用、魯棒性強(qiáng)等優(yōu)點(diǎn),但其局部搜索能力差,容易出現(xiàn)早熟現(xiàn)象。自1985年起,國(guó)際遺傳算法會(huì)議每?jī)赡暾匍_(kāi)一次,在歐洲,從1990年開(kāi)始每隔一年也舉辦一次類似的會(huì)議。1993年,國(guó)際上第一本以遺傳算法和進(jìn)化計(jì)算為核心內(nèi)容的學(xué)術(shù)期刊《EvolutionaryComputation》(進(jìn)化計(jì)算)在MIT創(chuàng)刊;1994年,在美國(guó)奧蘭多召開(kāi)的IEEEWorldCongressonComputationIntelligence(IEEE全球計(jì)算智能大會(huì))上,進(jìn)化計(jì)算與模糊邏輯、神經(jīng)網(wǎng)絡(luò)一起統(tǒng)稱為計(jì)算智能;1997年,《IEEETransactionsonEvolutionaryComputation》創(chuàng)刊。這些刊物及時(shí)全面地報(bào)道了近年來(lái)遺傳算法的最新研究成果。目前,與遺傳算法有關(guān)的學(xué)術(shù)會(huì)議包括ICGA、PPSN、ICEC、ANN&GA、EP、FOGA、COGANN、EC、GP、SEAL等。1遺傳算法求解遺傳算法是模擬生物在自然環(huán)境中優(yōu)勝劣汰、適者生存的遺傳和進(jìn)化過(guò)程而形成的一種具有自適應(yīng)能力的、全局性的概率搜索算法。它是從代表問(wèn)題可能潛在解集的一個(gè)種群開(kāi)始,首先將表現(xiàn)型映射到基因型即編碼,從而將解空間映射到編碼空間,每個(gè)編碼對(duì)應(yīng)問(wèn)題的一個(gè)解,稱為染色體或個(gè)體。初始種群產(chǎn)生之后,按照適者生存和優(yōu)勝劣汰的原理,逐代演化產(chǎn)生出越來(lái)越好的近似解。在每一代,根據(jù)問(wèn)題域中個(gè)體的適應(yīng)度大小選擇個(gè)體,并借助自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異,產(chǎn)生出代表新的解集的種群。這個(gè)過(guò)程使種群像自然進(jìn)化一樣,后代種群比前代更加適應(yīng)于環(huán)境,末代種群中的最優(yōu)個(gè)體經(jīng)過(guò)解碼可以作為問(wèn)題近似最優(yōu)解。利用遺傳算法求解問(wèn)題的流程如圖1所示。a)建立數(shù)學(xué)模型。b)編碼,即用設(shè)計(jì)好的算法將表現(xiàn)型映射到個(gè)體基因型。c)解碼,遺傳算子只對(duì)編碼后的染色體起作用,由個(gè)體表現(xiàn)型計(jì)算目標(biāo)函數(shù)值后就可以判斷染色體的優(yōu)劣。d)確定適應(yīng)度轉(zhuǎn)換規(guī)則,染色體所對(duì)應(yīng)的解空間的值可能相差很大,需要一定的轉(zhuǎn)換使其適合定量評(píng)估個(gè)體的優(yōu)劣。e)設(shè)計(jì)遺傳算子,即設(shè)計(jì)交叉、變異和選擇算子等。遺傳算子與待優(yōu)化問(wèn)題、染色體的編碼方案有很大的關(guān)系。f)確定運(yùn)行參數(shù),運(yùn)行參數(shù)包括交叉概率、變異概率和種群數(shù)目等。遺傳算法本身的參數(shù)還缺乏定量的標(biāo)準(zhǔn),目前采用的多是經(jīng)驗(yàn)數(shù)值,并且遺傳參數(shù)的選取與編碼和遺傳算子的設(shè)計(jì)有很大關(guān)系。2基于遺傳算法的改進(jìn)目前在遺傳算法的應(yīng)用中,最突出的問(wèn)題是局部搜索能力差和容易出現(xiàn)早熟現(xiàn)象。近年來(lái),眾多學(xué)者圍繞這兩個(gè)核心問(wèn)題發(fā)表了大量有價(jià)值的學(xué)術(shù)論文[7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31],從各方面對(duì)遺傳算法進(jìn)行了改進(jìn)。2.1增加了算法的全局搜索能力在遺傳算子方面,Pan等人提出自適應(yīng)變異算子,使得變異能夠根據(jù)解的質(zhì)量自適應(yīng)地調(diào)整搜索區(qū)域,較明顯地提高了搜索能力。Louis等人根據(jù)個(gè)體之間的海明距離進(jìn)行非均勻的交叉和變異,在保持群體多樣性的同時(shí)還防止了早熟。夏虎等人提出了一種考慮環(huán)境作用的協(xié)同免疫遺傳算法,在該算法中,設(shè)計(jì)了克隆環(huán)境演化算子和自適應(yīng)探索算子,并構(gòu)造了三個(gè)子種群協(xié)同進(jìn)化來(lái)發(fā)揮克隆環(huán)境演化算子的作用,從而提高了算法的全局搜索能力。蔡良偉等人提出一種改進(jìn)的交叉操作,根據(jù)種群的多樣性和個(gè)體的相關(guān)性選擇不同的交叉策略以減少無(wú)效的交叉操作,從而提高了交叉操作的效率并改善了算法的收斂性能。江雷等人提出的基于并行遺傳算法求解TSP,對(duì)遺傳算法的雜交算子進(jìn)行改進(jìn),探討了使用彈性策略來(lái)維持群體的多樣性,使得算法跨過(guò)局部收斂的障礙,向全局最優(yōu)解方向進(jìn)化。Whitley等人提出了自適應(yīng)和有指導(dǎo)的變異,這種方法對(duì)改進(jìn)遺傳算法的性能起了一定的作用。2.2基于新的變異算子多種群一些學(xué)者提出了基于多種群的遺傳算法,將一個(gè)大的種群分成多個(gè)小的種群,每個(gè)小種群獨(dú)立地進(jìn)行進(jìn)化,進(jìn)化一定代數(shù)后進(jìn)行種群間的通信。由于這種方式可以采用并行計(jì)算的模式,取得了較好的效果。賀新等人介紹了一種基于新的變異算子多種群的新遺傳算法,該算法引入一種基于主群、附屬子群的結(jié)構(gòu),可避免傳統(tǒng)遺傳算法難以克服的早熟收斂問(wèn)題。葉在福等人引入多種群,對(duì)不同種群賦予不同的控制參數(shù),實(shí)現(xiàn)不同的搜索目的,通過(guò)移民算子聯(lián)系各種群,通過(guò)人工選擇算子保存各種群每個(gè)進(jìn)化代中的最優(yōu)個(gè)體,對(duì)遺傳算法的早熟現(xiàn)象有了很大的改進(jìn)。朱燦等人提出了一種考慮性別特征的遺傳算法,該方法模擬生物系統(tǒng)多物種同時(shí)進(jìn)化,指出最優(yōu)種子的獲得不但需要一個(gè)好的個(gè)體(父體),而且需要一個(gè)好的進(jìn)化方向(母體),通過(guò)增加母體的方法加速最優(yōu)物種的進(jìn)化,從而提高了算法的效率。2.3選取控制參數(shù)遺傳算法的控制參數(shù)主要有種群數(shù)目Npop、交叉概率Pc和變異概率Pm,不同的參數(shù)組合對(duì)遺傳算法的運(yùn)行性能影響很大。DeJong首先系統(tǒng)地研究了不同的參數(shù)組合對(duì)遺傳算法的性能影響,他對(duì)五個(gè)函數(shù)進(jìn)行測(cè)試后,提出了一組參數(shù)選擇范圍:Npop=50,Pc=0.6,Pm=0.001,這一組參數(shù)值后來(lái)被作為標(biāo)準(zhǔn)參數(shù)廣泛使用。丁承明等人提出了利用正交試驗(yàn)法去優(yōu)化選取控制參數(shù),這種方法利用正交試驗(yàn)的均衡分散性,使得通過(guò)較少的試驗(yàn)次數(shù)就能搜索大部分參數(shù)組合空間,而且還可以確定哪個(gè)參數(shù)對(duì)結(jié)果影響最顯著,然后有針對(duì)性地進(jìn)行精確的搜索,從而使得參數(shù)問(wèn)題得到圓滿解決。李康順等人提出的改進(jìn)遺傳算法能夠根據(jù)個(gè)體適應(yīng)度大小和群體的分散程度自動(dòng)調(diào)整遺傳控制參數(shù),從而能夠在保持群體多樣性的同時(shí)加快收斂速度,克服了傳統(tǒng)遺傳算法的收斂性差、易早熟等問(wèn)題。2.4加速個(gè)數(shù)編碼的免疫遺傳算法很多學(xué)者受常識(shí)的啟發(fā)對(duì)遺傳算法進(jìn)行了改進(jìn)。Reynolds等人提出的文化算法是一種模擬人類文化進(jìn)化機(jī)制的算法,它模擬了種群空間和信賴空間兩級(jí)的進(jìn)化。在信賴空間級(jí)存儲(chǔ)和提煉由種群進(jìn)化中獲取的解決問(wèn)題的知識(shí)及經(jīng)驗(yàn);而種群級(jí)在信賴空間級(jí)的指導(dǎo)下不斷進(jìn)化,最后收斂。王磊等人研究的免疫遺傳算法根據(jù)生物的免疫原理,將免疫算法中抗體多樣性的維持機(jī)制、記憶機(jī)制、促進(jìn)抑制機(jī)制引入到遺傳算法中,在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上提出了加速實(shí)數(shù)編碼的免疫遺傳算法。該算法改進(jìn)了基本遺傳算法群體多樣性差、搜索區(qū)間大和免疫算法容易陷入局部最優(yōu)以及進(jìn)化后期搜索停滯不前的性能,使其快速成熟收斂的同時(shí)又提高了局部尋優(yōu)和全局尋優(yōu)的能力。朱燦等人將物種的概念引入遺傳算法,提出了一種基于物種選擇的遺傳算法,根據(jù)種子到當(dāng)前最優(yōu)點(diǎn)的距離將種群分為當(dāng)前最優(yōu)物種和物種倉(cāng)庫(kù),對(duì)這兩個(gè)物種分別以不同的交叉概率和變異概率進(jìn)行遺傳運(yùn)算,以平衡種群的選擇壓力和種群多樣性,在提高算法效率和穩(wěn)定性方面取得了很好的效果。周蘭鳳等人提出了一種基于知識(shí)的遺傳算法,該算法采用特定的遺傳算子,將領(lǐng)域知識(shí)納入初始種群及自適應(yīng)調(diào)整控制參數(shù),克服了傳統(tǒng)遺傳算法的早熟收斂問(wèn)題,提高了遺傳算法的效率。Giráldez等人對(duì)進(jìn)化算法中加入知識(shí)的各種技術(shù)進(jìn)行了分類和歸納,設(shè)計(jì)了一種基于知識(shí)的快速進(jìn)化算法并將其用于機(jī)器學(xué)習(xí)問(wèn)題,實(shí)驗(yàn)結(jié)果表明,該算法不但能保證解的質(zhì)量而且大大縮短了計(jì)算時(shí)間。2.5基于遺傳算法的域方法在計(jì)算基因遺傳算法的全局搜索能力較強(qiáng),能較快地確定全局最優(yōu)點(diǎn),但局部搜索能力較弱,進(jìn)一步精確求解要耗費(fèi)很長(zhǎng)時(shí)間。因此,將局部搜索能力強(qiáng)的算法與遺傳算法結(jié)合可以相互取長(zhǎng)補(bǔ)短。Hageman等人提出了遺傳算法與禁忌搜索相結(jié)合的策略;魏明等人將遺傳算法與混沌優(yōu)化相結(jié)合,在遺傳進(jìn)化過(guò)程中,根據(jù)種群相對(duì)多樣性對(duì)每代個(gè)體引入混沌領(lǐng)域方法搜索有效基因,并有效地結(jié)合遺傳算法善于全局優(yōu)化和混沌局部搜索能力強(qiáng)等特點(diǎn),顯著提高了計(jì)算效率,具有較大的實(shí)用價(jià)值。任子武等人將遺傳算法與粒子群優(yōu)化方法相結(jié)合,采用混沌序列產(chǎn)生初始種群、非線性排序選擇、多個(gè)交叉后代競(jìng)爭(zhēng)擇優(yōu)和變異尺度自適應(yīng)變化等改進(jìn)遺傳操作,并通過(guò)精英個(gè)體保留、粒子群優(yōu)化及改進(jìn)遺傳算法(IGA)三種策略共同作用產(chǎn)生種群新個(gè)體,以克服常規(guī)算法中收斂速度慢、早熟及局部收斂等缺陷。此外,還有遺傳算法與模擬退火算法相結(jié)合、遺傳算法與單純形法相結(jié)合、遺傳算法與神經(jīng)網(wǎng)絡(luò)相結(jié)合、遺傳算法與模糊集相結(jié)合、遺傳算法與爬山法和梯度法等局部搜索算法相結(jié)合、遺傳算法與小生境技術(shù)結(jié)合、將量子計(jì)算與遺傳算法相結(jié)合形成量子遺傳算法、在遺傳算法中加入免疫算子構(gòu)成免疫進(jìn)化算法等。這些混合策略不但提高了算法的性能,還擴(kuò)展了算法的應(yīng)用領(lǐng)域。還有許多學(xué)者從其他方面對(duì)遺傳算法進(jìn)行了改進(jìn),如設(shè)計(jì)交互式遺傳算法、引入量子理論等。這些改進(jìn)都在某種程度上提高了遺傳算法的性能,然而這些改進(jìn)都具有一定的局限性。因此,提高遺傳算法的收斂速度、克服早熟現(xiàn)象將是一個(gè)永恒的目標(biāo)。3遺傳算法的應(yīng)用由于遺傳算法具有全局并行搜索、簡(jiǎn)單通用、魯棒性強(qiáng)等優(yōu)點(diǎn),使得遺傳算法廣泛地應(yīng)用于計(jì)算機(jī)科學(xué)、自動(dòng)控制、人工智能[43,44,45,46,47,48,49,50]、工程設(shè)計(jì)、制造業(yè)、生物工程和社會(huì)科學(xué)[53,55,56等領(lǐng)域。3.1人工神經(jīng)網(wǎng)絡(luò)優(yōu)化遺傳算法在計(jì)算機(jī)科學(xué)與人工智能領(lǐng)域中的應(yīng)用包括數(shù)據(jù)庫(kù)查詢優(yōu)化、數(shù)據(jù)挖掘與知識(shí)獲取、人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)與參數(shù)優(yōu)化、模式識(shí)別、專家系統(tǒng)等。另外,遺傳算法在軟件測(cè)試用例自動(dòng)生成方面也作出了很大的貢獻(xiàn)。3.2其他方面的應(yīng)用遺傳算法可用于求解系統(tǒng)參數(shù)辨識(shí)問(wèn)題。Karr采用遺傳算法設(shè)計(jì)自適應(yīng)模糊邏輯控制器,取得了顯著的效果;Esposito等人將基于GA的優(yōu)化技術(shù)應(yīng)用于RBF神經(jīng)網(wǎng)絡(luò)輸出層權(quán)值的優(yōu)化;Vesin等人將GA用于解決網(wǎng)絡(luò)結(jié)構(gòu)和權(quán)值的完全優(yōu)化問(wèn)題。遺傳算法也可用于控制器參數(shù)優(yōu)化整定;Fonesca等人將MOGA(多目標(biāo)遺傳算法)用于控制器的優(yōu)化設(shè)計(jì)以解決磁懸浮列車(chē)的控制器設(shè)計(jì)問(wèn)題;顏文俊等人則提出了一類新型的多目標(biāo)魯棒優(yōu)化控制器設(shè)計(jì)方法,通過(guò)有效算法求解滿足系統(tǒng)魯棒穩(wěn)定性和魯棒性能的優(yōu)化解。此外,GA在故障診斷和機(jī)器人行走路徑規(guī)劃中的應(yīng)用也取得了成功。3.3生活中的問(wèn)題組合優(yōu)化(combinatorialoptimization)研究那些含有有限個(gè)可行解的、日常生活中大量存在的問(wèn)題。這其中一個(gè)重要并且普遍的應(yīng)用領(lǐng)域就是考慮如何有效利用稀缺資源來(lái)提高生產(chǎn)力。GA在組合優(yōu)化問(wèn)題中的應(yīng)用包括路徑覆蓋、裝箱、背包、確定最小生成樹(shù)、機(jī)器調(diào)度排序與平衡、車(chē)輛路徑、網(wǎng)絡(luò)設(shè)計(jì)與路徑、旅行推銷(xiāo)員分配等。3.4全局最優(yōu)搜索及優(yōu)化多目標(biāo)問(wèn)題最早由意大利經(jīng)濟(jì)學(xué)家Pareto在1896年從政治經(jīng)濟(jì)學(xué)的角度提出的。多目標(biāo)群體決策是當(dāng)前管理科學(xué)、決策理論、系統(tǒng)工程、運(yùn)籌學(xué)、福利經(jīng)濟(jì)學(xué)等學(xué)科研究中十分重要的內(nèi)容。GA很適合求解多目標(biāo)優(yōu)化問(wèn)題,因?yàn)镚A可以并行地處理各個(gè)目標(biāo),避免了目標(biāo)間的優(yōu)先排序處理。GA通過(guò)保持一個(gè)潛在解的種群進(jìn)行多方向搜索,這種種群對(duì)種群的搜索可以跳出局部最優(yōu)解,從而突破了數(shù)學(xué)規(guī)劃法的點(diǎn)對(duì)點(diǎn)的搜索方法。GA在整個(gè)解空間同時(shí)開(kāi)始尋優(yōu)搜索,注重區(qū)域搜索和空間擴(kuò)展的平衡,因此可以有效地避免陷入局部極值點(diǎn),具備全局最優(yōu)搜索性,不會(huì)受到如Pareto曲面形狀、目標(biāo)個(gè)數(shù)等條件的限制,還可處理帶隨機(jī)的、不確定的離散搜索空間問(wèn)題,這正是數(shù)學(xué)規(guī)劃法所難以克服的。Hajela等人把多目標(biāo)問(wèn)題通過(guò)效用函數(shù)轉(zhuǎn)換為單目標(biāo)問(wèn)題,再用GA來(lái)求解。目前,怎樣利用GA的智能性來(lái)求解多目標(biāo)函數(shù)優(yōu)化問(wèn)題,仍然是一個(gè)值得研究的新課題。3.5基于桶鏈算法的序列決策學(xué)習(xí)將遺傳算法用于知識(shí)獲取,構(gòu)成以遺傳算法為核心的機(jī)器學(xué)習(xí)系統(tǒng)。比較經(jīng)典的是Holland設(shè)計(jì)的用于序列決策學(xué)習(xí)的桶鏈算法(bucketbrigade)反饋機(jī)制(該系統(tǒng)被稱為分類器系統(tǒng)),以及機(jī)器人規(guī)則、概念學(xué)習(xí)、模式識(shí)別等。3.6基于bauer的方法早期的經(jīng)濟(jì)學(xué)研究采用遺傳算法來(lái)求解數(shù)學(xué)公式,取得了不錯(cuò)的效果,但離機(jī)器學(xué)習(xí)還差得很遠(yuǎn)。例如,Lettau在1997年建立的一個(gè)簡(jiǎn)單的主體模型中就使用了這種方法;Bauer對(duì)遺傳算法在經(jīng)濟(jì)與投資中的應(yīng)用進(jìn)行了全面分析。近年來(lái),商業(yè)、金融領(lǐng)域已經(jīng)成為遺傳算法應(yīng)用熱點(diǎn),目前已經(jīng)有許多基于遺傳算法的軟件包應(yīng)用于金融系統(tǒng)和股票投資分析。4對(duì)遺傳算法的改進(jìn)和完善遺傳算法的研究歸納起來(lái)可分為理論與技術(shù)研究和應(yīng)用研究?jī)蓚€(gè)方面?？梢哉f(shuō),遺傳算法的應(yīng)用已經(jīng)滲透到了各個(gè)領(lǐng)域。但目前遺傳算法的算法分析和理論分析還沒(méi)