周紅勛

（湖北汽車工業(yè)學(xué)院機(jī)械工程學(xué)院 湖北省十堰市 442002）

隨著機(jī)器人技術(shù)的日趨成熟，生產(chǎn)廠家為了保證產(chǎn)品質(zhì)量、縮短生產(chǎn)周期，紛紛采用以機(jī)器人為核心的柔性生產(chǎn)線（簡(jiǎn)稱機(jī)器人工作站），如在汽車白車身焊裝生產(chǎn)線上，焊接機(jī)器人幾乎分布在各個(gè)工位，它們相互協(xié)同完成焊接任務(wù)。為了更好的讓機(jī)器人為人類服務(wù)，如何合理布局各工位上的機(jī)器人、分配各工位機(jī)器人的焊接任務(wù)以及優(yōu)化各機(jī)器人的焊接路徑（即多機(jī)器人路徑規(guī)劃）便成為機(jī)器人領(lǐng)域研究的熱難點(diǎn)問(wèn)題。文中默認(rèn)機(jī)器人布局已經(jīng)完成，只討論多機(jī)器人路徑規(guī)劃問(wèn)題，即在滿足若干約束條件的前提下，以時(shí)間最短和系統(tǒng)安全性為基本目標(biāo)，對(duì)每臺(tái)機(jī)器人進(jìn)行焊接任務(wù)分配以及無(wú)碰撞焊接路徑優(yōu)化。這是一個(gè)錯(cuò)綜復(fù)雜的問(wèn)題，其中涉及的參數(shù)變量多、不穩(wěn)定且相互耦合，因此大多數(shù)學(xué)者采用粒子群算法、蟻群算法等智能算法來(lái)研究,但由于這些算法在解決此問(wèn)題時(shí)本身存在不足之處，故它們規(guī)劃的結(jié)果還有可提升的空間。國(guó)外Joon-woo lee 等人為避免蟻群算法在求解時(shí)陷入局部最優(yōu)，對(duì)蟻群算法進(jìn)行異構(gòu)改進(jìn)，但仍存在實(shí)時(shí)性不理想等不足。在前期遺傳算法(genetic algorithm, GA)對(duì)單臺(tái)機(jī)器人路徑規(guī)劃研究的基礎(chǔ)上，為彌補(bǔ)它在進(jìn)行多機(jī)器人路徑規(guī)劃時(shí)早熟收斂、對(duì)交叉變異參數(shù)敏感以及未能準(zhǔn)確體現(xiàn)機(jī)器人之間的相互協(xié)作關(guān)系等不足，文中采用多種群遺傳算法(multi-population genetic algorithm,MPGA)來(lái)求解。MPGA 先把研究的種群分為多個(gè)相對(duì)獨(dú)立的子種群，再把GA 并行的應(yīng)用到各子種群且采用不同的控制參數(shù)同時(shí)進(jìn)化，并且進(jìn)化過(guò)程中引入移民和人工選擇兩種算子，最后將MPGA、GA 分別用于某焊接工位上多機(jī)器人的路徑規(guī)劃仿真實(shí)驗(yàn)，從而對(duì)比驗(yàn)證MPGA 的可行性和優(yōu)越性。

1 問(wèn)題描述以及模型建立

多機(jī)器人最優(yōu)焊接路徑規(guī)劃要為每臺(tái)機(jī)器人進(jìn)行焊點(diǎn)任務(wù)分配并找到一條最優(yōu)或者次優(yōu)的焊接路徑，以保證所有機(jī)器人無(wú)碰撞完成各自所分配的焊接任務(wù)后所花費(fèi)的時(shí)間最短或者所運(yùn)動(dòng)的總路程最短,這一規(guī)劃過(guò)程要受到諸如焊接工藝、焊點(diǎn)分組方式、生產(chǎn)節(jié)拍以及機(jī)器人屬性等若干因素的約束，此處為了便于建模，降低問(wèn)題的復(fù)雜度，忽略部分因素，從而把焊接任務(wù)分配問(wèn)題簡(jiǎn)化為多背包問(wèn)題，即把n 個(gè)焊點(diǎn)的集合W={W,W,W,…,W}分配給m 臺(tái)機(jī)器人的集合R={R,R,R,…,R}，使每臺(tái)機(jī)器人無(wú)碰撞焊接完自己所有焊點(diǎn)所運(yùn)動(dòng)的總距離之和盡量小。用數(shù)字0 和1 來(lái)表示焊點(diǎn)與機(jī)器人的所屬關(guān)系，X=1 表示焊點(diǎn)i 由機(jī)器人j 焊接，反之，則不是，D表示焊點(diǎn)i 與機(jī)器人j 之間的距離，則焊點(diǎn)分配多背包問(wèn)題的目標(biāo)函數(shù)M 為：

