徐立云 史 楠 段建國 李愛平

同濟(jì)大學(xué)，上海，201804

0 引言

零件的工藝路線是指從零件模型獲取零件結(jié)構(gòu)、功能和設(shè)計(jì)要求等信息，然后確定其加工方法和所需資源，完成零件從毛坯狀態(tài)到成品狀態(tài)轉(zhuǎn)變的過程［1］。受產(chǎn)品多樣性、制造過程離散性、生產(chǎn)環(huán)境復(fù)雜性和系統(tǒng)狀態(tài)模糊性的綜合影響，零件制造過程中工藝路線的決策較為復(fù)雜。合理的工藝路線不僅可以優(yōu)化和節(jié)約制造資源、縮短產(chǎn)品制造周期、降低制造成本，還可以提高產(chǎn)品質(zhì)量和推動企業(yè)技術(shù)進(jìn)步，因此越來越受到企業(yè)的重視。

由于零件加工特征和加工方法的多樣性、加工要求的個性化以及約束的復(fù)雜性，當(dāng)排序規(guī)模較大、符合工藝規(guī)則的可行方案數(shù)量較多時(shí)，單純依靠經(jīng)驗(yàn)難以取得最優(yōu)或次優(yōu)的排序方案，而且也不能運(yùn)用傳統(tǒng)的邏輯決策或者運(yùn)籌學(xué)的經(jīng)典算法（如整數(shù)規(guī)劃、動態(tài)規(guī)劃或分支定界等方法）來求解。近年來一些啟發(fā)式算法，如遺傳算法［2-4］、蟻群算法［5-6］和模擬退 火算法［7］等被用來解決這類問題。文獻(xiàn)［8］對零件特征之間的約束關(guān)系進(jìn)行分類，通過特征關(guān)系圖描述基本的合理性約束，將最優(yōu)性約束的滿足程度視為工藝路線優(yōu)化的判斷標(biāo)準(zhǔn)，最后利用遺傳算法實(shí)現(xiàn)了工藝路線的排序。文獻(xiàn)［9］將遺傳算法應(yīng)用到零件特征加工方法決策過程中，根據(jù)工藝知識和加工要求，將每一種加工方法表示為遺傳空間的染色體，進(jìn)行基因編碼，然后通過實(shí)例介紹了利用遺傳算法進(jìn)行加工方法決策的過程。然而對于工藝路線的優(yōu)化，有時(shí)采用單一的優(yōu)化算法達(dá)不到理想的效果，需要改進(jìn)算法，或者采用混合算法，利用算法優(yōu)化機(jī)制之間的互補(bǔ)性，提高全局優(yōu)化效率。

遺傳算法是模仿自然界生物進(jìn)化機(jī)制發(fā)展起來的隨機(jī)全局搜索和優(yōu)化方法，并行性高、魯棒性強(qiáng)，適合大規(guī)模復(fù)雜問題的優(yōu)化求解，但是存在“早熟”的缺陷。模擬退火算法是模擬固體退火過程的熱平衡問題，利用固體物質(zhì)的退火過程與隨機(jī)搜索尋優(yōu)問題之間的相似性來優(yōu)化求解，達(dá)到全局最優(yōu)或近似最優(yōu)的目的。此算法局部搜索能力強(qiáng)，但收斂速度慢，存在“隨機(jī)漫步”的問題。

本文從分析工藝路線優(yōu)化的問題入手，構(gòu)建工藝路線優(yōu)化的數(shù)學(xué)模型，結(jié)合加工工藝等優(yōu)化約束條件，利用改進(jìn)的遺傳算法對模型求解，最后結(jié)合具體的實(shí)例進(jìn)行了驗(yàn)證。

1 工藝路線優(yōu)化問題描述

工藝路線的優(yōu)化需要綜合考慮零件特征、特征之間的幾何約束、制造資源的選擇以及工藝人員經(jīng)驗(yàn)等多方面因素［10］。圖1為零件加工層次示意圖。

