李忠群，郭文慧，王志康

（湖南工業(yè)大學(xué) 機(jī)械工程學(xué)院，湖南 株洲 412007）

基于混合改進(jìn)型遺傳算法的螺旋銑孔孔群加工路徑優(yōu)化研究

李忠群，郭文慧，王志康

（湖南工業(yè)大學(xué) 機(jī)械工程學(xué)院，湖南 株洲 412007）

在業(yè)已確定螺旋銑孔切削參數(shù)的前提下，孔群加工路徑的優(yōu)劣對加工效率有較大影響。研究TSP數(shù)學(xué)模型，應(yīng)用混合改進(jìn)遺傳算法求解孔群加工路徑優(yōu)化模型，獲得優(yōu)化的加工路徑。將3種算法基本遺傳算法、蟻群算法和混合改進(jìn)型遺傳算法進(jìn)行對比可知，本文提出的優(yōu)化方法可有效縮短走刀時(shí)間。

遺傳算法；螺旋銑孔；路徑優(yōu)化；蟻群算法

0　引言

螺旋銑孔是近年來新興的一項(xiàng)柔性制孔技術(shù)，能用同一把刀具加工各種不同直徑的孔［1-2］。螺旋銑孔工藝采用以銑代鉆的方式，彌補(bǔ)了傳統(tǒng)加工的不足，被廣泛運(yùn)用于高硬材料、鈦合金及碳纖維增強(qiáng)復(fù)合材料（carbon fiber reinforced polymer/plastic，CFRP）的制孔中［3-6］。采用螺旋銑孔工藝加工孔群時(shí)［7］，由于各孔的相對位置及孔徑的不同，刀具在孔群中的移動順序?qū)⒅苯佑绊懽叩稌r(shí)間。因此，有必要對走刀路徑進(jìn)行合理規(guī)劃，使刀具空行程最短。通常，數(shù)控編程人員根據(jù)設(shè)計(jì)圖紙人為確定加工路徑，這種做法在孔數(shù)較少時(shí)尚能確保加工路徑基本合理，但隨著孔數(shù)目的增加，很難保證能獲得合理的加工順序。

孔群路徑優(yōu)化問題可以直接抽象為典型的旅行商問題（travel saleman problem，TSP）。旅行商問題是一個(gè)經(jīng)典的組合優(yōu)化問題［8］，具體描述如下：有一旅行商要訪問n個(gè)城市，每個(gè)城市必須訪問且只能訪問一次，需要尋求到一條包含所有n個(gè)城市的最短訪問路線［9-10］。從圖論的角度來看，該問題實(shí)質(zhì)是在一個(gè)帶權(quán)完全無向圖中，找一個(gè)權(quán)值最小的Hamilton回路。由于該問題的可行解是所有頂點(diǎn)的全排列，隨著頂點(diǎn)數(shù)的增加，會產(chǎn)生組合爆炸，因此它是一個(gè)NP（non-deterministic polynomial）完全問題。NP完全問題一般被認(rèn)為是人們難以在有限的時(shí)間和空間內(nèi)對問題求出最佳解的問題，利用非常規(guī)的求解技術(shù)求解是其常用的一種方法［11-12］。早期研究者使用精確算法如分枝定界法、線性規(guī)劃法和動態(tài)規(guī)劃法等來求解規(guī)模較小的旅行商問題，但運(yùn)用到規(guī)模較大的問題中時(shí)，這些方法效果并不理想。因此，近來國內(nèi)外學(xué)者重點(diǎn)采用智能算法諸如遺傳算法、模擬退火算法、蟻群算法、禁忌搜索算法、貪婪算法和神經(jīng)網(wǎng)絡(luò)算法等來求解該問題。

針對螺旋銑孔孔群加工路徑優(yōu)化問題，本文提出了一種混合改進(jìn)型遺傳算法。將刀具當(dāng)作旅行商，待加工孔當(dāng)作旅行商訪問的城市，通過建立TSP數(shù)學(xué)模型并利用現(xiàn)代人工智能方法，進(jìn)行參數(shù)模型化處理，最終獲得最短加工路徑，從而提高加工效率。

