基于STEP-NC 加工工步序列的優(yōu)化

周楊 鐘建琳

摘要：研究了基于精英選擇遺傳算法的加工工步序列優(yōu)化技術(shù)。傳統(tǒng)的加工工藝路線是以工序?yàn)橹圃靻卧?/p>

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

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

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

關(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

引言：作用而導(dǎo)致當(dāng)前群體的最佳個(gè)體在下一代的丟失，De

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

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

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

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

處理，排除N 個(gè)工步序列中的許多無(wú)效工步序列，但

的問(wèn)題。

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

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

設(shè)計(jì)中，操作人員經(jīng)常依賴于經(jīng)驗(yàn)來(lái)進(jìn)行決策，由于操

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

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

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

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

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

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

數(shù)量的個(gè)體。

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

多學(xué)者都進(jìn)行了大量的研究，人們?cè)捎昧嘶趯?dǎo)數(shù)的

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

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

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

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

的求解效率比較低，有時(shí)甚至最先進(jìn)的計(jì)算工具上都無(wú)

法求解。

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

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

次，沒(méi)有明確的優(yōu)化目標(biāo)，適用度函數(shù)難以表達(dá)。遺傳

算法（Genetic Algorithm，簡(jiǎn)稱GA）由于其具有以編碼、

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

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

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

模型的遺傳算法來(lái)進(jìn)行工步序列的優(yōu)化。

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

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

1. 基因編碼（Gene encoding）

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

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

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

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

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

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

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

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

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

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

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

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

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

具進(jìn)行順次編號(hào)，考慮到在一次加工中可能含有多個(gè)工

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

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

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

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

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

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

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

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

3. 選種（selection）

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

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

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

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

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

（mating pool）。采用如下的方法進(jìn)行：

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

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

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

以逐步通過(guò)后面的經(jīng)營(yíng)選擇策略來(lái)實(shí)現(xiàn)；

（2）當(dāng)選出第一代種子后，接著進(jìn)行個(gè)體評(píng)價(jià)，

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

值賦予一個(gè)變量fmax 進(jìn)行保存，以便和下一代種群中

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

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

（4）對(duì)下一代種群進(jìn)行評(píng)價(jià)，并把適應(yīng)值最小

的個(gè)體作以標(biāo)記Bmin，同時(shí)把最大適應(yīng)值賦給一變量

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

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

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

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

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

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

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

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

標(biāo)記Bmax 換為Amax，而本代種群個(gè)體依舊保持不變。

重復(fù)上述的步驟（3）到（5），直到群體滿足某一指標(biāo)，

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

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

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

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

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

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

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

在工藝設(shè)計(jì)中，評(píng)價(jià)指標(biāo)是加工時(shí)間最短、加工

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

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

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

在這里主要考慮輔助時(shí)間對(duì)整個(gè)零件加工的影響，因此

目標(biāo)函數(shù)可以表達(dá)為：

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

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

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

時(shí)間。而每一條染色體其加工時(shí)間可通過(guò)下列等式計(jì)算：

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

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

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

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

對(duì)上式有下列的等式成立：

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

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

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

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

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

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

在這種情況下計(jì)算其加工時(shí)間即可得到最大理論值 。

5. 交叉運(yùn)算（crossover）

交叉運(yùn)算是進(jìn)化算法中遺傳算法具備的原始性的獨(dú)

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

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

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

用兩點(diǎn)交叉的方式進(jìn)行交叉運(yùn)算，具體步驟如下：

首先在種群中任意選取兩個(gè)種子作為父輩類進(jìn)行

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

和P2，在這兩個(gè)父類中任意指定兩個(gè)交叉點(diǎn)作為

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

分、中部右半部分。交叉運(yùn)算分兩步來(lái)進(jìn)行：1）對(duì)于

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

半部分和右半部分分別復(fù)制到子代Child1 的左右部分；

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

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

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

將父代P2 中剩下的基因按照它們?cè)瓉?lái)的順序依次復(fù)制

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

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

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

體也是有效的。

6. 變異算子（mutation）

變異操作是通過(guò)模擬自然界生物體進(jìn)化中染色體上

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

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

來(lái)完成變異運(yùn)算。由于交換基因代碼后，會(huì)出現(xiàn)無(wú)效的染

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

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

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

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

即可，這是因?yàn)樵诮粨Q位置以外的基因序列本身就繼承了

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

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

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

三、實(shí)例證明

1）精銑平面 2）鉆孔 3）擴(kuò)孔

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

圖2 零件加工工步圖

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

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

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

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

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

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

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

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

間為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)定性，收斂性。

參考文獻(xiàn)

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

工路線決策方法研究，中國(guó)機(jī)械工程，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]李敏強(qiáng)、寇紀(jì)淞等，遺傳算法的基本理論與應(yīng)

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

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

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

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