鄧 偉，宋 景, 黃昊旻，姚固文

（貴陽(yáng)學(xué)院機(jī)械工程學(xué)院，貴州，貴陽(yáng) 550005）

1 概述

隨著智能制造的興起，計(jì)算機(jī)輔助工藝規(guī)劃越來(lái)越引起企業(yè)的重視。工藝路線優(yōu)化決策是工藝規(guī)劃工程中的重要環(huán)節(jié)，其主要包括加工方法的排序及工藝方案的選擇。工藝路線優(yōu)化問(wèn)題屬于NP-hard問(wèn)題，在工藝路線優(yōu)化工程中，工藝路線不僅受到切削參數(shù)、加工方法、機(jī)床和刀具選擇等的影響，還受到工藝優(yōu)先約束關(guān)系的影響。傳統(tǒng)的經(jīng)典算法如SD法、Newton等由于算法本身的限制，已經(jīng)很難求解這類問(wèn)題，所以尋找高效的智能算法求解該問(wèn)題成為了國(guó)內(nèi)外學(xué)者的研究重點(diǎn)，也取得了豐碩的研究成果[1-3]。

粒子群算法[4]（Particle swarm sptimization,PSO）源于復(fù)雜適應(yīng)系統(tǒng)（Complex Adaptive System,CAS），最早是在 1995年由 Eberhart和Kennedy提出，國(guó)內(nèi)外學(xué)者對(duì)PSO算法進(jìn)行了大量的研究[5-8]。PSO算法由于其容易實(shí)現(xiàn)的特點(diǎn)，取得了大量的實(shí)際應(yīng)用，但它和其它隨機(jī)優(yōu)化算法一樣，也存在早熟收斂現(xiàn)象，極易陷入局部收斂。在粒子群優(yōu)化算法中，算法的收斂速度和精度是相互矛盾的，在算法初期，希望算法擁有較大的搜索步長(zhǎng)，快速收斂到最優(yōu)解附近，但較大的搜索步長(zhǎng)同時(shí)也意味著算法后期不易收斂，還可能從全局最優(yōu)區(qū)域中跳出。在粒子群算法中，動(dòng)態(tài)權(quán)重對(duì)算法搜索精度有著很大的影響，文獻(xiàn)[9-12]均對(duì)算法中的權(quán)重系數(shù)進(jìn)行了研究，取得了良好的效果。

本文在已有研究的基礎(chǔ)上，使算法中的權(quán)重系數(shù)根據(jù)當(dāng)前粒子到全局最優(yōu)粒子的距離而動(dòng)態(tài)遞增，同時(shí)為了避免算法過(guò)早陷入局部最優(yōu)，在標(biāo)準(zhǔn)粒子群算法中引入模擬退火思想，使每個(gè)粒子的速度和位置更新過(guò)程中加入模擬退火機(jī)制，使粒子群按Metropolis準(zhǔn)則接受優(yōu)化解的同時(shí)概率接受惡化解，有效避免局部收斂。最后建立了以加工成本為優(yōu)化目標(biāo)的目標(biāo)函數(shù)，結(jié)合實(shí)際的工藝約束，詳細(xì)介紹了該算法進(jìn)行加工工序決策及相關(guān)機(jī)床和刀具的選擇過(guò)程。

2 工藝排序約束矩陣

機(jī)加工過(guò)程中為了避免加工操作間發(fā)生干涉以及保證加工質(zhì)量，零件上的幾何特征在加工過(guò)程中必須滿足一定的先后順序，使各加工操作之間產(chǎn)生先后約束。這類約束主要來(lái)源于工藝制定過(guò)程，為確保工藝路線的合理性，必須遵循這些約束。在機(jī)加工過(guò)程中，這些約束應(yīng)遵循以下規(guī)則：

1）先主后次。在制定機(jī)加工工藝時(shí)，應(yīng)先加工主要表面，后加工次要表面；

2）先面后孔。當(dāng)一個(gè)待加工面上存在孔系特征時(shí)，該面的加工操作須安排在孔系特征加工操作之前；

3）先粗后精。同一個(gè)特征的若干加工操作須滿足粗加工——半精加工——精加工——光整加工這樣的加工次序；

4）基準(zhǔn)優(yōu)先?；鶞?zhǔn)面應(yīng)首先加工，如果存在多個(gè)基準(zhǔn)面，則需要按照基準(zhǔn)面的轉(zhuǎn)換順序來(lái)決定基準(zhǔn)面的加工順序。

2.1 操作優(yōu)先圖

