一種基于蝙蝠算法的工藝規(guī)劃方法

范孝良， 吳學(xué)華， 趙愛林， 王進(jìn)峰

(華北電力大學(xué)能源動力與機(jī)械工程學(xué)院，河北 保定 071003)

一種基于蝙蝠算法的工藝規(guī)劃方法

范孝良， 吳學(xué)華， 趙愛林， 王進(jìn)峰

(華北電力大學(xué)能源動力與機(jī)械工程學(xué)院，河北 保定 071003)

為了解決結(jié)構(gòu)復(fù)雜零件工藝規(guī)劃效率低、質(zhì)量差的問題，設(shè)計(jì)了一種改進(jìn)的蝙蝠算法用來進(jìn)行復(fù)雜零件的工藝規(guī)劃。在傳統(tǒng)的特征-工序的工藝路線表達(dá)方法的基礎(chǔ)上，設(shè)計(jì)了合理的蝙蝠編碼、解碼策略。建立了工藝路線和蝙蝠在搜索空間位置的映射矩陣，設(shè)計(jì)了蝙蝠種群的初始化方法。為了擴(kuò)大搜索范圍，改進(jìn)了蝙蝠算法原有的局部搜索策略，對局部最優(yōu)解進(jìn)行移位和變異操作，從而增加了種群的多樣性。仿真實(shí)驗(yàn)驗(yàn)證了該算法進(jìn)行工藝規(guī)劃的可行性。

工藝規(guī)劃；蝙蝠算法；工藝約束；局部搜索

計(jì)算機(jī)輔助工藝規(guī)劃(computer aided process planning，CAPP)是計(jì)算機(jī)集成制造系統(tǒng)(computer integrated manufacturing system，CIMS)的重要組成部分[1]，大大提高了工藝規(guī)劃效率和質(zhì)量。近年來，數(shù)控加工設(shè)備的應(yīng)用日益廣泛，可從事的工序類型遠(yuǎn)遠(yuǎn)超出了普通加工機(jī)床，許多傳統(tǒng)的CAPP系統(tǒng)已經(jīng)不能夠滿足新的加工環(huán)境要求。材料科學(xué)的不斷發(fā)展，使得特種裝備越來越多，其制造精度要求、尺寸要求、服役環(huán)境要求等也超出了傳統(tǒng)的機(jī)械加工工藝要求。另外，大型、奇型、結(jié)構(gòu)復(fù)雜的零件或者裝備在航天航空、深?？碧降阮I(lǐng)域出現(xiàn)的越來越頻繁，其加工工藝也變得日益復(fù)雜。為了解決上述問題，必須對傳統(tǒng)的CAPP方法進(jìn)行改進(jìn)。近年來，越來越多的人工智能技術(shù)應(yīng)用CAPP，用以解決當(dāng)前制造環(huán)境下的工藝規(guī)劃問題。

王忠賓等[2]通過同時考慮機(jī)床和刀具的選擇，進(jìn)行工藝路線的決策，并利用遺傳算法決策基于工藝約束的工藝路線規(guī)劃問題，同時考慮操作的選擇和工序的排序等多重任務(wù)來實(shí)現(xiàn)整個工藝過程的全局動態(tài)優(yōu)化。劉偉等[3]將被加工零件劃分為若干特征元，由各個特征元的加工鏈得到該零件的加工元。在禁忌準(zhǔn)則和約束條件的限制下，利用改進(jìn)的蟻群算法求解工藝規(guī)劃問題。Wang等[4]人將零件的工藝路線表示為二維的矩陣，通過將多種局部搜索算法結(jié)合進(jìn)傳統(tǒng)的粒子群優(yōu)化算法，進(jìn)行工藝路線的決策和優(yōu)化。近些年來，除了應(yīng)用智能搜索算法進(jìn)行工藝規(guī)劃以外，在CAPP的數(shù)學(xué)模型方面，也進(jìn)行了大量的研究。張祥祥等[5]為了在三維模型上實(shí)現(xiàn)工藝信息標(biāo)識，提出了一種基于模型定義(model based definition，MBD)技術(shù)和 GB/T 24734-2009的機(jī)加工工藝信息標(biāo)識方法。王進(jìn)峰等[6]考慮到作業(yè)車間的實(shí)際情況，進(jìn)行工藝規(guī)劃，獲得某種作業(yè)零件的多個可替換工藝路線，將傳統(tǒng)的工藝規(guī)劃問題和車間作業(yè)調(diào)度問題轉(zhuǎn)變?yōu)槎叩募蓡栴}。