圖1 零件加工層次示意圖

零件特征是指包括零件一定的幾何形狀、工程意義和加工要求的一組信息的集合，是構(gòu)成零件幾何形狀和信息模型的基本單元。零件通常由許多加工特征構(gòu)成，如平面、螺紋、槽等。設(shè)某零件有N 個加工特征，則所有特征組成的集合可表示為

式中，fi表示第i個加工特征，i＝1，2，…，N。

從零件的加工過程看，對于每個加工特征fi，一般要經(jīng)過多次加工，從而形成特征的加工序列（加工鏈），可表示為

其中，j表示加工特征fi需要的加工序列數(shù)目。

從毛坯開始，首先采用加工方法MP1加工出中間特征f′1；然后用加工方法MP2加工出中間特征f′2，直到采用加工方法MPj加工出合格的形狀特征fi為止。

以特征為核心的有關(guān)特征加工鏈的相關(guān)信息所形成的實(shí)體，定義為加工元（feature machining element，F(xiàn)ME），用七元組表示為

式中，ID表示加工元編碼；MPij表示在加工階段MLij對特征fi進(jìn)行加工所采用的加工方法；MMij、MTij和MSij表示采用加工方法MPij加工特征fi所需的機(jī)床、刀具和夾具等制造資源。

零件的加工工藝過程往往有若干道工序組成，一道工序包含若干個加工工步，一個工步中包含多個加工元，其關(guān)系如圖2所示。

圖2 工序、工步和加工元關(guān)系圖

零件的加工元集合構(gòu)成該零件的加工工藝，表示為

零件的任一工藝路線可以表示為x＝（fme1，fme2，…，fmeN），但在實(shí)際生產(chǎn)中，零件的工藝路線是加工元集合FME中的加工元fmeij滿足工藝約束和其他約束目標(biāo)的合理排序結(jié)果。

2 工藝路線約束分析

工藝路線安排中要考慮的約束因素眾多，比如零件特征加工方法的選擇、機(jī)床的選擇和刀具的選擇等，可表示為下列函數(shù)形式［11］：

式中，S為工藝路線；P為所選加工方法集合；Me為加工機(jī)床集合；G為零件各表面幾何形狀；Dev為各表面形位公差；Tec為加工階段的劃分、基準(zhǔn)的加工及熱處理和其他輔助工序的性質(zhì)等工藝要求；Cp為加工費(fèi)用。

除此之外，還要考慮工藝約束，例如優(yōu)先關(guān)系約束、聚類約束等的影響。因此，為了制定出合理的工藝路線，必須統(tǒng)籌考慮各種影響因素。

（1）典型工藝準(zhǔn)則。在考慮零件的加工順序時(shí)，對于某些特定特征，先安排粗加工、半精加工，再安排精加工或光整加工；對于不同的特征，某些特征的粗加工則可能安排在其他特征的半精或精加工之后，例如越程槽、倒角等輔助特征的粗加工一般在主特征的半精加工之后進(jìn)行；對于零件的全部特征，一般則遵循先基準(zhǔn)后其他的原則，即必須先加工作為基準(zhǔn)面的特征，再加工其他表面特征。

（2）聚類約束。隨著設(shè)備加工能力的提高，工序集中原則逐漸成為影響工藝路線的一個重要因素。按照工序集中的原則，某些特征應(yīng)安排在一起加工。例如屬于相同加工階段的特征加工單元、同一方位面的特征、相同類型或需同一把刀具加工的特征等。

（3）輔助加工約束。零件的退火、正火應(yīng)安排在粗加工之前或者粗加工和半精加工之間，滲碳處理應(yīng)安排在半精加工和精加工之間。

