基于NSGA-Ⅱ和最小二乘原理的加工軌跡擬合算法

瞿佳偉 張春雷 張 冀

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

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

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

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

1 帶精英策略的非支配排序的遺傳算法簡介

對于大多數(shù)多目標(biāo)優(yōu)化問題，其各個目標(biāo)往往是相互矛盾，所以很難找到一個解使得所有的目標(biāo)函數(shù)同時最優(yōu)，也就是說，一個解可能對于某個目標(biāo)函數(shù)最好，但對于其他目標(biāo)函數(shù)并不是最好，甚至最差。因此，對于多目標(biāo)優(yōu)化問題,通常存在一個解集，這些解之間就全體目標(biāo)函數(shù)而言是無法比較優(yōu)劣的，這類問題的特點是:不能在改進(jìn)任何目標(biāo)函數(shù)的同時不削弱至少一個其他目標(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-Ⅱ》中提出，是對1994年提出的NSGA的改進(jìn)，相比于NSGA，NSGA-Ⅱ的改進(jìn)有兩點：(1)提出一種快速非支配排序，使得Pareto支配排序的時間復(fù)雜度由O(N3)優(yōu)化到O(N2)；(2)提出一種擁擠距離來衡量解的分布性，并基于此選擇種群中的合適的個體[5]。

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

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

2 最小二乘擬合原理

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

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

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

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

3 算法設(shè)計

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

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

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

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

3.2 編碼與解碼

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

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

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

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

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

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

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

步驟3：返回擬合信息表。

3.4 從種群中選出父代

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

3.5 交叉變異算子

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

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

圖1 算法流程圖

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

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

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

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

圖3 擬合圖像

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

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

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

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

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

圖5 心形軌跡圖

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

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

5 結(jié)語

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

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