徐傳法 王士軍 王 冉 李建宏 齊娜

（山東理工大學(xué)機(jī)械工程學(xué)院，山東 淄博 255000）

隨著科學(xué)技術(shù)的不斷進(jìn)步，機(jī)械產(chǎn)品的結(jié)構(gòu)越來越合理，復(fù)雜曲面類零件被廣泛的應(yīng)用在動(dòng)力能源、航空航天和工業(yè)等領(lǐng)域，其形狀誤差對(duì)其所構(gòu)成產(chǎn)品的質(zhì)量和性能起著直接的決定性作用，研究高效率、高精度的測(cè)量技術(shù)具有重要的理論意義和實(shí)際應(yīng)用價(jià)值[1]。在對(duì)大型復(fù)雜曲面測(cè)點(diǎn)檢測(cè)時(shí)，曲面需要被檢測(cè)的點(diǎn)是非常多的，為了提高檢測(cè)效率，需要找到一條最優(yōu)的檢測(cè)路徑，既能不重復(fù)的走過所有的點(diǎn)，還要使其走過的路徑最短。

國內(nèi)外學(xué)者對(duì)于路徑優(yōu)化問題方面做了許多的研究。高延峰等將遺傳算法運(yùn)用到求解自由曲面測(cè)量路徑優(yōu)化問題上，把該問題簡(jiǎn)化成旅行商問題，試驗(yàn)證明遺傳算法結(jié)構(gòu)簡(jiǎn)單而且具有很強(qiáng)的優(yōu)化能力[2]；高國軍等提出了貪婪選擇雜交算子，有效地提高了大規(guī)模路徑優(yōu)化的收斂速度和穩(wěn)定性，并且對(duì)遺傳算法過程中的控制參數(shù)進(jìn)行了優(yōu)化，給出了適合不同規(guī)模路徑優(yōu)化問題的控制參數(shù)取值[3]；Tuncer D 等提出了改進(jìn)的變異算子，避免早熟的同時(shí)提高了算法的效率[4]；Srinivas M 等提出了自適應(yīng)算法，個(gè)體的交叉概率能夠隨個(gè)體的適應(yīng)度發(fā)生改變，防止陷入局部最優(yōu)的同時(shí)提高了算法的效率[5]；石紅國等提出一種 Hopfield 神經(jīng)網(wǎng)絡(luò)與歸約方法相結(jié)合求解TSP 路徑優(yōu)化的方法，使Hopfield 神經(jīng)網(wǎng)絡(luò)不再只適用于求解小規(guī)模城市路徑優(yōu)化問題[6]。

文獻(xiàn)[2]中，把遺傳算法運(yùn)用到自由曲面測(cè)量路徑優(yōu)化問題中，但并未對(duì)遺傳算法收斂速度慢、易陷入局部最優(yōu)解等問題做更深入研究，基于以上問題，本文設(shè)計(jì)了改進(jìn)的遺傳算法，實(shí)驗(yàn)結(jié)果表明，改進(jìn)的遺傳算法能夠更高效且優(yōu)質(zhì)地完成自由曲面測(cè)量路徑優(yōu)化問題。

1 自由曲面的測(cè)點(diǎn)檢測(cè)過程

三坐標(biāo)測(cè)量機(jī)測(cè)點(diǎn)檢測(cè)過程中測(cè)頭的具體運(yùn)動(dòng)過程如圖1 所示。首先測(cè)頭快速定位到A點(diǎn)，再以檢測(cè)速度沿路徑AB往B點(diǎn)移動(dòng)，當(dāng)檢測(cè)完B點(diǎn)后，再以回退速度移動(dòng)到C點(diǎn)，然后測(cè)頭再快速定位到D點(diǎn)重復(fù)剛才的運(yùn)動(dòng)過程。無論檢測(cè)路徑如何變化，AB段（a段）與BC段（b段）的運(yùn)動(dòng)過程總是固定不變的，為簡(jiǎn)化求解過程，不考慮測(cè)量過程a與回退過程b這種固定不變的路徑，只計(jì)算c這種影響總路程的路段，此時(shí)的測(cè)點(diǎn)檢測(cè)過程就被簡(jiǎn)化成了類旅行商（TSP）問題。

圖1 局部檢測(cè)路徑示意圖

自由曲面測(cè)點(diǎn)檢測(cè)過程與旅行商問題的主要區(qū)別在于：