2 基于MPGA的路徑規(guī)劃

MPGA 是一種改進(jìn)智能算法，通過(guò)將GA 引入到數(shù)個(gè)相對(duì)獨(dú)立的子種群中進(jìn)行同步優(yōu)化搜尋的思想來(lái)提升進(jìn)化效率，各子種群采用不同的遺傳進(jìn)化控制參數(shù)來(lái)克服算法對(duì)交叉、變異算子取值敏感的不足。每當(dāng)各子種群進(jìn)化一定代數(shù)時(shí)（一般取代數(shù)2），目標(biāo)種群中的最差個(gè)體就會(huì)被移民算子從源種群里選中的最優(yōu)良個(gè)體所替代，以此來(lái)體現(xiàn)各子種群之間的相互協(xié)同關(guān)系。各子種群在進(jìn)化過(guò)程中每一代最優(yōu)秀的個(gè)體會(huì)被人工選擇算子挑選出來(lái)組成一個(gè)新種群，里面?zhèn)€體不再進(jìn)行任何遺傳進(jìn)化操作。為了弱化MPGA 對(duì)進(jìn)化代數(shù)的依賴，采用更為科學(xué)合理的算法停止進(jìn)化判據(jù)，即以新種群中最佳個(gè)體最少不變代數(shù)作為判定算法終止依據(jù)。MPGA 將GA 并行的用于各子種群，用它們替代父種群進(jìn)行協(xié)同搜索最優(yōu)值，其求解多機(jī)器人路徑規(guī)劃步驟為：

2.1 編碼

將焊點(diǎn)分配問(wèn)題進(jìn)行參數(shù)化并使用二進(jìn)制編碼，用數(shù)字0 和1 組成的n×m 維矩陣來(lái)表示焊點(diǎn)與機(jī)器人的所屬關(guān)系；針對(duì)單臺(tái)機(jī)器人路徑優(yōu)化，采用整數(shù)編碼方式，即編碼數(shù)列直接代表機(jī)器人的焊點(diǎn)焊接順序。

2.2 初始化各子種群

為了能夠快速的得到比較典型的高質(zhì)量種群個(gè)體，采用隨機(jī)挑選初始種群個(gè)體的形式，并把其隨機(jī)分成10 個(gè)大小相同的相對(duì)獨(dú)立的子種群。

2.3 設(shè)定適應(yīng)度函數(shù)

在基于二進(jìn)制編碼的前提下，為避免各臺(tái)機(jī)器人被分配到不合理的焊點(diǎn)，此處采用懲罰函數(shù)法來(lái)等效上述約束條件對(duì)多機(jī)器人系統(tǒng)中焊點(diǎn)分配問(wèn)題的影響，則焊點(diǎn)分配問(wèn)題的適應(yīng)度函數(shù)Q 為：

2.4 選擇操作

采用輪盤賭的選擇方式，即個(gè)體被選上的概率取決于其適應(yīng)度值的大小，它的值越大，說(shuō)明個(gè)體越優(yōu)秀，被選中的概率越大，故把適應(yīng)度函數(shù)的倒數(shù)作為個(gè)體的適應(yīng)度值。

2.5 交叉、變異操作

交叉算子、變異算子分別是各子種群產(chǎn)生新個(gè)體的首要因子、輔助因子，取值大小分別影響多種群遺傳算法的全局、局部搜索能力，它們?cè)诟髯臃N群中的取值不一樣。對(duì)于焊點(diǎn)分配，采用單點(diǎn)交叉、單點(diǎn)變異操作；對(duì)于單臺(tái)機(jī)器人路徑優(yōu)化，采用兩點(diǎn)交叉、兩點(diǎn)變異操作，且這兩種操作都只在新個(gè)體適應(yīng)度值優(yōu)于舊個(gè)體時(shí)才更新個(gè)體 。

2.6 移民操作

各子種群在進(jìn)化過(guò)程中產(chǎn)生聯(lián)系的操作，是MPGA 不同于GA 的重要之處。每隔一定代數(shù)，用種群1 中最優(yōu)個(gè)體替換種群2 中最差個(gè)體，……，種群10 中最優(yōu)個(gè)體替換種群1 中最差個(gè)體。

2.7 人工選擇操作

它把各子種群進(jìn)化過(guò)程中每代最優(yōu)秀的個(gè)體挑選到精英種群中加以保存并不再進(jìn)行任何進(jìn)化操作。同時(shí)判斷精英種群中最優(yōu)解是否達(dá)到最少保持代數(shù)，如果達(dá)到，則程序結(jié)束，解碼并輸出路徑規(guī)劃結(jié)果；反之，則重新從步驟（4）處執(zhí)行，直至符合進(jìn)化停止條件為止，流程圖如圖1 所示。

圖1： MPGA 流程圖

