白 灝

(淮南職業(yè)技術(shù)學院學生處, 安徽淮南232001)

優(yōu)化求最值中遺傳法的應用分析

白 灝

(淮南職業(yè)技術(shù)學院學生處, 安徽淮南232001)

簡單介紹了遺傳算法,并對遺傳算法進行改進,對于多峰值問題,為了避免陷入局部最優(yōu),結(jié)合Matlab作出圖像,利用遺傳算法,調(diào)整控制參數(shù),得到全局的最優(yōu)解,并加以舉例驗證。

非線性規(guī)劃; 多峰值問題; 遺傳算法控制參數(shù)

一、遺傳算法介紹

遺傳算法是數(shù)學領(lǐng)域近年來發(fā)展起來的一種智能算法,已經(jīng)廣泛地應用于各個行業(yè)。根據(jù)名稱也可以看出遺傳算法其實是人們模仿自然界的遺傳進化規(guī)律而衍生出來的,它在可行空間內(nèi)自動地進行搜索,而后通過不斷地重復淘汰最終獲得最優(yōu)值。第一次提出遺傳算法的是Michigan大學Holland教授,他通過多年對自然界發(fā)展規(guī)律的研究探索與實踐經(jīng)驗在1975年的時候提出了這種可以在全局內(nèi)搜索的智能算法。傳統(tǒng)的優(yōu)化問題一般是通過導數(shù)的方法來求解的,但是計算的前提是函數(shù)必須是連續(xù)而且可導的,這對于解決實際的工程問題具有很大的局限性,而遺傳算法的出現(xiàn)徹底解決了這一問題,這是因為其魯棒性和隨意性都較強,可以更為客觀充分地解決實際問題。

學過生物的人都知道生物可以繼承親代的某些性狀,所以才使得瓜農(nóng)種下的瓜只能長出瓜來,想讓它長成豆是不可能的,這就是遺傳?？梢詻Q定這種遺傳特性的物質(zhì)是基因(DNA),基因是遺傳物質(zhì)的基本單位,生物體所有的遺傳性狀都來自于基因的控制。生物體是由一個個細胞構(gòu)成的,在細胞核內(nèi)有一種很容易被染色的物質(zhì),人們通常叫它染色體或染色質(zhì),染色體和染色質(zhì)是同一物質(zhì)在不同時期的兩種表現(xiàn)形式,生命體的基因就是附著在這種染色體上的。細胞具有可以分裂的特性,在有絲分裂剛開始的時候完成DNA的復制和蛋白質(zhì)的合成,而后相同的染色體隨著細胞的分裂分別進入兩個細胞內(nèi),這就完成了遺傳物質(zhì)的復制與傳遞過程,這是高等生物遺傳物質(zhì)的傳遞介質(zhì)和方法。而在那些低等的原核生物細胞內(nèi),根本沒有成型的細胞核,也沒有相應的染色體,它們的遺傳物質(zhì)是在RNA上面,RNA與DNA從結(jié)構(gòu)組成上有點類似,只是DNA是雙鏈的,而RNA是單鏈結(jié)構(gòu)。在有性生殖過程中,細胞內(nèi)的染色體首先兩兩形成同源染色的聯(lián)會,同源染色體是指控制同一性狀不同表現(xiàn)形式的染色體,他們通過交叉互換隨著細胞的分裂進入兩個不同的子細胞內(nèi),染色體交叉互換的過程就是變異,通過變異過程可以產(chǎn)生全新的染色體,由這些新的染色體又可以使生物體出現(xiàn)一些新的性狀,這樣循環(huán)下去就完成了生命體的遺傳變異過程。

根據(jù)上述的分析可以看出,我們平常所用的遺傳算法也是采用同樣的機理和步驟進行的。遺傳算法的第一步就是確定遺傳算子,遺傳算子如果應用于P(t)代的話就可以得到P(t+1)代。遺傳算法中幾個比較重要的概念是選擇、交叉和變異。其中選擇主要是指從第t代中按照某種規(guī)律選出部分比較好的個體,將這些個體遺傳到第t+1代,形成第t+1代的種群P(t+1),而選擇這些個體的規(guī)律我們稱之為適應度,一般用函數(shù)的形式表示。交叉主要是指把第t代的種群P(t)內(nèi)的個體按照隨機組合的方式兩兩配對,相互交叉。遺傳算法中的變異主要是指針對種群內(nèi)的個體,按照一定的概率將它們上面的某些基因換成它們的等位基因,具體的操作步驟:第一步是初始化,也就是建立一個遺傳算法進化代的計數(shù)器,將它的最大進化代數(shù)用字母T來表示,而后就是先隨機生成初始種群,用字母M來表示;第二步就是對這些生成的種群內(nèi)的個體進行評價分析,也就是按照前文所說的方法根據(jù)適應度函數(shù)分別計算它們的適應度值;第三步就是進行優(yōu)良個體的選擇,將那些適應度值高的個體選擇出來;第四步是遺傳算法的交叉運算,將選出的遺傳算子根據(jù)一定的概率兩兩交叉配對;第五步是遺傳算法的變異操作,遺傳算子的某些部位發(fā)生變異,而產(chǎn)生新一代的種群P(t+1);第六步就是終止條件的判斷,根據(jù)前面設(shè)置的最大遺傳代數(shù),當t沒有達到T時,t加上1跳轉(zhuǎn)到算法的第二步循環(huán)運算。如果t已經(jīng)達到了最大遺傳代數(shù),則整個計算結(jié)束,此時適應度值雖大的解有就是整個運算的最優(yōu)解。

