基于遺傳算法的工藝路線決策與優化

范順成 王進峰② 李世杰

(①河北工業大學機械工程學院，天津 300130;②華北電力大學機械工程系，河北保定 071003)

工藝路線決策是指利用所有的加工資源設計出從毛坯到零件的詳細加工過程，包括確定加工方法、選擇機床和刀具、計算切削用量、優化加工路線、裝夾工件等方面內容。計算機輔助工藝規劃是指利用計算機模仿經驗豐富的工藝設計人員完成工藝路線規劃，是一個典型的多目標決策和優化過程。隨著人工智能技術的發展，遺傳算法、蟻群算法等智能算法逐漸應用于工藝路線規劃問題的研究，為獲得最優或者接近最優的工藝路線提供了理論和技術支持［1－2］。目前的研究大部分著重于工藝路線染色體的交叉、變異算法設計，對于工藝知識表達方法、基因編碼規則等基礎性工作討論較少。

本文在工藝路線決策優化研究的基礎上，確定了基于特征的工藝知識表達方法，構建基于工藝約束的工藝路線決策空間，建立了多目標優化函數，通過遺傳算法對工藝路線進行優化。

1 工藝知識的表達

一個典型工藝路線決策一般通過以下步驟。

(1)選擇定位基準。

(2)選擇加工方法:1個零件被若干具有加工意義的加工特征所描述，例如孔、槽、倒角等。對于每一個加工特征，尋找所有能夠得到加工特征屬性(形狀、尺寸、公差和表面粗糙度)的加工方法。

(3)劃分加工階段。

(4)選擇機床、刀具、夾具:根據加工方法和制造資源能力，選擇機床和刀具。

(5)選擇切削用量:根據加工余量等，選擇合理的切削用量。

(6)加工方法排序:根據工藝約束、加工成本、效率、質量等指標對加工方法排序，形成工藝路線。

CAPP系統中利用計算機完成上述工藝路線的決策。而工藝知識表達方法直接影響工藝路線標準化、規范化和工藝路線的決策水平。在CAPP系統中，工藝知識表達就是將工藝知識通過某種數據結構結合到計算機系統的程序設計過程，是工藝知識的模型化和形式化。

實踐表明工藝知識粒度大小和關鍵工藝知識直接影響工藝知識的表達。工藝知識劃分越細，其所表達的知識量就越大［3］。據此原則，CAPP系統中將工藝知識劃分為工藝路線、工步、特征表面、加工階段、加工方法、刀具、夾具、機床和切削用量9個方面，每種工藝知識可通過相應特征向量表達。因此，某零件的工藝路線可以表示為:

i是該零件包含的工步數，OPi是構成該零件的第i道工步，可表示為7維特征向量。

式中:P為加工表面;S為加工階段，分為粗加工、半精加工、精加工;M為加工方法，分為車、銑、刨、磨、鉆、擴、鏜、鉸等;D為定位基準;R為切削用量;E為機床;C為刀具;J為夾具。

OPi中每一個特征向量又可表示為相應的特征向量。譬如，切削用量特征向量為

式中:ID為順序號，對于每一種零件工藝路線需要確定的切削用量統一編號，用以唯一確定每次選擇的切削用量;v為切削速度，m/s;f為進給量，mm/r或者mm/z;ap為背吃刀量，mm。

加工表面特征向量為

式中:ID為順序號，構成零件的每一個表面統一編號，用以唯一確定加工表面;PT為特征類型，包括平面、外圓、孔、鍵槽等。

CAPP系統中的其他工藝知識也可表述為相應的特征向量，由工藝路線、工步、加工表面等9種工藝知識向量能夠準確地表達復雜零件的工藝路線。在工藝路線決策過程中，零件的加工表面是工藝路線決策的依據，根據加工表面的特征，譬如尺寸、位置、形狀精度和表面層的物理機械性能進行定位基準、加工方法的確定，加工階段的劃分。為了能夠實現加工表面的技術要求，決策合理的工藝路線，必須遵循加工表面間的優先關系，即工藝約束［4］。在CAPP系統中，工藝約束稱之為關鍵工藝知識。關鍵知識影響工藝路線的決策過程。通常關鍵工藝知識包括以下內容:

(1)優先加工主要表面 當某個表面和其他表面存在形位公差時，確定該表面為主要表面，優先加工。當某個表面的加工影響到其他表面的裝夾時，確定該表面為主要表面，優先加工。零件的輔助表面應安排在主要表面之后加工。譬如對于獨立于其他工序的輔助工藝孔、槽、倒角等，應安排在主要表面之后加工。

(2)優先加工平面 先加工平面，再以平面定位加工孔。既能保證加工時孔有穩定可靠的定位基準，又有利于保證孔與平面間的位置精度要求。

(3)先粗加工，后精加工，粗精分開 一個零件各表面的加工一般都需要分階段進行，粗加工工序應安排在精加工工序之前。

(4)其他工藝約束，譬如基于加工效率最高、成本最低等表面優先加工約束。

2 工藝路線的決策

