瞿佳偉 張春雷 張 冀

（四川大學(xué) 制造科學(xué)與工程學(xué)院 成都 610065）

在現(xiàn)代機(jī)械加工零件的過(guò)程中，經(jīng)常需要加工復(fù)雜非圓曲線。對(duì)于非圓曲線輪廓的加工，CAD/CAM系統(tǒng)常用連續(xù)微小直線段來(lái)逼近輪廓曲線，但是直線逼近的結(jié)果往往導(dǎo)致加工效果、形狀精度不高，而且加工后表面粗糙度值大，特別是微線段不夠短時(shí)線段間的轉(zhuǎn)折更加明顯；而當(dāng)形狀精度要求較高或加工圖形過(guò)于復(fù)雜時(shí)，擬合線段數(shù)目將大大增加，導(dǎo)致加工時(shí)電機(jī)加減速頻繁，大大降低了生產(chǎn)效率[1-2]。

由于圓弧能夠較好地體現(xiàn)曲線曲率的變化且具有較低的計(jì)算復(fù)雜度,且目前大多數(shù)數(shù)控系統(tǒng)都具有圓弧插補(bǔ)指令，因此非常適合作為擬合的基本單元[3]。目前大多數(shù)基于最小二乘擬合算法，是將擬合點(diǎn)看做有序序列，逐次移位擬合，若擬合結(jié)果符合要求，則將擬合區(qū)間往后移一位重新擬合；否則將上次擬合結(jié)果保留，并以上次擬合終點(diǎn)作為新的擬合起點(diǎn)進(jìn)行新一次的擬合，直至將所有軌跡點(diǎn)擬合完畢[4]。這種傳統(tǒng)算法雖然簡(jiǎn)單快捷地實(shí)現(xiàn)了分段擬合，并得到了一種較優(yōu)的擬合方案，但這種算法沒(méi)有從整體考慮，因而得到的只是一種局部最優(yōu)方案。

本文利用最小二乘法對(duì)用微線段逼近的加工輪廓進(jìn)行圓弧擬合，并以擬合段數(shù)和擬合誤差為目標(biāo)，設(shè)計(jì)了一種基于NSGA-II的多目標(biāo)遺傳算法，找出擬合分界點(diǎn)，完成對(duì)加工軌跡的擬合。較傳統(tǒng)的最小二乘擬合方法而言，設(shè)計(jì)的算法，在滿足精度的前提下，可使擬合圓弧段數(shù)更少，并能夠減小擬合誤差、簡(jiǎn)化數(shù)值計(jì)算。

1 帶精英策略的非支配排序的遺傳算法簡(jiǎn)介

對(duì)于大多數(shù)多目標(biāo)優(yōu)化問(wèn)題，其各個(gè)目標(biāo)往往是相互矛盾，所以很難找到一個(gè)解使得所有的目標(biāo)函數(shù)同時(shí)最優(yōu)，也就是說(shuō)，一個(gè)解可能對(duì)于某個(gè)目標(biāo)函數(shù)最好，但對(duì)于其他目標(biāo)函數(shù)并不是最好，甚至最差。因此，對(duì)于多目標(biāo)優(yōu)化問(wèn)題,通常存在一個(gè)解集，這些解之間就全體目標(biāo)函數(shù)而言是無(wú)法比較優(yōu)劣的，這類問(wèn)題的特點(diǎn)是:不能在改進(jìn)任何目標(biāo)函數(shù)的同時(shí)不削弱至少一個(gè)其他目標(biāo)函數(shù)。這種解稱作非支配解(nondominated soluitons)或Pareto最優(yōu)解(Pareto optimal Soluitons)。

NSGA-Ⅱ是一種經(jīng)典的多目標(biāo)進(jìn)化算法，由Kalyanmoy Deb等人于2002年在文章《A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-Ⅱ》中提出，是對(duì)1994年提出的NSGA的改進(jìn)，相比于NSGA，NSGA-Ⅱ的改進(jìn)有兩點(diǎn)：(1)提出一種快速非支配排序，使得Pareto支配排序的時(shí)間復(fù)雜度由O(N3)優(yōu)化到O(N2)；(2)提出一種擁擠距離來(lái)衡量解的分布性，并基于此選擇種群中的合適的個(gè)體[5]。

