劉持平，董 成

(貴州大學(xué)機械工程學(xué)院，貴陽 550003)

改進遺傳算法在箱體零件加工路線優(yōu)化中的應(yīng)用

劉持平，董 成

(貴州大學(xué)機械工程學(xué)院，貴陽 550003)

研究了加工路線優(yōu)化問題和遺傳算法在此問題中的運用。在此基礎(chǔ)上添加懲罰函數(shù)來改進適應(yīng)度函數(shù)，添加自適應(yīng)策略并修改選擇算子來改進算法流程。最后以箱體零件為例，用VC++編程實現(xiàn)該算法的加工路線優(yōu)化，對結(jié)果進行分析，驗證了其可行性和有效性。

加工路線優(yōu)化;懲罰函數(shù);遺傳算法;工藝約束;CAPP

0 引言

計算機輔助工藝設(shè)計(Computer Aided Process Planning，CAPP)是聯(lián)接設(shè)計和制造的紐帶，其目的是提高工藝設(shè)計的質(zhì)量和效率，減少工藝人員從事的煩瑣重復(fù)性勞動。隨著現(xiàn)代集成制造技術(shù)的迅猛發(fā)展，以及多品種、小批量的生產(chǎn)越來越占主導(dǎo)地位，CAPP系統(tǒng)的研究與開發(fā)顯得尤為重要。工藝路線決策是CAPP的重點和難點之一。工藝路線的確定(主要是加工路線的排序)是工藝設(shè)計合理與否的關(guān)鍵，它直接影響CAPP系統(tǒng)的實用程度［1］。箱體零件不同于具有相識性的回轉(zhuǎn)體類零件，難以建立成組工藝，所以其工藝路線決策更加困難。

加工路線的確定實際上是一個帶約束的非線性規(guī)劃問題，因為它不僅受機床、刀具和夾具等因素的影響，而且受工藝約束的制約。文獻［2-8］研究了遺傳算法在工藝路線優(yōu)化中的應(yīng)用，獲得了較好的加工工藝。本文在研究原有理論的基礎(chǔ)上對適應(yīng)度函數(shù)進行改進，引入懲罰函數(shù)，綜合考慮機床、刀具、夾具因素和工藝約束限制的問題，并添加自適應(yīng)策略、修改選擇算子來改進算法流程。最后以箱體零件為例，用VC++編程實現(xiàn)了該算法的加工路線優(yōu)化，并對結(jié)果進行分析。

1 問題描述

對于加工路線優(yōu)化這種帶約束的非線性規(guī)劃問題，很難用傳統(tǒng)的優(yōu)化算法來解決。遺傳算法是將生物進化中自然選擇的法則用于解決科學(xué)研究和工程實際中遇到的各種優(yōu)化問題。運用遺傳算法，需要先將零件的每個特征按加工要求生成加工方法，例如:特征“平面”，設(shè)計公差I(lǐng)T=8、表面粗糙度Ra為3.2的加工方法為:粗銑—精銑，由兩個加工元組成。將所有特征的每個加工元組成鏈，生成加工鏈。然后利用遺傳算法中的交換和變異等算子對加工鏈進行迭代優(yōu)化，最終生成最優(yōu)加工路線。

2 改進遺傳算法

利用遺傳算法解決加工路線排序優(yōu)化問題，技術(shù)已經(jīng)比較成熟。關(guān)于基因編碼、初始種群的生成、交叉算子和變異算子，這里不再重復(fù)論述。本文中基因編碼和初始種群的生成采用文獻［4］的方式進行，但對種群中的個體不直接按照加工元的約束關(guān)系進行調(diào)整。交叉算子和變異算子采用文獻［5］的方式進行，但對子代個體不直接進行違反約束集的淘汰處理。下面對本文的改進遺傳算法進行詳細的論述。

2.1 工藝約束的制約問題和懲罰函數(shù)

一個合理的加工路線排序必須滿足加工方法之間的優(yōu)先關(guān)系約束，包括以下幾個方面:①定位約束;②基準約束;③裝夾約束;④非破壞性約束;⑤先主后次約束;⑥特征屬性自身決定的嚴格先后順序。違反任何一種約束的個體，其代表的加工路線都是不合理的，都是不可行解。由于特征加工鏈中約束條件很多，不可行解空間遠遠大于可行解空間，所以不能像傳統(tǒng)方式那樣將不可行解直接剔除。該算法引入懲罰函數(shù)，不用像文獻［4-6］對個體進行違反約束集的調(diào)整、驗證和剔除，也不用像文獻［7-8］對個體計算優(yōu)先權(quán)系數(shù)來生成大致符合約束集的個體。這樣將大大加快運算速度。

確定懲罰函數(shù)首先建立約束集合［5］，將加工元之間的先后關(guān)系用工藝約束矩陣表示，即用矩陣M［n］［n］(其中n等于加工鏈的長度)來表示。