選擇合理的工裝設備、切削用量、加工方法和順序是工藝路線決策的重要內容。在CAPP系統中，通過工藝約束，在相關工藝知識表達的基礎上，能夠初步確定工藝路線。但是，該工藝路線往往不是當前生產環境下最優的工藝路線，譬如，最低成本的工藝路線［5］、最高效率工藝路線等［6］。因此，工藝路線決策時，除了能夠滿足基本的設計要求外，還需要針對不同目標優化工藝路線。實際上，工藝路線決策是一個帶約束的非線性優化問題，即

式中優化變量x是工步順序，由n個7維工步向量組成的工藝路線;hi(x)、gj(x)是約束函數。所謂最優工藝路線，是指在滿足約束函數前提下，目標值最小。工藝路線進行優化決策的目標是使加工過程或者成本最低、或者質量最好、或者效率最高。

傳統加工方式下，這3者往往是相互影響的。工程實踐表明，頻繁地裝拆工件、刀具，更換機床會導致效率降低，成本升高，對于加工質量也有一定的影響。因此，本文以機床、刀具、工件的更換次數最少作為優化目標，關鍵工藝知識作為約束函數［7］。為了進一步明確優化目標，采用傳統的多目標優化函數處理方法，針對具體的生產環境，為上述三種優化目標分別設置權重系數，然后求和，作為優化目標。多目標的優化問題轉為單目標的優化問題。

3 基于遺傳算法的工藝路線優化

遺傳算法是一種全局搜索優化算法，將優勝劣汰的自然選擇法則應用到目標尋優過程中。它通過對包含可能解的種群反復應用基于遺傳學的操作，生成新的種群，從而使問題的解不斷進化，獲得滿足要求的最優或接近最優解。種群的基本單位為染色體。在遺傳算法中，主要存在以下5種操作。

(1)基因編碼:由二進制或十進制數字構成的鏈表構成染色體，鏈表中的每一位數字或者每一組數字對應染色體中的一個基因。

(2)種群初始化:選擇具有較好目標函數的染色體，構成第一代種群。

(3)復制:選擇具有較好目標值的染色體進行復制，在下一代中代替具有較差的目標值的染色體。

(4)交叉:在一定交叉率下，選取一定數量的染色體按照規則兩兩交換，形成新的子代染色體。

(5)變異:在一定變異率下，選擇一定數量的染色體，進行自身基因交換，形成新的子代染色體。

通過復制、交叉和變異生成的染色體將代替具有較差的目標函數的染色體，形成新的子代，這個過程被反復進行，直至達到優化目標或者規定的次數，然后停止搜索。下面以圖1所示零件為例詳細說明基于遺傳算法的工藝路線決策和優化過程。

3.1 基因編碼

基因編碼方式對于工藝路線決策空間和遺傳算法的搜索能力有重要影響。對于工藝路線決策和優化而言，染色體對應零件的工藝路線，基因對應構成工藝路線的每一道工步。設零件的工藝路線由n道工步組成，那么一個染色體中就有 n個基因，可以表示為{G1，G2，…，Gi，…，Gn}，基因 Gi表示第 i道工步。工藝路線決策以機床、刀具、工件的更換次數最少作為優化目標，通過對不同優化目標設置權重，將多目標優化問題轉化為單目標優化問題，因此，基因編碼需要包含機床、刀具、工件等的信息。根據第1節的論述，確定基因編碼為5位十進制數字碼，分別是加工表面碼、機床碼、刀具碼、第一定位基準(表面)碼，加工階段碼，其中前4個碼位的值域為1～n，分別對應為相應特征向量的ID順序號，加工階段碼的值域為數字1～3，分別代表粗加工階段、半精加工階段、精加工階段。圖1所示零件的基因編碼如表1所示。

表1 基因編碼

3.2 初始化種群

一般情況下，根據基因編碼規則和染色體長度隨機初始化種群，作為工藝路線的決策空間。但是工藝約束的存在，要求嚴格按照關鍵工藝知識的規則進行種群初始化。按照關鍵工藝知識的規則，圖1所示零件加工表面間的優先級關系如表2所示。

表2 加工表面的優先級關系

CAPP系統中，根據關鍵工藝知識，初始化種群的算法可采用循環遍歷法，對種群中的每一個染色體進行檢查。從染色體的最后一個基因開始，遍歷整個染色體，逐個判斷每個基因是否滿足關鍵工藝知識規則，不滿足，則退出該染色體檢查，如果滿足，則從倒數第二個基因開始，遍歷該基因以前所有基因，進行判斷，依次類推，直至遍歷該染色體的每一個基因。經過關鍵工藝知識檢驗的染色體構成了工藝路線決策空間，使遺傳算法的搜索空間減小，避免了缺陷染色體的出現。初始化種群的算法如圖2所示。對于初始種群的大小，實際應用中只能依據經驗或實驗確定，一般建議的取值范圍是20～100。圖3是生成的兩個有效染色體。

3.3 確定目標函數

