馬瑩瑩，杜暖男

(1. 天津市機(jī)電工藝技師學(xué)院 信息傳媒系，天津 300350； 2. 天津海運(yùn)職業(yè)學(xué)院 信息工程系，天津 300350)

0 引 言

機(jī)器人路徑規(guī)劃，簡(jiǎn)稱RPP，旨在決策給定起終點(diǎn)間的最優(yōu)路徑，從而使得線路長(zhǎng)度、機(jī)器人能耗等指標(biāo)達(dá)到最優(yōu)[1]。近年來(lái)，智能移動(dòng)機(jī)器人獲得了廣泛應(yīng)用，業(yè)務(wù)場(chǎng)景包含智慧生產(chǎn)、貨物搬運(yùn)、異常環(huán)境探測(cè)等[2]。因此，開(kāi)發(fā)RPP問(wèn)題的決策算法意義重大。

傳統(tǒng)RPP決策方法有視圖法、自由空間法以及人工勢(shì)場(chǎng)法等[3]。在各類實(shí)際工程場(chǎng)景中，以上算法逐步暴露出亟待改善的問(wèn)題點(diǎn)。視圖法所求路徑棱角明顯，因而所得線路難以構(gòu)成全局最優(yōu)；自由空間法的計(jì)算復(fù)雜度很大，難以應(yīng)對(duì)復(fù)雜障礙空間的情況。近年來(lái)進(jìn)化算法的發(fā)展為解決RPP問(wèn)題提供了新思路，諸如遺傳、蟻群等算法均在此問(wèn)題上獲得了成功應(yīng)用，但也存在些許不足。比如：遺傳算法生成線路容易包含障礙物在內(nèi)，使得結(jié)果容易違反約束；基本蟻群算法的搜索時(shí)間相對(duì)過(guò)長(zhǎng)、容易停滯。顯而易見(jiàn)，上述缺陷使得進(jìn)化算法求解RPP的效率較為低下。因此，有必要針對(duì)上述缺陷開(kāi)發(fā)基于進(jìn)化算法的高效RPP決策方法。

正余弦算法(sine cosine algorithm，SCA)是2016年由學(xué)者S. MIRJALILI[4]提出的一種新型進(jìn)化算法。SCA算法具有架構(gòu)簡(jiǎn)單、計(jì)算效率高等特點(diǎn)，且研究表明，SCA算法的整體搜索性能較螢火蟲(chóng)算法、花朵授粉算法、粒子群算法等更具優(yōu)勢(shì)[5]。SCA算法在眾多經(jīng)典優(yōu)化問(wèn)題上效果顯著，例如圖像分割、目標(biāo)跟蹤、電力系統(tǒng)調(diào)度等[6-8]。為此，筆者將該算法運(yùn)用到RPP這一重要工程問(wèn)題的求解。

SCA算法模擬了正余弦函數(shù)的震蕩特征，據(jù)此進(jìn)行迭代搜索，同時(shí)其初始化過(guò)程采用隨機(jī)方法，這一定程度上限制了算法的表現(xiàn)性能，同時(shí)SCA的種群更新過(guò)程過(guò)度依賴于當(dāng)前已知最優(yōu)解，且不同解個(gè)體間缺乏強(qiáng)有力的信息交流，這弱化了算法后期的求解能力。為解決以上問(wèn)題，筆者構(gòu)建的HSCA算法采用反學(xué)習(xí)初始化方法，用于產(chǎn)生優(yōu)質(zhì)初始解；在迭代環(huán)節(jié)中，該算法以優(yōu)化目標(biāo)為依據(jù)進(jìn)行模因分組進(jìn)而構(gòu)建多種群，并通過(guò)融合TLBO進(jìn)化機(jī)制強(qiáng)化個(gè)體交流，力求增強(qiáng)算法的局部挖掘能力。另外，筆者將HSCA算法與Spline插值法相結(jié)合，力求在確保RPP問(wèn)題路徑規(guī)劃精度的同時(shí)降低優(yōu)化難度，從而獲得高質(zhì)量的平滑路徑曲線。