1　數(shù)學(xué)模型的建立

采用螺旋銑孔工藝加工孔群，其工作流程如下：刀具從作業(yè)起點(diǎn)開始，按照加工順序依次對孔群進(jìn)行加工，最后回到刀具起始位置。為減少問題的復(fù)雜性，對模型作如下假設(shè)。

1）刀具位置的控制精度能滿足設(shè)計(jì)要求。

2）刀具在加工孔之間移動速度保持不變。

3）刀具在確定的銑削參數(shù)下進(jìn)行孔群加工。

針對螺旋銑孔路徑規(guī)劃中加工零件和加工工藝兩個(gè)對象，本文提出了一種解決路徑規(guī)劃的改進(jìn)算法。在孔群加工順序規(guī)劃中，待加工孔的信息由孔的位置坐標(biāo)（x， y）、孔徑Dh和孔深h三個(gè)參數(shù)來描述，加工工藝參數(shù)由刀具直徑Dt、主軸轉(zhuǎn)速n、切向每齒進(jìn)給量fzt和軸向每齒進(jìn)給量fza來描述。在確定銑削條件下，設(shè)C=｛C1， C2， …， Cn｝是刀具在一次加工中所有待加工孔組成的孔群。確定一條經(jīng)過各孔當(dāng)且僅當(dāng)一次的最短路徑，其圖論描述為：給定圖G=（V， A），其中V為頂點(diǎn)集，A為各頂點(diǎn)相互連接組成的邊集，已知各頂點(diǎn)間的邊接距離，求一個(gè)n結(jié)點(diǎn)的帶權(quán)完全圖的最短Hamilton回路。定義加工過程刀具空行程的分布為：

此時(shí)目標(biāo)函數(shù)可簡化為

2　混合改進(jìn)型遺傳算法

2.1經(jīng)典遺傳算法

經(jīng)典遺傳算法（classical genetic algorithm，CGA）是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法，其實(shí)質(zhì)是種群搜索策略和種群個(gè)體間的信息交換，搜索不依賴于梯度信息。該算法是一種全局搜索算法，尤其適用于傳統(tǒng)搜索算法難以解決的復(fù)雜和非線性問題。它的3個(gè)主要操作算子分別為選擇算子、交叉算子和變異算子。遺傳算法包括5個(gè)基本要素。

1）對參數(shù)進(jìn)行編碼。

2）設(shè)定初始種群大小。

3）設(shè)計(jì)適應(yīng)度函數(shù)。

4）設(shè)計(jì)遺傳操作。

5）設(shè)定控制參數(shù)（包括種群大小、最大進(jìn)化代數(shù)、交叉率、變異率等）。

遺傳算法的優(yōu)點(diǎn)是使用簡便、通用性強(qiáng)、實(shí)現(xiàn)簡單，具有并行性和全搜索能力，缺點(diǎn)是易出現(xiàn)早熟和欺騙問題并且在快要接近最優(yōu)解時(shí)會在最優(yōu)解附近左右擺動［13］。

2.2蟻群算法

蟻群算法（ant colony optimization，ACO）是M.Dorigo等［14-15］根據(jù)螞蟻群體在覓食過程中所體現(xiàn)出的智能行為提出的，通過模擬螞蟻在尋找食物所體現(xiàn)出的尋優(yōu)能力來解決現(xiàn)實(shí)中的優(yōu)化問題。螞蟻在尋找食物的過程中，會在沿途留下濃度不同的信息素（pheromone），路徑越長信息素濃度越低，同時(shí)信息素會隨著時(shí)間流逝而揮發(fā)，一條路徑上走過的螞蟻越多，則留下的信息素濃度越高，后來的螞蟻可根據(jù)信息素濃度，以較大幾率選擇信息素較濃的路徑。該過程是一種正反饋，并最終可以找到一條最優(yōu)路徑［16］。