在滿足約束規(guī)則的條件下，零件特征的加工先后關(guān)系一般采用一個(gè)有向圖將其形象地表示出來(lái)，稱為操作優(yōu)先圖。如圖1所示，圖中的圓圈稱為節(jié)點(diǎn)，每一個(gè)圓圈均表示一個(gè)操作，圓圈里的數(shù)字表示該操作的編號(hào)（每個(gè)編號(hào)唯一且不重復(fù)），圓圈和圓圈之間的有向線表示操作的先后順序。當(dāng)兩個(gè)圓圈之間通過(guò)有向線直接連接時(shí)，表示這兩個(gè)操作有嚴(yán)格的優(yōu)先關(guān)系。如圖1中，操作1和操作3就存在嚴(yán)格的優(yōu)先關(guān)系。

圖1 操作優(yōu)先圖Fig.1 Operation precedence graph

操作優(yōu)先圖能直觀地描述出各個(gè)加工操作之間的先后順序。為了便于計(jì)算機(jī)識(shí)別推理，需將操作優(yōu)先圖轉(zhuǎn)化為計(jì)算機(jī)可以識(shí)別的優(yōu)先關(guān)系矩陣，也叫約束矩陣。若某個(gè)工件上的所有特征需要n個(gè)加工操作，則優(yōu)先關(guān)系矩陣可表示為，式中的值為0或1。這里作如下定義，若第i個(gè)操作先于第j個(gè)操作，且存在嚴(yán)格的優(yōu)先關(guān)系時(shí)，則=1，否則= 0 ，顯然矩陣P為n階0-1矩陣。按照此轉(zhuǎn)化規(guī)則，圖1所示的操作優(yōu)先圖可轉(zhuǎn)化為圖2所示0-1矩陣。

圖2 約束矩陣Fig.2 Constraint matrix

2.2 操作優(yōu)先圖拓?fù)渑判?/h3>

按照操作優(yōu)先圖給出的操作先后關(guān)系，將操作優(yōu)先圖中所有圓圈排成一個(gè)線性序列，使得該圖中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足，由此所得到的線性序列稱之為拓?fù)溆行蛐蛄?。拓?fù)渑判虿襟E如下：

1）輸入操作優(yōu)先圖；

2）在圖中任選一個(gè)沒(méi)有直接前驅(qū)的節(jié)點(diǎn)，并輸出；

3）從優(yōu)先圖中刪去該節(jié)點(diǎn)，同時(shí)刪除該節(jié)點(diǎn)發(fā)出的有向邊；

4）重復(fù)步驟2）、3），直到全部節(jié)點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬桑負(fù)渑判蛲瓿伞?/p>

若操作優(yōu)先圖中還有節(jié)點(diǎn)未輸出，但此時(shí)已跳出排序循環(huán)，說(shuō)明優(yōu)先圖中必定存在有向環(huán)，此時(shí)操作優(yōu)先圖所代表的操作流程將無(wú)法進(jìn)行。文獻(xiàn)[13]對(duì)有向環(huán)檢測(cè)做了詳細(xì)的算法說(shuō)明。

各個(gè)操作的入度值按式（1）進(jìn)行計(jì)算：

其中，為約束矩陣中第i行j列的元素值。由此可知，第1步操作的入度值為0。對(duì)于刪除入度值為零的頂點(diǎn)，則可以以弧頭頂點(diǎn)的入度值減 1來(lái)實(shí)現(xiàn)。

3 動(dòng)態(tài)權(quán)重SA-PSO算法

3.1 標(biāo)準(zhǔn)粒子群算法

假設(shè)一個(gè)由N個(gè)粒子組成的群體對(duì)D維空間進(jìn)行搜索，任意一個(gè)粒子的位置可表示為()，對(duì)應(yīng)的速度可表示為)，任意一粒子的歷史最優(yōu)值記作=)，整個(gè)群體的歷史最優(yōu)值記作= ()。在每一次迭代過(guò)程中，群體里的每個(gè)粒子同時(shí)跟蹤自己的歷史最優(yōu)值與群體歷史最優(yōu)值來(lái)更新自己的位置和速度，當(dāng)?shù)K止時(shí)，將當(dāng)前的群體最優(yōu)值作為所求問(wèn)題的最優(yōu)解。單個(gè)粒子速度和位置的更新規(guī)則如式（2）、（3）所示。

式（2）中，k代表迭代次數(shù)；w為慣性權(quán)重，是保持原來(lái)速度的系數(shù)，表示上一次迭代的粒子速度對(duì)當(dāng)前迭代粒子速度的影響，影響算法全局尋優(yōu)能力和局部尋優(yōu)能力；為學(xué)習(xí)因子，分別代表粒子對(duì)自身歷史最優(yōu)值的學(xué)習(xí)程度和對(duì)群體歷史最優(yōu)值的學(xué)習(xí)程度；和是為保持群體多樣性而設(shè)置的[0,1]之間的隨機(jī)數(shù)；ε為速度約束因子。

