李建福,陳義保
(煙臺(tái)大學(xué) 機(jī)電汽車工程學(xué)院,山東煙臺(tái) 264005)
遺傳算法是上個(gè)世紀(jì)70年代由美國(guó)密執(zhí)安大學(xué)的Holland教授提出的[1],是一種基于自然遺傳和自然選擇機(jī)理的全局尋優(yōu)搜索方法。因?yàn)榫哂泻?jiǎn)單通用、魯棒性強(qiáng)、適于并行處理以及高效、實(shí)用等顯著特點(diǎn),所以其在各個(gè)領(lǐng)域得到了廣泛應(yīng)用,取得了良好效果,并逐漸成為重要的智能算法之一。但在實(shí)際應(yīng)用過(guò)程中,遺傳算法也暴露出了一些自身所固有的缺點(diǎn),比如容易早熟、局部尋優(yōu)能力差、求解精度不高等。
傳統(tǒng)的遺傳算法,可以很快到達(dá)最優(yōu)解的90%左右[2],但是要達(dá)到最優(yōu)解,往往還需要大量的時(shí)間,也就是遺傳算法具有較強(qiáng)的全局搜索能力,但是其局部搜索能力不強(qiáng)。本文提出的基于靈敏度分析的改進(jìn)遺傳算法,將目標(biāo)函數(shù)提供的導(dǎo)數(shù)信息加入到算法的搜索過(guò)程中去[3],使種群中的優(yōu)秀個(gè)體,能按照指定的方向繼續(xù)進(jìn)化,有效地提高了算法的局部搜索能力。同時(shí),在該算法中融入了小生境技術(shù),其應(yīng)用有效地保持了種群的多樣性,提高了全局搜索能力,避免陷入局部最優(yōu)解。
小生境是指在特定環(huán)境中一種組織的功能,而把有共同特性的組織稱為物種。該技術(shù)就是將每一代遺傳個(gè)體分成若干類,從每個(gè)類中選出若干適應(yīng)度較大的個(gè)體,作為一個(gè)類的優(yōu)秀代表組成一個(gè)種群,再在種群中以及不同的種群之間通過(guò)雜交、變異,產(chǎn)生新一代個(gè)體群。本文使用的是基于排擠的小生境算法[4],其基本思想是依據(jù)個(gè)體之間的相似性,將種群分為若干個(gè)小生境,并排擠掉同一小生境中的較差的個(gè)體。這樣,各小生境中的最優(yōu)個(gè)體,便可以認(rèn)為是局部最優(yōu)解鄰域內(nèi)的一點(diǎn)。個(gè)體之間的相似性,用編碼串之間的海明距離來(lái)度量:
很顯然,dij越小,Xi和 Xj的相似程度就越大;dij越大,Xi和Xj的相似程度就越小。如果dij<L (L為設(shè)定的一較小的正數(shù)),也就說(shuō)明它們屬于同一小生境,那么就對(duì)適應(yīng)度較小的施加較強(qiáng)的懲罰函數(shù)Fmin=Penalty,其中Penalty為一個(gè)很小的正數(shù)。在基本遺傳算法運(yùn)行的后期,小生境技術(shù)的融入,能克服適應(yīng)度高的個(gè)體大量繁殖而充滿整個(gè)群體的缺陷,避免早熟現(xiàn)象的發(fā)生,保證了種群的多樣性及對(duì)整個(gè)解空間的搜索。
靈敏度就是導(dǎo)數(shù)信息,從數(shù)學(xué)意義上講,它反映了函數(shù)對(duì)某些自變量xi的變化梯度,若函數(shù)F(x)可導(dǎo),其一階靈敏度S在連續(xù)系統(tǒng)中,可表示為S=F(x)/xi;在離散系統(tǒng)中,可表示為S=ΔF(x)/Δxi,分別為一階微分靈敏度和一階差分靈敏度[5]。當(dāng)前靈敏度計(jì)算方法主要有3類:解析法、差分法和兩者混合的半解析法。解析法精度有保證,差分法和半解析法求解過(guò)程簡(jiǎn)單,易于工程實(shí)現(xiàn)。
在遺傳算法中引入目標(biāo)函數(shù)的導(dǎo)數(shù)信息,就可以通過(guò)靈敏度向量所指的方向?qū)ふ易顑?yōu)解,如果設(shè)問(wèn)題的目標(biāo)函數(shù)為f(x),種群中個(gè)體維數(shù)為m,那么目標(biāo)函數(shù)f(x)的m維靈敏度向量可以表示為:
如果該向量方向始終指向增長(zhǎng)方向,說(shuō)明該方向是指向最大值,那么朝相反的方向移動(dòng)則得到極小值,即:
如果該向量方向指向下降的方向,說(shuō)明該方向是指向最小值,那么沿著該方向移動(dòng)便得到最小值:
其中,η稱為步長(zhǎng),是一個(gè)很小的正數(shù)。
在實(shí)際應(yīng)用中,由于某些目標(biāo)函數(shù)不具有可導(dǎo)性,有些甚至無(wú)法寫出數(shù)學(xué)表達(dá)式,因此目標(biāo)函數(shù)的導(dǎo)數(shù)信息往往不能用解析式表達(dá)出來(lái)。為了簡(jiǎn)便起見(jiàn),本文將利用目標(biāo)函數(shù)的一階偏微分,來(lái)近似地代替其導(dǎo)數(shù)信息,即表示為:
對(duì)群體中每個(gè)小生境的最優(yōu)個(gè)體進(jìn)行基于靈敏度向量的局部尋優(yōu),就能使個(gè)體向局部最優(yōu)解不斷地靠近,從而增強(qiáng)了算法的局部搜索能力,提高了算法的計(jì)算精確度,具體步驟如下:
else個(gè)體X已經(jīng)到達(dá)了峰值。
輪盤賭選擇法是一種回放式隨機(jī)采樣方法,也是遺傳算法中最早被提出來(lái)的一種方法。因?yàn)檫@種方法簡(jiǎn)單而且實(shí)用,所以被廣泛使用。但由于隨機(jī)操作的原因,這種選擇方法的選擇誤差比較大,有的時(shí)侯甚至?xí)霈F(xiàn)“退化”現(xiàn)象,這樣便使適應(yīng)度較高的個(gè)體失去了選擇機(jī)會(huì)。因此本文選用了一種改進(jìn)的多輪輪盤選擇算子[6],改進(jìn)的選擇算子每產(chǎn)生M個(gè)隨機(jī)數(shù)來(lái)確定一個(gè)個(gè)體,取代了傳統(tǒng)輪盤賭算子中的每產(chǎn)生一個(gè)隨機(jī)數(shù)確定一個(gè)個(gè)體,這樣產(chǎn)生隨機(jī)數(shù)的數(shù)量由原來(lái)的M增至M2,使隨機(jī)數(shù)的作用體現(xiàn)的更精確,從而降低了隨機(jī)操作所產(chǎn)生的誤差,提高了算子的選優(yōu)能力,確保了優(yōu)秀的個(gè)體能夠存留下來(lái)。
交叉運(yùn)算是產(chǎn)生新個(gè)體的主要方法,它決定了遺傳算法的全局搜索能力。為了提高算法的全局搜索能力,本文采用算術(shù)交叉算子[7]。交叉后一點(diǎn)落于進(jìn)行交叉的父代之間,另一點(diǎn)落于靠近較好父代的一側(cè),使解能朝著較好的方向發(fā)展。自適應(yīng)交叉系數(shù),能使交叉量隨著進(jìn)化代數(shù)的增大而減小。在算法中隨機(jī)選取兩個(gè)交叉?zhèn)€體Xi和Xj,先比較這兩個(gè)個(gè)體的適應(yīng)度值F(Xi)和F(Xj),在這里我們可以假設(shè)F(Xi)>F(Xj),交叉點(diǎn)選為xik和xjk,那么交叉結(jié)果可以表示為:
其中
a0為預(yù)定系數(shù);
t為當(dāng)前進(jìn)化代數(shù);
T為最大進(jìn)化代數(shù);
Nk為取值范圍的上限;
Mk為xik取值范圍的下限。
變異運(yùn)算雖是產(chǎn)生新個(gè)體的輔助方法,但也是必不可少的一個(gè)步驟,決定了遺傳算法的局部搜索能力。為了增強(qiáng)算法的局部尋優(yōu)能力,本文引入非均勻變異算子,重點(diǎn)搜索原個(gè)體附近的微小區(qū)域。如果變異個(gè)體設(shè)為X,變異點(diǎn)設(shè)為xi,取值范圍為[Nk,Mk],那么變異結(jié)果由下式?jīng)Q定:
式中
△(t,y)=y·(1-r(1-t/T)b),△(t,y)表示[0,y]范圍內(nèi)符合非均勻變異的一個(gè)隨機(jī)數(shù);
r為[0,1]范圍內(nèi)的符合均勻分布的一個(gè)隨機(jī)數(shù);
T為最大進(jìn)化代數(shù);
b為一個(gè)系統(tǒng)參數(shù)。
由此可見(jiàn),該算法在進(jìn)化的初始階段,將近似地進(jìn)行均勻隨即搜索,隨著進(jìn)化的延續(xù),到了后期該算法將重點(diǎn)搜尋個(gè)體附近的微小區(qū)域,也就是進(jìn)行局部搜索。
算法的具體步驟如下:
Step1:設(shè)置進(jìn)化代數(shù),隨機(jī)產(chǎn)生M個(gè)初始個(gè)體組成初始種群 p(t),并求出各個(gè)個(gè)體的適應(yīng)度 Fi(i=1,2,…,M)。
Step2:根據(jù)個(gè)體的適應(yīng)度對(duì)其進(jìn)行降序排列,記憶前N個(gè)個(gè)體(N Step3:選擇運(yùn)算。用前面提的多輪輪盤賭法,對(duì)群體P(t)進(jìn)行選擇運(yùn)算,得到種群p'(t)。 Step4:交叉運(yùn)算。對(duì)種群p'(t)進(jìn)行算術(shù)交叉運(yùn)算,得到種群p''(t)。 Step5:變異算法。對(duì)種群p''(t)進(jìn)行非均勻變異運(yùn)算,得到種群p'''(t)。 Step6:小生境排擠運(yùn)算。將上面經(jīng)過(guò)選擇、交叉、變異運(yùn)算得到的M個(gè)個(gè)體和步驟2所記憶的N個(gè)個(gè)體合并在一起,得到一個(gè)含有M+N個(gè)個(gè)體的新群體。按照式(1)求出這M+N個(gè)個(gè)體中每?jī)蓚€(gè)個(gè)體Xi和Xj之間的海明距離。當(dāng) Xi-Xj莨L時(shí),比較個(gè)體Xi和Xj的適應(yīng)度大小,并對(duì)其中適應(yīng)度較低的個(gè)體處以罰函數(shù)。 Step7:敏度優(yōu)化運(yùn)算。按照式(5)計(jì)算得到的靈敏度向量,對(duì)這M+N個(gè)個(gè)體進(jìn)行靈敏度優(yōu)化。 Step8:計(jì)算、評(píng)價(jià)這M+N個(gè)個(gè)體,按適應(yīng)度降序排序,并分別記錄記憶前M和前N個(gè)個(gè)體。 Step9:終止條件判斷。若不滿足終止條件,則:t=t+1,并將步驟8排序中的前M個(gè)個(gè)體作為新的下一代群體P(t),轉(zhuǎn)到步驟3;若滿足終止條件,則輸出計(jì)算結(jié)果,算法結(jié)束。 為了驗(yàn)證本文提出的改進(jìn)算法的性能,選用Shubert作為測(cè)試函數(shù),這是一個(gè)多峰函數(shù),該函數(shù)在其定義域內(nèi)共有760個(gè)局部最小值,其中18個(gè)是全局最小值。全局最優(yōu)點(diǎn)處的函數(shù)值為F=-186.73090883,其函數(shù)數(shù)學(xué)表達(dá)式如下: 本試驗(yàn)用Matlab語(yǔ)編寫程序,種群規(guī)模M=100,記錄優(yōu)秀個(gè)體為N=40,最大進(jìn)化代數(shù)T=500,交叉概率pc=0.8,變異概率pm=0.1,海明距離下限L=0.4,罰函數(shù)Penalty=10-3,自適應(yīng)交叉參數(shù)a0=40.0,靈敏度運(yùn)算中參數(shù)η=10-4。 表1給出了本文算法與常規(guī)遺傳算法(GA)、基本小生境遺傳算法(NGA)、改進(jìn)的小生境遺傳算法(GNGA)[8]的性能對(duì)比: 表1 本文算法與其他遺傳算法的性能對(duì)比 從表1中的結(jié)果可以明顯看出,本文所使用的改進(jìn)算法對(duì)多峰Shubert函數(shù)進(jìn)行全局尋優(yōu),收斂速度明顯比其他遺傳算法要快,計(jì)算結(jié)果的精確度也較高。 以文獻(xiàn)[9]中的曲柄搖桿機(jī)構(gòu)再現(xiàn)運(yùn)動(dòng)規(guī)律為優(yōu)化實(shí)例。所謂再現(xiàn)運(yùn)動(dòng)規(guī)律,是指當(dāng)主動(dòng)件運(yùn)動(dòng)規(guī)律一定時(shí),要求從動(dòng)件按給定規(guī)律運(yùn)動(dòng)[10],曲柄搖桿機(jī)構(gòu)簡(jiǎn)圖如下所示: 圖1 曲柄搖桿機(jī)構(gòu)簡(jiǎn)圖 由于按比例對(duì)桿件的長(zhǎng)度進(jìn)行縮放,將不會(huì)改變曲柄搖桿機(jī)構(gòu)的運(yùn)動(dòng)規(guī)律,所以通常情況下設(shè)l1=1,l2、l3可由l1決定,機(jī)架長(zhǎng)l4事先給定,因而設(shè)計(jì)變量定為: 其中l(wèi)2、l3為桿件尺寸。 以給定的運(yùn)動(dòng)規(guī)律與機(jī)構(gòu)實(shí)際運(yùn)動(dòng)規(guī)律間的偏差最小為目標(biāo)函數(shù),即: 其中ΨEi為期望輸出角,Ψi為實(shí)際輸出角,m為輸入角的等分?jǐn)?shù)。 約束條件由傳動(dòng)角滿足的許用值和曲柄搖桿機(jī)構(gòu)滿足的曲柄存在條件決定,傳動(dòng)角的最大最小許用值為,通過(guò)計(jì)算整理得約束為: 用基于靈敏度分析改進(jìn)的遺傳算法,對(duì)曲柄搖桿機(jī)構(gòu)再現(xiàn)運(yùn)動(dòng)規(guī)律進(jìn)行優(yōu)化,并與小生境GA[9]及罰函數(shù)法[10]的優(yōu)化結(jié)果進(jìn)行對(duì)比,如表2所示。 表2 本文算法與其他算法的計(jì)算結(jié)果對(duì)比 如表2所示,本文的算法收斂精度較高,而且結(jié)果更優(yōu)。 本文將傳統(tǒng)優(yōu)化算法的精髓導(dǎo)數(shù)信息引到了遺傳算法中,在保證了算法的全局搜索能力的同時(shí),加強(qiáng)了算法的局部搜索能力。小生境技術(shù)的利用,增加了種群中個(gè)體的多樣性,在保留了最優(yōu)解的同時(shí),有效的防止了早熟現(xiàn)象的發(fā)生。改進(jìn)的遺傳算子,改善了算法的各項(xiàng)性能,有效提高了算法的可靠性。通過(guò)對(duì)多峰Shubert函數(shù)的仿真試驗(yàn),說(shuō)明該算法能有效的提高局部搜索能力及解的精度;對(duì)曲柄搖桿機(jī)構(gòu)再現(xiàn)運(yùn)動(dòng)規(guī)律的實(shí)例優(yōu)化,表明該算法具有一定實(shí)際應(yīng)用價(jià)值。 [1]Holland J H.Adaptation in Natural and Artificial Systems[M].Cambridge,MA,USA:MIT Press,1975. [2]周洪偉,徐松林,徐 靜.改進(jìn)的小生境遺傳算法[J].軟件時(shí)空,2007,23(6-3):208-209. [3]何新貴,梁久禎.利用目標(biāo)函數(shù)梯度的遺傳算法[J].軟件學(xué)報(bào),2001,12(7):981-986. [4]周 麗,孫樹(shù)棟.遺傳算法原理及應(yīng)用[M].北京:國(guó)防工業(yè)出版社,2001. [5]HAFTKA R T.Second order sensitivity derivatives in structural optimization[J].AIAA Journal,1982,(20):1765-1766. [6]陳友文.一種改進(jìn)選擇算子和基于小生境的遺傳算法[J].計(jì)算機(jī)與數(shù)字工程,2006,37(6):21-24. [7]董 穎,劉歡杰.一種基于實(shí)數(shù)編碼的改進(jìn)遺傳算法[J].東北大學(xué)學(xué)報(bào),2005,26(4):119-221. [8]黃聰明,陳湘秀.小生境遺傳算法的改進(jìn)[J].北京理工大學(xué)學(xué)報(bào),2004,24(8):675-678. [9]陳格娟,崔 煒,張京軍.小生境遺傳算法在機(jī)械優(yōu)化設(shè)計(jì)中的應(yīng)用[J].河北建筑科技學(xué)院學(xué)報(bào),2004,21(1):56-59. [10]劉惟信.機(jī)械最優(yōu)化設(shè)計(jì)[M].北京:清華大學(xué)出版社,1994.4 試驗(yàn)及實(shí)例優(yōu)化
4.1 試驗(yàn)及分析
4.2 實(shí)例優(yōu)化
5 結(jié)束語(yǔ)