改進(jìn)的NSGA2算法在航空活塞發(fā)動(dòng)機(jī)裝配中的應(yīng)用

李春林，龐曉平，張 果

(重慶大學(xué) 機(jī)械工程學(xué)院，重慶 400044)

航空發(fā)動(dòng)機(jī)的諸多性能與航空發(fā)動(dòng)機(jī)的裝配質(zhì)量，裝配效率密切相關(guān)[1]。裝配是發(fā)動(dòng)機(jī)制造過程中最為重要的環(huán)節(jié)之一[2]，航空發(fā)動(dòng)機(jī)裝配成本占發(fā)動(dòng)機(jī)成本的40%，裝配工作量占整體工作量的50%[3]。選擇裝配法能夠在零部件按照經(jīng)濟(jì)精度加工時(shí)，仍然可以獲得較高的裝配精度，因此成為航空發(fā)動(dòng)機(jī)等精密復(fù)雜機(jī)械的常用裝配方法。所謂選擇裝配是指通過檢測和挑選待裝零配件，有選擇性地進(jìn)行裝配，以達(dá)到較高裝配精度的一種裝配方法。在航空發(fā)動(dòng)機(jī)等一些高精度裝配體上，存在多個(gè)需要同時(shí)保證的裝配功能要求，稱為多質(zhì)量要求[4]。因此，航空發(fā)動(dòng)機(jī)選擇裝配往往是一個(gè)多目標(biāo)優(yōu)化問題，與單目標(biāo)優(yōu)化結(jié)果不同的是多目標(biāo)優(yōu)化希望獲得的是一組豐富度高，分布均勻的解。

第二代帶精英保留策略的NSGA2(non-dominated sorting genetic algorithm2) 快速非支配排序算法，基于擁擠距離的分布性方法和精英保留策略，憑借簡單、高效等優(yōu)點(diǎn)，在多目標(biāo)優(yōu)化領(lǐng)域中得到廣泛的應(yīng)用。張守京等[5]提出基于擁擠度的自適應(yīng)交叉算子，引進(jìn)競爭選擇機(jī)制，保證解集的多樣性；Bin等[6]采用自適應(yīng)交叉和變異的方法，提高了算法的收斂速度和搜索能力；Xu等[7]采用正交設(shè)計(jì)和累積排序策略改進(jìn)了NSGA2算法，并以尾燈支架裝配為例，證明改進(jìn)的NSGA2算法具有明顯的優(yōu)化效果；Baviskar等[8]提出兩種基于漸進(jìn)式步長機(jī)制的算法，并與現(xiàn)有非支配排序遺傳算法的搜索方式相結(jié)合，通過控制步長和分割數(shù)目，在下一代中產(chǎn)生更好的染色體，實(shí)現(xiàn)快速收斂。張曉娟[9]提出一種鏈?zhǔn)街悄荏w遺傳算法CAGA(chainlike agents genetic algorithm)，通過引入動(dòng)態(tài)鄰域競爭、鄰域正交交叉、自適應(yīng)變異等提高了算法的收斂速度。

以上研究在一定程度上改善了NSGA2算法的優(yōu)化性能，但依然存在一些不足。在航空活塞發(fā)動(dòng)機(jī)活塞與缸體的選擇裝配過程中，由于部分零部件的尺寸數(shù)據(jù)一致，必然存在相同的選配結(jié)果。相同個(gè)體經(jīng)基因重組后不會(huì)改變基因結(jié)構(gòu)，從而產(chǎn)生大量的重復(fù)個(gè)體。筆者針對NSGA2算法的精英保留策略無法抑制個(gè)體大量重復(fù)，造成解集多樣性降低這一缺陷，提出一種基于擁擠度與種群豐富度相結(jié)合的子代精英保留策略。在零件裝配中，由于零件尺寸不能更改的限制，本文提出僅在鄰域圓環(huán)上的近鄰搜索方式，提高了非支配解集的收斂性能，探究出一種適合航空活塞發(fā)動(dòng)機(jī)選擇裝配的NSGA2算法。

1 目標(biāo)函數(shù)

1.1 裝配合格數(shù)

假設(shè)有一批零部件進(jìn)行裝配，裝配完畢之后有n組零部件裝配合格，則裝配合格數(shù)為n。

1.2 裝配精度

