周楊 鐘建琳

摘要：研究了基于精英選擇遺傳算法的加工工步序列優(yōu)化技術(shù)。傳統(tǒng)的加工工藝路線是以工序為制造單元，

而在基于STEP-NC的加工中，是以加工工步為制造單元，并且面向數(shù)控加工（中心）的一種加工過程。本文以由加

工工步變換所帶來的零件轉(zhuǎn)位、刀具更換等所消耗的輔助加工時間為最短作為優(yōu)化目標，來進行加工工步序列的優(yōu)

化，并對加工工步序列的優(yōu)化算法進行了驗證。

關(guān)鍵字：工步序列優(yōu)化遺傳算法STEP-NC

Abstract:

Genetic algorithm based on elite choice for the oPtimization of working stepsSequence was developed. In

the conventional manufacturing the working procedure is used as machining unit, While under the application of STEP-NC

the working step is as machining unit and the machining is numerical control machining center-oriented.The Optimization

goal is to find the best working steps sequence according to the least assistant machining time consumed by the part location

transform and tool replacing, and the algorithm for optimization of working steps sequence was tested in this prototype

system.

Keywords: OptimizationofworkingstePssequenc, Genetic Algorithm, STEP-NC

引言：作用而導致當前群體的最佳個體在下一代的丟失，De

Jong[4] 提出了精英選擇（elitist seleetion）策略。從GA

非線性工藝設(shè)計是生成眾多條工步序列( 從種工藝

的整個選擇策略來講，精英選擇將解決群體收斂到優(yōu)化

方案)，通過對工序排序約束規(guī)則和工步序列的有效化

處理，排除N 個工步序列中的許多無效工步序列，但

的問題。

是剩下的有效工步序列的數(shù)目仍然是龐大的。在傳統(tǒng)的

原理：如果下一代群體的最佳個體適應(yīng)值小于當

設(shè)計中，操作人員經(jīng)常依賴于經(jīng)驗來進行決策，由于操

前群體最佳個體的適應(yīng)值，則將當前群體最佳個體或者

作人員知識水平的不一致和生產(chǎn)實踐經(jīng)驗的局限性，往

適應(yīng)值大于下一代最佳個體適應(yīng)值的多個個體直接復制

往不能考慮到影響排序的各方面因素，因而編排的工藝

到下一代，隨機替代或替代最差的下一代群體中的相應(yīng)

路線往往不是最佳方案。因此，工序的自動排序和優(yōu)化

數(shù)量的個體。

技術(shù)已成為CAPP 系統(tǒng)集成化、智能化的瓶頸之一。許

多學者都進行了大量的研究，人們曾采用了基于導數(shù)的

解析方法、枚舉法和其它啟發(fā)式搜索方法來進行工序排

序的優(yōu)化，但由于這些優(yōu)化方法大部分都是基于局部的

搜索，因此很難達到一個全局的最優(yōu)解，而枚舉法雖然

能求出精確的最優(yōu)解，但是當集合空間較大時，該方法

的求解效率比較低，有時甚至最先進的計算工具上都無

法求解。

由于工藝約束優(yōu)化過程與其它數(shù)值化的優(yōu)化問題

不同，首先，它的優(yōu)化量不是數(shù)值，而是排列順序；其

次，沒有明確的優(yōu)化目標，適用度函數(shù)難以表達。遺傳

算法（Genetic Algorithm，簡稱GA）由于其具有以編碼、

基因重組和變異為基礎(chǔ)的全局搜索優(yōu)點，近年來受到了

廣泛的重視和研究，遺傳算法被越來越多地應(yīng)用到加工

工步排序的優(yōu)化領(lǐng)域中[1~3]，本文利用基于精英選擇

模型的遺傳算法來進行工步序列的優(yōu)化。

一、基于精英選擇模型的遺傳算法原理

為了防止由于選擇誤差，或者交叉和變異的破壞二、加工工步序列的優(yōu)化過程

1. 基因編碼（Gene encoding）

基因編碼是GA 方法應(yīng)用的第一步，本文采用自然

數(shù)字鏈進行基因編碼。在STEP-NC 數(shù)據(jù)模型中，一個

加工工步主要包含了刀具的安全平面（its_secplane）、

工件特征（its_feature）以及加工該特征所對應(yīng)的加工操

作（its_operations）等信息，而在加工操作元素中，除

了包含加工工藝（its_technology）、加工機床參數(shù)（its_

machine_functions）等信息外，還包括了與加工行為密

切相關(guān)的刀具信息（its_tool）。因此為了充分反映特征

和所對應(yīng)的加工等信息，每一個基因由四部分組成，它

們分別是：加工方位代碼、制造特征代碼、加工操作

（加工方法）代碼和加工刀具代碼，每一個基因?qū)?yīng)于

SETP-NC 中的一個加工工步。在生成基因代碼之前，

首先分別給加工方位、制造特征、加工方法和被選用刀