3.2 動(dòng)態(tài)權(quán)重SA-PSO算法

在優(yōu)化求解過(guò)程中，最終的目的是尋找全局最優(yōu)解。對(duì)于算法的每次迭代，都應(yīng)重點(diǎn)考慮在全局最優(yōu)粒子領(lǐng)域內(nèi)進(jìn)行搜索，因?yàn)樵诖祟I(lǐng)域內(nèi)有可能存在真正的全局最優(yōu)解。從式（2）可知，慣性權(quán)重決定著粒子的飛行速度，由于算法開(kāi)始時(shí)隨機(jī)產(chǎn)生的粒子幾乎不可能在最優(yōu)位置，此時(shí)較大的慣性權(quán)重w意味著較大的搜索步長(zhǎng)，有利于算法快速收斂到局部或全局最優(yōu)點(diǎn)附近，但隨著迭代次數(shù)的增加，有，，則式（2）近似為， 可知此時(shí)慣性權(quán)重對(duì)粒子飛行速度有著決定性的影響，如此時(shí)慣性權(quán)重w依舊很大，當(dāng)前粒子有可能跳出全局最優(yōu)的領(lǐng)域范圍。因此較為理想的方法是慣性權(quán)重w隨著當(dāng)前粒子與全局最優(yōu)粒子的距離而變化。當(dāng)距離遠(yuǎn)時(shí)，較大的慣性權(quán)重w有利于粒子的大范圍搜索；當(dāng)距離近時(shí)，較小的慣性權(quán)重w可保證其收斂精度。

用li表示第i個(gè)粒子到全局最優(yōu)粒子的距離，并限定粒子到全局最優(yōu)粒子的距離最大為，最小為。當(dāng)距離大于最大值時(shí)，慣性權(quán)重取最大值；當(dāng)距離小于最小值時(shí)，權(quán)重取最小值；當(dāng)距離在兩者之間時(shí)，慣性權(quán)重應(yīng)隨著距離遞增。其計(jì)算公式如下：

為了使適應(yīng)度較好的個(gè)體盡可能地保留，同時(shí)也為了避免算法局部收斂，將模擬退火思想引入PSO算法當(dāng)中。模擬退火算法[14]（Simulated Annealing Algorithm,SA）源于金屬退火原理，利用物理退火與優(yōu)化問(wèn)題的相似性，將優(yōu)化目標(biāo)看作是退火過(guò)程中的金屬能量狀態(tài)，并利用Metropolis準(zhǔn)則接受優(yōu)化解和概率接受惡化解，從而實(shí)現(xiàn)大范圍粗略搜索與局部精準(zhǔn)搜索的有效結(jié)合。動(dòng)態(tài)權(quán)重SA-PSO算法過(guò)程如下：

1）初始化搜索空間維度D，設(shè)置最大迭代次數(shù)K并產(chǎn)生一個(gè)有N個(gè)粒子的種群；

2）初始化慣性權(quán)重w，學(xué)習(xí)因子，退火起始溫度T0，終止溫度T；

3）計(jì)算第k次迭代中每個(gè)粒子的適應(yīng)度，i= 1 ,2,… ,N；

4）將粒子的適應(yīng)度與個(gè)體歷史最優(yōu)值進(jìn)行比較，若優(yōu)于，則用替代，否則保持不變；

5）將每個(gè)粒子的適應(yīng)度與群體最優(yōu)進(jìn)行比較，若優(yōu)于，則用替代，否則保持不變；

6）增加迭代次數(shù)，若，則進(jìn)行步驟7）。否則，結(jié)束計(jì)算；

7）根據(jù)式（5）改變慣性權(quán)重；

8）根據(jù)式（1）、（2）更新每個(gè)粒子的的位置和速度；

9）計(jì)算更新后的每個(gè)粒子適應(yīng)度；