蟻群算法的優(yōu)點(diǎn)是它同時(shí)具有自適應(yīng)、自組織、正向反饋和本質(zhì)并行的特點(diǎn)，但其搜索時(shí)間較長，且容易受到因?qū)?yōu)過程中早期發(fā)現(xiàn)較好解的影響而陷入局部最優(yōu)解，使搜索停滯。2.3混合改進(jìn)型遺傳算法

針對經(jīng)典遺傳算法和蟻群算法各自優(yōu)缺點(diǎn)，本文將在遺傳算法的基礎(chǔ)上，通過適應(yīng)度函數(shù)的修正和蟻群算法早期能發(fā)現(xiàn)較好初始種群等兩方面來提高遺傳算法的求解效率。在適應(yīng)度函數(shù)構(gòu)造上，將問題約束以動態(tài)方式合并到適應(yīng)度函數(shù)中，得到一個(gè)具有變化懲罰項(xiàng)的適應(yīng)度函數(shù)，用來指導(dǎo)遺傳搜索；在初始種群生成方面，從蟻群算法早期產(chǎn)生的種群中選擇初始解，構(gòu)建更有效、更具有多樣性的初始種群。

適應(yīng)度函數(shù)的選擇對能否快速、準(zhǔn)確地找到最優(yōu)解起著關(guān)鍵作用。針對旅行商問題，若目標(biāo)函數(shù)為最小值問題，適應(yīng)度函數(shù)可表示為

式中u（x）為個(gè)體的路徑長度。

當(dāng)初始群體中存在適應(yīng)度超常（適應(yīng)度值特別大或特別?。﹤€(gè)體時(shí)，這些特殊個(gè)體可能會影響整個(gè)群體的發(fā)展方向，造成算法收斂于局部最優(yōu)解，使局部最優(yōu)解取代全局最優(yōu)解。因此，限制超常個(gè)體的繁殖十分必要。此外，當(dāng)?shù)胶笃谒惴ㄖ饾u收斂時(shí)，優(yōu)劣個(gè)體間適應(yīng)度值相差不明顯，導(dǎo)致優(yōu)良個(gè)體難以被繼續(xù)優(yōu)化，只能在最優(yōu)解附近搖擺。基于上述考慮，本文對適應(yīng)度值進(jìn)行修正，即：

式中：f， g分別為修正前后的適應(yīng)度值；

fmax， fmin分別為修正前適應(yīng)度函數(shù)值的上下界（若該值未知，可用當(dāng)前代或目前為止群體中最大/最小值來代替）；

δ為開區(qū)間（0， 1）內(nèi)的一個(gè)正實(shí)數(shù)，可防止分母為零并增加遺傳算法的隨機(jī)性；

Cmax為當(dāng)前代的最長路徑。

圖1是以原始適應(yīng)度f（x）為自變量，新適應(yīng)度函數(shù)值g（x）為因變量的一次函數(shù)關(guān)系圖。圖中，gmax， gmin分別為修正后適應(yīng)度的最大、最小值。

由圖1可知，隨著fmax和fmin差值的增大，修正后的適應(yīng)度函數(shù)的傾斜角變小，修正后的適應(yīng)度值變化范圍也會變小，從而可有效防止特殊個(gè)體影響整個(gè)群體造成局部收斂；若fmax和fmin的差值越小，則

越大，這樣修正后的適應(yīng)度值變化范圍變大。在計(jì)算后期，拉開了群體中個(gè)體之間差距，避免了算法在最優(yōu)解附近發(fā)生擺動。修正后的適應(yīng)度可以依據(jù)群體適應(yīng)度的值擴(kuò)大或者縮小，變更選擇壓力。

圖1　適應(yīng)度值的修正圖Fig.1　Corrected of fitness values

在初始種群生成方面，本文利用蟻群算法得到遺傳算法的初始種群。用m只螞蟻對所有孔進(jìn)行訪問，選用不同的迭代次數(shù)作為停止條件，每只螞蟻在不同迭代次數(shù)下走過的路徑就表示一條基因（a0，a1，…， an），此基因表示此螞蟻從a0出發(fā)經(jīng)歷a1， a2，…，an后再回到a0。為了提高初始種群的多樣性，蟻群算法產(chǎn)生初始種群時(shí)，選用不同迭代次數(shù)下產(chǎn)生的基因。這樣遺傳算法在剛開始進(jìn)行選擇、交叉時(shí)就能以較大概率選擇到路徑最短的個(gè)體，以提高算法的效率和精度。

