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

白 灝

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

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

白 灝

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

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

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

一、遺傳算法介紹

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

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

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

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

二、算法的改進(jìn)

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

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

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

第二步進(jìn)行變異。令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個(gè)分量具有相互獨(dú)立性.α∈(0,1]為壓縮因子.若xi+m(t)∈Ω,則轉(zhuǎn)進(jìn)入第三步;否則重做第二步。

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

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

三、數(shù)值舉例

該函數(shù)在[0,1]區(qū)間內(nèi)有多個(gè)局部極值點(diǎn),其全局最優(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)具有多個(gè)局部極值點(diǎn)和一個(gè)全局最優(yōu)點(diǎn),全局最優(yōu)值為: f(0.438 974,0.305 734)=-16.091 72。

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

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

四、結(jié)果與分析

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

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

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

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

[3] 詹仁超,李應(yīng)岐.基于混合算法的導(dǎo)彈部隊(duì)鐵路機(jī)動(dòng)路徑選擇[J].四川兵工學(xué)報(bào),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ù)學(xué)院科技基金項(xiàng)目“高校貧困生認(rèn)定的模糊綜合評(píng)判”(項(xiàng)目編號(hào):HKJ12-10),安徽省高等學(xué)校省級(jí)優(yōu)秀青年人才基金項(xiàng)目“基于遺傳算法的DNA編碼序列優(yōu)化設(shè)計(jì)與探索”(項(xiàng)目編號(hào):2012SQRL259)

白灝(1978-),男,山東菏澤人,講師,研究方向?yàn)槟Ｊ阶R(shí)別與數(shù)字圖像處理,電話:0554-6656532。