遺傳算法概述

1、遺傳算法概述1、遺傳算法的起源遺傳算法是霍蘭(J.H.Holland,1975)提出1,通過(guò)模擬生物的進(jìn)化過(guò)程,運(yùn)用啟發(fā)搜索規(guī)那么,把一組模型中優(yōu)良個(gè)體生存和隨機(jī)變異的信息交換結(jié)合在一起.從一組初始模型出發(fā),根據(jù)給定的參數(shù)變化范圍及變化步長(zhǎng),將每個(gè)模型的全部參數(shù)用許多串聯(lián)在一起的二進(jìn)制編碼(或其他編碼)串表示,通過(guò)選擇、交叉互換和變異不斷保存優(yōu)勢(shì)特征,最后得到問(wèn)題的最優(yōu)解.其不依賴(lài)于梯度信息,而是通過(guò)模擬自然進(jìn)化過(guò)程來(lái)搜索最優(yōu)解,它利用某種編碼技術(shù),作用于染色體的字符串,模擬由這些串組成的群體的進(jìn)化過(guò)程.具有以下特點(diǎn)：對(duì)可行解的表示廣泛；具有群體并行搜索特性；具有很強(qiáng)的魯棒性；然而它也有一些缺

2、乏,它的編碼不規(guī)那么及編碼存在的不準(zhǔn)確性,其搜索的計(jì)算量大且搜索效率低,出現(xiàn)早熟收斂等等,嚴(yán)重影響了遺傳算法的應(yīng)用,也是需要解決和改良研究的地方.進(jìn)入90年代,遺傳算法迎來(lái)了興盛開(kāi)展時(shí)期,無(wú)論是理論研究還是應(yīng)用研究都成了十分熱門(mén)的課題,成為求解全局優(yōu)化問(wèn)題的有力工具之一.在根本理論開(kāi)展方面來(lái)說(shuō),模式定理和積木塊假設(shè)是遺傳算法有效的理論依據(jù).模式定理保證了較優(yōu)先的模式樣本呈指數(shù)級(jí)增長(zhǎng),從而滿足了尋找最優(yōu)解得必要條件,即遺傳算法存在著找到全局最優(yōu)解得可能性.而積木塊假設(shè)指出,遺傳算法所具備尋找到全局最優(yōu)解得水平,即具有低階、短距、高平均適應(yīng)度的模式在遺傳算子的作用下,相互結(jié)合,遺傳算法全能生成高階

3、、長(zhǎng)距、低適應(yīng)度模式,最終求得全局最優(yōu)解局收斂性分析取得了很大進(jìn)展,文獻(xiàn)1給出了基于二進(jìn)制編碼的收斂性經(jīng)典結(jié)果及在群體無(wú)限大的假設(shè)下,討論了分別單獨(dú)使用交叉和變異算子實(shí)數(shù)編碼遺傳算法的收斂性.文獻(xiàn)2在采用最優(yōu)個(gè)體保存策略的前提下得到了保證收斂的一般條件,并以之檢驗(yàn)了采用常用的交叉與變異算子時(shí)的實(shí)數(shù)編碼遺傳算法的收斂性.總體而言,遺傳算法的根底理論研究至今還沒(méi)有取得突破性進(jìn)展,理論與應(yīng)用之間還存在著很大差距.在算法設(shè)計(jì)方面開(kāi)展,遺傳算法需要選擇的運(yùn)行參數(shù)主要有群體規(guī)模,交叉概率、變異概率、終止代數(shù),然而編碼方式也對(duì)遺傳算法的性能有較大的影響.在編碼方式的開(kāi)展,從由二進(jìn)制編碼逐漸開(kāi)展為十進(jìn)制編碼.

