趙德勝，張 雪，李彩琴

ZHAO De-sheng,ZHANG Xue,LI Cai-qin

（西安郵電學(xué)院，西安 710121）

0 引言

所謂遺傳算法收斂的復(fù)雜條件，是指約束條件苛刻、可行解的可行區(qū)域狹窄的條件。降低發(fā)動機(jī)顫振故障發(fā)生的幾率，對發(fā)動機(jī)壓氣機(jī)轉(zhuǎn)子的制造、安裝作出一系列的限制措施是必要的。其中，最重要的兩個問題是如何控制葉片靜質(zhì)量矩和葉片固有頻率。除了在制造時采取措施以外，在安裝時降低葉片靜質(zhì)量矩和保證轉(zhuǎn)子葉片具有合格的固有頻率也是必不可少的。這就需要對葉片安裝施加必要的約束條件。在復(fù)雜條件下，人工葉片排序效率很低。

利用計算機(jī)求解此類問題時，葉片排序問題被看作是一個組合優(yōu)化問題。采用常規(guī)的組合優(yōu)化求解葉片排序問題，算法復(fù)雜，對于某些“惡劣”的數(shù)據(jù)可能求不出正確的排序結(jié)果。遺傳算法在求解組合優(yōu)化問題上具有很大的優(yōu)勢,但是當(dāng)葉片排序條件較為復(fù)雜時，收斂速度慢、甚至不能求出優(yōu)化排序結(jié)果；適應(yīng)度函數(shù)設(shè)計也較為困難。為解決這個問題，本文利用改進(jìn)遺傳算法，在此基礎(chǔ)上進(jìn)行了適應(yīng)度函數(shù)設(shè)計,并采用植入種子染色體導(dǎo)引法和內(nèi)外交換法進(jìn)行排序,所得結(jié)果正確，收斂速度快。

1 葉片排序約束條件

某航空設(shè)備制造廠根據(jù)實際工作需要提出了下述葉片安裝條件：

1） 整級中的每個葉片與相鄰葉片應(yīng)具有頻率差，且各葉片頻率應(yīng)為一大一小鋸齒型分布，不允許連續(xù)增大或減小。即為“錯頻”排列。

2） 在整級葉片中，其中三對葉片1～2、8～9、16～17的頻率差應(yīng)不小于11Hz，且應(yīng)比其它的相鄰葉片對的頻率差高出不小于2Hz。允許這三對葉片的頻率差比這三對中的任一葉片與相鄰葉片的頻率差高出不小于2Hz。

3） 整級葉片中，相鄰的4個葉片之間的三個頻率差不得完全相同。

4） 相鄰葉片之間頻率差應(yīng)不小于6Hz，允許在互不相鄰的三處，與相鄰葉片頻率之差不小于4Hz。

5） 整級葉片的最大頻率與最小頻率之差應(yīng)不小于14Hz。

6） 整級葉片中的每六分之一位置（即1～4號、5～8號、9～12號、13～16號、17～20號、21～24號）上的葉片靜質(zhì)量矩的和之差應(yīng)當(dāng)不大于138g ·cm，相鄰象限葉片靜質(zhì)量矩的和之差應(yīng)當(dāng)不大于115g ·cm。

7）壓縮機(jī)全部葉片共分為3級，每級葉片都必須符合上述條件。為了生產(chǎn)率，單級葉片所提供的備選葉片數(shù)量不得大于26枚。程序運行時，一次最多可以輸入100枚備選葉片，至少輸出4組葉片數(shù)據(jù)。

8）非可行解可行化。如果葉片數(shù)據(jù)確實“惡劣”，有一組輸出數(shù)據(jù)不是可行解。則應(yīng)給出最佳備選葉片的頻率和靜質(zhì)量矩范圍（也就是如果有一組輸出葉片不合格，這時，更換里面的一枚或幾枚葉片，則更新后的葉片組是合格的。此時，應(yīng)當(dāng)給出更換葉片的頻率和靜質(zhì)量矩的值）。

上述約束條件，給出了葉片優(yōu)化排序的多個目標(biāo)。為了方便求解，把3級葉片逐次求解，因此，三級葉片可以采用同一目標(biāo)函數(shù)。因此，一個多目標(biāo)優(yōu)化問題轉(zhuǎn)化為三個單目標(biāo)函數(shù)求解問題。

2 單級葉片目標(biāo)函數(shù)

本文的研究目標(biāo)就是要求排列在180°相對位置的兩片葉片的靜質(zhì)量矩差的絕對值之和最小，即

式中：k為葉片個數(shù)的一半，(mr)i為第i個葉片的靜質(zhì)量矩(g ·mm)。因此：目標(biāo)函數(shù)設(shè)計為：

3 適應(yīng)度函數(shù)設(shè)計

