梅小華 鄭力新

(華僑大學(xué)信息科學(xué)與工程學(xué)院，福建 廈門 361021)

0 引言

標(biāo)志工業(yè)產(chǎn)品性能的參數(shù)主要取決于零件的定值與容差。進(jìn)行零件參數(shù)的設(shè)計，就是要確定其標(biāo)定值和容差。將零件組裝成產(chǎn)品時，若產(chǎn)品參數(shù)偏離預(yù)先設(shè)定的目標(biāo)值，就會造成質(zhì)量損失，偏離越大，損失越大;零件的容差大小則決定了制造成本，容差設(shè)計得越小，成本越高。正確有效地設(shè)計零件的最優(yōu)化參數(shù)，是保證產(chǎn)品質(zhì)量、減少產(chǎn)品總費用的重要環(huán)節(jié)。

零件參數(shù)優(yōu)化設(shè)計的常用方法有梯度法、單純形法和隨機尋優(yōu)法等。梯度法只能對連續(xù)參數(shù)進(jìn)行運算，參數(shù)數(shù)量也不能太多，且容易陷于局部最優(yōu)解。單純形法受初值和計算步長的影響較大，易收斂于局部最優(yōu)解。傳統(tǒng)的隨機尋優(yōu)技術(shù)效率較低。遺傳算法［1－2］是一種全新的優(yōu)化搜索算法，它不受結(jié)構(gòu)模型、約束條件和參數(shù)初值的限制，以其并行性和快速尋優(yōu)等特點，解決了許多領(lǐng)域的難題，從而得到各界的重視。

基于上述認(rèn)識，本文提出了一種改進(jìn)的遺傳算法，用來優(yōu)化零件參數(shù)。該算法具有如下特點:①可變的交叉概率和變異概率使得尋優(yōu)效率大大提高，改善了收斂性;②有效地消除了對參數(shù)初值的依賴性，不會陷入局部極值點;③具有較強的魯棒性，是較好的大規(guī)模參數(shù)尋優(yōu)方法。

1 零件參數(shù)的模型

1.1 問題提出

粒子分離器某參數(shù)(記作y)由7個零件的參數(shù)(記作 x1，x2，…，x7)決定，經(jīng)驗公式為［3］:

y的目標(biāo)值(記作y0)為1.50。當(dāng)y偏離目標(biāo)值±0.1時，產(chǎn)品為次產(chǎn)品，質(zhì)量損失為1000元;當(dāng)y偏離目標(biāo)值±0.3時，產(chǎn)品為廢品，損失為9000元。

零件參數(shù)的標(biāo)定值有一定的容許變化范圍，容差分為A、B、C三個等級，用與標(biāo)定值的相對值表示。A級為±1%、B級為±5%、C級為±10%。7個零件參數(shù)標(biāo)定值的容許范圍及不同容差等級零件的成本如表1所示。

表1 零件參數(shù)標(biāo)定值及容差等級Tab.1 Scaling values and tolerance levels of parts parameters

現(xiàn)進(jìn)行成批生產(chǎn)，每批產(chǎn)量為1000個。在原設(shè)計中，7個零件參數(shù)的標(biāo)定值為:x1=0.1、x2=0.3、x3=0.1、x4=0.1、x5=1.5、x6=16、x7=0.75;容差均取最便宜的等級。綜合考慮y偏離y0造成的損失和零件成本，按照總經(jīng)濟(jì)損失最低的原則，進(jìn)行零件參數(shù)(標(biāo)定值和容差)設(shè)計。

1.2 基本假設(shè)

在設(shè)計零件參數(shù)時，作如下基本假設(shè)。

① 零件參數(shù) x1，x2，…，xn為相互獨立的隨機變量，期望值和均方差分別記作xi0和σi，絕對容差記作ri=3σi，相對容差記作 ti=ri/xi0。

② 產(chǎn)品參數(shù)y由x1，…，xn決定，記作y=f(x1，…，xn)。由于xi偏離xi0很小，可在 x0=(x10，…，xn0)處對 f作泰勒級數(shù)展開，并略去二階及以上項，有y=f(x0)+)，于是隨機變量y的期望值為Ey=f(x0)，方差為或用ti表示為

③由y偏離目標(biāo)值y0造成的(單件產(chǎn)品)質(zhì)量損失記作L(y)，根據(jù)所給數(shù)據(jù)，可設(shè)L(y)與(y－y0)2成正比，即 L(y)=k(y － y0)2，可得 k=103/0.12=105。

④批量生產(chǎn)時，平均每件產(chǎn)品質(zhì)量損失費EL(y)取決于零件參數(shù)標(biāo)定值x0和容差t，記作:

⑤單件產(chǎn)品的零件成本僅取決于容差等級ti，第i種零件的成本記作ci(ti)，于是零件總成本為C(t)=。