（1）當(dāng)測(cè)頭檢測(cè)完最后一個(gè)測(cè)點(diǎn)時(shí)，測(cè)頭不需要回到初始測(cè)點(diǎn)。

（2）旅行商問題中用到的城市坐標(biāo)是二維坐標(biāo)，而自由曲面測(cè)點(diǎn)的坐標(biāo)是三維的。

2 遺傳算法簡(jiǎn)介

遺傳算法（genetic algorithm，GA）最早是由美國的 John Holland 于20 世紀(jì)70 年代提出，該算法效仿大自然“物競(jìng)天擇，適者生存”的演化規(guī)律來求解各類問題。遺傳算法把問題參數(shù)編碼為基因，把問題的解編碼為染色體，然后對(duì)各個(gè)染色體進(jìn)行選擇、交叉和變異等操作，通過迭代來不斷優(yōu)化各個(gè)染色體中的信息，以優(yōu)勝劣汰的方式最終生成一條較優(yōu)的染色體作為問題的解。

3 改進(jìn)遺傳算法的設(shè)計(jì)

3.1 編碼方式

采用自然編碼方式，每個(gè)自然數(shù)表示1 個(gè)要檢測(cè)的測(cè)點(diǎn)，例如一個(gè)染色體的基因串為26 379，則表示測(cè)頭從2 號(hào)測(cè)點(diǎn)出發(fā)，順序經(jīng)過6、3、7、9號(hào)測(cè)點(diǎn)完成該條路徑的檢測(cè)。

3.2 適應(yīng)度函數(shù)

遺傳算法在尋求最優(yōu)解的過程中僅依據(jù)適應(yīng)度函數(shù)來選擇優(yōu)質(zhì)解和淘汰劣質(zhì)解，算法的求解質(zhì)量和求解效率與適應(yīng)度函數(shù)的選取密不可分。由于影響總路程變化的只有像c這樣的路徑段，所以求得的目標(biāo)函數(shù)為，目標(biāo)函數(shù)越小，優(yōu)化的結(jié)果越好，輪盤賭選擇算子個(gè)體適應(yīng)度值越大，被選擇的概率越高，所以對(duì)目標(biāo)函數(shù)做了一次倒數(shù)轉(zhuǎn)換，轉(zhuǎn)換后用作適應(yīng)度函數(shù)

3.3 選擇算子

采用輪盤賭選擇算子，輪盤賭算法的基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度函數(shù)值大小成正比，它是為了防止適應(yīng)度數(shù)值較小的個(gè)體被直接淘汰而提出的。它的實(shí)施步驟為：

（1）計(jì)算種群中各個(gè)個(gè)體的適應(yīng)度。

（2）通過式（2）與式（3）分別計(jì)算各個(gè)個(gè)體的被選擇概率和累計(jì)概率。

（3）在區(qū)間[0,1]隨機(jī)選取1 個(gè)數(shù)x，x落在哪個(gè)個(gè)體的累計(jì)概率區(qū)間內(nèi)，則該個(gè)體被選中。

3.4 自適應(yīng)參數(shù)調(diào)節(jié)

交叉概率和變異概率對(duì)遺傳算法的性能有著重要的影響，選擇合適的交叉概率和變異概率，有利于提高種群的尋優(yōu)效率和防止局部最優(yōu)解的出現(xiàn)。在傳統(tǒng)的遺傳算法中，交叉概率和變異概率在算法迭代過程中是固定不變的，這樣不利于遺傳算法更好地發(fā)揮其性能。許多學(xué)者對(duì)參數(shù)的自適應(yīng)調(diào)節(jié)做了研究[7-9]，在此基礎(chǔ)上，本文對(duì)交叉概率和變異概率的自適應(yīng)參數(shù)調(diào)節(jié)做了如下設(shè)置。

3.4.1 自適應(yīng)交叉概率調(diào)節(jié)機(jī)制

在種群進(jìn)化初期，種群個(gè)體的適應(yīng)度比較分散，為增加新個(gè)體的產(chǎn)生速度，加快種群整體搜索效率，應(yīng)該增大Pc的值；在種群進(jìn)化后期，種群個(gè)體適應(yīng)度比較集中，為使優(yōu)良個(gè)體不被破壞，應(yīng)該減小Pc的值；另外交叉算子有可能會(huì)破壞種群中的優(yōu)良基因，為使交叉算子能夠更好地工作，對(duì)適應(yīng)度差的個(gè)體，給與較高的Pc值，使其能夠更好地進(jìn)化；對(duì)適應(yīng)度高的個(gè)體，應(yīng)該減小Pc的值，使優(yōu)良的基因得以延續(xù)；文獻(xiàn)[9]以迭代次數(shù)作為進(jìn)化處于何種階段的評(píng)判依據(jù)，對(duì)終止代數(shù)的選取是十分苛刻的，代數(shù)設(shè)置的太大會(huì)對(duì)自適應(yīng)參數(shù)調(diào)節(jié)產(chǎn)生很大的影響。如圖2 所示。

