童安璐，宗光華，王 巍

（北京航空航天大學 機械工程及自動化學院，北京 100191）

0 引言

機器人切割路徑執(zhí)行順序問題即切割軌跡規(guī)劃問題，實際上可以理解為一個旅行商問題（Traveling Salesman Problem，TSP）。TSP是經(jīng)典的組合優(yōu)化問題，人們對求解TSP問題已經(jīng)進行了大量的研究，提出了許多用以解決該類問題的進化算法，如遺傳算法、退火算法、貪婪算法等。20世紀90年代，意大利學者Dorigo和Colorni等［1］人首先提出蟻群（Ant Colony System ACS）算法，該算法具有較強的魯棒性、較好的全局優(yōu)化能力和分布計算能力，同時還容易與其他方法相結合，特別適合于求解困難的組合優(yōu)化問題［2－3］。

1 蟻群算法基本原理

為了闡述基本蟻群算法對TSP問題的描述，首先設m為蟻群中螞蟻的數(shù)量，ρ為信息素揮發(fā)率，τij為城市i和j之間的信息素量，dij為城市i和j之間的距離。信息素量τij可以表示為：

式（1）中加號左邊為殘余信息素量，右邊為更新的信息素量。螞蟻覓食過程中，隨著時間的推移，以前留下的信息素逐漸揮發(fā)，信息素揮發(fā)率ρ的值介于0～1之間。

其中：Q為一個常數(shù)；Lk為第k只螞蟻完成覓食的行走路徑長度。第k只螞蟻對城市i和j間信息素的更新量與該螞蟻在旅行過程中總的行走距離成反比。

每一只螞蟻都面臨著下一個路徑的選擇問題，下一個路徑選擇機制描述如下：當螞蟻k處在城市i時，將螞蟻下一個可選城市集表示為一個集合N（sp）；當前城市為i，cij表示螞蟻選擇城市j，cil表示螞蟻選擇城市l(wèi)。參數(shù)α和β是常數(shù)，控制著信息素τ與啟發(fā)式信息η的比例，螞蟻k選擇從城市i到j的概率為：

式（3）中，當j不屬于可選城市集時，螞蟻選擇下一城市j的概率為0，而當j處于可選城市集時，概率是信息素τ與啟發(fā)式信息η的函數(shù)，第一行分母表示當前城市i的所有可選城市路徑集合中τ與η多項式之和。啟發(fā)式信息η可表示為：

2 機器人切割軌跡規(guī)劃問題描述

2.1 軌跡分析

將蟻群算法應用于機器人切割軌跡規(guī)劃需要解決算法中的城市與軌跡規(guī)劃中的軌跡的對應問題。

經(jīng)過分析發(fā)現(xiàn)，用戶選擇的切割路徑主要是以線、圓、圓弧、樣條等基本圖形信息為主，這些輪廓信息可以歸納為有若干節(jié)點的開放式軌跡和由若干節(jié)點圍成的封閉式軌跡［4］。無論是開放式軌跡段，還是封閉式軌跡段，所有軌跡都是有向軌跡，都擁有軌跡的起點和終點。把一段軌跡視為蟻群算法中的一個城市，且限定只能軌跡終點指向軌跡起點，那么兩個城市間的距離有兩個值，需要對城市距離進行二值化修改。

此外與蟻群算法不同的是，所有的切割路徑都是相鄰的，即所有的城市都屬于相連的城市，不存在間接連接的城市。

2.2 規(guī)劃目標分析

將蟻群算法應用于機器人切割軌跡規(guī)劃還需要針對機器人切割實際情況對規(guī)劃目標進行分析。

首先單個城市軌跡起點到終點的長度不應計入螞蟻行走總長度。軌跡規(guī)劃的目標是對走刀空程總長進行優(yōu)化，而軌跡路徑是有效切割路徑，不屬于空程長度，蟻群算法中應忽略其影響。

其次機器人切割軌跡規(guī)劃與旅行商不同點在于旅行商在走完所有城市之后還應回到出發(fā)城市，最終構成一個路徑回路，而機器人切割軌跡規(guī)劃無需回到出發(fā)城市，只是在所有城市之間選擇一條單向的最優(yōu)路徑。

3 算法設計

設計蟻群算法流程如圖1所示，將其作為一個模塊嵌入機器人切割軟件中。具體流程如下：

（1）輸入?yún)?shù)為用戶選擇的圖元鏈vector容器，使用該容器初始化城市數(shù)目相關參數(shù)，包括城市間距離數(shù)組、蟻群數(shù)目、城市間信息素數(shù)組。其中城市間距離數(shù)組根據(jù)圖元鏈起點和終點的不同值進行相應初始化，每兩個城市間距離有兩個值。

（2）進入迭代求解過程，每次迭代都要對蟻群的m只螞蟻進行路徑求解。每只螞蟻的求解策略如下：首先初始化訪問城市數(shù)據(jù)，同時隨機選擇一個城市作為出發(fā)城市；然后依據(jù)城市選擇策略選擇適當?shù)某鞘?，直到完成所有的城市訪問；最后記錄下該螞蟻訪問的路徑節(jié)點及長度信息。