（4）優(yōu)化約束。合理的工藝路線，不僅要考慮零件的幾何形狀、技術(shù)要求、工藝方法等因素，還要考慮生產(chǎn)率、加工時(shí)間或成本等約束。優(yōu)化約束的目的是使零件的工藝路線更加合理。

3 數(shù)學(xué)模型

零件的工藝路線是將其所有特征的加工鏈組合在一起，滿足一定約束目標(biāo)優(yōu)化排序的結(jié)果，可歸結(jié)為數(shù)學(xué)中的組合優(yōu)化問題。組合優(yōu)化問題的目標(biāo)是從組合問題的可行解集中求出最優(yōu)解，通?？擅枋鰹椋毫瞀?＝｛x1，x2，…，xn｝為所有狀態(tài)構(gòu)成的解空間，f（xi）為xi狀態(tài)對應(yīng)的目標(biāo)函數(shù)值，要求尋找最優(yōu)解x＊，使得對于所有的xi∈Ω，有f（x＊）≤f（x）。 該問題的數(shù)學(xué)模型描述為

其中，f（x）為目標(biāo)函數(shù)，g（x）為約束函數(shù)，x 為決策變量，Ω表示有限個解組成的集合。

實(shí)際加工過程中，為了提高零件的加工質(zhì)量，縮短制造周期，應(yīng)盡量降低制造資源（機(jī)床、刀具或者夾具等）的更換頻率?；鶞?zhǔn)的頻繁更換會造成裝夾誤差，不利于工藝過程的穩(wěn)定性；換刀次數(shù)的增多會增加非切削加工的時(shí)間，降低機(jī)床的利用效率。可將目標(biāo)函數(shù)表示為

其中，αF、αC和αM分別為夾具變換次數(shù)、換刀次數(shù)和機(jī)床變換次數(shù)的權(quán)重系數(shù)，由工藝人員根據(jù)具體情況確定，本文取αF＝0.3，αC＝0.2，αM＝0.5；FF（x）、FC（x）、FM（x）分別表示裝夾次數(shù)、換刀次數(shù)和機(jī)床變換次數(shù)；GiD、GiFS、GiFt、GiC、GiM 分別表示加工中用到的定位基準(zhǔn)、裝夾表面、夾具、刀具和機(jī)床；δ（a，b）是一個判斷函數(shù)，表示為

因此，零件加工工藝路線的數(shù)學(xué)模型可表示為：對于零件特征的加工元集合FME＝（fme1，fme2，…，fmeN），尋 找 一 個加工元序列x ＝（fmea（1），fmea（2），…，fmea（N）），在滿足相應(yīng)的約束條件下，使F（（fmea（1），fmea（2），…，fmea（N）））最小。

4 基于改進(jìn)遺傳算法的工藝路線優(yōu)化

4.1 遺傳模擬退火算法

遺傳模擬退火算法的基本步驟如下：

（1）設(shè)置控制參數(shù)：種群規(guī)模n，進(jìn)化終止代數(shù)N，初始退火溫度t＝ts（s＝0），終止溫度tf，馬爾科夫鏈長Ls；

（2）初始化種群P（k），k＝0；

（3）對種群P（k）進(jìn)行遺傳操作，直至產(chǎn)生下一代種群：①計(jì)算種群P（k）的適應(yīng)度；②選擇適應(yīng)度高的個體進(jìn)行復(fù)制，以概率Pc進(jìn)行個體的交叉操作，以概率Pm進(jìn)行個體的變異操作；

（4）種群P（k）的模擬退火操作。①隨機(jī)產(chǎn)生一個初始解i作為最優(yōu)解，計(jì)算其目標(biāo)函數(shù)值f（i）；②在解i的鄰域內(nèi)產(chǎn)生新解j，計(jì)算新的目標(biāo)函數(shù)值f（j）；按 Metropolis準(zhǔn)則判斷是否接受新的解為最優(yōu)解：

③若s＜Ls，則s←s＋1，轉(zhuǎn)向②；④若t≥tf，則更新溫度ts＋1＝update（ts），轉(zhuǎn)向 ①；