NSGA-Ⅱ算法的基本思想：首先，隨機(jī)產(chǎn)生規(guī)模為N的初始種群，非支配排序后通過(guò)遺傳算法的選擇、交叉、變異三個(gè)基本操作得到第一代子代種群；其次，從第二代開(kāi)始，將父代種群與子代種群合并，進(jìn)行快速非支配排序，同時(shí)對(duì)每個(gè)非支配層中的個(gè)體進(jìn)行擁擠度計(jì)算，根據(jù)非支配關(guān)系以及個(gè)體的擁擠度選取合適的個(gè)體組成新的父代種群；最后，通過(guò)遺傳算法的基本操作產(chǎn)生新的子代種群，依此類推，直到滿足程序結(jié)束的條件。

NSGA-Ⅱ的提出，為多目標(biāo)進(jìn)化算法的一大進(jìn)步，特別是其基于Pareto支配關(guān)系的框架被后來(lái)許多算法采用，如NSGA-Ⅲ，VaEA等。同時(shí)，NSGA-Ⅱ?qū)τ诘途S多目標(biāo)優(yōu)化問(wèn)題效果是比較好的，但是對(duì)于高維多目標(biāo)優(yōu)化問(wèn)題，其首先面對(duì)的是基于Pareto支配關(guān)系所導(dǎo)致的選擇壓力過(guò)小的問(wèn)題；其次，是擁擠距離在高維空間不適用，計(jì)算復(fù)雜度也比較高。

2 最小二乘擬合原理

最小二乘法的基本思想：給定一組有序數(shù)據(jù)，以誤差平方和最小的原則，找出這些數(shù)據(jù)的最佳匹配函數(shù)。但僅使用最小二乘法進(jìn)行分段擬合時(shí)，顯然不同段端點(diǎn)不一定會(huì)重合，由此引入端點(diǎn)約束條件改進(jìn)最小二乘法。即固定起點(diǎn)和終點(diǎn)坐標(biāo)對(duì)n個(gè)點(diǎn)進(jìn)行圓弧擬合，設(shè)軌跡點(diǎn)坐標(biāo)為(xi,yi)(i=1,2,3,…,n)，起點(diǎn)坐標(biāo)為(x1,y1)，終點(diǎn)坐標(biāo)為(xn,yn)，圓心坐標(biāo)為(x0,y0)。擬合圓經(jīng)過(guò)起點(diǎn)和終點(diǎn)，則圓心一定在起點(diǎn)和終點(diǎn)連線的中垂線上，可設(shè)該直線方程為y=k?x+b則有：

擬合圓應(yīng)滿足以下條件：

由此即可求出擬合圓心坐標(biāo)。

由于軌跡中可能也存在直線部分，這時(shí)計(jì)算機(jī)在進(jìn)行圓弧擬合計(jì)算時(shí)，求出的圓心坐標(biāo)將為非數(shù)（NAN），為方便處理，可以將這種結(jié)果的擬合圓弧用直線段代替。

3 算法設(shè)計(jì)

本文試圖基于 NSGA-Ⅱ算法找出不同擬合段的分界點(diǎn)并利用最小二乘原理實(shí)現(xiàn)對(duì)不同擬合段的圓弧擬合。具體算法設(shè)計(jì)如下：

3.1 目標(biāo)函數(shù)

本文以擬合段數(shù)最少和擬合誤差最小作為目標(biāo)函數(shù)，試圖找出加工軌跡的最佳擬合方案，目標(biāo)函數(shù)數(shù)學(xué)模型如下：

其中f1為擬合基元段數(shù)，N為原軌跡點(diǎn)數(shù)，f2為擬合誤差，mi為第i段的擬合點(diǎn)數(shù)。 fi(x,y)為第i段擬合軌跡方程，P xij,yij為第i段第j個(gè)擬合點(diǎn)坐標(biāo)。

3.2 編碼與解碼

擬合的過(guò)程是將原始點(diǎn)列形成的軌跡用線段或圓弧組合的形式來(lái)表達(dá)，因此關(guān)鍵是找出每段（線段或圓弧）之間的分界點(diǎn)，這里采用二進(jìn)制編碼方法進(jìn)行編碼，即將原始點(diǎn)分為連續(xù)點(diǎn)和分界點(diǎn)，連續(xù)點(diǎn)用0表示，分界點(diǎn)用1表示。