應(yīng)用混合改進(jìn)型遺傳算法（improved hybrid genetic algorithm，IHGA）求解孔群加工順序的流程圖如圖2所示。混合改進(jìn)型遺傳算法描述如下。

1）確定蟻群算法基本參數(shù)，通過改變最大迭代次數(shù)斜獲取較優(yōu)的螞蟻序列群。

2）根據(jù)獲得的優(yōu)秀種群進(jìn)行遺傳交叉和變異操作獲取符合要求的最優(yōu)解。

圖2　混合改進(jìn)型遺傳算法流程圖Fig.2　Flow chart of the improved hybrid genetic algorithm

3　孔群加工路徑優(yōu)化實(shí)例

在孔群加工中，孔的幾何特征可表示為（x， y， Dh，h， num），其中x， y為孔的中心坐標(biāo)，Dh為待加工孔的直徑，h為孔深，num為孔的編號［17］。采用螺旋銑孔工藝對由30個(gè)孔組成的孔群進(jìn)行加工，孔的參數(shù)如表1所示。位置分布如圖3所示。

表1　30個(gè)孔的參數(shù)值表Table 1　Parameter value table of 30 holes mm

圖3　某零件孔位置分布圖Fig.3　Distribution of the component holes

本文分別利用基本遺傳算法、蟻群算法和混合改進(jìn)型遺傳算法求解孔群的加工路徑長度。計(jì)算平臺為Pentium（R） Dual-Core CPU E5500 @ 2.80 GHz 1.87 GB，操作系統(tǒng)為Windows 7，仿真分析在MATLAB 7.0運(yùn)行，仿真結(jié)果如表2所示。采用基本遺傳算法和混合改進(jìn)型遺傳算法計(jì)算加工路徑時(shí)，種群大小設(shè)定為100，交叉概率為0.8，變異概率為0.1；采用蟻群算法計(jì)算路徑和產(chǎn)生初始種群時(shí)，設(shè)定螞蟻個(gè)數(shù)m=31， 表征信息素重要程度的參數(shù)Alpha=1，表征啟發(fā)式因子重要程度的參數(shù)Beta=5，信息素蒸發(fā)系數(shù)Rho=0.5，信息素增加強(qiáng)度系數(shù)Q=100。

表2　基本遺傳算法、蟻群算法和混合改進(jìn)型遺傳算法仿真結(jié)果對比表Table 2　Comparison table of simulation results of CGA， ACO and IHGA

由表2可知：在參數(shù)設(shè)置相同條件下，基本遺傳算法、蟻群算法和混合改進(jìn)型遺傳算法求解同一孔群加工路徑，得到的最短加工路徑長度分別為：1 902.8，1 695.0， 1 410.6 mm，3種算法對應(yīng)的運(yùn)行時(shí)間分別為：4.1， 7.2， 3.9 s。加工路徑長度方面，混合改進(jìn)型遺傳算法比基本遺傳算法縮短路徑長度26%，比蟻群算法縮短路徑長度17%；程序運(yùn)行時(shí)間方面，混合改進(jìn)型遺傳算法與經(jīng)典遺傳算法得到各自最優(yōu)結(jié)果的運(yùn)行時(shí)間大致相同，蟻群算法獲得最優(yōu)解的運(yùn)行時(shí)間比2種遺傳算法所需的時(shí)間都要長，此例中混合改進(jìn)型遺傳算法獲得最優(yōu)解的時(shí)間比蟻群算法獲得最優(yōu)解的時(shí)間節(jié)省約46%，混合改進(jìn)型遺傳算法在整體上以更短的執(zhí)行時(shí)間以及有限的迭代次數(shù)獲得最短路徑?；旌细倪M(jìn)型遺傳算法放棄了基本遺傳算法中隨機(jī)產(chǎn)生初始種群的方法，利用蟻群算法具有正反饋、自適應(yīng)的特點(diǎn)，從蟻群算法中螞蟻已走過的路徑中選擇生成初始種群，在保證了初始種群高質(zhì)量的同時(shí)也避免了部分初始解超常導(dǎo)致算法局部收斂的情況。此外，混合改進(jìn)型遺傳算法在計(jì)算由交叉、變異后產(chǎn)生的新個(gè)體的適應(yīng)度時(shí)，構(gòu)建具有變化懲罰項(xiàng)的適應(yīng)度函數(shù)來避免算法在運(yùn)算后期時(shí)，求解結(jié)果在最優(yōu)解附近擺動而始終無法逼近最優(yōu)解的情況，提高了算法效率。