（5）判斷進(jìn)化終止代數(shù)k是否達(dá)到N，如果滿足條件則轉(zhuǎn)至步驟（6），否則轉(zhuǎn)向步驟（3）；

（6）停止計(jì)算，輸出最優(yōu)解。

遺傳模擬退火算法的流程如圖3所示。

4.2 基因編碼

編碼方式不僅影響染色體的排列方式，還決定個體從搜索空間的基因型變換到解空間的表現(xiàn)型的解碼方式。本文采用自然數(shù)字鏈進(jìn)行基因編碼來表達(dá)加工元的排序問題。

為了便于工藝路線的描述和遺傳操作，將加工元表示為fme＝｛ID，f，MP，ML，MM，MT，MS｝，其中：ID、f、MP、ML、MM、MT 和MS 分別為加工元編號、加工特征、加工方法、所需的機(jī)床、刀具和夾具，如圖4所示。

基因表示零件加工元集合中的一個加工元，染色體為零件的一種加工元序列，代表了零件的一種工藝方案。對于要求連續(xù)加工或同時(shí)加工的多個加工元，可合并為一個。

4.3 初始種群的產(chǎn)生

圖3 遺傳模擬退火算法的流程圖

圖4 加工元基因編碼

種群初始化過程中，隨機(jī)產(chǎn)生一定數(shù)量的種群作為組合優(yōu)化問題的初始解。即原始種群為由一定數(shù)量的加工元序列組成的集合，集合中每個個體代表一種工藝路線。對于初始種群的大小，目前尚無理論上的指導(dǎo)，實(shí)際應(yīng)用中常常根據(jù)經(jīng)驗(yàn)確定，一般取值范圍為20～100。

4.4 選擇

選擇操作是建立在對個體的適應(yīng)度評價(jià)的基礎(chǔ)上的，對種群中的個體按照適應(yīng)度從大到小進(jìn)行排序，采用輪盤選擇法。假設(shè)每個個體的適應(yīng)度為fk（k＝1，2，…，l），種群總的適應(yīng)度為則將作為第k個個體的選擇概率。通過選擇操作使得群體中個體的適應(yīng)度值不斷接近最優(yōu)解。

4.5 交叉變異

交叉運(yùn)算是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成新的個體的算法。變異是指個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個新的個體的過程。變異與交叉結(jié)合后，能夠避免由于選擇和交叉運(yùn)算造成的某些信息的丟失，從而保證遺傳算法的有效性。

交叉算子采用雙點(diǎn)交叉，在相互配對的兩個個體編碼串中隨機(jī)設(shè)置兩個交叉點(diǎn)，交換兩個個體在所設(shè)定的兩個交叉點(diǎn)之間的部分染色體，其示意圖見圖5。

圖5 二點(diǎn)交叉算子示意圖

變異算子采用均勻變異，依次指定個體編碼串中的每個基因座為變異點(diǎn)，對每個變異點(diǎn)，以變異概率從對應(yīng)基因的取值范圍內(nèi)取一隨機(jī)數(shù)代替原有值，其示意圖見圖6。

圖6 變異算子示意圖

4.6 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)的選擇至關(guān)重要，因?yàn)樵谶z傳算法中指導(dǎo)搜索的主要依據(jù)是個體的適應(yīng)度值。適應(yīng)度函數(shù)不僅能夠有效地指導(dǎo)搜索沿著面向優(yōu)化參數(shù)組合的方向，逐漸逼近最佳參數(shù)組合，而且不會導(dǎo)致搜索不收斂或者陷入局部最優(yōu)解。

本文中的適應(yīng)度函數(shù)表示為

4.7 退火過程中新個體的接受

