梅小華 鄭力新

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

0 引言

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

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

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

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

1.1 問題提出

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

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

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

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

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

1.2 基本假設(shè)

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

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

② 產(chǎn)品參數(shù)y由x1，…，xn決定，記作y=f(x1，…，xn)。由于xi偏離xi0很小，可在 x0=(x10，…，xn0)處對(duì) f作泰勒級(jí)數(shù)展開，并略去二階及以上項(xiàng)，有y=f(x0)+)，于是隨機(jī)變量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)時(shí)，平均每件產(chǎn)品質(zhì)量損失費(fèi)EL(y)取決于零件參數(shù)標(biāo)定值x0和容差t，記作:

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

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

2 遺傳算法

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

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

2.1 編碼策略

粒子分離器參數(shù)包括7個(gè)連續(xù)參數(shù)xi和7個(gè)離散參數(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ù)實(shí)際的精度需要選取。

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

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

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

算法設(shè)計(jì)如下。

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

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

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

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

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

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

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

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

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

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

交叉概率為:

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

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

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

3 仿真結(jié)果

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

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

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

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

4 結(jié)束語

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

［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é)建模競(jìng)賽(A題)［J］.數(shù)學(xué)的認(rèn)識(shí)與實(shí)踐，1998(1):2－4.

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

［5］吳新燁，徐學(xué)林.在零件的參數(shù)優(yōu)化設(shè)計(jì)中的數(shù)學(xué)建模［J］.煤礦機(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é)報(bào):自然科學(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)用與軟件實(shí)現(xiàn)［M］.西安:西安交通大學(xué)出版社，2003:104－122.

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