零件的裝配精度以田口質(zhì)量損失來度量，裝配的質(zhì)量損失常采用具有望目特性的田口質(zhì)量損失模型，具有望目特性的田口質(zhì)量損失模型可以保證配對公差是否落在設(shè)計(jì)公差帶以內(nèi)，對于滿足設(shè)計(jì)公差的配對，理論上越靠近理想配合值的配對擁有更好的穩(wěn)定性，對產(chǎn)品造成的質(zhì)量損失也會(huì)最小[10-12]。田口質(zhì)量損失模型如下：

(1)

式中：T示公差帶寬度，y表示實(shí)際配合公差，o表示最佳配合值，λ∈[0,1]表示配合值處于設(shè)計(jì)公差帶邊緣的可接受程度，[o-αT,o+βT]表示設(shè)計(jì)公差帶的范圍。

在某航空活塞發(fā)動(dòng)機(jī)中，設(shè)計(jì)要求缸體與活塞間隙范圍為0.11～0.13 mm，取中間值0.12 mm為最佳配合o值，則α=β=0.5，公差帶寬度T為0.02 mm，λ取1。在本文中以裝配合格的零部件的平均質(zhì)量損失來表征裝配精度。

1.3 優(yōu)化模型

在航空活塞發(fā)動(dòng)機(jī)裝配中，只需考慮裝配合格部分的平均裝配精度q1(X)：

(2)

式中：X表示一批零部件的某一選配組合，N表示參與裝配的零件組數(shù)，n表示裝配合格的零件組數(shù)。因此q1(X)越小，X的裝配精度越高。由式(1)(2)以及裝配合格數(shù)n建立多目標(biāo)化模型：

minF(X)=min[n(X),q1(X)]，

(3)

其中，X∈Ω，Ω表示解空間。

2 優(yōu)化算法

2.1 NSGA2算法

NSGA2算法基于非支配排序[13-14]將種群個(gè)體進(jìn)行分層，對每層個(gè)體進(jìn)行適應(yīng)度分配，第一支配層級的適應(yīng)度最高，然后依次降低，從而保證下一子代的優(yōu)良性，提高算法進(jìn)化效率。同時(shí)，采用外部存檔機(jī)制的精英保留策略，結(jié)合擁擠度和支配層級篩選個(gè)體，具有良好的收斂性，得到的非支配解集分布也較為均勻。算法操作細(xì)節(jié)如下：

1)構(gòu)造初始種群S0，設(shè)置算法控制參數(shù)(交叉概率Pc，變異概率Pm，最大進(jìn)化代數(shù)g1，初始進(jìn)化代數(shù)g=0，初始種群個(gè)體數(shù)目L)，清空外部存檔種群S1。

2)計(jì)算初始種群每個(gè)個(gè)體的裝配合格率η和裝配合格個(gè)體平均質(zhì)量損失q，利用Pareto支配原理進(jìn)行分層。

3)對每層個(gè)體賦予適應(yīng)度值P(i)，非支配層級高的適應(yīng)度大，低的適應(yīng)度小。

4)根據(jù)適應(yīng)度值選擇個(gè)體，對選擇的個(gè)體進(jìn)行交叉和變異，再次計(jì)算每個(gè)個(gè)體的裝配合格數(shù)n和裝配合格個(gè)體平均質(zhì)量損失q，利用Pareto支配原理進(jìn)行分層F1,F2,…,Fm?；趥€(gè)體的支配層級和擁擠度選擇個(gè)體。

5)將篩選出的個(gè)體存入外部種群S1，作為下一代親代繼續(xù)進(jìn)化。

6)判斷是否達(dá)到最大進(jìn)化代數(shù)g1，如果沒有，返回第(2)步，如果達(dá)到最大進(jìn)化代數(shù)，則輸出種群中最高支配層級F1的所有相異個(gè)體。

圖1 NSGA2算法流程圖Fig. 1 Flow chart of NSGA2 algorithm

2.2 NSGA2算法的改進(jìn)及應(yīng)用

2.2.1 構(gòu)造適應(yīng)度分配函數(shù)