CAPP問題一直是工業(yè)領(lǐng)域和學(xué)術(shù)界研究的熱點(diǎn)問題，尤其是隨著零件結(jié)構(gòu)日益復(fù)雜，奇型、異構(gòu)件越來越多，應(yīng)用傳統(tǒng)的方法進(jìn)行工藝規(guī)劃往往面臨的解空間太大，導(dǎo)致算法不收斂或者收斂過慢，最后無法獲得最優(yōu)解。本文利用蝙蝠算法求解工藝規(guī)劃問題，設(shè)計(jì)了合理的蝙蝠編碼、解碼規(guī)則和種群初始化的方法，并將兩種局部搜索算法結(jié)合到蝙蝠的局部搜索算法中，從而提高了算法求解工藝規(guī)劃問題的效率。

1　工藝路線的表達(dá)

在CAPP系統(tǒng)中，工序內(nèi)容是針對零件需要加工的特征表面。所以，在工藝規(guī)劃過程中，零件表面的加工特征首先要映射為相應(yīng)的工序?？紤]到車間的實(shí)際情況，有可能會出現(xiàn)同一加工特征映射成不同的可選工序，在這種情況下，工藝規(guī)劃首先要解決工序的選擇，然后對選擇的工序進(jìn)行排序。零件特征與工序的映射關(guān)系如圖1所示。

如圖1所示，同一特征可以由多種不同機(jī)床、夾具、刀具進(jìn)刀方向組合的工序表示[7]。CAPP第一步是根據(jù)零件的特征選擇工序進(jìn)行加工。第二步，根據(jù)特征之間的結(jié)構(gòu)關(guān)系，確定工序之間的工藝約束。在工藝規(guī)劃過程中常見的工藝約束主要包括先主后次，先粗后精、基準(zhǔn)先行、先面后孔等。根據(jù)工序間的工藝約束，對第一步確定的工序進(jìn)行排序。表1為某個零件的工藝路線。

圖1　零件特征與工序的映射關(guān)系

表1　可選擇的工藝路線示例

在CAPP系統(tǒng)中，通過工藝約束，在相關(guān)工藝知識表達(dá)的基礎(chǔ)上，能夠初步確定工藝路線。本文以生產(chǎn)成本最小化作為工藝規(guī)劃的目標(biāo)，并將生產(chǎn)成本分解為5個方面，即機(jī)床成本、刀具成本、裝夾成本、機(jī)床更換成本和刀具更換成本[7-8]。

(1) 機(jī)床總成本TMC：

MCi表示機(jī)床Mi的成本。

(2) 刀具總成本TTC：

TCi表示刀具Ti的成本。

(3) 機(jī)床更換總成本TMCC：

MCC表示單次機(jī)床更換成本，?1(x,y)是判斷函數(shù)：

(4) 刀具更換總成本TTCC：

式中TCC表示單次刀具更換成本，?2(x,y)是判斷函數(shù)：

(5) 裝夾總成本TSC：

式中SCC為單次裝夾成本。

(6) 總加工成本TPC：

2　基于蝙蝠算法的工藝規(guī)劃

2.1蝙蝠算法

自然界中，蝙蝠能夠根據(jù)回聲定位原理搜尋目標(biāo)，避開障礙物。受蝙蝠回聲定位行為的啟發(fā)，Yang[9]提出了一種新型的元啟發(fā)式算法-蝙蝠算法。所有的蝙蝠運(yùn)用回聲定位去感應(yīng)距離，在搜索空間中蝙蝠i在位置xi以速度vi隨意飛行，以固定頻率f、可變波長λ和響度A0去搜索食物，并根據(jù)與目標(biāo)物體的距離自動調(diào)節(jié)發(fā)射脈沖波長(或頻率)，在靠近目標(biāo)時調(diào)整脈沖發(fā)射頻度ri。對于解空間搜索的蝙蝠 i而言，其位置 xi和速度 vi通過式(9)～(11)更新。

同時，脈沖發(fā)射的響度Ai和頻度ri隨著迭代過程而更新。

2.2編碼

蝙蝠算法主要用于連續(xù)解空間的搜索，而工藝規(guī)劃問題是離散的組合優(yōu)化問題。因此，應(yīng)用蝙蝠算法求解工藝規(guī)劃問題，首先要進(jìn)行工藝規(guī)劃的編碼和解碼。工藝規(guī)劃問題要解決工序選擇和工序排序兩方面的問題，因此，通過2×n的矩陣表示蝙蝠i在第t次迭代的位置。

