宣東軍 曲家辰

（1.大連紫曦科技工程有限公司 遼寧省大連市 116033 2.大連交通大學(xué)機車車輛工程學(xué)院 遼寧省大連市 116028）

近年來，航空制造業(yè)發(fā)展迅速，作為鉆鉚技術(shù)的應(yīng)用對象，飛機壁板加工的孔位數(shù)量越來越多并且分布較散亂，為了縮短加工時間，需要對鉆鉚的順序進行規(guī)劃。馬躍晏等[1]針對機器人制孔路徑規(guī)劃問題，提出動態(tài)改變信息揮發(fā)因子的方式，改善蟻群算法的無目的性缺陷。蕭蘊詩等[2]提出了一種小窗口蟻群算法，使得迭代的初始值較為優(yōu)秀，有效縮短了計算時間。顏雪松等[3]針對粒子群優(yōu)化算法容易陷入局部最優(yōu)的缺點，通過加入精英選擇來提高收斂速度的方式以獲得更精準(zhǔn)的路徑。本文針對蟻群算法在搜索時容易陷入局部最優(yōu)和螞蟻搜索容易偏離路徑終點的情況，提出2-opt 策略以跳出局部最優(yōu)，加入方向因子為螞蟻搜索提供方向，提高算法的性能。

1 研究基礎(chǔ)

典型的路徑規(guī)劃是在有妨礙機器人正常工作時，機器人需要尋找到一條從初始位置到終點位置的最優(yōu)路徑，評價路徑最優(yōu)的標(biāo)準(zhǔn)就是路徑是否最短。針對不合理問題，提出數(shù)學(xué)模型。

在眾多滿足條件的路徑中選擇一條最優(yōu)路徑，從本質(zhì)上講就是帶約束的組合優(yōu)化問題，即旅行商問題（Traveling Salesman Problem,TSP)，也是機器人研究中的一個重點方向，本文當(dāng)中的末端執(zhí)行器就是商人，制孔點位就是城市坐標(biāo)，模型保證所有制孔點位均被訪問，并且只被訪問一次。

首先給定一個賦權(quán)圖G(V,E,r)，其中V={1,2,…,n}為起始點位的集合，E 為路徑的集合，權(quán)值定義為路徑的長度。

假設(shè)：

經(jīng)典TSP 的數(shù)學(xué)模型為：

約束條件：

根據(jù)公式（2）和公式（4）規(guī)定所有點位只會被經(jīng)過一次，（3）為TSP 的目標(biāo)函數(shù)。約束條件當(dāng)中的S 為V 的子集V={V1,V2,…,VS}且s＜v。公式（4）第一個約束則保證了沒有任何子回路解的產(chǎn)生。第二個約束是對每個孔位而言，僅有一條路徑進和一條路徑出，保證每個孔位只連接兩條路徑。于是，滿足上述約束的解構(gòu)成了一條哈密頓回路。

2 改進蟻群算法的實現(xiàn)

2.1 基本原理

以TSP 問題為例[4]，城市的數(shù)量為n，螞蟻的數(shù)量為m，dij表示城市i 和城市j 之間的距離，τij(t)表示t 時刻兩個城市之間的信息濃度，選擇從城市i 到城市j 這條路徑的概率為：

其中，allowed 表示螞蟻下一步允許選擇的城市，經(jīng)過n 個時刻，螞蟻完成一次循環(huán)，每只螞蟻所走過的路徑就是一個解。此時，要根據(jù)下面公式對各路徑上的信息量作更新：

由上述可知，蟻群算法優(yōu)化過程的本質(zhì)在于：

（1）選擇機制。路徑上信息素濃度越大，后續(xù)螞蟻選擇該路徑的幾率也越大。

（2）更新機制。經(jīng)過螞蟻的數(shù)量越多，信息素濃度越高，以此同時，信息素濃度也會跟著時間的推移而降低。

（3）協(xié)調(diào)機制。螞蟻之間是通過通信進行協(xié)調(diào)工作，因此蟻群算法得到解的質(zhì)量很高。

2.2 改進蟻群算法

由于蟻群優(yōu)化算法作為一種新的啟發(fā)式搜索算法，自適應(yīng)性、魯棒性好，但是在蟻群搜索過程中，當(dāng)問題規(guī)模較大時，需要花費大量的時間，另外易陷入局部解。算法的正反饋機制保證了算法的搜索過程朝著問題最優(yōu)解的方向進行，然而，由于蟻群算法的正反饋特性，很容易將蟻群搜索集中在某些路徑上，導(dǎo)致無法進一步探索其他路徑。此時，算法的搜索容易停滯，陷入局部最優(yōu)解，問題的規(guī)模越大，這種現(xiàn)象就越明顯。同時初始參數(shù)的設(shè)置對算法有很大的影響，初始參數(shù)的設(shè)置雖然不影響收斂性，但對最終的優(yōu)化結(jié)果影響很大。如果在蟻群搜索過程中，能在初始操作階段得到合理的參數(shù)和較好的初始解，就能引導(dǎo)蟻群朝著正確的方向搜索，其速度將大大提高。鑒于以上問題對蟻群算法進行了改進。