適應(yīng)度函數(shù)構(gòu)造的基本準(zhǔn)則是非支配層級高的個(gè)體適應(yīng)度大，被選中的概率高，所有非支配層級的適應(yīng)度值的和為1。因此以某一大于1的正整數(shù)a為底，非支配層級i為指數(shù)的指數(shù)函數(shù)來構(gòu)造適應(yīng)度函數(shù)P(i)。

(4)

式中m表示種群總層級數(shù)。由公式(4)可知，a越大非支配層級高的個(gè)體被選中的概率就越高，算法進(jìn)化速度就越快，但是不利于種群多樣性的維護(hù)，算法易陷入局部收斂，因此a的取值不宜過大。當(dāng)初始種群規(guī)模為50時(shí)，a取不同的值非支配解集中相異個(gè)體的數(shù)量如表1所示。

表1 a的取值對非支配解集中相異個(gè)體數(shù)量的影響

因此存在個(gè)體重復(fù)現(xiàn)象且重復(fù)個(gè)體處于較高支配層級時(shí)，a的取值應(yīng)盡可能小，這里取a=2。

2.2.2 改進(jìn)子代精英保留策略

NSGA2的精英保留策略如圖2所示。

圖2 NSGA2 子代產(chǎn)生原理Fig. 2 Principle of NSGA2 generation

如圖2所示，將親代Pt與子代Qt合并得到Rt，應(yīng)用Pareto支配原理將Rt中的個(gè)體分為m層，即F1,F2,…,Fm，每層包含的個(gè)體數(shù)量為n1,n2,…,nm，顯然有n1+n2+…+nm=N，其中N表示Rt中的所有個(gè)體的數(shù)量。由于支配層級高，處于第一和第二支配層級的所有個(gè)體F1,F2全部存入外部存檔種群Pt+1，然后再在第三支配層中利用擁擠度比較選出N/2-n1-n2個(gè)個(gè)體加入外部存檔種群，其中N/2表示外部存檔種群Pt+1的數(shù)量。

下面給出NSGA2精英保留策略中常用的兩個(gè)基本定義。

定義1(個(gè)體擁擠度)為了測算某點(diǎn)附近其他個(gè)體的聚集程度，定義變量idistance(擁擠度)，表示覆蓋個(gè)體i但不覆蓋其他點(diǎn)的矩形面積，而同一支配層級首尾兩端個(gè)體的擁擠度定義為無窮大。如圖3[9]所示。

定義2(擁擠度比較算子)擁擠度比較算子，用于搜尋分布均勻的個(gè)體，兩個(gè)體i和j的比較邏輯如下[9]。

i

(5)

式中irank表示個(gè)體i的非支配等級。

圖3 擁擠度原理Fig. 3 Principle of crowding degree

由圖3可知，計(jì)算擁擠度時(shí)非支配解集是以第一目標(biāo)值f1按升序進(jìn)行排列，因此當(dāng)兩個(gè)非支配解的擁擠度相等時(shí)會(huì)優(yōu)先選擇第一目標(biāo)值大的個(gè)體，這就導(dǎo)致種群中第一目標(biāo)值較大的個(gè)體數(shù)量過多。隨著迭代的進(jìn)行，非支配解集在第一目標(biāo)值較小的部分逐漸缺失，不能完整地填充整個(gè)解空間。而基于種群均勻度和擁擠度相結(jié)合的子代精英保留策略則能夠彌補(bǔ)這一缺陷。

以種群均勻度和擁擠度相結(jié)合的子代精英保留策略如圖4所示。

圖4 改進(jìn)后的NSGA2 算法子代精英保留Fig. 4 Improved NSGA2 algorithm for elite preservation

2.2.3 解集評價(jià)指標(biāo)

采用多目標(biāo)優(yōu)化結(jié)果常見的評價(jià)指標(biāo)：解集收斂性測度、豐富度測度，以及本文中提出的種群均勻度。

1)收斂性測度。設(shè)X1,X2為2種算法獲得的非支配解集，則收斂度計(jì)算公式為[15]：

(6)

式中|.|表示集合中的元素個(gè)數(shù)，x1≥x2表示個(gè)體x1支配x2。如果C(X1，X2)=1，則表示X2中的個(gè)體均被X1所支配，反之，如果C(X1,X2)=0，則表示X2中的個(gè)體均不被X1所支配。同樣的方法計(jì)算C(X2,X1)，如果C(X1,X2)>C(X2,X1)，則表明X1在種群收斂性測度方面優(yōu)于X2。