4　結(jié)語

1） 考慮遺傳算法中欺騙問題和初始種群的有效性，構(gòu)建了具有變化懲罰項(xiàng)的適應(yīng)度函數(shù)和新的初始種群產(chǎn)生方法。

2） 應(yīng)用混合改進(jìn)型遺傳算法求解孔群加工路徑優(yōu)化模型，獲得優(yōu)化的加工路徑。對比優(yōu)化前后的路徑長度發(fā)現(xiàn)，本文提出的優(yōu)化方法可有效縮短走刀時(shí)間。

3） 混合改進(jìn)型遺傳算法仿真結(jié)果，可為螺旋銑孔工藝加工孔群實(shí)際工程應(yīng)用提供理論指導(dǎo)。

［1］李忠群，鄭敏，王鑫.螺旋銑孔技術(shù)研究進(jìn)展［J］.湖南工業(yè)大學(xué)學(xué)報(bào)，2013，27（1）：38-42.LI Zhongqun，ZHENG Min，WANG Xin.Research Progress of Helical Milling Operation［J］.Journal of Hunan University of Technology，2013，27（1）：38-42.

［2］BRINKSMEIER E，F(xiàn)ANGMANN S，MEYER I.Orbital Drilling Kinematics［J］.Production Engineering，2008，2（3）：277-283.

［3］DENKENA B，BOEHNKE D，DEGE J H.Helical Milling of CFRP Titanium Layer Compounds［J］.Cirp Journal of Manufacturing Science & Technology，2008，1（2）：64-69.

［4］李忠群，夏磊，彭岳榮，等.基于實(shí)驗(yàn)?zāi)B(tài)分析的銑削加工系統(tǒng)動力學(xué)特性參數(shù)測試與分析［J］.湖南工業(yè)大學(xué)學(xué)報(bào)，2015，29（4）：6-9.LI Zhongqun，XIA Lei，PENG Yuerong，et al.Dynamic Characteristics Test and Analysis of Milling System Based on Expermental Modal Analysis［J］.Journal of Hunan University of Technology，2015，29 （4）：6-9.

［5］李忠群，彭岳榮，夏磊，等.基于改進(jìn)歐拉法的銑削穩(wěn)定性半解析法預(yù)測［J］.湖南工業(yè)大學(xué)學(xué)報(bào)，2015，29（6）：6-10.LI Zhongqun，PENG Yuerong，XIA Lei，et al.Semi-Analytical Method for Milling Process Stability Prediction Based on Improved Euler Method［J］.Journal of Hunan University of Technology，2015，29（6）：6-10.

［6］李忠群，董亞峰，夏磊，等.考慮過程阻尼的切削穩(wěn)定性建模與仿真分析［J］.湖南工業(yè)大學(xué)學(xué)報(bào)，2014，28（6）：23-26.LI Zhongqun， DONG Yafeng，XIA Lei，et al.Modeling and Simulation on Cutting Process Stability Considering Process Damping［J］.Journal of Hunan University of Technology，2014，28（6）：23-26.

［7］BULLNHEIMERB，KOTSISG，STRAUC.Parallelization Strategies for the Ant System［J］.High Performance Algorithms and Software in Nonlinear Optimization，1998，24：87-100.