具進行順次編號，考慮到在一次加工中可能含有多個工

步的情況，基因中的每一部分則由兩位十進制數(shù)組成。

根據(jù)每一部分的編號，可以將各個組合分別表示成相應(yīng)

的十進制代碼，這樣就完成了基因編碼工作。所有工步

的基因按任意方式進行排列就組成了一條染色體。

2. 初始群體的產(chǎn)生（population Initialization）

通過工步約束規(guī)則和有效工步序列轉(zhuǎn)換算法，將

那些無效工步序列逐一轉(zhuǎn)化成有效工步序列，所有有效

的工步序列集就組成了初始群體。

3. 選種（selection）

選種是指從初始群體中選擇出一些優(yōu)良的個體進

行后代的繁衍和進化，種子個數(shù)控制在20~100 以內(nèi)。

一般遺傳算法都是依據(jù)染色體個體的適應(yīng)值來進行選

擇，即按照給定的適應(yīng)度函數(shù)首先計算每個個體的適

應(yīng)值，然后將適應(yīng)值較高的個體作為種子生成交配池

（mating pool）。采用如下的方法進行：

（1）從初始群體中任意選擇出一些個體作為第一

代的種子，雖然這些種子開始并不能保證是一些較好的

個體，但是它們都是有效的個體，而優(yōu)良個體的選擇可

以逐步通過后面的經(jīng)營選擇策略來實現(xiàn)；

（2）當選出第一代種子后，接著進行個體評價，

把適應(yīng)值最大的個體作以標一記Amax 并把該最大適應(yīng)

值賦予一個變量fmax 進行保存，以便和下一代種群中

的最大的適應(yīng)值進行比較；

（3）進行交叉、變異操作，初步形成下一代種群；

（4）對下一代種群進行評價，并把適應(yīng)值最小

的個體作以標記Bmin，同時把最大適應(yīng)值賦給一變量

f‘max 且標記該個體( 具有最大適應(yīng)值)Bmax；

（5）將上一代的最大適應(yīng)值與本代（下一代）的

最大適應(yīng)值進行比較，如果上代的最大適應(yīng)值大于本代

的最大適應(yīng)值，則將上一代的最大個體Amax 代替掉本

代適應(yīng)值最小的個體Bmin，而本代中的其它個體保持

不變，這樣就形成了本代最終的種群P（t+1）；如果

上代的最大適應(yīng)值小于本代的最大適應(yīng)值，則將本代的

最大適應(yīng)值賦予變量fmax，即：fmax = f‘max，且將其

標記Bmax 換為Amax，而本代種群個體依舊保持不變。

重復上述的步驟（3）到（5），直到群體滿足某一指標，

或者己完成預定的迭代次數(shù)，則優(yōu)化算法結(jié)束。

4. 評價函數(shù)（適應(yīng)函數(shù)，fitness evaluation）

由于適應(yīng)值是群體中個體生存機會選擇的唯一確

定性指標，所以適應(yīng)函數(shù)的形式直接決定著群體的進化

行為。為了能夠直接將適應(yīng)函數(shù)與群體中的個體優(yōu)劣度

量相聯(lián)系，在遺傳算法中適應(yīng)值規(guī)定為非負，并且在任

何情況下總是希望越大越好。

在工藝設(shè)計中，評價指標是加工時間最短、加工

成本最低。我們以加工時間最短作為工步序列的優(yōu)化目

標，數(shù)控加工中心中影響加工時間的主要是零件特征的

加工時間和零件轉(zhuǎn)位、刀具更換等所占用的輔助時間，

在這里主要考慮輔助時間對整個零件加工的影響，因此

目標函數(shù)可以表達為：

g（x）=Min（f1，f2……fm）

其中m 為種群中染色體的個數(shù)，人為第i 條染色體

所對應(yīng)的加工時間，即第i 條工步序列鏈條所對應(yīng)的加工

時間。而每一條染色體其加工時間可通過下列等式計算：

上式中，n為染色體的長度( 即工步序列所包含的

工步個數(shù))，t1[j] 為連續(xù)兩道工步的轉(zhuǎn)位時間，t2[j]為

連續(xù)兩道工步的換刀時間，L[j]為第j 個工步所對應(yīng)的

加工方位代碼，T[j]為第j 個工步所對應(yīng)的刀具代碼。

對上式有下列的等式成立：

為了保證目標函數(shù)的優(yōu)化方向?qū)?yīng)于適應(yīng)值增大

的方向，有必要建立適應(yīng)函數(shù)與目標函數(shù)的映射關(guān)系，

保證映射后的適應(yīng)值是非負的。由于上述目標函數(shù)是屬

于最小化問題，因此對于適應(yīng)函數(shù)f（x）和目標函數(shù)g（x）有以下的映射關(guān)系：

其中， 是一個理論最大值，設(shè)定最大的加工時間

為理論最大值，即假設(shè)每道工步都存在轉(zhuǎn)位和換刀操作，