2)豐富度測度。種群的豐富度測度以種群中相異個(gè)體的數(shù)量m表示。

3)種群均勻度。由于在種群中某一個(gè)體的大量存在，相異個(gè)體數(shù)量分布不均，導(dǎo)致種群豐富度降低，目前的評價(jià)指標(biāo)中忽略了這一影響，這里提出種群均勻度的概念可以抑制這一影響，提高種群豐富度。具體定義如下：

假設(shè)一個(gè)種群有N個(gè)個(gè)體，其中相異個(gè)體有m個(gè)，它們的數(shù)量分別為n1,n2,…,nm，有n1+n2+…+nm=N，則種群均勻度H的定義為

(7)

式中n0=(n1+n2+…+nm)/m，可見當(dāng)種群內(nèi)的個(gè)體都是相異個(gè)體時(shí)，種群均勻度H最大為1，相同個(gè)體數(shù)量分布越不均勻，種群均勻度就越低。

2.3 基于種群均勻度與擁擠度相結(jié)合的子代精英保留策略的應(yīng)用

以某型號航空活塞發(fā)動(dòng)機(jī)缸體與活塞的裝配為例，發(fā)動(dòng)機(jī)缸體與活塞的裝配間隙是極為重要的技術(shù)參數(shù)，裝配間隙對發(fā)動(dòng)機(jī)整機(jī)裝配尺寸和裝配質(zhì)量影響很大，間隙的合格范圍是0.11～0.13 mm，因此缸體內(nèi)徑與活塞外徑尺寸精度也比較高，將151組缸體與活塞的尺寸數(shù)據(jù)按照升序排序如表2所示。

表2 缸體與活塞尺寸數(shù)據(jù)

缸體與活塞的配合為孔軸配合，封閉環(huán)即配合間隙為缸體內(nèi)徑與活塞外徑的差值。為了更好地檢驗(yàn)改進(jìn)的子代精英保留策略對輸出結(jié)果的影響，需要排除遺傳算法交叉、變異環(huán)節(jié)的隨機(jī)性，將改進(jìn)前后的算法設(shè)立為并行的方式。采用直接編碼的方式，以序號和對應(yīng)的尺寸組成一個(gè)不可分割的基因位，將151組數(shù)據(jù)隨機(jī)排列構(gòu)成一個(gè)染色體，染色體的每一列表示一組缸體與活塞的裝配，如表3所示。

表3 染色體結(jié)構(gòu)

重復(fù)隨機(jī)排列50次，得到初始種群S1，即初始種群的個(gè)體數(shù)是50，每個(gè)染色體表示一種選擇裝配方式。復(fù)制該初始種群，得到與S1完全相同的初始種群S2。將S1和S2在同一隨機(jī)序列下進(jìn)行交叉和變異，在同一分層機(jī)制下分層。子代精英保留方面，S1采用原始算法的子代精英保留策略，S2在此基礎(chǔ)之上結(jié)合種群均勻度最大策略選擇個(gè)體。

2個(gè)種群在相同的算法控制參數(shù)下運(yùn)行，得到的非支配解集分布如圖5所示。

圖5 改進(jìn)前后非支配解集分布對比Fig. 5 Comparison of non-dominated solution set distribution before and after improvement

星號點(diǎn)表示S2得到的非支配解集，菱形點(diǎn)表示S1得到的非支配解集。S1的非支配解集中非支配解有86個(gè)，S2有79個(gè)。S2非支配解集中相異個(gè)體有27個(gè)，S1僅僅只有17個(gè)，對2個(gè)解集的相異非支配解進(jìn)行編號，統(tǒng)計(jì)各自數(shù)量，如圖6所示。

圖6 兩組非支配解集相異個(gè)體數(shù)量分布對比Fig. 6 Comparison of the number distribution of different individuals in two groups of non-dominated solution sets

圖中空心柱表示S1非支配解集相異個(gè)體數(shù)量分布，實(shí)心柱S2表示非支配解集相異個(gè)體數(shù)量分布?？梢钥闯鯯2的非支配解集中個(gè)相異個(gè)體數(shù)量分布更加均勻，沒有出現(xiàn)某一個(gè)體大量重復(fù)的情況。