4、參數(shù)的限制由靜態(tài)的設(shè)置逐漸演變?yōu)閯?dòng)態(tài)自適應(yīng)技術(shù),而交叉、變異算子也不斷進(jìn)行改良,將算法分層3或其他算法進(jìn)行融合,很好的改良了遺傳算法.2、遺傳算法的根本原理及實(shí)現(xiàn)的主要因素遺傳算法模擬基因重組與進(jìn)化的自然過(guò)程,把待解決的問(wèn)題的參數(shù)進(jìn)行編碼為基因,假設(shè)干基因組成一個(gè)染色體個(gè)體,許多染色體類(lèi)似于自然選擇、配對(duì)交叉和變異的運(yùn)算,經(jīng)過(guò)屢次重復(fù)迭代直至得到最后的優(yōu)化結(jié)果.遺傳算法的實(shí)現(xiàn)需要對(duì)其進(jìn)行參數(shù)編碼、遺傳操作運(yùn)算包括交叉運(yùn)算、變異運(yùn)算、選擇運(yùn)算、適應(yīng)度函數(shù)設(shè)計(jì)、參數(shù)的限制與約束條件的處理來(lái)實(shí)現(xiàn).對(duì)各個(gè)局部進(jìn)行良好的處理才能使整個(gè)算法性能最正確,尋求出最優(yōu)解4?6.編碼是遺傳算法要解決的首要問(wèn)題.編

5、碼就是把一個(gè)問(wèn)題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法.為了克服二進(jìn)制代碼之間的漢明距離很大的問(wèn)題提出格雷碼,然而引入了另一層隱懸崖,采用大符號(hào)集編碼及逐漸提出了十進(jìn)制編碼、動(dòng)態(tài)編碼等等編碼方式.交叉運(yùn)算是按較大概率從種群中選擇兩個(gè)個(gè)體,按某種方式相互交換兩個(gè)個(gè)體的某個(gè)或某些局部基因,從而形成兩個(gè)新的個(gè)體,其繼承了父代的根本特征.它是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征,是產(chǎn)生新個(gè)體的主要方法,也對(duì)算法的收斂性起主要作用.交叉算子的設(shè)計(jì)和實(shí)現(xiàn)與具體的問(wèn)題密切相關(guān),前面的編碼一同考慮,得到一種好的交叉算子是研究者們一直致力于的工作.變異運(yùn)算以較小的概率對(duì)個(gè)體編碼串上的某個(gè)或

6、某些值進(jìn)行改變,進(jìn)而形成新個(gè)體.變異本身是一種隨機(jī)算法,與交叉和選擇算子結(jié)合能夠預(yù)防某些信息的喪失,維持種群的多樣性預(yù)防出現(xiàn)早熟現(xiàn)象,變異的方向性可能引導(dǎo)遺傳的方向性,加速最優(yōu)解得收斂.交叉算子和變異算子相互配合,共同完成對(duì)空間的全局搜索和局部搜索,從而使遺傳算法能夠以良好的搜索性能完成最優(yōu)化問(wèn)題的尋優(yōu)過(guò)程.選擇運(yùn)算對(duì)個(gè)體進(jìn)行優(yōu)勝劣汰,根據(jù)每個(gè)個(gè)體的適應(yīng)度值大小選擇,適應(yīng)度較高的個(gè)體被遺傳到下一代群體中的概率較大；適應(yīng)度較低的個(gè)體被遺傳到下一代群體中的概率較小.可以使得到群體中個(gè)體的適應(yīng)值不斷接近最優(yōu)解.選擇算子在預(yù)防基因損失,提升搜索速度和全局收斂方面有著舉足輕重的作用.選擇不的開(kāi)展方當(dāng)會(huì)造

7、成群體進(jìn)化停止不前；或使適應(yīng)度值偏大的個(gè)體誤導(dǎo)群體向,使遺傳失去多樣性,產(chǎn)生早熟問(wèn)題.另外,選擇與編碼方式無(wú)關(guān).適應(yīng)度函數(shù)設(shè)計(jì),適應(yīng)度函數(shù)用于轉(zhuǎn)換目標(biāo)函數(shù)值,給每一個(gè)個(gè)體一個(gè)非負(fù)的價(jià)值數(shù).適應(yīng)度函數(shù)通常根據(jù)目標(biāo)函數(shù)采用一定的轉(zhuǎn)換關(guān)系來(lái)設(shè)置.選擇運(yùn)算是根據(jù)適應(yīng)值函數(shù)得到結(jié)果來(lái)進(jìn)行選擇的,其分辨程度對(duì)選擇及整個(gè)算法都有很大的影響.即適應(yīng)度函數(shù)設(shè)計(jì)不當(dāng),有可能造成在遺傳進(jìn)化的初期,超常個(gè)體會(huì)因競(jìng)爭(zhēng)力突出而限制選擇過(guò)程,影響算法的全局優(yōu)化性能；在遺傳進(jìn)化的后期,種群中個(gè)體適應(yīng)度差異較小時(shí),繼續(xù)優(yōu)化的潛能下降,可能獲得某個(gè)局部最優(yōu)解,這兩種問(wèn)題的出現(xiàn).良好的適應(yīng)度函數(shù)能夠起到重要作用,是遺傳算法設(shè)計(jì)的一