為防止蟻群算法過快收斂于局部最優(yōu)解，本算法的信息素更新只在一個迭代完成之后進行。一個迭代步中，所有螞蟻的城市選擇策略基于上一個迭代步遺留信息素量。引入?yún)?shù)fij來描述城市選擇策略：其中：Vi為未訪問的節(jié)點集合。

計算所有n個城市fij之和∑fij，并在0與∑fij之間取一個隨機數(shù)temp，使用輪盤賭實現(xiàn)下一個城市輸出［6］。第k次轉動輪盤，temp減去對應本次轉動的fik，直到temp小于0。由于temp均勻地落在0～∑fij之間，選擇每一個城市的概率符合式（3）。

（3）完成一次迭代，對全局信息素進行更新。根據(jù)式（2）計算每只螞蟻的數(shù)組，最后疊加上揮發(fā)后的原有信息素，實現(xiàn)城市間信息素的全局更新。信息素揮發(fā)系數(shù)ρ與常數(shù)Q根據(jù)文獻［5］分別取為0.7與100。

（4）到當前迭代次數(shù)為止，所建立的所有局部最優(yōu)解中，值最小的解作為當前迭代次數(shù)的全局最優(yōu)解。

圖1 設計蚊群算法流程

4 實驗驗證

由2.1節(jié)敘述可知，把一段軌跡視為蟻群算法中的一個城市，則城市間的距離有兩個值。軌跡起點、終點重合，兩個值相同，若不重合，則兩個值不同。切割軌跡起點、終點重合與否對不同算法軌跡規(guī)劃的效果有一定影響。為驗證本文改進蟻群算法對兩種情況均有較強適應性，做如下實驗。

首先驗證切割路徑起點和終點重合時，蟻群算法的全局較優(yōu)性。定義30個城市，城市坐標即為切割路徑起點、終點的重合點，坐標數(shù)據(jù)見表1。

引入兩種路徑求解算法：圖元順序求解和最近距離求解。圖元順序即按照城市坐標的原始順序計算空程總長，表1中城市間距離即為空程長度，從城市1開始，依次求解30個城市距離即可。最近距離即按照單個城市局部最優(yōu)解的順序計算空程總長，從城市1開始尋找下一個最近距離城市，計算空程長度，然后再訪問下一個最近距離城市，疊加空程長度，直到所有城市訪問完畢。蟻群算法與圖元順序求解、最近距離求解結果對比見圖2。圖元順序空程總長850.152km，最近距離空程總長427.340km，蟻群算法空程總長371.725km，蟻群算法求解結果比圖元順序求解結果有著顯著優(yōu)化，比最近距離求解結果優(yōu)化了13%。

表1 城市坐標數(shù)據(jù) km

其次，切割路徑起點、終點不相同時，定義10段切割軌跡代表10個城市，軌跡編號與軌跡方向見圖3（a）中原始數(shù)據(jù)。蟻群算法求解的最短路徑結果與按圖元順序以及按最近距離求解的結果對比見圖3。圖元順序空程總長227.786km，最近距離空程總長175.652km，蟻群算法空程總長145.325km，蟻群算法求解結果比圖元順序求解結果有著顯著優(yōu)化，比最近距離求解結果優(yōu)化了17%。

5 結束語

考慮到機器人切割過程與TSP求解過程有所不同，因此本文對機器人切割軌跡和規(guī)劃目標進行了分析，并設計了符合機器人切割加工實際的改進蟻群算法。通過與圖元順序以及按最近距離求解的算例仿真對比顯示，基本蟻群算法具有較明顯的優(yōu)勢，同樣切割路徑下，可以得到空行程更短的加工路徑。由于基本蟻群算法容易收斂于局部最優(yōu)解，因此想要得到更優(yōu)的解，有待進一步研究。

圖2 起點終點重合實驗結果

圖3 起點終點不重合實驗結果

［1］Dorigo M，Maniezzo V，Colorni A.Ant system：optimization by a colony of cooperating［J］.IEEE Trans on Systems，Man and Cybernetics，1996，26（1）：29－41.

［2］張軍英，敖磊，賈江濤.求解TSP問題的改進蟻群算法［J］.西安電子科技大學學報（自然科學版），2005，32（5）：681－685.

［3］肖健梅，付宇，王錫淮.一種求解旅行商問題的改進蟻群算法［J］.南京航空航天大學學報，2006，38（增刊1）：50－53.

［4］侯媛彬，高陽東，鄭茂全.基于貪心－遺傳算法的混合軌跡加工走刀空行程路徑優(yōu)化［J］.機械工程學報，2013，49（21）：153－159.

［5］詹士昌，徐婕，吳俊.蟻群算法中有關算法參數(shù)的最優(yōu)選擇［J］.科技通報，2003，19（5）：381－386.

［6］畢軍，付夢印，張宇河.一種改進的蟻群算法求解最短路徑問題［J］.計算機工程與應用，2003（3）：107－109.