將兩組非支配解集進(jìn)行收斂性測度、豐富度測度和種群均勻度檢驗(yàn)，令S2的非支配解集為X2，S1的非支配解集為X1，計(jì)算結(jié)果如表4所示。

表4 非支配解集性能比較

由表4可知：C(X1,X2)>C(X2,X1)，表明引進(jìn)種群豐富度之后得到的非支配解集在收斂性測度方面并沒有得到提高。這是因?yàn)樵谟?jì)算個(gè)體擁擠度時(shí)，首先以第一子目標(biāo)(合格數(shù))升序排列，當(dāng)兩個(gè)體擁擠度相等時(shí)，合格數(shù)較大個(gè)體更容易保留下來，因而導(dǎo)致合格數(shù)較大的非支配個(gè)體在種群中大量存在，在后續(xù)的變異中有更大的概率獲得更加優(yōu)異的非支配解。在豐富度測度方面和均勻度方面有：m(X1)

結(jié)合2組非支配解集，找出所有的非支配解，如圖7所示。

圖7 兩組非支配解集合并后非支配解分布Fig. 7 Distribution of non-dominated solutions after merging two sets of non-dominated solutions

2.4 近鄰搜索

針對引進(jìn)種群均勻度的精英保留策略會(huì)降低非支配解集收斂性，導(dǎo)致算法進(jìn)化速度減慢這一缺陷，引進(jìn)近鄰搜索算子。近鄰搜索能夠提高多目標(biāo)優(yōu)化遺傳算法的收斂速度，彌補(bǔ)引進(jìn)種群均勻度后非支配解集收斂性測度降低的不足。所謂近鄰搜索指的是在某一范圍內(nèi)算法往某一特定的方向進(jìn)化[16]。文獻(xiàn)[16]提出的近鄰搜索是在整個(gè)近鄰圓內(nèi)進(jìn)行鄰域搜索，如圖8所示。

圖8中圓心點(diǎn)表示經(jīng)交叉變異后獲得的非支配解，星號點(diǎn)表示在圓心點(diǎn)附近的最優(yōu)解，由于NSGA2的交叉變異環(huán)節(jié)具有隨機(jī)性，局部搜索能力不足，很難得到最優(yōu)解。

在整個(gè)近鄰圓內(nèi)的鄰域搜索范圍表達(dá)式如下[16]：

R=X±ρ。

(8)

由于染色體的基因位是由零件尺寸和序號組成，是一一對應(yīng)關(guān)系，不能更改。為了滿足這一約束條件，重新定義搜索半徑和搜索范圍。任意交換2對基因位，交換之后的染色體與之前的染色體的歐式距離定義為搜索半徑ρ1。

若個(gè)體X1=(x1,x2,x3,x4,…,xn)交換兩對基因位之后變?yōu)閄2=(x2,x1,x4,x3,…,xn)，則對X1局部搜索的搜索半徑ρ1表示為：

(9)

因此，每個(gè)非支配解的搜索半徑是不相等的，若對m個(gè)非支配解進(jìn)行近鄰搜索，搜索半徑向量為：

ρ=(ρ1,ρ2,…ρm)，

(10)

則搜索范圍表示為：

R=X+ρ。

(11)

近鄰搜索的示意圖如圖9所示。

圖8 在整個(gè)近鄰圓內(nèi)進(jìn)行鄰域搜索Fig. 8 Neighborhood search in the whole neighborhood circle

圖9 在圓環(huán)上進(jìn)行鄰域搜索Fig. 9 Neighborhood search on a ring

圓心表示原始非支配解，星號點(diǎn)表示更優(yōu)異的非支配解?？梢钥闯鼋徦阉鞑⒎鞘窃谡麄€(gè)鄰域范圍內(nèi)進(jìn)行搜索，由于零件尺寸不能更改的限制，鄰域搜索只是在以非支配點(diǎn)為圓心，搜索半徑為圓的圓環(huán)上進(jìn)行，每個(gè)點(diǎn)的搜索半徑由于交換基因位的隨機(jī)性是不相等的。