對(duì)于個(gè)體進(jìn)行評(píng)價(jià)時(shí)需要計(jì)算其適應(yīng)度，解碼時(shí)將兩個(gè)分界點(diǎn)所有點(diǎn)看成一段，分別進(jìn)行最小二乘擬合，并根據(jù)擬合結(jié)果分別計(jì)算每個(gè)點(diǎn)的擬合誤差。

3.3 初始解的產(chǎn)生

遺傳算法中，初始解的優(yōu)劣影響著算法的收斂速度。在軌跡擬合的誤差要求限制下，全體解空間中有許多無(wú)用解，因此，如何快速地產(chǎn)生一些可行的初始解便成了提升算法性能的關(guān)鍵。

產(chǎn)生的初始解包括編碼和隨機(jī)擬合兩部分，隨機(jī)擬合在計(jì)算機(jī)程序上使用遞歸方式進(jìn)行實(shí)現(xiàn)。

步驟1：以原始的第一點(diǎn)和最后一點(diǎn)為分界點(diǎn)，兩個(gè)分界點(diǎn)之間的所有點(diǎn)進(jìn)行擬合，計(jì)算擬合誤差；擬合誤差不符合要求，轉(zhuǎn)到步驟2，否則轉(zhuǎn)到步驟3。

步驟 2：在原始軌跡中隨機(jī)選擇一個(gè)點(diǎn)為分界點(diǎn)，將原始軌跡分成兩段新的需要擬合的軌跡；對(duì)兩段新的軌跡分別遞歸調(diào)用函數(shù)本身，即轉(zhuǎn)到step1，將兩個(gè)函數(shù)返回的信息表組合成一個(gè)新的信息表并作為函數(shù)返回值。

步驟3：返回?cái)M合信息表。

3.4 從種群中選出父代

計(jì)算種群中個(gè)體在不同目標(biāo)函數(shù)下的適應(yīng)度，對(duì)種群進(jìn)行非支配排序，分成不同的帕累托前沿（Pareto front），計(jì)算不同前沿中同一前沿不同個(gè)體的擁擠距離，從種群中選出非支配等級(jí)高，擁擠距離大的一定數(shù)量個(gè)體參加錦標(biāo)賽，從而通過(guò)錦標(biāo)賽選出父代。

3.5 交叉變異算子

交叉算子，這里選擇兩點(diǎn)交叉。計(jì)算每個(gè)基因位上的擬合誤差與0到1之間隨機(jī)數(shù)的積，選出其中值最大的基因位作為交叉點(diǎn)，據(jù)此隨機(jī)從父代中選出兩個(gè)不同的染色體，并從兩個(gè)染色體中分別選出兩個(gè)交叉點(diǎn)，得到新的子代染色體。

變異算子，這里同等概率隨機(jī)選擇變異點(diǎn)，并將變異點(diǎn)的原有基因取反得到新的子代染色體。算法流程圖，如圖1所示。

圖1 算法流程圖

4 算法仿真及算法改進(jìn)

本文算法已在Matlab平臺(tái)上實(shí)現(xiàn)，圖2為用來(lái)驗(yàn)證本文算法的測(cè)試圖像數(shù)據(jù)點(diǎn)，是CAM軟件對(duì)蜘蛛圖像生成的 G代碼中的軌跡點(diǎn)，總共有 1121個(gè)點(diǎn)。這里設(shè)置種群大小為50，迭代終止條件為連續(xù) 10代擬合段數(shù)最少個(gè)體的擬合段數(shù)或者迭代次數(shù)達(dá)到1000次。

圖2 原始數(shù)據(jù)點(diǎn)

圖3為最后一代pareto前沿中擬合段數(shù)最少的軌跡擬合圖像，圖4為擬合過(guò)程中第一代和最后一代的pareto前沿。圖3由114條圓弧和6條線段（可視為半徑為無(wú)窮大的圓?。┙M成，擬合總誤差為0.02134mm，原軌跡每個(gè)點(diǎn)到擬合曲線的誤差均小于 0.01mm，擬合效果比較令人滿意，但是對(duì)于本例，算法平均計(jì)算時(shí)間達(dá)到了幾十分鐘，這顯然無(wú)法滿足實(shí)際生產(chǎn)工作對(duì)效率的要求。因此需要對(duì)算法進(jìn)行改進(jìn)。