2.3 局部優(yōu)化

蟻群算法的信息素更新方式具有正反饋性。正反饋能夠提高算法的收斂速度，但也易陷入局部最優(yōu)，無論后續(xù)增加多少的迭代次數(shù)，仍然無法跳出。為此，在蟻群算法中加入k-optimization(k-opt)策略，能夠改善這一情況，增強蟻群算法跳出局部最優(yōu)的能力。其中2-opt 在面對城市的數(shù)量較少的情況下，既可以跳出局部最優(yōu)，又可以花費較少的時間，提高算法效率，因此而得到推崇。2-opt方法的基本原理就是在一條完整的漢密爾頓回路(Hamilton Tour)上通過改變連接兩個城市之間的路徑，算法會在一定范圍之內(nèi)進行搜索。假設(shè)全局最優(yōu)路徑為1-2-3-4-5-6-7-8-9-1，子路徑2-3-4-5 變?yōu)?-4-3-5 如圖1所示，交換之后的路徑長度大于交換之前，則保持路徑，繼續(xù)搜索，直至搜索到比交換之前路徑短的情況或者交換之前的路徑為最短路徑停止，繼續(xù)下一階段的搜索。

圖1：2-opt 路徑交換示意圖

這種局部優(yōu)化雖然能夠提高解的質(zhì)量，但是同時消耗過多時間。鑒于其中只有少部分路徑能夠成為當(dāng)前的最優(yōu)路徑。為了提高效率，我們可以將這些路徑從短到長進行排列，選擇路徑長度位于前25%的路徑進行優(yōu)化。

2.4 方向因子的引入

根據(jù)圖2 顯示，從城市1 到達(dá)城市7 到路徑有很多，在搜索初期，每條路徑的信息素濃度基本相同，此時位于城市1 的螞蟻選擇城2和城市3 都存在可能性，如果選擇了城市2 作為下一站就會偏離原本的最優(yōu)路徑，從而失去找到最優(yōu)解，降低了收斂于最優(yōu)解概率。

圖2：無向圖

此時將城市1 投影到城市2 到城市3 的路徑上會發(fā)現(xiàn)，城市1向城市2 運動增加不必要的路徑，引進方向因子就是將這種與路徑終點相反的選擇去除，提高搜索優(yōu)質(zhì)解的幾率。

A 點為起點，B 點為終點，C 點為搜索域中的一點，設(shè)他們的坐標(biāo)分別為(XA,YA)，(XB,YB)，(XC,YC)，則向量AB 的坐標(biāo)為(XB- XA,YB-YA)，則向量AC 的坐標(biāo)為(XC- XA，YC- YA)，最短路徑與搜索路徑的夾角為θ，如圖3所示。

圖3：最短路徑與搜索路徑的夾角

向量之間的夾角變大的時候，夾角的余弦值將會變小，方向因子也會變小，對于方向偏移的路徑指導(dǎo)性將會變?nèi)酢?/p>

根據(jù)方向因子的特點，加入激勵函數(shù) Sigmoid 函數(shù)：，將兩者結(jié)合起來，得到方向因子的數(shù)學(xué)模型。

根據(jù)公式顯示，當(dāng)起始點到終止點的直線距離和當(dāng)前路徑的夾角越大，選擇這條路徑的幾率會越小。經(jīng)過改進處理后的螞蟻選擇概率如下：

對于γ 的值，表明了方向因子對選擇概率的影響。通過方向因子的加入，螞蟻選擇相反方向的幾率大大降低，去除一些劣質(zhì)解的出現(xiàn)。

3 算法的仿真及分析

該仿真的主要目的是驗證本文提出的改進蟻群算優(yōu)于基本蟻群算法和遺傳算法。

改進蟻群算法的參數(shù)alpha=2，beta=3，ρ=0.7，m=2，其仿真結(jié)果如圖4所示。

圖4：各算法路徑長度

在其他參數(shù)不變的情況下，重復(fù)實驗30 次，根據(jù)經(jīng)典蟻群算法和改進之后的蟻群算法仿真結(jié)果的對比，如表1所示，改進蟻群算法在計算效率方面明顯優(yōu)于經(jīng)典蟻群算法，而且能夠搜索出更加優(yōu)秀的路徑。從收斂曲線中可以得到，改進蟻群算法的收斂性明顯優(yōu)路徑長于基本蟻群算法。

表1：各算法最優(yōu)路徑長度和迭代次數(shù)

4 結(jié)語

本文針對飛機壁板鉆鉚過程中刀具空行的路徑進行了規(guī)劃。首先對走刀的路徑規(guī)劃問題進行了數(shù)學(xué)描述，對于蟻群算法搜索容易偏離路徑終點和容易陷入局部最優(yōu)解的缺陷，提出一種改進蟻群算法(IACO)。通過加入2-opt 策略，改變了兩個“城市”間的路徑，提高解的質(zhì)量，同時將激勵函數(shù)Sigmoid 與方向因子相結(jié)合，為螞蟻搜索提供方向保證，減少較差解的產(chǎn)生。通過比較改進前后算法的迭代次數(shù)、路徑長度，證實改進算法確實對路徑的規(guī)劃起到優(yōu)化作用。