第1行表示選擇的工序，第2行表示已選擇工序的排序。其中選擇的工序可表示為：

其中，m_id、t_id、s_id分別代表工序n可選的機(jī)床編號、刀具編號和TAD編號。c可通過式(16)獲得：

其中，NM、NT、NS分別代表加工本零件的機(jī)床、刀具、TAD的最大數(shù)量。對于表1所示的某條工藝路線可表示為表2所示的矩陣。

表2　工藝路線編碼矩陣示例

在算法執(zhí)行過程中，需要對蝙蝠的位置矩陣進(jìn)行解碼，以計(jì)算其所代表的工藝路線的總成本，從而衡量其優(yōu)劣。對蝙蝠的位置編碼矩陣xit1n解碼可按照式(17)～(20)進(jìn)行。

表3　示例編碼矩陣的工藝路線

2.3初始化

蝙蝠種群初始化按照以下步驟進(jìn)行：

步驟1. 參數(shù)初始化。包括種群規(guī)模Pmax，最大迭代次數(shù)Nmax，最大重復(fù)次數(shù)Rmax等。

步驟2. 按照2.2節(jié)所示的方法初始化蝙蝠種群的每一只個體的初始位置xi和速度vi。

步驟3. 解碼每一只蝙蝠的位置矩陣，獲得其工藝路線，并計(jì)算其TPC，獲得當(dāng)前全局最優(yōu)的蝙蝠位置矩陣x*。

2.4迭代和局部搜索

(1) 根據(jù)式(14)～(16)，更新每一只蝙蝠的位置。

(2) 解碼每一只蝙蝠的位置矩陣為響應(yīng)的工藝路線，并計(jì)算其TPC。

雖然蝙蝠算法通過即時更新脈沖響度和頻率的方式來進(jìn)行局部搜索，但是實(shí)際進(jìn)行復(fù)雜零件工藝路線優(yōu)化的時候依然存在局部收斂或者收斂過慢的情況。因此，針對這兩種情況，本文采用兩種改進(jìn)的局部搜索手段來進(jìn)行工藝路線的優(yōu)化。

在算法的執(zhí)行過程中，早期階段的非正常收斂依然時常發(fā)生。本文通過控制重復(fù)次數(shù)Rmax來避免過早的局部收斂，保持算法的穩(wěn)定。如果連續(xù)Rmax次輸出相同工藝路線，則重新啟動算法。

當(dāng)蝙蝠種群的循環(huán)迭代次數(shù)達(dá)到Nmax時，則算法結(jié)束。

3　實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證算法的有效性，以圖2的零件為例進(jìn)行說明[8]。該零件的加工特征和工序的映射和工藝約束如表4所示，成本信息如表5所示。

針對圖2所示的零件進(jìn)行了大量的重復(fù)性試驗(yàn)，試驗(yàn)結(jié)果表明在參數(shù)Pmax= 50，Nmax= 200，fmin= 0，fmax=1，A0= 1，α=0.9，γ = 0.9，w=0.75，pm=0.3，ps= 0.2 and Rmax=10的情況下，能夠獲得較好的工藝路線，最終的輸出結(jié)果如表6所示。

圖2　示例零件

表4　特征和工序的映射關(guān)系

表7對比了蝙蝠算法與遺傳算法[8]、模擬退火算法[8]、禁忌搜索算法[10]和粒子群算法[11]的平均成本、最大成本和最小成本。從對比結(jié)果看，在表中所列舉的3個評價指標(biāo)下，蝙蝠算法都獲得了最好的結(jié)果。

表5　機(jī)床、刀具成本表

表6　最優(yōu)的工藝路線

表7　實(shí)驗(yàn)對比結(jié)果

4　結(jié)　論

本文改進(jìn)了傳統(tǒng)的蝙蝠算法用于復(fù)雜零件的工藝規(guī)劃。設(shè)計(jì)了合理的蝙蝠編碼、解碼策略，建立了工藝路線和蝙蝠在搜索空間位置的映射矩陣，設(shè)計(jì)了蝙蝠種群的初始化方法。為了擴(kuò)大搜索范圍，改進(jìn)了蝙蝠算法原有的局部搜索策略。對局部最優(yōu)解進(jìn)行移位和變異操作，增加了種群的多樣性。針對典型零件的仿真試驗(yàn)驗(yàn)證了算法的有效性，對比試驗(yàn)結(jié)果表明在平均成本，最小成本、最大成本3個評價指標(biāo)方面，蝙蝠算法都取得了最優(yōu)秀的結(jié)果。