⑥綜合考慮y偏離y0造成的損失和零件成本，將本問題的目標(biāo)函數(shù)定義為成批生產(chǎn)時平均每件產(chǎn)品的總費用，即 z(x0，t)=Q(x0，t)+c(t)。

2 遺傳算法

遺傳算法首先隨機地產(chǎn)生一組潛在的解X(該解稱為“染色體”，解的特定集合稱為“種群”，解中的變量稱為“基因”);然后采用生物進(jìn)化的過程(如染色體交叉、變異、淘汰等)，不斷提高解的品質(zhì);最后獲得最優(yōu)解。

遺傳算法不要求具有梯度信息，就可以處理大量的離散參數(shù)運算，因此非常適用于上述粒子分離器參數(shù)的設(shè)計。

2.1 編碼策略

粒子分離器參數(shù)包括7個連續(xù)參數(shù)xi和7個離散參數(shù)ti，根據(jù)參數(shù)范圍的限制，采用二進(jìn)制進(jìn)行編碼，粒子分離器參數(shù)的二進(jìn)制編碼如表2所示。

表2 參數(shù)二進(jìn)制編碼Tab.2 Binary coding of parameter

表2 中，a、b、c、d 取 0 或 1，xi編碼長度為 4，t2、t7編碼長度為 1，t3、t4、t6編碼長度為 2，t1、t5不參加編碼，因此染色體長度為36。在此情況下，采用二進(jìn)制編碼的精度已足夠。若精度要求發(fā)生變化，編碼的位數(shù)可根據(jù)實際的精度需要選取。

2.2 目標(biāo)函數(shù)的建立

總費用的目標(biāo)函數(shù)［4－5］為非線性規(guī)劃模型，由零件成本費和產(chǎn)品參數(shù)偏離目標(biāo)值y0引起的質(zhì)量損失費組成。零件成本由簡單的線性代數(shù)確定，質(zhì)量損失是涉及概率分布的非線性函數(shù)。標(biāo)定值或容差設(shè)計得不合理，會使產(chǎn)品參數(shù)遠(yuǎn)離目標(biāo)值，造成質(zhì)量損失;而容差設(shè)計得太小，又會增加零件制造成本。為了使總費用Z(x0，t)達(dá)到最小，且滿足約束條件，即標(biāo)定值x0落在給定的容許范圍內(nèi)，本算法所采用的目標(biāo)函數(shù)為:

2.3 遺傳算法與粒子分離器的結(jié)合

算法設(shè)計如下。

①全局變量設(shè)定，給出群體規(guī)模m、最大迭代次數(shù) Tmax的大小，選擇 m=100、Tmax=150，k為當(dāng)前進(jìn)化的次數(shù)。

②種群的產(chǎn)生及初始化。設(shè)進(jìn)化代數(shù)計數(shù)器T=0，以零件參數(shù)為基因組成染色體X，X由36個基因組成。初始染色體中的基因(設(shè)計參數(shù))在各自的取值范圍內(nèi)隨機產(chǎn)生，但必須滿足所有約束條件。種群由m個染色體構(gòu)成。

③適應(yīng)度函數(shù)值計算和選擇操作。適應(yīng)度函數(shù)是選擇操作的依據(jù)，適應(yīng)度函數(shù)應(yīng)是非負(fù)的，假設(shè)適應(yīng)度函數(shù)為:

式中:f(x)為模型目標(biāo)值。

目標(biāo)函值較小的個體對應(yīng)的適應(yīng)度較大，在選擇操作中被選中的概率也較大。算法中采用適應(yīng)度比例策略和保存最優(yōu)策略相結(jié)合的方式［6］進(jìn)行選擇操作，每次只保留所有進(jìn)化代中適應(yīng)度最大的個體。選出m個優(yōu)良個體的步驟如下。

根據(jù)適應(yīng)度函數(shù)，計算每個個體的適應(yīng)度Fi(i=1，2，…，m)，得到的每個個體的適應(yīng)概率為:

根據(jù)每個個體的適應(yīng)概率，得到每個個體的累積概率為:

隨機產(chǎn)生一個(0，1)的實數(shù)r，對m個累積概率進(jìn)行判斷，若 Qi－1＜r＜ Qi成立，則第 i個個體便是被選中并留在基因池的個體;重復(fù)以上步驟，直到選中m個個體。

④交叉概率Pc與變異概率Pm的計算。其中一種方法是采用 Pan等人［7－8］提出的 Pc和 Pm能夠隨適應(yīng)度自動改變的自適應(yīng)遺傳算法。當(dāng)群體最大適應(yīng)度fmax與平均適應(yīng)度favg接近時，群體趨于收斂，即此時群體中的各個個體趨于一致，其父代間的距離比較小，群體的多樣性較弱。為了提高群體的多樣性，應(yīng)增大Pm;反之，則群體多樣性較強，應(yīng)減小Pm。此方法對算法時間和空間復(fù)雜度要求較高，程序運行時間較長。另一種方法是采用Pc和Pm都隨迭代次數(shù)的增加而逐級變化的遺傳算法。該方法在進(jìn)化的初期交叉率較大，變異概較小，可以防止群體的早熟。在進(jìn)化后期，交叉率較小，變異率較大，尋優(yōu)過程加速。但該方法要求最大迭代次數(shù)較大，若最大迭代次數(shù)較小，則每代Pc和Pm變化幅度較大，不利于在規(guī)定次數(shù)內(nèi)保證算法的收斂性。