圖2 優(yōu)化過程

對(duì)50 個(gè)城市尋求最優(yōu)路徑，在遺傳算法其他部分相同的情況下，算法a 未使用自適應(yīng)調(diào)節(jié)機(jī)制，算法b 使用文獻(xiàn)[9]的自適應(yīng)調(diào)節(jié)機(jī)制，從圖2a 與b 的比較可知，在終止代數(shù)為2 000 的情況下，優(yōu)化過程已無明顯差異，自適應(yīng)參數(shù)調(diào)節(jié)機(jī)制幾乎失去作用?；谝陨峡紤]，本文在文獻(xiàn)[9]的基礎(chǔ)上做了以下改進(jìn)。

式中：Pci為種群中個(gè)體i發(fā)生交叉運(yùn)算的概率；Pcmax與當(dāng)前種群的適應(yīng)度有關(guān)；fmax和fmin分別為當(dāng)前種群最優(yōu)個(gè)體的適應(yīng)度和最差個(gè)體的適應(yīng)度；fi為個(gè)體i的適應(yīng)度值；為當(dāng)前種群的平均適應(yīng)度值。從式（5）可以看出Pcmax與當(dāng)前種群個(gè)體的適應(yīng)度分布情況有關(guān)。

改進(jìn)后的自適應(yīng)調(diào)節(jié)機(jī)制在遺傳算法其他部分與前面相同的情況下，對(duì)50 個(gè)城市尋求最優(yōu)路徑，如圖3 所示。

圖3 使用改進(jìn)的自適應(yīng)參數(shù)調(diào)節(jié)機(jī)制

改進(jìn)的自適應(yīng)調(diào)節(jié)機(jī)制在終止代數(shù)為2 000 的情況下，依然能穩(wěn)定地發(fā)揮其性能，不會(huì)因終止代數(shù)設(shè)置過大而導(dǎo)致自適應(yīng)調(diào)節(jié)機(jī)制失效。

3.4.2 自適應(yīng)變異概率調(diào)節(jié)機(jī)制

選取合適的變異概率，有利于保持種群多樣性和防止種群陷入局部最優(yōu)。當(dāng)種群中個(gè)體的適應(yīng)度值沒有太大差距時(shí)，種群多樣性降低，易陷入局部最優(yōu)，此時(shí)應(yīng)該增大變異概率，通過變異增加種群多樣性，跳出局部最優(yōu)。另外在種群進(jìn)化過程中，為延續(xù)較優(yōu)個(gè)體，應(yīng)給與較優(yōu)個(gè)體小的變異概率?；谝陨峡紤]，本文在文獻(xiàn)[9]的基礎(chǔ)上做了以下改進(jìn)。

式中：Pmi為種群中個(gè)體i發(fā)生變異運(yùn)算的概率；Pmmin與當(dāng)前種群的適應(yīng)度有關(guān)。

3.5 貪婪交叉算子

貪婪交叉算子能夠充分利用染色體的局部信息指導(dǎo)遺傳進(jìn)化搜索。該算子在兩條父代染色體的兩個(gè)基因中使用局部貪婪策略得到一條新的染色體，這樣的子代染色體缺乏多樣性，容易陷入局部最優(yōu)解。為防止局部收斂，另一條染色體由整體貪婪策略得到，增加群體多樣性。

假如參與交叉運(yùn)算的父代個(gè)體為L(zhǎng)1和L2，生成的子代個(gè)體為l1和l2，隨機(jī)產(chǎn)生的初始測(cè)點(diǎn)為Gstart。l1以Gstart為第一個(gè)監(jiān)測(cè)點(diǎn)，分別計(jì)算父代中Gstart與與其右相鄰的兩個(gè)測(cè)點(diǎn)Gnext1與Gnext2之間的距離，若Gstart與Gnext1之間的距離小，則下一個(gè)測(cè)點(diǎn)選Gnext1，反之則選Gnext2，以此類推選出l1染色體上剩余的所有測(cè)點(diǎn)。l2的選取遵循整體貪婪策略的規(guī)則，以Gstart為第一個(gè)測(cè)點(diǎn)，計(jì)算Gstart與剩余所有測(cè)點(diǎn)之間的距離，選取與之距離最短的測(cè)點(diǎn)作為下一個(gè)測(cè)點(diǎn)，以此類推選出l2染色體上剩余的所有測(cè)點(diǎn)。

