基于靈敏度分析的改進(jìn)遺傳算法

李建福，陳義保

（煙臺(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)用過程中，遺傳算法也暴露出了一些自身所固有的缺點(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ù)信息加入到算法的搜索過程中去[3],使種群中的優(yōu)秀個(gè)體，能按照指定的方向繼續(xù)進(jìn)化，有效地提高了算法的局部搜索能力。同時(shí)，在該算法中融入了小生境技術(shù)，其應(yīng)用有效地保持了種群的多樣性，提高了全局搜索能力，避免陷入局部最優(yōu)解。

1 算法策略

1.1 小生境算法

小生境是指在特定環(huán)境中一種組織的功能，而把有共同特性的組織稱為物種。該技術(shù)就是將每一代遺傳個(gè)體分成若干類，從每個(gè)類中選出若干適應(yīng)度較大的個(gè)體，作為一個(gè)類的優(yōu)秀代表組成一個(gè)種群，再在種群中以及不同的種群之間通過雜交、變異，產(chǎn)生新一代個(gè)體群。本文使用的是基于排擠的小生境算法[4]，其基本思想是依據(jù)個(gè)體之間的相似性，將種群分為若干個(gè)小生境，并排擠掉同一小生境中的較差的個(gè)體。這樣，各小生境中的最優(yōu)個(gè)體，便可以認(rèn)為是局部最優(yōu)解鄰域內(nèi)的一點(diǎn)。個(gè)體之間的相似性，用編碼串之間的海明距離來度量：

很顯然，dij越小，Xi和 Xj的相似程度就越大；dij越大，Xi和Xj的相似程度就越小。如果dij＜L (L為設(shè)定的一較小的正數(shù))，也就說明它們屬于同一小生境，那么就對(duì)適應(yīng)度較小的施加較強(qiáng)的懲罰函數(shù)Fmin=Penalty，其中Penalty為一個(gè)很小的正數(shù)。在基本遺傳算法運(yùn)行的后期，小生境技術(shù)的融入，能克服適應(yīng)度高的個(gè)體大量繁殖而充滿整個(gè)群體的缺陷，避免早熟現(xiàn)象的發(fā)生，保證了種群的多樣性及對(duì)整個(gè)解空間的搜索。

1.2 敏度分析原理

靈敏度就是導(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類：解析法、差分法和兩者混合的半解析法。解析法精度有保證，差分法和半解析法求解過程簡(jiǎn)單，易于工程實(shí)現(xiàn)。

在遺傳算法中引入目標(biāo)函數(shù)的導(dǎo)數(shù)信息，就可以通過靈敏度向量所指的方向?qū)ふ易顑?yōu)解，如果設(shè)問題的目標(biāo)函數(shù)為f(x)，種群中個(gè)體維數(shù)為m，那么目標(biāo)函數(shù)f(x)的m維靈敏度向量可以表示為：

如果該向量方向始終指向增長(zhǎng)方向，說明該方向是指向最大值，那么朝相反的方向移動(dòng)則得到極小值，即：

如果該向量方向指向下降的方向，說明該方向是指向最小值，那么沿著該方向移動(dòng)便得到最小值：

其中，η稱為步長(zhǎng)，是一個(gè)很小的正數(shù)。

在實(shí)際應(yīng)用中，由于某些目標(biāo)函數(shù)不具有可導(dǎo)性，有些甚至無法寫出數(shù)學(xué)表達(dá)式，因此目標(biāo)函數(shù)的導(dǎo)數(shù)信息往往不能用解析式表達(dá)出來。為了簡(jiǎn)便起見，本文將利用目標(biāo)函數(shù)的一階偏微分，來近似地代替其導(dǎo)數(shù)信息，即表示為：

對(duì)群體中每個(gè)小生境的最優(yōu)個(gè)體進(jìn)行基于靈敏度向量的局部尋優(yōu),就能使個(gè)體向局部最優(yōu)解不斷地靠近，從而增強(qiáng)了算法的局部搜索能力，提高了算法的計(jì)算精確度，具體步驟如下：

else個(gè)體X已經(jīng)到達(dá)了峰值。

2 遺傳算子

2.1 選擇算子

輪盤賭選擇法是一種回放式隨機(jī)采樣方法，也是遺傳算法中最早被提出來的一種方法。因?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ù)來確定一個(gè)個(gè)體，取代了傳統(tǒng)輪盤賭算子中的每產(chǎn)生一個(gè)隨機(jī)數(shù)確定一個(gè)個(gè)體，這樣產(chǎn)生隨機(jī)數(shù)的數(shù)量由原來的M增至M2，使隨機(jī)數(shù)的作用體現(xiàn)的更精確，從而降低了隨機(jī)操作所產(chǎn)生的誤差，提高了算子的選優(yōu)能力，確保了優(yōu)秀的個(gè)體能夠存留下來。

2.2 交叉算子

交叉運(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取值范圍的下限。

2.3 變異算子

變異運(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ù)。

由此可見，該算法在進(jìn)化的初始階段，將近似地進(jìn)行均勻隨即搜索，隨著進(jìn)化的延續(xù)，到了后期該算法將重點(diǎn)搜尋個(gè)體附近的微小區(qū)域，也就是進(jìn)行局部搜索。

3 算法流程

算法的具體步驟如下：

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)過選擇、交叉、變異運(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é)束。

4 試驗(yàn)及實(shí)例優(yōu)化

4.1 試驗(yàn)及分析

為了驗(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語編寫程序，種群規(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é)果的精確度也較高。

4.2 實(shí)例優(yōu)化

以文獻(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)角的最大最小許用值為，通過計(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)。

5 結(jié)束語

本文將傳統(tǒng)優(yōu)化算法的精髓導(dǎo)數(shù)信息引到了遺傳算法中，在保證了算法的全局搜索能力的同時(shí)，加強(qiáng)了算法的局部搜索能力。小生境技術(shù)的利用，增加了種群中個(gè)體的多樣性，在保留了最優(yōu)解的同時(shí)，有效的防止了早熟現(xiàn)象的發(fā)生。改進(jìn)的遺傳算子，改善了算法的各項(xiàng)性能，有效提高了算法的可靠性。通過對(duì)多峰Shubert函數(shù)的仿真試驗(yàn)，說明該算法能有效的提高局部搜索能力及解的精度；對(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]周 麗，孫樹棟.遺傳算法原理及應(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.