宣東軍 曲家辰

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

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

1 研究基礎(chǔ)

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

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

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

假設(shè)：

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

約束條件：

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

2 改進(jìn)蟻群算法的實(shí)現(xiàn)

2.1 基本原理

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

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

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

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

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

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

2.2 改進(jìn)蟻群算法

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

2.3 局部?jī)?yōu)化

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

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

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

2.4 方向因子的引入

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

圖2：無(wú)向圖

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

A 點(diǎn)為起點(diǎn)，B 點(diǎn)為終點(diǎn)，C 點(diǎn)為搜索域中的一點(diǎn)，設(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：最短路徑與搜索路徑的夾角

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

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

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

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

3 算法的仿真及分析

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

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

圖4：各算法路徑長(zhǎng)度

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

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

4 結(jié)語(yǔ)

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