下面用7 個(gè)檢測(cè)點(diǎn)為例，說明貪婪交叉算子的運(yùn)行過程。7 個(gè)測(cè)點(diǎn)的坐標(biāo)分別為：1：（10，12，20），2：（41，26，23），3：（25，58，63），4：（81，55，42），5：（72，31，66），6：（55，43，82），7：（61，28，53），7 個(gè)測(cè)點(diǎn)之間的距離如表1 所示。

表1 7 個(gè)測(cè)點(diǎn)之間的距離

假設(shè)參加交叉運(yùn)算的染色體L1和L2分別為（2 3 5 4 6 1 7）和（7 2 1 6 3 4 5），隨機(jī)產(chǎn)生初始測(cè)點(diǎn)為3，右轉(zhuǎn)動(dòng)使3 成為初始測(cè)點(diǎn)。新生成L1'和L2'分別為（3 5 4 6 1 7 2）和（3 4 5 7 2 1 6），則l1的第一個(gè)基因?yàn)?，分別計(jì)算父代染色體中與測(cè)點(diǎn)3右相鄰的兩個(gè)測(cè)點(diǎn)的距離，得d35=54.29＜d34=59.89，則L1''和L2''分別為（3 5 4 6 1 7 2）和（3 5 4 7 2 1 6），l1的第二個(gè)基因?yàn)?，以此類推，得到的l1為（3 5 4 7 6 2 1）；l2由整體貪婪策略得到，計(jì)算測(cè)點(diǎn)3 與剩余所有測(cè)點(diǎn)之間的距離，d36＜d37＜d32＜d35＜d34＜d31，則l2的第二個(gè)基因?yàn)?，以此類推得到l2為（3 6 5 7 4 2 1）。

3.6 貪婪倒位變異算子

貪婪倒位變異算子是基于貪婪策略的倒位變異，首先在一條染色體上隨機(jī)選取一個(gè)基因Gx，計(jì)算該基因與左右相鄰兩基因Gxleft和Gxright之間的距離d1、d2，若d1＞d2,則選Gxleft為待變異基因，反之則選Gxright為待變異基因，再從除Gx、Gxleft和Gxright以外剩余的基因中，選取距離Gx最近的基因Gclose作為另一個(gè)待變異基因，在不改變其他基因位置的情況下，交換兩待變異基因位置，完成貪婪倒位變異運(yùn)算。

以L1（2 3 5 4 6 1 7）為例，隨機(jī)選取的測(cè)點(diǎn)為3。先計(jì)算測(cè)點(diǎn)3 與左右相鄰兩測(cè)點(diǎn)之間的距離d32、d35，d35＞d32則第一個(gè)待變異測(cè)點(diǎn)為5，再從除3、2 和5以外的剩余測(cè)點(diǎn)中選取距離3 最近的基因作為另一個(gè)待變異基因，經(jīng)計(jì)算得該基因?yàn)?，交換兩待變異基因的位置，得到變異后的染色體l1為(2 3 6 4 5 1 7)。

3.7 精英保存策略

為防止選擇過程中最優(yōu)解的丟失和交叉變異過程中最優(yōu)解的破壞，實(shí)施精英保存策略。通過選擇、交叉和變異后，復(fù)制子代中的最優(yōu)個(gè)體并保存到下一輪的子代中，剩余子代繼續(xù)下一輪的選擇、交叉和變異，用復(fù)制的最優(yōu)個(gè)體替代下一輪子代的最差個(gè)體。繼續(xù)實(shí)施精英保存策略，直至迭代結(jié)束。

4 改進(jìn)遺傳算法結(jié)構(gòu)

改進(jìn)遺傳算法的流程圖如圖4 所示，基本流程如下：

圖4 改進(jìn)遺傳算法流程圖

（1）生成初始種群。

（2）計(jì)算種群各個(gè)個(gè)體的適應(yīng)度值。