適應(yīng)度函數(shù)的優(yōu)良與否在很大程度上影響程序的收斂速度。在構(gòu)造遺傳算法時，處理約束條件主要有三種方法：搜索空間限定法、懲罰函數(shù)法、可行解變換法。本文采用罰函數(shù)法。本文將約束條件作為罰函數(shù)包含到適應(yīng)度函數(shù)中去 ,從而將約束優(yōu)化問題轉(zhuǎn)換為無約束優(yōu)化問題進(jìn)行求解 。此時適應(yīng)度函數(shù)可以寫為：

其中，r1、r2、r3、r2為罰函數(shù)尺度系數(shù)，f (x)為目標(biāo)函數(shù)，Hz1為整級葉片中相鄰葉片的頻率差。Hz2是約束條件中（2）所允許的三對大頻率差值與其他相鄰葉片頻率差值的頻率差。

4 種群初始化

由于條件要求在100枚葉片里同時輸出4組數(shù)據(jù)，因此本文把4組數(shù)據(jù)作為4條染色體，每條染色體代表一組葉片。程序同時對4組葉片優(yōu)化排序。但是，在種群初始化時，一次只能產(chǎn)生一條染色體。這樣做的結(jié)果是：最先產(chǎn)生的染色體把性狀好的葉片挑選了，留到最后的是性狀“惡劣”的葉片，這樣很可能最后一組得不到可行解，造成資源浪費。為了避免這個問題，我們先來看單級葉片染色體的產(chǎn)生辦法：

在單級葉片中，由于對1和2號位、8號和9號位、16和17號位的頻率差要求嚴(yán)格，因此，為了加快收斂速度，在每條染色體中，本文先在原始數(shù)據(jù)中選取三個頻率最大的葉片，隨機(jī)放入1、9、17號位置；然后，選取三個頻率最小的葉片，隨機(jī)放入2、8、16號位置。這樣，每一級葉片中，還有18個位置沒有安放葉片。原始數(shù)據(jù)的剩余葉片，程序自動按照頻率把它分成兩部分，葉片頻率大于平均頻率的為一部分，小于平均頻率的為另一部分。利用輪盤賭法按照一大一小的原則，先從大頻率數(shù)據(jù)組里面隨機(jī)抽取一個，再從小頻率數(shù)據(jù)組里面隨機(jī)抽取一個。以此類推，安裝完畢一條染色體的剩余基因位置。利用同樣方法，產(chǎn)生其他染色體。通過在種群初始化時，實施人工干擾，間接減少了排序的約束條件。

由單級葉片染色體的產(chǎn)生辦法可知：每條染色體在挑選葉片時，總是把頻率最大和最小的葉片優(yōu)先選取。因此，本文在種群初始化時，先選取12枚頻率最大的和12枚頻率最小的葉片。在產(chǎn)生每一條染色體時，其關(guān)鍵位置的葉片都從這兩組葉片里隨機(jī)選取。其余葉片按照單級葉片辦法產(chǎn)生。這樣就較好的保證了最后一條染色體的葉片性狀。

這樣做的結(jié)果是產(chǎn)生了4個種群。程序同時對4個種群進(jìn)行優(yōu)化。

5 遺傳算法編碼與算子

5.1 編碼方式

常用的編碼方式包括二進(jìn)制編碼 、浮點數(shù)編碼 、順序編碼 、布爾矩陣編碼等 。為了調(diào)試程序的方便，本文采用十進(jìn)制編碼方式。本文把一級葉片中的總?cè)~片數(shù)目（24個葉片）作為作為一條染色體，即每條染色體含有24個基因，每個基因包含一片葉片的相關(guān)信息。染色體上，第一號基因位置表示第一枚葉片安裝位置。

5.2 選擇算子

從適應(yīng)度函數(shù)的設(shè)計上可以看出適應(yīng)度大的個體優(yōu)于適應(yīng)度小的個體 ,這與一般遺傳算法中適應(yīng)度大的個體優(yōu)于適應(yīng)度小的個體一致,因此適于直接采用基于比例的適應(yīng)度分配方法。本文采用輪盤賭選擇法。

5.3 交叉算子

本文的編碼方式允許一個個體的染色體編碼中在不同位置出現(xiàn)相同的基因碼，如果出現(xiàn)相同的基因碼，則表明有兩個或多個葉片的相關(guān)參數(shù)是相同的,這與實際工作情況是相符合的。本文采用多點交叉。但并非完全隨機(jī)交叉。由于在種群初始化時的人為因素，每個染色體中的1～2、8～9、16～17號位置基因不能和其他位置基因交叉。

5.4 變異算子

變異算子較為簡單，對個體內(nèi)的基因排列按一定的變異率進(jìn)行隨機(jī)交換即可。同樣，每個染色體中的1～2、8～9、16～17號位置基因不能和其他位置基因交換。只能相同性質(zhì)的基因交換，即：1、9、17可以隨機(jī)交換，2、8、16可以隨機(jī)交換。

6 種子染色體