針對上述問題，本文將以上兩種方法相結(jié)合，在算法中采用隨迭代次數(shù)變化的變異概率和自適應(yīng)變化的交叉概率。

交叉概率為:

式中:f為變異個體的適應(yīng)度;fmax為群體最大適應(yīng)度;favg為平均適應(yīng)度;Pm1=0.1、Pm2=0.001。

⑤交叉、變異操作。對父代群體進(jìn)行兩兩配對，然后對每對個體按Pc概率進(jìn)行交叉操作。采用多點交叉，在36個基因中的前28個基因中，隨機產(chǎn)生一個交叉點;在后6個基因中也產(chǎn)生一交叉點，經(jīng)過交叉運算后得到子代群體編碼。對于子代群體編碼的每一位，采用多點變異，以Pm的概率進(jìn)行變異，生成新一代群體。

⑥過程結(jié)束判定。當(dāng)最優(yōu)個體的適應(yīng)度和群體適應(yīng)度不再上升時，算法的迭代過程收斂、算法結(jié)束;否則，用經(jīng)過選擇、交叉、變異所得到的新一代群體取代上一代群體，并返回到步驟③繼續(xù)循環(huán)執(zhí)行。

3 仿真結(jié)果

以零件參數(shù)設(shè)計為例，在CPU 2.0 GB、內(nèi)存512 MB的機器上用 Matlab 6.0 對其進(jìn)行仿真［9－10］，在遺傳代數(shù)T=80時，得到如下結(jié)果。

單位產(chǎn)品總費用min z=748.9349元，與原設(shè)計費用z0=6507.2相比，費用減少了5758.3元，產(chǎn)品質(zhì)量參數(shù)值 Ey=1.4976。

目標(biāo)值進(jìn)化曲線如圖1所示，各種遺傳算法目標(biāo)值進(jìn)化曲線如圖2所示。

Jong D提出了兩個評價遺傳算法性能的指標(biāo)，即在線性能指標(biāo)和離線性能指標(biāo)。根據(jù)圖1仿真結(jié)果可知，在線性能指標(biāo)為4.0568×104，說明算法具有很好的動態(tài)性能;離線性能指標(biāo)為755.3421，說明算法具有很好的收斂性能。仿真運行表明，改進(jìn)的遺傳算法，其4/5的主程序(20次)的最小費用值落在(748～752)元之間，表明改進(jìn)的遺傳算法在解決大規(guī)模參數(shù)設(shè)計中具有較好的穩(wěn)定性。

4 結(jié)束語

將改進(jìn)的遺傳算法應(yīng)用于零件的參數(shù)尋優(yōu)，尋優(yōu)效率較簡單遺傳算法有了大幅提高;在保持群體多樣性的同時，又保證了算法的收斂性，可為大規(guī)模參數(shù)設(shè)計提供捷徑。

［1］Holland J.Adaptation in neural and artificial systems［M］.Ann Arbor:Michigan University，1975.

［2］張文修.遺傳算法的數(shù)學(xué)基礎(chǔ)［M］.2版.西安:西安交通大學(xué)出版社，2003:146－202.

［3］1997年全國大學(xué)生數(shù)學(xué)建模競賽(A題)［J］.數(shù)學(xué)的認(rèn)識與實踐，1998(1):2－4.

［4］趙靜.數(shù)學(xué)建模與數(shù)學(xué)實驗［M］.北京:高等教育出版社，2000:64－73.

［5］吳新燁，徐學(xué)林.在零件的參數(shù)優(yōu)化設(shè)計中的數(shù)學(xué)建模［J］.煤礦機械，2004(1):10 －12.

［6］Filho J L R，Treleaven P C，Alippi C.Genetic algorithm programming environments［J］.IEEE Computer，1994，27(6):28 －43.

［7］熊軍，高敦堂，都思丹，等.變異率和種群數(shù)目自適應(yīng)的遺傳算法［J］.東南大學(xué)學(xué)報:自然科學(xué)版，2004(4):553 －556.

［8］Pan Zhengjun，Kang Lishan，Nie Sixiang.Evolving both the topology and weights of neural network［J］.Parallel Algorithms and Applications，1996，9(3):299 －307.

［9］王小平，曹立明.遺傳算法－理論、應(yīng)用與軟件實現(xiàn)［M］.西安:西安交通大學(xué)出版社，2003:104－122.

［10］雷英杰.Matlab遺傳算法工具箱及應(yīng)用［M］.西安:西安電子科技大學(xué)出版社，2005:95－105.