懲罰函數(shù):

2.2 適應(yīng)度函數(shù)的確定

綜合考慮換機床次數(shù)、換刀次數(shù)、裝夾次數(shù)的因素和違反約束集的問題，本文的適應(yīng)度函數(shù)由兩部分組成:f1和懲罰函數(shù)fpunish。f1又由換機床得分、換刀得分、裝夾得分組成。

f1=w1fm+w2ft+w3fp(w1、w2、w3為0 ～ 1;w1+w2+w3=1);指定 w1、w2、w3的值可以確定機床、刀具和夾具的權(quán)重，一般w1＞w3＞w2。

最終的適應(yīng)度函數(shù):F=f1×(1-w4)+w4fpunish;對于懲罰系數(shù)w4，一般大于0.5，這樣突出了特征的加工元順序約束的重要性。

2.3 自適應(yīng)策略

本文的變異概率pm采用自適應(yīng)調(diào)整，不是用F來調(diào)整，而是f1(換機床得分、換刀得分與裝夾得分的總和)來進行調(diào)整:

pm1、pm2為0 ～1，f1max和f1avg分別為f1的最大值和平均值。這樣有利于個體向著換機床次數(shù)最少，換刀次數(shù)最少，裝夾次數(shù)最少的方向進化發(fā)展。對于算法的交叉概率pc取固定值，取值通常在0.5～0.9之間。

2.4 改進選擇算子

本文對算法的選擇操作采用“父代種群參與競爭的聯(lián)賽選擇”的方式，將父代復(fù)制之后再進行交叉變異，避免了把某個中間步驟中得到最優(yōu)解丟失的弊端，這樣將大幅度提高運算速度。在此基礎(chǔ)上本文還選擇其中適應(yīng)度F最大的前N×K3個(取整)個體作為子代(N為種群規(guī)模，K3一般取50% ～100%之間)，再隨機生成個體補充種群規(guī)模到N。這樣保證了種群的個體異性，搜索到全部解空間。

2.5 算法流程

改進選擇算子和加入自適應(yīng)策略，最終改進的算法流程如下:

(4)當(dāng)t等于Tmax時，輸出結(jié)果X，算法結(jié)束。否則t=t+1，返回步驟(3)。

3 運行實例

下面對VC++編制的系統(tǒng)進行論述。示例零件為離合器殼，鑄造成毛坯，材料為鑄鐵，加工特征數(shù)一共為30個，如圖1～圖3所示。

圖1 零件示意圖1

圖2 零件示意圖2

圖3 零件示意圖3

對各個特征進行分析后，將最終生成的加工鏈載入系統(tǒng)，一共29個加工元，則個體基因為X［29］。如圖4，圖5所示。

圖4 零件加工鏈(上)

圖5 零件加工鏈(下)

3.1 GA參數(shù)輸入

遺傳算法的參數(shù)輸入界面如圖6所示，機床系數(shù)、刀具系數(shù)與裝夾系數(shù)分別為 0.65、0.05、0.3，懲罰系數(shù)、參數(shù) k1、k2分別為 0.7，0.4，0.6，交叉變異率參數(shù) pc、pm1、pm2分別為 0.8、0.8、1，種群大小確定為80，迭代200代。

3.2 約束集輸入的改進

對于約束集M［n］［n］的輸入問題，特征屬性自身決定的嚴格先后順序，系統(tǒng)能自動識別。約束集的其它輸入，筆者采用如圖7所示的輸入方式:

(1)包括工藝孔在內(nèi)的重要定位特征 f1、f25、f26、f27、f28 先加工，之后是其它特征，最后 f16、f17、f25 的攻絲，對應(yīng)序號:1，2，21，22，23，24，25，26 ＞ 3，4，5，6，7，8，9，10，12，13，14，15，16，17，18，19，27，28，29 ＞ 11，20;

(2)特征f26、f27面加工后才能加工工藝孔f1:22，23，24，25 ＞ 1，2;

(3)特征f20端面先加工，之后是f22孔，最后是f30 的孔:13，14 ＞ 17，18 ＞ 28，29;

(4)特征f17的面先于f2～f9孔加工:9＞3;

(5)特征f21的面先于f10～f16孔加工:15，16＞ 4，5，6，7，8;

(6)特征f19的端面先于f18的螺紋孔加工:12＞ 10，11;

(7)特征f28的端面先于f16、f17的螺紋孔加工:13，14 ＞ 19，20。

一共7組，每一組用“;”號隔開區(qū)分，系統(tǒng)能對其自動識別并填充 M［n］［n］。

如圖7所示的三項最終填入內(nèi)容為:

(1)先 加 工:1，2，21，22，23，24，25，26;13，14;22，23，24，25;9;15，16;12;13，14;