1 機(jī)器人路徑規(guī)劃建模

1.1 環(huán)境模型

圖1給出了RPP的示意，起終點(diǎn)分別以正方形和三角形表示，障礙物用圓表示。

圖1 RPP示意Fig. 1 Schematic diagram of RPP

基于二維平面坐標(biāo)系，每個(gè)圓可表示為：

(x-a)2+(y-b)2=r2

(1)

式中：參數(shù)(a,b)為圓中心；r為半徑。

RPP要求確定一條由連接起點(diǎn)(x0,y0)和終點(diǎn)(xn+1,yn+1)的路徑H={(x0,y0),(x1,y1),…,(xn,yn),(xn+1,yn+1)}，從而使得決策目標(biāo)最優(yōu)。其中，(x1,y1),(x2,y2),…,(xn,yn)為待優(yōu)化的導(dǎo)航點(diǎn)坐標(biāo)?；谝陨厦枋隹芍?，導(dǎo)航點(diǎn)的數(shù)目n決定了當(dāng)前待優(yōu)化問(wèn)題的維度。同時(shí)，直接將路徑點(diǎn)相連繪制的線路圖形棱角較為明顯。為此，筆者引入Spline方法構(gòu)造線路[9-10]。如圖2，算法所需優(yōu)化的坐標(biāo)點(diǎn)為采樣導(dǎo)航點(diǎn)，而插值導(dǎo)航點(diǎn)表示通過(guò)Spline方法得到的坐標(biāo)。

圖2 Spline插值示意Fig. 2 Schematic diagram of spline interpolation method

1.2 路徑評(píng)價(jià)函數(shù)

筆者在RPP模型以線路長(zhǎng)度作為目標(biāo)函數(shù)，在線路評(píng)價(jià)函數(shù)構(gòu)建中引入懲罰函數(shù)法以解決線路避開(kāi)障礙物這一約束：

(2)

(3)

式中：ω為懲罰系數(shù)，取值為正；K為障礙物總數(shù)；(ak,bk)為障礙物k的坐標(biāo)中心；rk為半徑；Vi,k∈[0,1]為當(dāng)前線路中第i個(gè)導(dǎo)航點(diǎn)(xi,yi)與第k個(gè)障礙物間避障約束值；Vi,k=0為滿足避障約束?；诖耍u(píng)價(jià)函數(shù)L取值越小，線路長(zhǎng)度越短且違反避障約束程度越小，該線路的質(zhì)量越優(yōu)。

2 SCA與TLBO算法

2.1 SCA算法

(4)

式中：d=1,…,D;i=1,…,N。

在表達(dá)式中，xi=(xi1,xi2,…,xiD)為第i個(gè)解的表達(dá)式，xid為xi第d維的取值，rand(0,1)為[0,1]上的隨機(jī)數(shù)。

在迭代過(guò)程中，針對(duì)解xi，迭代更新公式為：

(5)

式中：g為當(dāng)前迭代次數(shù)；x*為已知最好解；參數(shù)r2、r3和r4為隨機(jī)量，取值范圍設(shè)置為r2∈[0,2π]、r3∈[0,2]、r4∈[0,1]?？刂茀?shù)r1定義為：

(6)

式中：a為常數(shù)；G為算法的最大迭代次數(shù)。

SCA算法流程為：

Step 1初始化：借助隨機(jī)方法生成初始種群。

Step 2目標(biāo)函數(shù)計(jì)算：計(jì)算每個(gè)解的目標(biāo)函數(shù)值。

Step 3確定最優(yōu)個(gè)體：將算法迭代至當(dāng)前階段所搜得的目標(biāo)函數(shù)值最小個(gè)體標(biāo)記為已知最優(yōu)解。