本文通過選擇、交叉、變異等遺傳操作產(chǎn)生一組新個體，隨機(jī)選擇各個個體中的兩個基因作為擾動點(diǎn)，經(jīng)擾動后的個體所得的適應(yīng)度增強(qiáng)，則按Metropolis準(zhǔn)則接受這個新個體，否則以某一概率接受惡化的新個體。這正是模擬退火算法區(qū)別于一般的局部搜索算法的本質(zhì)所在，判斷準(zhǔn)則如式（12）所示。

4.8 終止計(jì)算條件

遺傳算法中如果連續(xù)迭代次數(shù)達(dá)到一定值后，最優(yōu)個體的適應(yīng)度值保持不變，或者迭代次數(shù)達(dá)到規(guī)定的最大迭代次數(shù)，則終止計(jì)算，輸出最優(yōu)適應(yīng)度對應(yīng)的加工序列。遺傳算法的終止進(jìn)化代數(shù)一般取100～500。

模擬退火的溫度是按照ts＋1＝λts衰減的，λ為衰減系數(shù)，當(dāng)退火溫度下降至終止溫度時(shí)，停止尋優(yōu)，否則重新進(jìn)行交叉和變異操作。

5 應(yīng)用實(shí)例

以圖7所示的某型號發(fā)動機(jī)缸體為例說明該混合算法的實(shí)現(xiàn)過程。

圖7 發(fā)動機(jī)缸體三維模型

通過分析得到缸體主要特征有：頂面、底面、前端面、后端面、左面以及右面等面特征，以及油道孔、凸輪軸孔、曲軸孔以及缸孔等孔特征。將幾何特征相同的特征聚類為一個特征，用同一代號表示，然后參與排序。經(jīng)過特征聚類后，該缸體零件有35個主要制造特征，相關(guān)的特征和加工元信息、加工資源分別由表1和表2給出。圖8為在分析缸體特征加工先后順序基礎(chǔ)上的加工元優(yōu)先關(guān)系圖。

算法參數(shù)的設(shè)置如下：種群規(guī)模設(shè)為50，算法的最大迭代次數(shù)為100，交叉率為0.7，變異率為0.01，模擬退火初始溫度t0為100℃，衰減系數(shù)為0.8，終止溫度為90℃。根據(jù)初始化信息和約束條件，運(yùn)用MATLAB軟件編寫相關(guān)程序，采用遺傳模擬退火算法和遺傳算法搜索過程的收斂情況如圖9所示。從圖中可以看出，采用遺傳模擬退火算法比單純采用遺傳算法的收斂速度快、目標(biāo)函數(shù)最優(yōu)值小。

得到的最優(yōu)缸體工藝路線如表3所示，其中機(jī)床變換5次，夾具變換5次，刀具更換44次。然后插入輔助工序（中間清洗、試漏、合裝軸承蓋、壓入凸輪軸孔襯套、最終清洗、施膠壓裝水悶、試漏和成品檢查）形成完整的發(fā)動機(jī)缸體加工工藝路線。

表1 缸體的特征和加工元信息

表2 可用的刀具和機(jī)床信息

圖8 缸體特征加工元的優(yōu)先關(guān)系

表3 缸體加工的工藝路線

圖9 算法比較

6 結(jié)論

針對發(fā)動機(jī)缸體的復(fù)雜性，在得到缸體各個特征加工方法鏈的基礎(chǔ)上，將特征細(xì)化為加工元后建立缸體工藝路線優(yōu)化的數(shù)學(xué)模型；利用遺傳模擬退火算法的優(yōu)點(diǎn)，通過復(fù)制、交叉和變異等操作對模型進(jìn)行求解，對工藝路線的排序進(jìn)行啟發(fā)式全局尋優(yōu)，避免了局部優(yōu)化結(jié)果的產(chǎn)生，并用實(shí)例驗(yàn)證了模型的實(shí)用性和算法的可行性。