圖3 擬合圖像

圖4 第一代及最后一代pareto前沿圖

通過(guò)對(duì)本處案例的跟蹤運(yùn)行發(fā)現(xiàn)，算法花費(fèi)時(shí)間最多的地方為交叉變異函數(shù)，因?yàn)槿旧w長(zhǎng)度較長(zhǎng)，經(jīng)過(guò)交叉變異操作得到的個(gè)體有較大可能為非可行解，因此需要多次重復(fù)操作得到可行解，浪費(fèi)了大量時(shí)間。經(jīng)過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，染色體越短，交叉變異得到可行解的概率越高，因此可以從這個(gè)角度考慮改進(jìn)原算法。

改進(jìn)后的算法考慮到實(shí)際情況中的加工軌跡可能有多個(gè)尖點(diǎn)，通過(guò)提前找出尖點(diǎn)，將一條加工軌跡分成幾部分，對(duì)于每部分看成獨(dú)立的軌跡分別調(diào)用擬合算法，可以有效地降低整條軌跡的擬合計(jì)算時(shí)間。使用改進(jìn)算法對(duì)圖2進(jìn)行擬合，設(shè)置同樣的種群大小及迭代終止條件。擬合時(shí)間對(duì)比原算法的數(shù)小時(shí)縮短到了50 s左右。擬合性能也有一定的提升。

NSGA2的最差時(shí)間復(fù)雜度為O(mn2)，其中，m為目標(biāo)函數(shù)個(gè)數(shù)，n為種群大小。在本文中，假設(shè)一條軌跡由n個(gè)點(diǎn)組成，其中包含 1個(gè)尖點(diǎn)，改進(jìn)算法將軌跡以尖點(diǎn)為分界線，分成兩段小軌跡，點(diǎn)數(shù)分別為n1和n2，分別調(diào)用原擬合算法，因此改進(jìn)算法的最差時(shí)間復(fù)雜度為 O 2n12+2n22小于原算法的最差時(shí)間復(fù)雜度O(2n2)，這也從理論上證明了改進(jìn)策略的有效性。

為了具體比較說(shuō)明本文算法及改進(jìn)算法性能，下面通過(guò)使用不同算法對(duì)圖5中的心型圖形進(jìn)行擬合，每種算法均運(yùn)行100次，記錄其平均性能如表1所示。

圖5 心形軌跡圖

表1 針對(duì)心形案例算法性能參數(shù)表

從表中可知，本文算法作為啟發(fā)式進(jìn)化算法，所求解趨近于全局最優(yōu)解，因此所求解比傳統(tǒng)算法往往更優(yōu)，雖然計(jì)算效率有所下降，但在對(duì)加工軌跡精度要求更高的場(chǎng)合還是有其優(yōu)勢(shì)的。

5 結(jié)語(yǔ)

本文設(shè)計(jì)了基于 NSGA-Ⅱ的以圓弧為最小二乘基元的軌跡擬合算法，以較少圓弧與較小逼近誤差為優(yōu)化目標(biāo)。實(shí)現(xiàn)算法時(shí)，為提高算法自適應(yīng)性，設(shè)計(jì)了初始解生成算法，改進(jìn)了交叉操作，自適應(yīng)產(chǎn)生交叉概率，為了提高對(duì)復(fù)雜圖形的擬合效率改進(jìn)了擬合算法。

通過(guò)對(duì)CAM軟件生成的微小線段表達(dá)的加工軌跡的擬合,可以有效減少加工時(shí)傳輸?shù)臄?shù)據(jù)，提高后續(xù)對(duì)加工軌跡的速度規(guī)劃效率，從而提高加工速度。本文算法較傳統(tǒng)算法，給出一系列Pareto最優(yōu)解以供選擇，同等擬合段數(shù)下的擬合軌跡更為逼近原始軌跡，但如何進(jìn)一步完善，提高其收斂速度，減少計(jì)算量，還有待后續(xù)研究。