(2)后 加 工:3，4，5，6，7，8，9，10，12，13，14，15，16，17，18，19，27，28，29;17，18;1，2;3;4，5，6，7，8;10，11;19，20;

(3)最后加工:11，20;28，29;

相比傳統(tǒng)矩陣式的輸入方式，這將大大加快約束集輸入的速度，節(jié)約大量的時間。

圖6 算法參數(shù)的輸入

圖7 約束集的載入

3.3 結(jié)果分析

最終在200代后生成的加工路線結(jié)果:先對主要基準進行加工24＞21＞22＞26＞23＞25＞，再對工藝孔進行加工 ＞1＞2＞，最后以工藝孔和主要基準來定位加工 ＞15＞16＞9＞27＞7＞3＞8＞13＞14＞19＞4＞5＞6＞17＞18＞28＞29＞12＞10＞11＞20。換床6次、換刀25次、裝夾10次、違反約束0次、適應(yīng)度函數(shù)為97.3471，結(jié)果合理。如圖8，圖9所示。

圖8 運行結(jié)果(上)

圖9 運行結(jié)果(下)

系統(tǒng)中加入了適應(yīng)度顯示模塊如圖10，將F、f1、fpunish三者隨進化代數(shù)的變化走勢顯示出來。從中發(fā)現(xiàn)在迭代初期，個體fpunish值比較低，嚴重違反約束集，但是這些個體包含很多有用信息，某些代的f1值比最終結(jié)果的f1值都要高。不用專門對這些個體進行違反約束集的調(diào)整，也不能直接將這些個體剔除，添加懲罰函數(shù)讓這些個體參與迭代有利于算法最優(yōu)結(jié)果的生成，提高了搜索的收斂效率，加快運算速度。

圖10 適應(yīng)度圖

4 結(jié)束語

基于遺傳算法的箱體零件加工路線排序優(yōu)化，綜合考慮機床、刀具、夾具因素和工藝約束限制的問題來改進適應(yīng)度函數(shù)，并改進了算法流程，提高了算法的收斂速度和準確性。最終設(shè)計的加工路線優(yōu)化系統(tǒng)，對CAPP系統(tǒng)的開發(fā)有一定的參考意義。

［1］王細洋，萬在紅.CAPP的關(guān)鍵問題及其對策［J］.制造業(yè)自動化，2000，22(2):25-29.

［2］Rocha J，Ramos C，Vale Z.Process planning using a genetic algorithm approach［A］.Proc of the 1999 IEEE Int Symp on Assembly and Task Planning［C］.Porto，Portugal:IEEE，1999:82-86.

［3］張冠偉，趙相松，李佳.基于遺傳算法的工步優(yōu)化排序方法［J］. 計算機集成制造系統(tǒng)，2005，11(2):242-246.

［4］劉連發(fā)，張振明，田錫天，等.基于遺傳算法的工藝過程優(yōu)化決策方法研究［J］.機械制造，2008，46(6):59-62.

［5］王忠賓，王寧生，陳禹六.基于遺傳算法的工藝路線優(yōu)化決策［J］. 清華大學(xué)學(xué)報，2004，44(7):988-992.

［6］劉偉，王太勇.基于遺傳算法的工藝路線生成及優(yōu)化［J］. 農(nóng)業(yè)機械學(xué)報，2009，40(8):202-208.

［7］袁青，李迎光，王偉，等.基于遺傳算法的飛機結(jié)構(gòu)件加工特征排序［J］.機械科學(xué)與技術(shù)，2011，30(1):86-91.

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

［9］陳國良.遺傳算法及其應(yīng)用［M］.北京:人民郵電出版社，1996.

Optimization of Manufacturing Sequence Based on Improved Genetic Algorithm about Box Part

LIU Chi-ping，DONG Cheng
(School of Mechanical Engineering，Guizhou University，Guiyang 550003，China)

Researched on the problem of manufacturing sequence optimization and the application of genetic algorithms in this problem.On the basis，the paper added punish function to improve fitness function.Besides，the paper added adaptive strategy and modified Selection operator to improved flow of genetic algorithm，which can improve the velocity of convergence and veracity of genetic algorithms.Eventually，taken the box parts as the example to achieve the optimization of manufacturing sequence by programming with VC++and analyzed the result，which proves the algorithm's feasibility and effectiveness.

manufacturing sequence optimization;punish function;genetic algorithms;process constraint;CAPP

TH162;TP391

A

1001-2265(2012)01-0085-04

2011-06-13;

2011-07-12

劉持平(1954—)，女，江蘇人，貴州大學(xué)機械工程學(xué)院教授，從事制造系統(tǒng)自動化、計算機輔助工藝過程設(shè)計、計算機輔助生產(chǎn)管理系統(tǒng)的研究，(E-mail)cpliu@gzu.edu.cn。

(編輯 李秀敏)