10）計(jì)算，按模擬退火接受概率) = min{ 1,exp接受或舍棄更新后的位置，由文獻(xiàn)[2]可知，a為溫度衰減率，通常取為；若，則接受新位置為當(dāng)前位置，并返回步驟4）；若，則產(chǎn)生一個(gè)[0,1]之間的隨機(jī)數(shù)ε；若 e xp，則接受新位置，返回步驟4），否則不接受位置更新，返回步驟7）。

4 工藝路線優(yōu)化目標(biāo)函數(shù)的構(gòu)建

工藝路線優(yōu)化是將約束作用到加工操作上，在一定的約束條件下獲得最優(yōu)的加工工藝方案，使加工時(shí)間、加工成本等目標(biāo)達(dá)到最優(yōu)。工藝路線優(yōu)化過(guò)程中，常用的評(píng)價(jià)指標(biāo)有加工時(shí)間（T）和加工成本（C）。本文將最小加工成本作為優(yōu)化目標(biāo)進(jìn)行工藝線路優(yōu)化，加工成本包括機(jī)床成本（MC）、刀具成本（TC）、機(jī)床變換成本（MCC）、裝夾變化成本（SCC）和刀具變換成本（TCC），計(jì)算方式如式（5）～（9）所示[15]。

式（5）～（9）中，MCI為機(jī)床成本指數(shù)，表示機(jī)床在機(jī)加工過(guò)程中的單位時(shí)間成本；TCI為刀具成本指數(shù)，表示機(jī)加工過(guò)程中所用刀具的單位時(shí)間成本；MCCI為機(jī)加工過(guò)程中機(jī)床變換成本指數(shù)，表示機(jī)加工過(guò)程中每變換一次機(jī)床所需要的成本，包括人工成本、搬運(yùn)成本、運(yùn)輸成本等；SCCI為工藝線路中的裝夾變換成本指數(shù)，表示機(jī)加工過(guò)程中每更換一次裝夾方式所需要的成本；TCCI為刀具變換成本指數(shù)，表示機(jī)加工過(guò)程中每更換一次刀具所需要的成本；ti表示第i工步所消耗的機(jī)加工時(shí)間，分別表示第i工步所采用的機(jī)床、夾具及刀具。

綜上，零件加工過(guò)程中的總成本為式（10）所示。

5 實(shí)例驗(yàn)證

5.1 實(shí)例描述

如圖3所示零件，通過(guò)分析得到該零件一共有9個(gè)特征需要加工，共需要11個(gè)加工操作，每個(gè)特征的機(jī)加工時(shí)間可根據(jù)切削參數(shù)進(jìn)行計(jì)算。

圖3 零件模型Fig.3 The part model

零件加工信息如表1所示。

表1 零件加工信息Table 1 Processing information of the part

上述11個(gè)工步的操作優(yōu)先順序圖如圖4所示，按照文中所述規(guī)則，可將該操作優(yōu)先圖轉(zhuǎn)化為約束矩陣。

圖4 操作順序圖Fig.4 Operation sequence graph

在該零件加工過(guò)程中，共有鉆床、三軸立式銑床、數(shù)控立式銑床三種機(jī)床可供使用，其機(jī)床成本指數(shù)MCI分別為3、5、8，機(jī)床變換成本指數(shù)MCCI=5，裝夾變換成本指數(shù)SCCI=3，刀具變換成本指數(shù)TCCI=1?？捎玫毒咝畔⑷绫?所示。

表2 刀具信息Table 2 Tool information

5.2 工序的確定

根據(jù)文中所述算法，初始化粒子群粒子數(shù)N= 40，設(shè)置最大迭代次數(shù)K= 100，位置更新時(shí)速度約束因子ε=1，退火起始溫度，終止溫度，溫度衰減率α=0.8，=1，，慣性權(quán)重= 0 .9，= 0 .2。在迭代運(yùn)算中，設(shè)每次換刀時(shí)間均為 5 s，裝夾時(shí)間為15 s，并將換刀時(shí)間和裝夾時(shí)間計(jì)算在機(jī)床使用成本時(shí)間以內(nèi)，如特征F1切削時(shí)間為90 s，則加工該特征的機(jī)床的使用時(shí)間記為110 s。為了驗(yàn)證本文算法的有效性，應(yīng)用標(biāo)準(zhǔn)粒子群算法對(duì)圖3進(jìn)行了工藝路線求解，初始條件與文中算法一致。兩種算法的迭代對(duì)比如圖5所示。

圖5 兩種算法運(yùn)算結(jié)果Fig.5 The results of two algorithms

由運(yùn)算結(jié)果可知，采用標(biāo)準(zhǔn)粒子群算法時(shí)，迭代次數(shù)為54時(shí)收斂到最優(yōu)值272.3。采用文中的算法時(shí)，迭代次數(shù)為29時(shí)收斂到最優(yōu)值266.7?？芍捎梦闹兴惴〞r(shí)收斂速度相對(duì)較快，目標(biāo)函數(shù)值更優(yōu)，得到較優(yōu)機(jī)加工順序?yàn)椋?/p>