在這種情況下計算其加工時間即可得到最大理論值 。

5. 交叉運算（crossover）

交叉運算是進化算法中遺傳算法具備的原始性的獨

有特征。GA 交叉算子是模仿自然界中有性繁殖的基因重

組過程，其作用在于將原有的優(yōu)良基因遺傳給下一代個體，

并生成包含更復雜基因結(jié)構(gòu)的新個體。在本文中，我們采

用兩點交叉的方式進行交叉運算，具體步驟如下：

首先在種群中任意選取兩個種子作為父輩類進行

交叉運算，假設(shè)兩個父類分別為P1

和P2，在這兩個父類中任意指定兩個交叉點作為

交叉的位置，這樣父類染色體被分成了三部分：左半部

分、中部右半部分。交叉運算分兩步來進行：1）對于

下一代染色體個體Child1 的生成，首先將父類P1 的左

半部分和右半部分分別復制到子代Child1 的左右部分；

2）然后在父代P2 中依次尋找出與父代P1 中左半部分

和右半部分基因具有相同加工方位代碼、制造特征代碼

和加工操作（加工方法）代碼的全部基因，并將它們劃掉，

將父代P2 中剩下的基因按照它們原來的順序依次復制

到子代Child1 的中間部分，這樣子代Child1 就生成了，

采用同樣的方法就可生成子代Child2，由于父代染色體

是有效的染色體，因此采用該交叉方法生成的子代染色

體也是有效的。

6. 變異算子（mutation）

變異操作是通過模擬自然界生物體進化中染色體上

某位基因發(fā)生的突變現(xiàn)象，從而改變?nèi)旧w的結(jié)構(gòu)和物理

性狀。我們采用隨機交換染色體中的兩個基因代碼的位置

來完成變異運算。由于交換基因代碼后，會出現(xiàn)無效的染

色體，因此當完成位置交換后，還必須依據(jù)工步的約束規(guī)

則對染色體的有效性進行判斷，如果出現(xiàn)了無效染色體則

需要將其轉(zhuǎn)化為有效的染色體。轉(zhuǎn)換方法同前述的方法，

只需要將位于兩個交換點之間的基因序列進行有效性轉(zhuǎn)化

即可，這是因為在交換位置以外的基因序列本身就繼承了

染色體變異以前的合理性，因此只要保證交換點之間序列

的有效性就能保證整條染色體的有效性。

7. 循環(huán)終止條件 （100次后終止）

三、實例證明

1）精銑平面 2）鉆孔 3）擴孔

4）粗銑型腔 5）精銑型腔

圖2 零件加工工步圖

利用VisualC++ 語言開發(fā)了一個STEP-NC 加工系統(tǒng)

[5] ，演示了非線性工藝設(shè)計的過程，并對上述提出的遺傳

優(yōu)化算法進行了驗證。圖2 為零件加工工步圖，1）粗銑

平面2）精銑平面3）鉆孔4）擴孔5）粗銑型腔6）精銑

型腔。為了驗證本文提出的遺傳優(yōu)化算法的有效性和穩(wěn)定

性，利用Matalab 軟件對上述實例零件進行了不同參數(shù)情

形下的優(yōu)化仿真計算，其收斂效果見圖3 所示，運行參數(shù)

和結(jié)果見圖4，假設(shè)零件平均轉(zhuǎn)位時間為5s，平均換刀時

間為15s，優(yōu)化結(jié)果得出的最短加工輔助約為130 秒。

圖3 工步序列優(yōu)化收斂圖 種群大小交叉概率變異概率收斂次數(shù)最優(yōu)值

50 0.8 0.08 60 130s

30 0.6 0.1 35 130s

40 0.7 0.09 50 130s

圖4 遺傳算法的參數(shù)表值

結(jié)論：

基于精英選擇策略的遺傳優(yōu)化算法在工藝優(yōu)化中，

該算法具有很好的有效性、合理性、穩(wěn)定性，收斂性。

參考文獻

[1]秦寶榮、柯文等，基于遺傳算法的箱體零件加

工路線決策方法研究，中國機械工程，2002年13卷第

24期：2071-2075

[2]M.Shakeri ,IlnPlementation of an

automated oPeration Planning and oPtimum

oPeration sequencing and tool seleetion

algorithms，ComPuters in Industry，Volume54，

Issue3，August2004，Pages223-236

[3]D.Kritsis，K-P.Neuendorf and

P.Xirouehakis，Petri net teehniques for

Proees Planning cost estimation，Advanees

in Engineering Software，Volume30，Issue6，

June1999，Pages375-387

[4]李敏強、寇紀淞等，遺傳算法的基本理論與應(yīng)

用，北京:科學出版社，2002年3月，50~300

[5] 白麗, STEP-NC 數(shù)控系統(tǒng)整體規(guī)劃及程序解

釋器設(shè)計,2011年3月

注：文章內(nèi)所有公式及圖表請以PDF形式查看。