Step 4更新算法參數(shù)：更新系數(shù)r1、r2、r3和r4。

Step 5更新個(gè)體位置：依據(jù)式(5)生成子代種群。

Step 5終止判斷：若滿足終止條件，停止迭代并輸出最好解；否則轉(zhuǎn)Step 2。

2.2 TLBO算法

在TLBO算法中，個(gè)體更新包括 “教學(xué)階段”和“學(xué)習(xí)階段”兩部分[11]。

(7)

在學(xué)習(xí)階段，TLBO通過(guò)將候選解與其他解進(jìn)行位置差分，并據(jù)此進(jìn)行位位置更新，表達(dá)式為：

(8)

TLBO算法流程為：

Step 1初始化：采用隨機(jī)方法生成初始解。

Step 3學(xué)習(xí)階段：對(duì)于當(dāng)前種群中的每個(gè)解，借助該個(gè)體與其他解向量之間的差分量生成新個(gè)體，并借助貪婪保留策略生成子代解。

Step 4終止判斷：若達(dá)到終止條件，停止搜索并給出最優(yōu)解；否則轉(zhuǎn)Step 2。

3 HSCA算法

SCA的隨機(jī)初始化方法一定程度上制約了其搜索效率，同時(shí)其迭代過(guò)程僅借助已知最優(yōu)解和候選解之間的差分量更新個(gè)體位置，忽略了其他個(gè)體間的信息交流。鑒于此，HSCA以反向?qū)W習(xí)方法構(gòu)建質(zhì)量較高的初始種群，同時(shí)憑借模因分組和TLBO進(jìn)化機(jī)制強(qiáng)化不同個(gè)體信息交流，旨在增強(qiáng)基本SCA算法的搜索性能。

3.1 反向?qū)W習(xí)初始化方法

HSCA采用反學(xué)習(xí)方法構(gòu)建種群：首先，利用隨機(jī)方法生成N個(gè)解，并為每個(gè)解生成對(duì)應(yīng)的反向解，最后選取最好的N個(gè)解作為初始種群[12]。

圖3為對(duì)比了兩種初始化方法在二維解空間的隨機(jī)分布情況。顯然，反向?qū)W習(xí)初始化方法在均勻、全面地探索解空間方面更具優(yōu)勢(shì)。

圖3 初始化方法對(duì)比Fig. 3 Comparison of initialization methods

算法的初始解構(gòu)造過(guò)程為：

Step 1定義參數(shù)i←1和參數(shù)d←1。

Step 2若表示式i≤S成立，轉(zhuǎn)Step 3，否則轉(zhuǎn)Step 7。

Step 3若表達(dá)式d≤D成立，轉(zhuǎn)Step 4，否則轉(zhuǎn)Step 5。

Step 5定義參數(shù)d←d+1，若d>D成立，轉(zhuǎn)Step 6；否則轉(zhuǎn)Step 3。

Step 6定義參數(shù)i←i+1，隨后轉(zhuǎn)Step 2。

3.2 模因分組與種群進(jìn)化

HSCA算法保留了基本SCA算法的進(jìn)化機(jī)制，利用式(5)更新個(gè)體位置，即借助已知最優(yōu)解和候選解之間的差分量更新種群?；诖?，按照目標(biāo)值排序，并以q個(gè)解為一組劃分為p個(gè)模因組[13]。分組過(guò)程歸納如下：①將最優(yōu)解放在第一組，第二優(yōu)解放在第二組，依次類推；②將排位第p+1位的個(gè)體將被置入第一組，排位第p+2位的個(gè)體將被置入第二組；③重復(fù)以上分配過(guò)程，直至將最后一個(gè)解置入第p組。

隨后，HSCA算法采用TLBO的“教學(xué)階段”更新組內(nèi)的非局部最優(yōu)解，并以TLBO的“學(xué)習(xí)階段”更新組內(nèi)的所有解。給定一個(gè)解x，式(9)、式(10)分別為HSCA算法中“教學(xué)階段”和“學(xué)習(xí)階段”涉及的更新公式：