普通遺傳算法程序，在多約束條件下，如果原始數(shù)據(jù)比較惡劣，容易陷入局部尋優(yōu)。并且，一旦陷入局部尋優(yōu)，很難跳出這個局部“陷阱”，從而影響收斂速度。為了加快收斂速度，本文采用了種子染色體導(dǎo)引法。即事先給定一個性狀比較好的染色體作為種子，其作用是引導(dǎo)種群向最優(yōu)點靠近。在多約束條件下，人工給出性狀較好的染色體可行性不高。為了減少人工工作量，本文采用種群自動產(chǎn)生種子的方法。通常情況下，在程序運行時，把種群最大遺傳代數(shù)作為程序循環(huán)次數(shù)。本文只設(shè)定較低的最大遺傳代數(shù)。例如，設(shè)定100代，即程序循環(huán)100次。在程序初次運行時，把初始種群中適應(yīng)度最大個體作為種子染色體。程序運行結(jié)束后，如果沒有得到優(yōu)化解，所產(chǎn)生的種群中適應(yīng)度最大個體被用來當(dāng)作下一次程序運行是的種子染色體。該種子染色體被植入下一次運行時的初始種群。通過植入種子染色體不僅能夠引導(dǎo)種群向最優(yōu)點靠近；而且，當(dāng)種群遺傳若干代后，種群變得過于龐大，從而影響運算速度，通過再一次種群初始化，可以有效解決這個問題。

7 內(nèi)外交換法

染色體一旦產(chǎn)生，其交叉、變異等操作只能在染色體內(nèi)部進(jìn)行，不能再與外部數(shù)據(jù)進(jìn)行數(shù)據(jù)交換。這不但造成剩余葉片資源浪費，也會使收斂速度變慢。本文用內(nèi)外交換法解決了這個問題。即：在一個種群里，隨機(jī)選取一條染色體。計算它的頻率差和單元靜質(zhì)量矩之和等相關(guān)參數(shù)。如果葉片靜質(zhì)量矩的和之差大于138g.cm，或相鄰象限葉片靜質(zhì)量矩的和之差大于115g.cm，則查找出靜質(zhì)量矩之和大的單元；然后，在這個單元里，查找一枚靜質(zhì)量矩最大的葉片，并記為big。此時，原始數(shù)據(jù)的剩余葉片里，查找一枚葉片，其靜質(zhì)量矩比big要小，并且其頻率在代替big的頻率后，新的頻率差應(yīng)符合上述約束條件；或者與big的頻率相等。同樣，查找一枚靜質(zhì)量矩最小的葉片，并記為small。在原始數(shù)據(jù)的剩余葉片里，查找一枚葉片，其靜質(zhì)量矩比small要大，在代替small后，其頻率要求同上。實踐證明，這種方法對解決陷入局部最優(yōu)解問題行之有效。

8 非可行解可行化

如果有非可行解問題，則用虛擬葉片片法解決非可行解尋優(yōu)問題。在初次種群初始化時，每枚葉片都是隨機(jī)選取，并且只能選取一次。對非可行解葉片組，允許部分葉片可重復(fù)選取，等于增加了葉片數(shù)量。得到可行解后，有個別葉片在染色體里出現(xiàn)了兩次。則該葉片參數(shù)即為待更新葉片的參數(shù)。

9 實例驗證

給定一組葉片原始數(shù)據(jù)如表1所示。（因篇幅限制，只給出一組數(shù)據(jù)）。

在沒有種子染色體引導(dǎo)和沒有利用內(nèi)外交換法的情況下，普通遺傳算法，程序循環(huán)運行了25分鐘，沒有得出正確結(jié)果。在有種子染色體引導(dǎo)和利用內(nèi)外交換法時，程序循環(huán)運行20分鐘，得出正確結(jié)果如表2所示。

表1 原始數(shù)據(jù)

表2 運行結(jié)果

10 結(jié)論

程序運行結(jié)果表明：在多約束條件下，該程序收斂速度大為加快，并且運行結(jié)果正確。同時，以上算例證明，改進(jìn)遺傳算法在多約束和原始數(shù)據(jù)惡劣條件下，利用種子引導(dǎo)法和內(nèi)外交換法并在種群初始化時施加人工干擾使程序收斂速度較快，結(jié)果準(zhǔn)確。用此方法編制的程序?qū)嵱眯詮?qiáng)。能有效解決在復(fù)雜條件下的多級葉片排序問題。

[1] 楊訓(xùn). 基于遺傳算法的轉(zhuǎn)子葉片優(yōu)化排序[J]. 計算機(jī)仿真,2008,25(11).YANG Xun Optimum Arrangement of Rotor Blade Based on Genetic Algorithms[J].simmulink of Computer 2008,25(11).

[2] 彭國華. 混合遺傳算法在葉片排序問題中的應(yīng)用[J]. 西南民族大學(xué)學(xué)報,32.PENG Gguohua Application of hybrid genetic algorithm in blade arrangement of engine[J]. 32.

[3] DeJong Ka An Analysis of the Behavior of a Class of Gentic Adaptive Systems[J].Dissertion Abstracts International,1975(10).

[4] Back T,Schwefel H P.An Over View of Evolutionary Algorithms for Paramater Optimization[J].Evolutionary Computation,1999(1).