OP1——OP3——OP7——OP5——OP2——OP4——OP6——OP8——OP10——OP11——OP9。

詳細(xì)機(jī)床和刀具的選擇如表3所示。

表3 最優(yōu)工藝路線Table 3 Optimal processing route

6 結(jié)束語(yǔ)

在滿足實(shí)際工藝約束的情況下，解決復(fù)雜的機(jī)加工排序一直是工藝規(guī)劃過(guò)程中的難點(diǎn)之一。本文在標(biāo)準(zhǔn)PSO算法基礎(chǔ)上，引入了模擬退火精英保留策略，并使權(quán)重隨著當(dāng)前粒子到最優(yōu)粒子的距離變化而改變，一定程度上加快了算法早期的收斂，提高了算法后期收斂精度。最后以某零件的加工為例，以最小生產(chǎn)成本為優(yōu)化目標(biāo)，得出了較為理想的機(jī)加工工序，表明文中所建立的算法在工藝路線決策中具有一定的應(yīng)用價(jià)值。

[1]Triki H, Mellouli A, Masmoudi F. A multi-objective genetic algorithm for assembly line resource assignment and balancing problem of type 2 (ALRABP-2)[J]. Journal of Intelligent Manufacturing, 2017, 28(2):371-385.

[2]張思建,方彥軍,賀瑤,等. 基于模擬退火算法的 AVS/RS多批貨箱入庫(kù)貨位優(yōu)化[J].武漢大學(xué)學(xué)報(bào):工學(xué)版, 2016,49(2):315-320.

[3]Cinar D, Oliveira J A, Topcu Y I, et al. A priority-based genetic algorithm for a flexible job shop scheduling problem[J]. Journal of Industrial & Management Optimization, 2017, 12(4):1391-1415.

[4]張水平,王碧. 動(dòng)態(tài)搜索空間的粒子群算法[J].計(jì)算機(jī)應(yīng)用研究, 2016, 33(7):2047-2050.

[5]Garg H. A hybrid PSO-GA algorithm for constrained optimization problems[J]. Applied Mathematics &Computation, 2016, 274(11):292-305.

[6]Aziz M A A, Taib M N, Hussin N M. An improved event selection technique in a modified PSO algorithm to solve class scheduling problems[C]. Industrial Electronics &Applications, IEEE, 2016:203-208.

[7]毛君,楊辛未,潘德文,等. 基于改進(jìn)粒子群算法的刨煤機(jī)多目標(biāo)優(yōu)化設(shè)計(jì)[J].機(jī)械設(shè)計(jì)與研究, 2016(1): 168-170.

[8]徐立云,徐昌飛,鄧偉,等. 基于SA-PSO算法的發(fā)動(dòng)機(jī)缸體機(jī)加工線平衡研究[J].農(nóng)業(yè)機(jī)械學(xué)報(bào), 2014, 45(2):16-21.

[9]譚熠峰,孫婷婷,徐新民. 基于動(dòng)態(tài)因子和共享適應(yīng)度的改進(jìn)粒子群算法[J]. 浙江大學(xué)學(xué)報(bào):理學(xué)版,2016,43(06):696-700.

[10]封京梅,劉三陽(yáng). 基于慣性權(quán)重指數(shù)遞減的粒子群優(yōu)化算法求解絕對(duì)值方程[J]. 吉林大學(xué)學(xué)報(bào):理學(xué)版,2016,54(06):1265-1269.

[11]張志宇,白云霞. 粒子群算法不同慣性權(quán)重之間的比較[J].淮海工學(xué)院學(xué)報(bào):自然科學(xué)版, 2016,25(01):1-6.

[12]皮倩瑛,葉洪濤. 一種動(dòng)態(tài)調(diào)節(jié)慣性權(quán)重的粒子群算法[J].廣西科技大學(xué)學(xué)報(bào),2016,27(03):26-32.

[13]李愛(ài)平,魯力,王世海,等. 復(fù)雜箱體零件柔性機(jī)加工生產(chǎn)線平衡優(yōu)化[J].同濟(jì)大學(xué)學(xué)報(bào):自然科學(xué)版, 2015,43(4):625-632.

[14]楊衛(wèi)波,王萬(wàn)良,張景玲,等. 基于遺傳模擬退火算法的矩形件優(yōu)化排樣[J].計(jì)算機(jī)工程與應(yīng)用, 2016,52(7):259-263.

[15]黃偉軍,蔡力鋼,胡于進(jìn),等. 基于遺傳算法與有向圖拓?fù)渑判虻墓に嚶肪€優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng), 2009,15(9):1770-1778.