(9)

(10)

3.3 HSCA算法流程

HSCA算法的實(shí)現(xiàn)流程梳理如下：

Step 1初始化：利用反向?qū)W習(xí)法創(chuàng)建初始解。

Step 2SCA更新：確定當(dāng)前種群中的最優(yōu)解，利用SCA算法更新式(2)生成新個(gè)體的位置。

Step 3模因分組：依據(jù)個(gè)體的路徑評(píng)價(jià)函數(shù)值將種群劃分為p個(gè)子種群。

Step 4組內(nèi)教學(xué)：對(duì)于各個(gè)子種群，采用TLBO的“教學(xué)階段”更新組內(nèi)的非局部最優(yōu)解。

Step 5組內(nèi)學(xué)習(xí)：對(duì)于各個(gè)子種群，借助TLBO的“學(xué)習(xí)階段”更新組內(nèi)的各個(gè)解。

Step 6終止判斷：若滿足HSCA決策算法所設(shè)置的終止條件，停止迭代并輸出最好解；否則轉(zhuǎn)到Step 2。

4 實(shí)驗(yàn)結(jié)果與分析

為分析HSCA的性能，開(kāi)展基準(zhǔn)函數(shù)和RPP問(wèn)題測(cè)試，并進(jìn)行多種同類算法的對(duì)比。利用MATLAB2016b編程，平臺(tái)參數(shù)為內(nèi)存8 GB、CPU為Intel Core i5-2430M 2.4 Hz。

4.1 基準(zhǔn)函數(shù)測(cè)試

選取文獻(xiàn)[14]中的函數(shù)進(jìn)行測(cè)試(表1)，參數(shù)n為函數(shù)維度。首先，對(duì)比HSCA與SCA算法，目的在于分析驗(yàn)證改進(jìn)措施的有效性。考慮n分為20和40的情形，對(duì)于每組算例，兩種決策方法分別跑20次。HSCA與SCA的種群置為60，迭代終止次數(shù)置為2 000，同時(shí)HSCA的q值設(shè)為10。表2給出了測(cè)試結(jié)果的均值和標(biāo)準(zhǔn)差數(shù)值比較。

表1 函數(shù)定義Table 1 Function definition

由表2可知，HSCA相比于SCA所取得的均值更小。換而言之，HSCA算法的整體尋優(yōu)效果更優(yōu)。同時(shí)，HSCA算法20次獨(dú)立運(yùn)行所得結(jié)果的標(biāo)準(zhǔn)差較SCA更小，說(shuō)明HSCA算法魯棒性更佳。

表2 SCA與HSCA算法目標(biāo)函數(shù)值對(duì)比Table 2 Objective function value comparison of SCA andHSCA algorithm

進(jìn)一步地，將HSCA與其他幾種改進(jìn)SCA算法對(duì)比，包括MSCA[8]、OBSCA[15]和SCA-DE[7]。維度n=40，對(duì)于各測(cè)試算例，所有方法分別跑20次，種群規(guī)模取60，迭代終止次數(shù)置為2 000，HSCA算法的子種群規(guī)模設(shè)置為10，其他參數(shù)設(shè)置同文獻(xiàn)[7,8,15]。表3對(duì)4種算法的仿真結(jié)果進(jìn)行了分析，圖4為4種算法求解基準(zhǔn)測(cè)試函數(shù)的平均進(jìn)化曲線。

由表3可知，HSCA算法所得結(jié)果的均值優(yōu)于MSCA、OBSCA和SCA-DE算法，表明反向?qū)W習(xí)初始化方法以及基于TLBO的多種群進(jìn)化策略的嵌入使得SCA的搜索性能更強(qiáng)。同時(shí)，HSCA算法的標(biāo)準(zhǔn)差更小則驗(yàn)證了其運(yùn)行狀態(tài)更穩(wěn)定。另外，由圖4可知， HSCA算法初始階段的種群質(zhì)量更優(yōu)，且最終所尋得的解更具競(jìng)爭(zhēng)性。