（3）通過精英保存策略，復(fù)制適應(yīng)度值最大的個(gè)體直接進(jìn)入子代，其余個(gè)體繼續(xù)進(jìn)行選擇、交叉和變異操作。

（4）判斷是否達(dá)到最大迭代次數(shù)，若是，輸出最優(yōu)解，若否，則返回過程2，計(jì)算種群中各個(gè)個(gè)體的適應(yīng)度值，用上一輪過程3 復(fù)制的最優(yōu)個(gè)體替換這一輪父代中的最差個(gè)體，繼續(xù)下面的迭代過程。

5 實(shí)驗(yàn)研究

5.1 仿真實(shí)驗(yàn)

設(shè)計(jì)一個(gè)參數(shù)曲面作為本次仿真實(shí)驗(yàn)的自由曲面，如圖5 所示。在該曲面上隨機(jī)生成100 個(gè)點(diǎn)作為路徑測(cè)點(diǎn)，用Matlab2018a 編寫算法程序，初始種群數(shù)為250，自適應(yīng)交叉概率為Pci，自適應(yīng)變異概率為Pmi，代溝GGAP=0.9，最大迭代次數(shù)傳統(tǒng)遺傳算法和改進(jìn)遺傳算法分別是1 200 和500 代。分別用傳統(tǒng)遺傳算法和改進(jìn)遺傳算法對(duì)這100 個(gè)測(cè)點(diǎn)求解最優(yōu)路徑，優(yōu)化軌跡和優(yōu)化過程如圖6 所示，優(yōu)化的路徑長(zhǎng)度和時(shí)間如表2 所示。

圖5 參數(shù)曲面

圖6 優(yōu)化軌跡與優(yōu)化過程

從圖6a 與b，c 與d 的比較中可以看出，相比于改進(jìn)的遺傳算法，傳統(tǒng)的遺傳算法生成的最優(yōu)路徑拐角比較多，且優(yōu)化代數(shù)比改進(jìn)的遺傳算法高很多，通過表2 可以得出，傳統(tǒng)的遺傳算法出現(xiàn)了過早收斂現(xiàn)象，而且工作效率遠(yuǎn)不及改進(jìn)的遺傳算法，在路徑長(zhǎng)度方面改進(jìn)的遺傳算法比傳統(tǒng)的遺傳算法路徑長(zhǎng)度縮短6.8%，在程序耗時(shí)方面改進(jìn)的遺傳算法比傳統(tǒng)的遺傳算法時(shí)間縮短了75%。

5.2 實(shí)際檢測(cè)實(shí)驗(yàn)

參數(shù)曲面檢測(cè)實(shí)驗(yàn)在意大利COORD3 三坐標(biāo)測(cè)量機(jī)下進(jìn)行，選擇測(cè)球直徑為3 mm，定位和回退距離為5 mm，觸測(cè)和回退速度為0.55 mm/s，移動(dòng)速度為10 mm/s，分別對(duì)用傳統(tǒng)遺傳算法和改進(jìn)遺傳算法優(yōu)化后的100 個(gè)測(cè)點(diǎn)路徑進(jìn)行檢測(cè)，檢測(cè)過程如圖7 所示，并對(duì)整個(gè)檢測(cè)過程計(jì)時(shí)，實(shí)驗(yàn)結(jié)果如表2 所示。

表2 實(shí)驗(yàn)數(shù)據(jù)

圖7 曲面零件的三坐標(biāo)檢測(cè)

從表2 可以得出，用改進(jìn)遺傳算法求得的最優(yōu)路徑檢測(cè)時(shí)間比傳統(tǒng)遺傳算法的減少了12 s，測(cè)量效率提高了2.45%，這可以很好地提高大批量零件檢測(cè)的效率，對(duì)大批量零件檢測(cè)具有重要的意義。

6 結(jié)語

在自由曲面測(cè)點(diǎn)測(cè)量路徑優(yōu)化方面，改進(jìn)的遺傳算法無論是在尋求最優(yōu)路徑的長(zhǎng)度方面還是程序的耗時(shí)方面都比傳統(tǒng)遺傳算法好很多，改進(jìn)的遺傳算法不僅找到了更優(yōu)的測(cè)點(diǎn)測(cè)量路徑，而且大大提高了求解效率，實(shí)驗(yàn)結(jié)果表明改進(jìn)的遺傳算法能夠更高效且優(yōu)質(zhì)的完成自由曲面測(cè)量路徑優(yōu)化。