［1］胥利軍，張振明，田錫天，等.基于三維零件模型的工藝路線設(shè)計(jì)方法研究［J］.機(jī)械設(shè)計(jì)與制造，2010（1）：28－30.Xu Lijun，Zhang Zhenming，Tian Xitian，et al.Research on a Feasible Approach for the Process Route Planning of Mechanical Machining Based on Three Dimensional Part Model［J］.Machinery Design and Manufacture，2010（1）：28－30.

［2］王忠賓，王寧生，陳禹六.基于遺傳算法的工藝路線優(yōu)化決策［J］.清華大學(xué)學(xué)報(bào)，2004，44（7）：988－992.Wang Zhongbin，Wang Ningsheng，Chen Yuliu.Optimization of Process Routing Based on the Genetic Algorithm［J］.Journal of Tsinghua University，2004，44（7）：988－992.

［3］Zhang W B，Lu Z H，Zhu G Y.Optimization of Process Route by Genetic Algorithms［J］.Robotics and Computer－integrated Manufacturing，2006，22（2）：180－188.

［4］劉偉，王太勇.基于遺傳算法的工藝路線生成及優(yōu)化［J］.農(nóng)業(yè)機(jī)械學(xué)報(bào)，2009，40（8）：203－208.Liu Wei，Wang Taiyong.Generation and Optimization of Process Routing Based on Genetic Algorithm［J］.Transactions of the Chinese Society for Agriculture Machinery，2009，40（8）：203－208.

［5］Krishna A G，Rao K M.Optimization of Operations Sequence in CAPP Using an Ant Colony Algorithm［J］.The International Journal of Advanced Manufacturing Technology，2006，29（1／2）：159－164.

［6］田穎，江平宇，周光輝，等.基于蟻群算法的零件多工藝路線決策方法研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2006，12（6）：882－887.Tian Ying，Jiang Pingyu，Zhou Guanghui，et al.Research on Part Multiple Process Routes Decision Making Based on Ant Colony Algorithm［J］.Computer Integrated Manufacturing Systems，2006，12（6）：882－887.

［7］Ma G H，Zhang Y F，Nee A Y C.A Simulated Annealing Based Optimization Algorithm for Process Planning［J］.International Journal of Production Research，2000，38（12）：2671－2687.

［8］朱海平，肖詩旺，黃剛.基于遺傳算法的工藝過程排序研究［J］.華中科技大學(xué)學(xué)報(bào)，2006，34（3）：50－53.Zhu Haiping，Xiao Shiwang，Huang Gang.Research on Operation Sequencing Based on Genetic Algorithm［J］.Journal of Huazhong University of Science and Technology，2006，34（3）：50－53.

［9］頡潭成，李慶軍，李寶棟，等.基于遺傳算法的零件特征加工方法決策系統(tǒng)［J］.農(nóng)業(yè)機(jī)械學(xué)報(bào)，2005，36（9）：120－122.Xie Tancheng，Li Qingjun，Li Baodong，et al.Decision Making of Feature Process Method Based on Genetic Algorithm［J］.Transactions of the Chinese Society for Agriculture Machinery，2005，36（9）：120－122.

［10］常智勇，楊建新，趙杰，等.基于自適應(yīng)蟻群算法的工藝路線優(yōu)化［J］.機(jī)械工程學(xué)報(bào)，2012，48（9）：163－169.Chang Zhiyong，Yang Jianxin，Zhao Jie，et al.Optimization of Process Based on Adaptive Ant Colony Algorithm［J］.Journal of Mechanical Engineering，2012，48（9）：163－169.

［11］譚顯春，劉飛，曹華軍.綠色制造的一種工藝路線決策模型及其求解算法［J］.機(jī)械工程學(xué)報(bào)，2004，40（4）：154－159.Tan Xianchun，Liu Fei，Cao Huajun.Decisionmaking Model for Process Route in Green Manufacturing and Its Algorithm［J］.Chinese Journal of Mechanical Engineering，2004，40（4）：154－159.