在通常的情況下染色體的長度應該是固定不變的,但是在個別情況下可以發(fā)生變化,此時的等位基因可以用整數(shù)或者實數(shù)來表示,當然也是可以用0和1來表示的,當用0和1表示的時候,染色體其實就是一串二進制的符號,每串二進制符號代表一種性狀,而且一般呈現(xiàn)出一一對應的關(guān)系。對于遺傳算法中的每個個體,都是要根據(jù)提前設(shè)定的適應度函數(shù)進行計算,求出它們各自的適應度值,而后根據(jù)對應的選擇概率從中找出較好的個體進行交叉變異的操作,從而形成新一代的個體,這樣循環(huán)下去種群中較好的適應度值與最優(yōu)值之間的差距越來越小,最終趨近于最優(yōu)值。

二、算法的改進

(一) 約束優(yōu)化問題

其中x=(x1,x2,…,xn)T,Ω為有界閉集。

(二) 改進遺傳算法的步驟

第二步進行變異。令xi+m(t)=xi(t)+αξ(i=1,2,…,m),其中ξ=N(0,σ)=(N(0,σ1), N(0,σ2),…,N(0,σm))T,N(0,σi)為均值為0、方差為的正態(tài)分布,且ξ的n個分量具有相互獨立性.α∈(0,1]為壓縮因子.若xi+m(t)∈Ω,則轉(zhuǎn)進入第三步;否則重做第二步。

第三步新個體計算。計算新個體xi+m(t)(i=1,2,…,m)處的目標函數(shù)值f(xi+m(t)),(i= 1,2,…,m)。

第五步終止檢驗。判別X(t+1)是否已達到終止檢驗的條件,若已滿足,則計算結(jié)束,并輸出最優(yōu)解x*(t+1);否則,令t=t+1,返回第二步。

三、數(shù)值舉例

該函數(shù)在[0,1]區(qū)間內(nèi)有多個局部極值點,其全局最優(yōu)值為f小(x)=-7.456 2,f大(x)= 1.1730。

例2 f(x,y)=(cos(2πx)+cos(2.5πx)-2.1)×(2.1-cos(3πy)-cos(3.5πy),其中(x,y)∈[0,3]×[0,1.5],利用Matlab作圖,如圖2所示。

該函數(shù)在[0,3]×[0,1.5]區(qū)域內(nèi)具有多個局部極值點和一個全局最優(yōu)點,全局最優(yōu)值為: f(0.438 974,0.305 734)=-16.091 72。

雖然該函數(shù)是一個單峰函數(shù),但卻十分光滑,其全局最優(yōu)值為f(0,0)=0,如圖3所示。

表1是算法A對上述三算例的計算結(jié)果:

四、結(jié)果與分析

由以上遺傳算法的解題過程不難看出,無論是搜索能力還是計算速度,改進后的遺傳算法都有了很大的提高。在實際的工程應用中,遺傳算法中的三個參數(shù)σ、m和α要根據(jù)具體的情況來定值,具體來說是從以下幾個角度著手。三個參數(shù)中種群m對遺傳算法結(jié)果的影響很大,如果我們選擇的種群太小,那么搜索就具有一定的局限性,也有可能陷入局部收斂的極值點內(nèi),但是也不是說種群規(guī)模就是越大越好,如果種群規(guī)模過大,會使得整個運算的速度大大降低,這樣要花費更多的時間,影響運算的效率;變異算子是遺傳算法中生成新種群的關(guān)鍵,有了它的存在搜索空間才可以不斷的得到更新和擴展,使循環(huán)過程不至于過早地進入局部的收斂中去,這是因為變異產(chǎn)生的新個體有很大的隨機性,可以覆蓋空間中的任何一個點,這里的σ表示正太分布的均方差,在遺傳算法中其實就相當于步長,隨著循環(huán)迭代次數(shù)的增加,步長值應該越來越小,只有這樣才能提高運算的精度。

改進后的遺傳算法是在循環(huán)迭代過程中修正步長。如果在好幾代內(nèi)都沒出現(xiàn)合適的下降點,那么就表明選擇的步長不合適,要進行縮小。如果在計算中發(fā)現(xiàn)問題的可行解范圍很大,那么初始步長σ的設(shè)定也應該大一些,這樣就可以使整個運算的搜索能力大大的提升。所以步長σ的主要作用就是用來將循環(huán)迭代的精度和速度控制在合理的范圍內(nèi)的。

[1] 吳昌友,孫福田,王福林.改進實數(shù)遺傳算法在減速器設(shè)計中的應用[J].東北農(nóng)業(yè)大學學報,2006(1): 78-81.

[2] 劉立民,靳晨霞,楊麗蕓,等.兩階段遺傳算法的結(jié)構(gòu)及性能分析[J].河北科技大學學報,2007(1):44-48.

[3] 詹仁超,李應岐.基于混合算法的導彈部隊鐵路機動路徑選擇[J].四川兵工學報,2012(7):62-65.

TP18

B

1671-4733(2014)06-0080-04

10.3969/j.issn.1671-4733.2014.06.021

2014-11-20

淮南職業(yè)技術(shù)學院科技基金項目“高校貧困生認定的模糊綜合評判”(項目編號:HKJ12-10),安徽省高等學校省級優(yōu)秀青年人才基金項目“基于遺傳算法的DNA編碼序列優(yōu)化設(shè)計與探索”(項目編號:2012SQRL259)

白灝(1978-),男,山東菏澤人,講師,研究方向為模式識別與數(shù)字圖像處理,電話:0554-6656532。