根據第2節的討論，多目標函數經過加權處理，轉變為單目標函數。假設種群初始化后形成了染色體空間R，包含n條染色體，每條染色體包含14個基因，n條染色體構成了工藝路線的決策空間。目標函數可表示為

式中:x為染色體;SJ(x)為染色體x的裝夾次數;SC(x)為染色體x的換刀次數;SE(x)為染色體x的機床變換次數;αJ、αC、αE為裝夾次數、換刀次數、機床變換次數的權重;Gi(3)為基因i的第3碼位，刀具碼位;Gi(2)為基因i的第2碼位，機床碼位;Gi(4)為基因i的第4碼位，基準碼位。

λ(x，y)是一個判斷函數，表示為

根據優化目標可知，Sx值越小，染色體則越接近最優，工藝路線越接近最優解。

3.4 復制、交叉、變異

復制是遺傳算法的基本算子，將一代種群中目標函數值較小的染色體直接復制到下一代種群中，即精英染色體保留策略，同時，為了避免陷入局部最優，對于精英染色體中目標函數相同或者接近的染色體設置復制概率，一般為10% ～20%，使下一代種群既保留了精英染色體，又避免了陷入局部最優。交叉運算從種群中隨機選擇兩個父代染色體，隨機產生兩個交叉位置，在一個父代染色體中取出兩個交叉點之間的基因，雜交點外的基因保持不變，然后在另一個父代染色體中尋找交叉點外缺少的基因，按照原來的排列順序插入到兩個交叉點之間的位置，形成一個新的子代染色體。以上述的兩個染色體為例，取染色體1的交叉點X=5和Y=9，經過交叉運算則形成一個新的染色體如圖4所示。取染色體1的相應兩個交叉點，經過交叉運算也可形成新的染色體。執行交叉操作的染色體個數一般取種群染色體個數的50% ～90%，經過交叉運算后生成的新染色體，需要經過關鍵工藝知識的檢驗，符合要求進入下一代染色體。變異操作一般是在一定的變異率下，選擇一部分染色體，在單個染色體內部進行兩個或多個基因交換，形成新的染色體符合關鍵工藝知識的規則，則直接形成新的子代，否則，放棄。在這個過程中，如果變異率過大，會破壞杰出群體而使解遠離最優，變異率過小，則不會產生新的基因塊。為了保護杰出群體，變異率取值范圍為1% ～10%。

表3 最優工藝路線

復制、交叉、變異操作反復進行，經過若干次的迭代后，到達目標函數的最小值或者接近最小值，對應的工藝路線為最優的工藝路線。

上述示例零件，取20條染色體構成決策空間，復制概率10%，交叉概率80%，變異概率5%，αJ、αC、αE分別設置為0.2、0.2、0.6，迭代次數取100，最后得到最優染色體如圖5，對應工藝路線如表3。

4 結語

在CAPP系統中，工藝路線的決策和優化是非常重要和復雜的。本文將遺傳算法應用于工藝路線的決策和優化過程中，分析了基于加工特征的工藝知識表達方法，設計了目標函數和適應度函數，采用了基于十進制數的基因編碼規則，通過選擇、改進的交叉和變異算法反復作用于種群來優化工藝路線，從而獲得最優或者接近最優的工藝路線。另外，工藝路線的優化是機加工工藝優化的一方面，切削參數的優化也影響工藝路線的決策和優化［8］?？紤]到實際加工環境，工藝路線的優化還要考慮具體的車間作業任務等問題［9］。上述問題將在以后的工作中予以關注。

［1］劉曉芳，趙萬生，遲關心，等.基于改進遺傳算法的工藝過程優化設計［J］.中國機械工程，2003，14(2):137－140.

［2］田穎，江平宇，周光輝，等.基于蟻群算法的零件多工藝路線決策方法研究［J］.計算機集成制造系統，2006，12(6):882 －887.

［3］劉晨，殷國富，龍紅能.制造工藝知識粒度描述方法與獲取算法研究［J］.計算機集成制造系統，2008，14(10):1966－1973.

［4］胡于進，張正義，凌玲，等.基于工藝約束矩陣的加工序列優化［J］.中國機械工程，2009，20(9):1062－1066.

［5］王忠賓，王寧生，陳禹六.基于遺傳算法的工藝路線優化決策［J］.清華大學學報:自然科學版，2004，44(7):988 －992.

［6］王志紅，杜平安，郭志龍，等.基于遺傳算法與動態規劃法的工藝過程優化［J］.電子科技大學學報，2007，36(1):146 －149.

［7］凌玲，王青青，張正義，等.基于改進遺傳算法的箱體類零件加工路線優化問題研究［J］.組合機床與自動化加工技術，2009(1):75－80.

［8］蔡力鋼，張建設，張正義，等.復雜零件工藝方案全局多層并行優化［J］.機械工程學報，2008，44(9).

［9］LEUNG C W，WONG T N，MAK K L，et al.Integrated process planning and scheduling by an agent－ based ant colony optimization［J］.Computers＆ Industrial Engineering，2010，54:166－180.