基于蟻群算法的機(jī)器人切割軌跡規(guī)劃

童安璐，宗光華，王 巍

（北京航空航天大學(xué) 機(jī)械工程及自動(dòng)化學(xué)院，北京 100191）

0 引言

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

1 蟻群算法基本原理

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

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

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

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

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

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

2.1 軌跡分析

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

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

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

2.2 規(guī)劃目標(biāo)分析

將蟻群算法應(yīng)用于機(jī)器人切割軌跡規(guī)劃還需要針對(duì)機(jī)器人切割實(shí)際情況對(duì)規(guī)劃目標(biāo)進(jìn)行分析。

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

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

3 算法設(shè)計(jì)

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

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

（2）進(jìn)入迭代求解過程，每次迭代都要對(duì)蟻群的m只螞蟻進(jìn)行路徑求解。每只螞蟻的求解策略如下：首先初始化訪問城市數(shù)據(jù)，同時(shí)隨機(jī)選擇一個(gè)城市作為出發(fā)城市；然后依據(jù)城市選擇策略選擇適當(dāng)?shù)某鞘校钡酵瓿伤械某鞘性L問；最后記錄下該螞蟻訪問的路徑節(jié)點(diǎn)及長度信息。

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

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

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

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

圖1 設(shè)計(jì)蚊群算法流程

4 實(shí)驗(yàn)驗(yàn)證

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

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

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

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

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

5 結(jié)束語

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

圖2 起點(diǎn)終點(diǎn)重合實(shí)驗(yàn)結(jié)果

圖3 起點(diǎn)終點(diǎn)不重合實(shí)驗(yàn)結(jié)果

［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ìn)蟻群算法［J］.西安電子科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2005，32（5）：681－685.

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

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

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

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