8、個(gè)重要方面.參數(shù)的限制與約束條件的處理,限制參數(shù)選擇的是否合理直接影響算法的收斂速度和搜索效率,當(dāng)前沒(méi)有完善的理論指導(dǎo)它的選擇,還主要是根據(jù)經(jīng)驗(yàn).參數(shù)的限制對(duì)遺傳算法的性能有較大的影響.良好的參數(shù)設(shè)置可以很好的改良算法的性能,加速算法的收斂.對(duì)約束條件進(jìn)行處理,目前尚無(wú)處理各種約束條件的方法,根據(jù)具體問(wèn)題而定,常采用搜索空間限定法,可行解變換法和罰函數(shù)法等等.3、遺傳算法開(kāi)展趨勢(shì)遺傳算法作為一種優(yōu)化算法,其目的在于針對(duì)目標(biāo)函數(shù)來(lái)進(jìn)行求解未知參量的最優(yōu)解.對(duì)于其研究的方向也是根據(jù)其目標(biāo)函數(shù)來(lái)如何進(jìn)行求解得到最優(yōu)解.即可以應(yīng)用于能建立出目標(biāo)函數(shù)的任何一領(lǐng)域.對(duì)算法本身的性能研究,使算法在其可靠性、

9、計(jì)算效率提升；通過(guò)不同算法的優(yōu)點(diǎn)有機(jī)結(jié)合,形成混合算法；可以根據(jù)實(shí)際問(wèn)題建立目標(biāo)函數(shù)選擇適宜的參數(shù)限制及應(yīng)用范圍調(diào)整.基于遺傳算法自身的研究,早熟問(wèn)題使種群失去了進(jìn)化水平,是目前最難解決的問(wèn)題.通常的表現(xiàn)是群體中所有的個(gè)體進(jìn)化一定的代數(shù)后就陷于同一極值而停止進(jìn)化了,或者接近最優(yōu)解的個(gè)體總是被淘汰,找不到最優(yōu)解.然而它的編碼不規(guī)那么及編碼存在的不準(zhǔn)確性,其搜索的計(jì)算量大且搜索效率低等等,也嚴(yán)重影響了遺傳算法的應(yīng)用.需要設(shè)計(jì)出良好的編碼、良好的選擇方式及良好的交叉、變異算子來(lái)改良算法中的不中之處.遺傳算法與其他計(jì)算智能方法的相互滲透和結(jié)合7.如遺傳算法與模糊推理以及混沌理論、與傳統(tǒng)算法、神經(jīng)網(wǎng)絡(luò)算法、粒子群算法、蟻群算法等等其他智能計(jì)算方法相互滲透和結(jié)合,必能到達(dá)取長(zhǎng)補(bǔ)短的作用.混合算法的實(shí)質(zhì)是通過(guò)不同算法的優(yōu)點(diǎn)有機(jī)結(jié)合,改善單純算法的性能.然而隨著實(shí)際問(wèn)題難度的增加,對(duì)遺傳算法本身的缺乏逐漸顯露,即需要進(jìn)一步改良,如單目標(biāo)函數(shù)不在是以前的單峰一維或多峰單維或單峰多維,而是多峰多維且維數(shù)的增高,對(duì)求解的問(wèn)題難度將急劇增加.針對(duì)不同問(wèn)題采用重新設(shè)計(jì)程序、設(shè)計(jì)算法,采用一切有效方法來(lái)完成工程任務(wù),是研究的目的.對(duì)多峰高維單目標(biāo)函數(shù)在有限時(shí)間或迭代次數(shù)穩(wěn)定優(yōu)化8將是以后開(kāi)展的一個(gè)重要方向,對(duì)多目標(biāo)函數(shù)優(yōu)化也成為研究熱點(diǎn)94、小結(jié)本文從遺傳算法的起源入手,介紹了