表3 4種改進(jìn)SAC算法目標(biāo)函數(shù)值對(duì)比Table 3 Objective function value comparison of four kinds ofimproved SCA algorithms

圖4 平均進(jìn)化曲線對(duì)比Fig. 4 Comparison of mean evolution curves

4.2 路徑規(guī)劃仿真

分別將HSCA、MSCA、OBSCA和SCA-DE算法運(yùn)用于簡(jiǎn)單(以Case 1表示)和復(fù)雜環(huán)境(以Case 2表示)的路徑規(guī)劃實(shí)驗(yàn)。問(wèn)題參數(shù)設(shè)置如下：Case 1障礙數(shù)和導(dǎo)航點(diǎn)數(shù)為6和10，Case 2中相應(yīng)參數(shù)為12和100。算法設(shè)置如下：決策方法運(yùn)行次數(shù)置為20，種群規(guī)模和迭代次數(shù)為30和300， HSCA子種群規(guī)模為6，對(duì)比算法的其他參數(shù)同各文獻(xiàn)[7,8,15]。實(shí)驗(yàn)結(jié)果歸納如圖5、圖6和表4。

圖5 最優(yōu)路徑Fig. 5 Optimal paths

圖6 最優(yōu)進(jìn)化曲線Fig. 6 Optimal evolution curves

表4 兩種環(huán)境下4種測(cè)試算法線路長(zhǎng)度對(duì)比Table 4 Comparison of the path length with four kinds oftest algorithms in two environment m

圖5對(duì)比了4種SCA算法在Case 1和Case 2中所得的最佳路徑，HSCA算法所規(guī)劃出的路徑最優(yōu)。特別是在Case 2對(duì)應(yīng)的復(fù)雜障礙環(huán)境中，筆者所提出的HSCA算法優(yōu)勢(shì)明顯。進(jìn)一步的，圖6對(duì)比了4種SCA算法在Case 1和Case 2下的最優(yōu)進(jìn)化曲線。據(jù)此可知，反向?qū)W習(xí)方法使得HSCA算法在迭代初期解的質(zhì)量更佳；同時(shí)，模因分組以及基于TLBO的多種群進(jìn)化方法有效提升了算法的搜索性能。表4為4種改進(jìn)SCA算法的優(yōu)化結(jié)果，顯然筆者提出的HSCA在優(yōu)化目標(biāo)優(yōu)越性和穩(wěn)定性兩方面很具有競(jìng)爭(zhēng)性。

5 結(jié) 論

提出了一種混合正余弦算法來(lái)求解機(jī)器人路徑規(guī)劃問(wèn)題。算法采用反向?qū)W習(xí)初始化方法，用于構(gòu)建高質(zhì)量的初始種群；同時(shí)在迭代搜索過(guò)程中，以優(yōu)化目標(biāo)為依據(jù)進(jìn)行模因分組進(jìn)而構(gòu)建多種群；并通過(guò)融合TLBO算法強(qiáng)化各子種群內(nèi)的信息交流，達(dá)到了增強(qiáng)算法局部挖掘能力的目的。在仿真實(shí)驗(yàn)部分，結(jié)合基準(zhǔn)函數(shù)開(kāi)展了HSCA算法的橫向和縱向的對(duì)比實(shí)驗(yàn)，同時(shí)將HSCA算法應(yīng)用于簡(jiǎn)單和復(fù)雜障礙環(huán)境的機(jī)器人路徑規(guī)劃問(wèn)題。測(cè)試結(jié)果表明，HSCA算法的收斂效果顯著，具有良好的尋優(yōu)精度和穩(wěn)健的魯棒性。