因?yàn)閷?shí)際的車間運(yùn)行狀態(tài)直接影響著工藝規(guī)劃的效率和結(jié)果，下一步的工作是將機(jī)床、刀具等裝備的實(shí)時運(yùn)行狀態(tài)考慮到工藝規(guī)劃的數(shù)學(xué)模型中，使工藝規(guī)劃實(shí)時性更強(qiáng)。

[1] 邵新宇, 蔡力鋼. 現(xiàn)代CAPP技術(shù)與應(yīng)用[M]. 北京: 機(jī)械工業(yè)出版社, 2004: 5.

[2] 王忠賓, 王寧生, 陳禹六. 基于遺傳算法的工藝路線優(yōu)化決策[J]. 清華大學(xué)學(xué)報: 自然科學(xué)版, 2004, 44(7): 988-992.

[3] 劉偉, 王太勇, 周明, 等. 基于蟻群算法的工藝路線生成及優(yōu)化[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2010, 16(7): 1378-1382.

[4] Wang Y F, Zhang Y F, Fuh J Y H. A hybrid particle swarm based method for process planning optimization [J]. International Journal of Production Research, 2012, 50(1): 277-292.

[5] 張祥祥, 陳興玉, 程五四, 等. 基于模型的工藝信息標(biāo)識方法研究[J]. 圖學(xué)學(xué)報, 2012, 33(6): 146-150.

[6] 王進(jìn)峰, 范孝良, 宗鵬程, 等. 一種改進(jìn)的蟻群算法在工藝規(guī)劃與車間調(diào)度集成優(yōu)化中的應(yīng)用[J]. 圖學(xué)學(xué)報, 2014, 35(3): 396-401.

[7] Zhang F, Zhang Y F, Nee A Y C. Using genetic algorithms in process planning for job shop machining [J]. IEEE Transactions on Evolutionary Computation, 1997, 1(4): 278-289.

[8] Li W D, Ong S K, Nee A Y C. Hybrid genetic algorithm and simulated annealing approach for the optimization of process plans for prismatic parts [J]. International Journal of Production Research, 2002, 40(8): 1899-1922.

[9] Yang X S. A new metaheuristic bat-inspired algorithm nature inspired cooperative strategies for optimization (NICSO) [J]. Studies in Computational Intelligence, 2010, 284: 65-74.

[10] Li W D, Ong S K, Nee A Y C. Optimization of process plans using a constraint-based tabu search approach [J]. International Journal of Production Research, 2004, 42(10): 1955-1985.

[11] Guo Y W, Mileham A R, Owen G W, et al. Operation sequencing optimization using a particle swarm optimization approach [J]. Proceedings of the Institution of Mechanical Engineers B: Journal of Engineering Manufacture, 2006, 220(12): 1945-1958.

An Approach of Process Planning Based on Bat Algorithms

Fan Xiaoliang,Wu Xuehua,Zhao Ailin,Wang Jinfeng
(School of Energy, Power and Mechanical Engineering, North China Electric Power University, Baoding Hebei 071003, China)

An improved bat algorithm is employed to optimize the process planning for the complicated part to improve the efficiency and quality in process planning. A feasible bat encoding and decoding strategy is designed based on traditional process route representation method from the features to processes. The mapping matrix of process route and bat positions in the search space is constructed, and an initialized approach of bat population is designed. A modification for the local search of bat algorithms (BA) is executed to explore the search space. And displacement and mutation operation for local optimal solution are executed to diverse the population. Simulation experiments verify the feasibility of the proposed algorithm for process planning.

process planning; bat algorithm; operation constraints; local search

TP 301

A

2095-302X(2015)06-0856-06

2015-06-24；定稿日期：2015-07-31

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(13MS100，14ZD37)；國家自然科學(xué)基金資助項(xiàng)目(51301068)；河北省自然科學(xué)基金資助項(xiàng)目(E2014502003)

范孝良(1962–)，男，河北承德人，教授，碩士生導(dǎo)師。主要研究方向?yàn)橛?jì)算機(jī)集成技術(shù)、現(xiàn)代制造信息系統(tǒng)、工業(yè)工程等。E-mail：wcx803@163.com