顯然，若只對一個(gè)點(diǎn)進(jìn)行近鄰搜索是很難得到更優(yōu)的非支配解，但是同時(shí)對所有的非支配解進(jìn)行鄰域搜索，隨著迭代的進(jìn)行，搜索到最優(yōu)的非支配解的概率會(huì)大幅提升。與標(biāo)準(zhǔn)的NSGA2多目標(biāo)遺傳算法不同之處在于，引進(jìn)了近鄰搜索后，算法對每次進(jìn)化得到外部存檔種群中所有個(gè)體進(jìn)行近鄰搜索，若在搜索圓環(huán)上存在更優(yōu)異的非支配解，即X2≥X1，那么就用X2替換X1。為了排除交叉變異環(huán)節(jié)的隨機(jī)性，采取程序并行的方式，2個(gè)相同的初始種群S1和S2在相同的算法控制參數(shù)下運(yùn)行，星號點(diǎn)表示改進(jìn)后，菱形點(diǎn)表示改進(jìn)前，輸出結(jié)果如圖10所示。

圖10 引進(jìn)鄰域搜索前后非支配解集的分布Fig. 10 Distribution of non-dominated solution set before and after introducing neighborhood search

令引進(jìn)近鄰搜索后的非支配解集為X2，引進(jìn)之前為X1，計(jì)算結(jié)果如表5所示。

表5 引入鄰域搜索后兩組非支配解集性能對比

兩組非支配解集性能計(jì)算可以得知，引進(jìn)鄰域搜索以后，得到的非支配解集在收斂性測度優(yōu)于之前的非支配解集。但近鄰搜索并不能夠使非支配解集的豐富度和均勻度增加，即近鄰搜索并不能夠消除種群中個(gè)體大量重復(fù)的現(xiàn)象。

2.5 NSGA2算法的綜合改進(jìn)

由2.3和2.4兩小節(jié)得到的結(jié)果可知，單獨(dú)引進(jìn)種群均勻度和近鄰搜索在提高算法某一方面性能的同時(shí)，另一方面算法的性能卻并沒有得到提高。因此，同時(shí)引入近鄰搜索和種群均勻度，對算法進(jìn)行綜合優(yōu)化，仍然采用程序并行的方式，星號點(diǎn)表示改進(jìn)后得到的非支配解集，菱形點(diǎn)表示標(biāo)準(zhǔn)NSGA2算法得到的非支配解集，兩個(gè)相同的初始種群在相同的算法控制參數(shù)下運(yùn)行，改進(jìn)前后的非支配解集如圖11所示。

圖11 綜合改進(jìn)前后非支配解集的分布Fig. 11 Distribution of non-dominated solution set before and after comprehensive improvement

令改進(jìn)之后的非支配解集為X2，改進(jìn)之前為X1，計(jì)算結(jié)果如表6所示。

表6 綜合改進(jìn)后兩組非支配解集性能對比

因此，2個(gè)方面同時(shí)可進(jìn)行改進(jìn)后，非支配解集的收斂性和豐富度測度均得到了提高，算法的綜合性能得到改進(jìn)。將改進(jìn)前后2組解在同一合格數(shù)下的平均質(zhì)量損失進(jìn)行對比，如表7所示。

表7 綜合改進(jìn)前后兩組解同一合格數(shù)下的平均質(zhì)量損失對比

由表7可知，算法經(jīng)過綜合改進(jìn)之后，同一合格數(shù)的選擇裝配方案，改進(jìn)后評價(jià)質(zhì)量損失降低了10.9%到22.2%之間，這表明改進(jìn)后的選擇裝配方案裝配精度更高，裝配質(zhì)量更好。

3 結(jié) 論

1)當(dāng)種群存在重復(fù)個(gè)體時(shí)，種群的均勻度和豐富度是正相關(guān)關(guān)系，均勻度越大，種群中相異個(gè)體數(shù)量也隨之越大。以種群均勻度和擁擠度相結(jié)合的子代精英保留策略會(huì)抑制個(gè)體大量重復(fù)，提高非支配解集的豐富度，從而擴(kuò)大解的分布范圍，但會(huì)降低解集的收斂性。

2)采用近鄰搜索以后，會(huì)得到許多優(yōu)于原來的非支配解，提高解集收斂性，但并不能提高大種群的豐富度和均勻度。

3)當(dāng)同時(shí)引進(jìn)種群豐富度和鄰域搜索后，非支配解集的綜合性能得到改進(jìn)，算法的進(jìn)化速度和收斂速度得到提高。