遺傳算法的優(yōu)化原理及應(yīng)用

遺傳算法的優(yōu)化原理及應(yīng)用

遺傳算法方法（ga）是模擬自然界生物進化過程和機制以解決極端問題的一種自組織和適應(yīng)性人工智能技術(shù)。它是模擬達爾文的遺傳在選擇和自然淘汰的生物進化過程的計算模型。由于它具有良好的并行性,不受搜索空間是否連續(xù)、可微的限制,能夠處理傳統(tǒng)優(yōu)化方法難以解決的復(fù)雜問題,具有極高的魯棒性和通用性而廣泛應(yīng)用于生產(chǎn)調(diào)度、工程設(shè)計、自動化控制等領(lǐng)域。盡管遺傳算法有許多優(yōu)點,但在實際使用中仍然存在許多不足和問題,主要表現(xiàn)為遺傳算法的“早熟”現(xiàn)象,即很快收斂到局部最優(yōu)解而不是全局最優(yōu)解;遺傳算法的搜索結(jié)果是在最優(yōu)值附近擺動,而不能達到最優(yōu)值。1改進方法1.1選擇問題:是提出了上世紀20傳統(tǒng)的二進制編碼存在解碼技術(shù)問題,更為重要的是二進制編碼還存在計算精度與計算速度之間兩難選擇的問題。十進制浮點數(shù)編碼可以避免數(shù)制的轉(zhuǎn)換、提高計算精度和速度。在多參數(shù)優(yōu)化的問題中為了計算精度和使用方便,通常采用十進制浮點數(shù)編碼。假設(shè)有n個待尋優(yōu)變量,則n個尋優(yōu)變量范圍內(nèi)的十進制浮點數(shù)排列在一起成為一個個體。如:x=x1,x2,?,xn.x=x1,x2,?,xn.1.2隨機搜索法算法大量地研究表明交叉過程的成熟化效應(yīng)使得在經(jīng)過若干代進化后種群的多樣度逐漸趨于零,從而導(dǎo)致過早收斂。為了避免陷入局部最優(yōu)解,必須拓寬搜索空間,增加群體多樣性。交叉和變異是對擴大解空間造成新區(qū)的有效方法,高交叉率會使體原有的高質(zhì)量個體淘汰速度高于其產(chǎn)生高質(zhì)量個體的速度,難以達到進化(優(yōu)化)的效果,但交叉率低又會使搜索過程停滯不前。突變率低則擴大算法搜索解空間的效率低,突變率高則可能破壞優(yōu)質(zhì)個體多,使整個算法趨于隨機搜索,從而使算法喪失模擬進化的仿生實質(zhì),缺乏有向性。上面的各個分寸如何確定,因具體問題而異,另外亦需要經(jīng)驗,到目前為止還無明確的計算公式。保持種群多樣性的確可以對算法的全局收斂性能進行改善,但這樣做究竟對全局收斂性有多大貢獻無從考量,片面地強調(diào)多樣性有時不僅不能防止早斂的發(fā)生,還會對算法的穩(wěn)定性、種群的整體收斂性造成很大影響。隨機試驗法,又稱為Monte-Carlo法、統(tǒng)計試驗法,其特點是占用內(nèi)存少,并且有較好的概率統(tǒng)計特性。在不改變交叉率和變異率的同時,利用隨機試驗法以防止局部收斂,即當算法在連續(xù)n代的最優(yōu)個體都無任何變化時,表明算法陷入了局部極值,需要采取措施使其跳出局部極值的束縛。這時,就對群體進行隨機試驗操作,對進化過程中的種群施加一較大擾動,使其脫離局部最優(yōu)點,開始新的搜索。具體操作為:只保留最優(yōu)值,重新生成其余個體。采用隨機試驗操作并非使種群退化,而是盡快擺脫進化遲鈍狀態(tài),開始新搜索。1.3基于馬爾科夫鏈的定量算法,采用最優(yōu)保留的機制,保證算法具有全局收斂性,但如果算法具有全局收斂性,則一般在10傳統(tǒng)的基于模式定理的對全局收斂性的定性分析認為遺傳算法是全局收斂的,最近基于馬爾科夫鏈的定量的數(shù)學(xué)證明認為簡單遺傳算法不是全局收斂的,而帶最優(yōu)保存的遺傳算法是全局收斂的。采用最優(yōu)保留的機制,以保證算法具有全局收斂性。即用父代的最優(yōu)個體來替換子代中最差個體。1.4優(yōu)解周邊搜索的控制在算搜索法的早期,應(yīng)擴大搜索范圍,以便快速的到最優(yōu)解附近;而在后期應(yīng)縮小搜索范圍,以防止搜索結(jié)果在最優(yōu)值附近擺動。作者采用自適應(yīng)的搜索范圍進行求解最優(yōu)值,即隨著算法進行到一定階段,搜索范圍隨之改變。2求解過程中的個體數(shù)據(jù)的預(yù)處理改進的遺傳算法步驟為:1)初始化,即輸入待求解問題的各種數(shù)據(jù)及控制參數(shù)如種群規(guī)模、雜交概率、變異概率及終止進化規(guī)則;2)確定染色體編碼方案(采用十進制浮點數(shù)編碼),隨機產(chǎn)生初始群體;3)求解出每個染色體的適應(yīng)值;4)模仿“適者生存,不適者淘汰”的自然規(guī)律進行競爭選擇,為了編程方便,本文采用將最優(yōu)的m個個體替換最差的m個個體以形成新的種群;5)判斷是否改變搜索范圍,是則進行,否則不改變搜索范圍;6)根據(jù)雜交概率、變異概率獨立地對解群中的個體進行交叉和變異操作;7)保留父代最優(yōu)個體,產(chǎn)生新的種群;8)若解群已滿足預(yù)設(shè)的進化終止準則,則停止,否則進行下一步;9)若算法陷入局部收斂,則進行隨機試驗法,然后返回第3步;否則直接返回第3步。利用改進的遺傳算法的程序流程框圖如圖1所示:3改進的遺傳計算方法的性能分析1x2算例1:求最大值,F1(x)=x+10sin(5x)+7cos(4x),x∈;算例2:求最大值,F2(x)=exp(-0.001x)cos2(0.8x),x∈.兩函數(shù)圖像如圖2、圖3所示:從圖2、圖3中可以看出兩函數(shù)有多個極值點,極易陷入局部最優(yōu)解。2兩種算法的比較改進后算法的參數(shù)為:種群規(guī)模為80,交叉率為0.95,變異率為0.08,最大進化代數(shù)為100。為了便于比較,GA參數(shù)與改進后算法的參數(shù)相同,進化終止條件相同,即連續(xù)n代最優(yōu)個體的適應(yīng)度函數(shù)值相等,則進化終止。對兩種算法各進行100次隨機仿真,不同算法實驗結(jié)果如表1。從表1可以看出,GA很容易早熟,并且求出的最好解大多是在最優(yōu)值的附近,很難求出最優(yōu)值。改進后的遺傳算法能很好地擺脫早熟,并能求出最優(yōu)值。3種算法間的隨機仿真實驗減少種群規(guī)模,其余參數(shù)保持不變,即種群規(guī)模為60,交叉率為0.95,變異率為0.08,最大進化代數(shù)為100的改進算法與種群規(guī)模為80,交叉率為0.95,變異率為0.08,最大進化代數(shù)為100的改進算法。對2種算法各進行100次隨機仿真,實驗結(jié)果如表2。從表2可以看出,改進后的遺傳算法在種群規(guī)模減少的情況下也能求出最優(yōu)值,這可以降低多參數(shù)尋優(yōu)問題的計算機內(nèi)存占有量和提高程序的運