［8］KHAN W A，HAYHURST D R，CANNINGS C.Determination of Optimal Path Under Approach and Exit Constraints［J］.European Journal of Operational Research，1999，117（2）：310-325.

［9］LIN W，DELGADO-FRIAS J G，GAUSE D C，et al.Hybrid Newton-Raphson Genetic Algorithm for the Traveling Salesman Problem［J］.Cybernetics and Systems，1995，26（4）：387-412.

［10］MANIEZZO V，COLORNI A.The Ant System Applied to the Quadratic Assignment Problem［C］//IEEE Transactions on Knowledge and Data Engineering.［S.l.］：IEEE，1999，11（5）：769-778.

［11］Holland J H.Adaptation in Natural and Artificial Systems：An Introductory Analysis With Applications to Biology，Control， and Artificial Intelligence［J］.Control & Artificial Intelligence University of Michigan Press，1975，6（2）：126-137.

［12］COFFMAN E G，GAREY M R，JOHNSON D S.Approximation Algorithms for Bin Packing：A Survey［C］// Approximation algorithms for NP-Hard Problems.［S.l.］：PWS Publishing Co.，1996：46-93.

［13］MAK K L，WONG Y S，WANG X X.An Adaptive Genetic Algorithm for Manufacturing Cell Formation［J］.International Journal of Advanced Manufacturing Technology，2000，16（7）：491-497.

［14］DORIGO M，MANIEZZO V，COLORNI A.Ant System：Optimization by a Colony of Cooperating Agents［J］.IEEE Transactions on Systems， Man， and Cybernetics：Part B（Cybernetics），1996，26（1）：29-41.

［15］DORIGO M，GAMBARDELLA L M.Ant Colony System：A Cooperative Learning Approach to the Traveling Salesman Problem［J］.IEEE Transactions on Evolutionary Computation，1997，1（1）：53-66.

［16］DORIGO M，GAMBARDELLA L M.Ant Colonies for the Travelling Salesman Problem［J］.Bio Systems，1997，43（2）：73-81.

［17］王鑫.基于加工特征的機(jī)床關(guān)鍵零件高效數(shù)控加工切削參數(shù)優(yōu)化技術(shù)研究［D］.株洲：湖南工業(yè)大學(xué)，2014.WANG Xin.Machining Features Based on Cutting Conditions Optimization for High Performance CNC Machining of Key Machine Parts［D］.Zhuzhou：Journal of Hunan University of Technology，2014.

（責(zé)任編輯：鄧彬）

On the Optimized Machining Path for Group Holes Realized by Helical Milling Based on an Improved Hybrid Genetic Algorithm

LI Zhongqun，GUO Wenhui，WANG Zhikang
（School of Mechanical Engineering，Hunan University of Technology，Zhuzhou Hunan 412007）

A great influence will be exerted on the machining efficiency by the optimization degree of machining paths for group holes.An optimized processing path， based on a research of TPS mathematical models， can be achieved by the application of an improved hybrid genetic algorithm to the solution of the optimization of holes machining paths.A comparison between the classical genetic algorithm， the ant colony algorithm and an improved hybrid genetic algorithm shows that the proposed optimized method helps to improve the machining efficiency by greatly shortening the machining time.

genetic algorithm；helical milling；path optimization；ant colony algorithm

TG54 ；TH313

A

1673-9833（2016）04-0027-05

10.3969/j.issn.1673-9833.2016.04.006

2016-05-30

國家科技重大專項(xiàng)基金資助項(xiàng)目（2012ZX04011-011）

李忠群（1966-），男，湖南永州人，湖南工業(yè)大學(xué)教授，博士，主要從事數(shù)字化制造與裝備技術(shù)，虛擬制造方面的研究，E-mail：zhqunli@163.com

郭文慧（1990-），男，山西大同人，湖南工業(yè)大學(xué)碩士生，主要研究方向?yàn)閿?shù)字化制造與裝備技術(shù)，E-mail：guowenhuizongwu@163.com