3 仿真實(shí)驗(yàn)結(jié)果分析

以某一焊接工位為例，此工位需要將99 個(gè)焊點(diǎn)（見(jiàn)附件）分配給4 臺(tái)機(jī)器人進(jìn)行焊接，另外Home1(900,-150,0)、Home2(2100,-150,0)、Home3(2100,1300,0)、Home4(900,1300,0) 分 別 為 機(jī) 器 人Robot1、Robot2、Robot3、Robot4 末端執(zhí)行器的初始位置。對(duì)于MPGA：代溝、子種群個(gè)數(shù)、種群大小分別取0.9、10、1000，交叉以及變異概率分別在區(qū)間[0.7,0.9]、區(qū)間[0.001,0.05]隨意生成，最優(yōu)個(gè)體至少保持10 代；對(duì)于GA：代溝、種群大小、迭代次數(shù)、交叉概率、變異概率分別取0.9、1000、500、0.9、0.05。在MATLAB 中分別編寫兩種算法的路徑規(guī)劃程序并將仿真實(shí)驗(yàn)進(jìn)行100 次，由仿真實(shí)驗(yàn)結(jié)果可知，MPGA 每次得到的結(jié)果一樣，而GA 每次運(yùn)行的結(jié)果基本都不一樣。為了便于兩者的比較，分別選擇其中焊接路徑之和最短的一次作為各自路徑規(guī)劃的最優(yōu)解。表1 是兩種算法的多機(jī)器人路徑規(guī)劃最優(yōu)分配方案，圖2、3 分別為兩種算法最優(yōu)解變化圖，表2為兩種算法路徑規(guī)劃結(jié)果的對(duì)比。由表1 可知，GA 最優(yōu)路徑規(guī)劃分配給Robot1、Robot2、Robot3、Robot4 機(jī)器人的焊點(diǎn)數(shù)分別為25、22、25、27；MPGA 最優(yōu)路徑規(guī)劃分配給Robot1、Robot2、Robot3、Robot4 機(jī)器人的焊點(diǎn)數(shù)分別為23、22、27、27。

表1： 兩種算法的多機(jī)器人路徑規(guī)劃最優(yōu)分配方案

表2： 兩種算法路徑規(guī)劃結(jié)果

圖2： GA 最優(yōu)解變化圖

圖3： MPGA 運(yùn)行3 次的最優(yōu)解變化圖

單從焊點(diǎn)分配均勻、無(wú)碰撞等方面來(lái)說(shuō)，兩種算法的分配結(jié)果都滿足，但由于焊點(diǎn)多的機(jī)器人所需焊接的時(shí)間長(zhǎng)一些，為了使四臺(tái)機(jī)器人能夠盡快同步協(xié)同完成焊接任務(wù)，就必須保證焊點(diǎn)少的機(jī)器人運(yùn)動(dòng)路徑長(zhǎng)一些，且各臺(tái)機(jī)器人的焊接距離相差不大。由表2 可知，MPGA 規(guī)劃得到的方案走過(guò)的總路徑最優(yōu)值較小，且任務(wù)分配更合理，更加利于機(jī)器人同步完成焊接任務(wù)。

由圖2、3 以及表1、2 知，MPGA 提高了路徑規(guī)劃的進(jìn)化效率，能夠快速得到十分穩(wěn)定的結(jié)果，7-12 代之間便可以搜尋到最優(yōu)解，GA 在150 代左右才能搜索到最優(yōu)解，且基于MPGA 所得的規(guī)劃結(jié)果總路徑長(zhǎng)度平均值和最小值，都比GA 要小。

由上可知，在多機(jī)器人的路徑規(guī)劃方面，MPGA 在搜索速度、穩(wěn)定性、路徑長(zhǎng)度等方面都比GA 具有優(yōu)勢(shì)，能提供更優(yōu)的規(guī)劃結(jié)果。

4 結(jié)論

（1）把GA 并行的應(yīng)用到各子種群且采用不同的控制參數(shù)同時(shí)進(jìn)化，能動(dòng)態(tài)調(diào)整改進(jìn)算法的局部和全局搜索能力；

（2）引進(jìn)人工選擇算子來(lái)挑選保留各子種群每代進(jìn)化過(guò)程中的最優(yōu)個(gè)體，并作為判斷算法是否繼續(xù)進(jìn)化的依據(jù)更為科學(xué)；引進(jìn)移民算子能保證最優(yōu)解的獲得是各子種群共同進(jìn)化的結(jié)果；

（3）MPGA 在求解多機(jī)器人路徑規(guī)劃問(wèn)題上具有顯著優(yōu)點(diǎn)，能夠迅速、精確的找到更合理的解，相對(duì)于GA 能將進(jìn)化搜索到最優(yōu)解所需的代數(shù)至少縮減90%、路程最小值縮減2.14%。