基于動(dòng)態(tài)自確定并行模糊聚類雞群優(yōu)化算法的水稻機(jī)器人路徑規(guī)劃

余曉蘭，萬 云，朱景建，陳靖照

（1.重慶城市職業(yè)學(xué)院，重慶 永川 402160；2.浙江工業(yè)大學(xué)，浙江 杭州 310014；3.鄭州大學(xué)，河南 鄭州 450000）

1 引言

水稻機(jī)器人的使用為處理農(nóng)業(yè)信息采集等問題提供了高效便利的解決途徑，解決了大面積農(nóng)田信息傳輸“擺渡”難題，然而如何有效規(guī)劃水稻機(jī)器人的移動(dòng)路徑，已成為當(dāng)前研究領(lǐng)域熱點(diǎn)方向之一。鑒于對(duì)外部環(huán)境信息的熟知度，路徑規(guī)劃分為全局路徑規(guī)劃和局部路徑規(guī)劃兩類[1]。常見的傳統(tǒng)全局路徑規(guī)劃算法有柵格法、人工勢(shì)場(chǎng)方法、隨機(jī)擴(kuò)展樹法和自由空間法等[2-4]。近年來，隨著群智能優(yōu)化技術(shù)的不斷發(fā)展，智能優(yōu)化算法為路徑規(guī)劃問題提供了全新的研究視角[5]。

全局路徑規(guī)劃作為機(jī)器人路徑規(guī)劃研究基礎(chǔ)，學(xué)者們開展了系列研究：文獻(xiàn)[6]針對(duì)路徑冗余點(diǎn)問題，提出了一種改進(jìn)的A＊算法，得到了路徑拐點(diǎn)處最小轉(zhuǎn)彎角，但是，復(fù)雜環(huán)境下算法占用較多內(nèi)存空間的問題仍沒有得到很好解決；文獻(xiàn)[2]通過引入目標(biāo)偏差搜索策略和神經(jīng)網(wǎng)絡(luò)處理機(jī)制，克服了隨機(jī)擴(kuò)展樹法實(shí)時(shí)性差、路徑不平滑的缺陷。隨著外部環(huán)境復(fù)雜性不斷增加，傳統(tǒng)全局路徑規(guī)劃方法面臨內(nèi)存占用加劇、時(shí)效性降低、所得路徑非最優(yōu)解等問題，為此，學(xué)者們將智能優(yōu)化計(jì)算法應(yīng)用于路徑規(guī)劃問題，并得到了大量研究成果。文獻(xiàn)[3]在煙花算法中引入量子行為，提高了算法樣本多樣性和收斂速度，并應(yīng)用于路徑規(guī)劃，仿真結(jié)果也證明了該方案的有效性。然而，智能優(yōu)化算法求解復(fù)雜問題時(shí)收斂效率低、容易產(chǎn)生早熟等問題[7]，降低了路徑規(guī)劃的時(shí)效性和最優(yōu)性。

雞群優(yōu)化（Chicken Swarm Optimization，CSO）算法[8]作為一種全新的群智能優(yōu)化技術(shù)，已被應(yīng)用于電力工程應(yīng)用領(lǐng)域。針對(duì)CSO算法固有缺陷，設(shè)計(jì)動(dòng)態(tài)自確定并行模糊聚類雞群優(yōu)化算法（DMCSO）：在MPI并行運(yùn)行架構(gòu)下，利用動(dòng)態(tài)自確定分類個(gè)數(shù)的核FCM對(duì)雞群種群進(jìn)行聚類分析，建立雞群跟隨關(guān)系，并證DMCSO算法具有良好的種群多樣性。對(duì)于水稻機(jī)器人全局路徑規(guī)劃問題，構(gòu)建基于碰撞威脅度、路徑長度和路徑平滑度等評(píng)價(jià)指標(biāo)的極坐標(biāo)水稻機(jī)器人路徑規(guī)劃模型，最后，采用DMCSO算法對(duì)模型求解。

2 路徑規(guī)劃模型構(gòu)建

2.1 路徑規(guī)劃評(píng)價(jià)指標(biāo)

對(duì)于二維全局路徑規(guī)劃問題，其目的是在路徑起點(diǎn)Xstar(xstar，ystar)和終點(diǎn)Xend(xend，yend)之間尋找一條最優(yōu)或次優(yōu)路徑l(Xstar→Xend)，使得路徑規(guī)劃適應(yīng)度函數(shù)F(l)最優(yōu)。選取碰撞威脅度Lthr(l)、路徑長度Lpɑ(l)和路徑平滑度Lsm(l)構(gòu)建路徑規(guī)劃適應(yīng)度函數(shù)：

式中：ω1、ω2、ω3—權(quán)重系數(shù)。

碰撞威脅度 對(duì)于路徑l(Xstar→Xend)，定義碰撞威脅度Lthr(l)為：

式中：ω—安全因子［9］；(x，y)—路徑l上的點(diǎn)；(xk，yk)、R(k)—第k個(gè)（1≤k≤K）障礙物的坐標(biāo)和最大幾何半徑。

路徑長度 對(duì)于路徑l(Xstar→Xend)，定義路徑長度Lpɑ(l)為：

路徑平滑度 對(duì)于路徑l(Xstar→Xend)，定義路徑平滑度Lsm(l)為：

式中：K(x，y)—路徑l在(x，y)處的曲率。

從路徑規(guī)劃適應(yīng)度函數(shù)定義可以看出，選取碰撞威脅度、路徑長度和路徑平滑度作為評(píng)價(jià)指標(biāo)，使得F（l）取最小值時(shí)，所得機(jī)器人路徑在有效避開障礙物的同時(shí)，路徑長度更短且更加平滑。

2.2 路徑空間描述

為降低路徑規(guī)劃復(fù)雜度，一般將路徑規(guī)劃問題轉(zhuǎn)化為在Xstar(xstar，ystar)與Xend(xend，yend)之間尋找N-1節(jié)點(diǎn)，并按照順序連接組成l(Xstar→Xend)=[Xstar，X1，…，XN-1，Xend為了進(jìn)一步降低路徑規(guī)劃求解維度，對(duì)路徑規(guī)劃空間進(jìn)行極坐標(biāo)處理，如圖1（a）所示。

圖1 極坐標(biāo)處理與種群多樣性分析Fig.1 Polar Coordinate Processing and Population Diversity Analysis

式中：α—l(Xstar→Xend)與x的軸夾角。從式（7）可以看出，只需要得到θi信息就可以確定Xi坐標(biāo)，因此，路徑l(Xstar→Xend)可以用一個(gè)N-1維向量θ=[θ1，…，θN-1]進(jìn)行描述，從而降低了求解維度。此時(shí)，路徑規(guī)劃適應(yīng)度函數(shù)描述為：

3 DMCSO算法實(shí)現(xiàn)及在路徑規(guī)劃中的應(yīng)用

群智能優(yōu)化技術(shù)已被廣泛應(yīng)用于NP-Hard優(yōu)化問題，并展現(xiàn)出了優(yōu)秀的尋優(yōu)能力。在雞群優(yōu)化（CSO）算法的基礎(chǔ)上，設(shè)計(jì)動(dòng)態(tài)自確定并行模糊聚類雞群優(yōu)化算法（DMCSO），重點(diǎn)分析導(dǎo)致算法收斂精度不高和容易產(chǎn)生早熟的原因，并提出改進(jìn)策略（CSO算法基本原理見相關(guān)文獻(xiàn)，不再贅述）。

3.1 動(dòng)態(tài)自確定模糊聚類

FCM算法是目前應(yīng)用最為廣泛的模糊聚類算法之一［10］，但是存在分類數(shù)目事先確定、對(duì)初始聚類中心敏感等缺陷。為此提出動(dòng)態(tài)自確定模糊聚類算法，并對(duì)雞群種群進(jìn)行聚類分析。

其中，定義Θ(s，v)=ΦT(s)Φ(v)為核函數(shù)內(nèi)積，選取Θ(s，v)為：

將式（12）～式（13）代入式（11），分別對(duì)V、U求偏導(dǎo)：

對(duì)式（14）執(zhí)行迭代操作，直至滿足終止條件，從而實(shí)現(xiàn)數(shù)據(jù)聚類分析，使得同一類數(shù)據(jù)具有更多相似性，不同類數(shù)據(jù)具有更多差異性。

動(dòng)態(tài)自確定聚類個(gè)數(shù) 為了克服核FCM實(shí)現(xiàn)確定聚類個(gè)數(shù)的缺陷，根據(jù)內(nèi)核誘導(dǎo)距離，定義“自確定因子Δ(C)”：

式中：|C(i)|—第i個(gè)聚類中數(shù)據(jù)個(gè)數(shù)。

3.2 基于動(dòng)態(tài)自確定模糊聚類的雞群迭代更新

CSO算法模擬雞群覓食行為，通過建立內(nèi)部社會(huì)關(guān)系，賦予個(gè)體不同進(jìn)化策略，進(jìn)而得到全局最優(yōu)解。隨著CSO算法迭代次數(shù)不斷增加，種群樣本多樣性逐漸降低，如果個(gè)體Pi（如圖1（b）所示）選擇與自身空間特性相近的個(gè)體Pj進(jìn)行學(xué)習(xí)更新，則更新后的Pi，new空間位置變化不大；如果選擇與自身空間特性相差較大的個(gè)體Pk進(jìn)行學(xué)習(xí)更新，則更新后的增加了算法搜索空間。特別的，當(dāng)Pj處于局部極值空間范圍內(nèi)時(shí)，很容易導(dǎo)致算法陷入局部最優(yōu)，導(dǎo)致產(chǎn)生早熟現(xiàn)象。可見，合理科學(xué)選取個(gè)體學(xué)習(xí)進(jìn)化對(duì)象，對(duì)保持種群樣本多樣性具有重要意義，為此選取動(dòng)態(tài)自確定模糊聚類方法對(duì)種群進(jìn)行聚類分析，并在此基礎(chǔ)上建立雞群跟隨關(guān)系，執(zhí)行迭代進(jìn)化操作：

（1）聚類分析：對(duì)雞群執(zhí)行動(dòng)態(tài)自確定模糊聚類操作，得到C個(gè)子種群。

（2）角色劃定：設(shè)定每個(gè)子種群內(nèi)適應(yīng)度最優(yōu)的個(gè)體為“公雞”，適應(yīng)度最差的χ個(gè)個(gè)體為“小雞”，其余為“母雞。

（3）建立跟隨關(guān)系：在第i個(gè)子種群內(nèi)，選擇作為跟隨對(duì)象，選擇適應(yīng)度最佳的跟隨對(duì)象。

（4）進(jìn)化更新：對(duì)于第i個(gè)子種群分別執(zhí)行G輪CSO算法進(jìn)化更新操作。

（5）終止判定：判定是否滿足終止條件，若滿足則終止算法，否則返回（1）。

結(jié)論1 基于動(dòng)態(tài)自確定模糊聚類的CSO算法具有較高的種群多樣性

證明：對(duì)于具有P個(gè)個(gè)體的雞群，每個(gè)個(gè)體維度為N，即P(p1，…，pN)，t時(shí)刻，種群多樣性為：

式（20）表明，(t)決定了雞群的種群多樣性，通過對(duì)雞群種群樣本多樣性分析，基于動(dòng)態(tài)自確定模糊聚類能夠提高個(gè)體學(xué)習(xí)對(duì)象選取的合理性科學(xué)性，從而使得改進(jìn)后的CSO算法具有更好的樣本多樣性。

基于動(dòng)態(tài)自確定模糊聚類的CSO算法的計(jì)算復(fù)雜度 種群初始化復(fù)雜度為O(PN)，每次執(zhí)行動(dòng)態(tài)自確定模糊聚類操作復(fù)雜度為tmax(Cmax-1)O(P（)tmax為模糊聚類最大迭代次數(shù)），執(zhí)行個(gè)體更新復(fù)雜度為G×O(PN)。算法總計(jì)算復(fù)雜度為（當(dāng)N?P）：

3.3 MPI并行運(yùn)算架構(gòu)

從式（21）可以看出，基于動(dòng)態(tài)自確定模糊聚類的CSO算法雖然具有較高種群多樣性，但是算法計(jì)算復(fù)雜度較高，主要原因是每次迭代需要執(zhí)行Cmax次動(dòng)態(tài)自確定模糊聚類操作，為此構(gòu)建MPI［11］并行運(yùn)算架構(gòu)：搭建具有Cmax個(gè)節(jié)點(diǎn)的局域網(wǎng)，其中一個(gè)為中心節(jié)點(diǎn)，主要執(zhí)行種群初始化、模糊聚類初始化、最佳聚類個(gè)數(shù)判定、雞群跟隨關(guān)系建立、算法終止條件判定等操作，其余節(jié)點(diǎn)為邊緣節(jié)點(diǎn)，主要執(zhí)行核FCM聚類操作、G輪雞群個(gè)體更新等操作。

3.4 基于DMCSO算法的路徑規(guī)劃實(shí)現(xiàn)

個(gè)體編碼 對(duì)于路徑規(guī)劃規(guī)劃問題，DMCSO算法個(gè)體編碼定義為P(θ1，…，θN-1)。

適應(yīng)度函數(shù) 對(duì)于路徑規(guī)劃規(guī)劃問題，定義DMCSO算法的適應(yīng)度函數(shù)為：

基于DMCSO算法的路徑規(guī)劃實(shí)現(xiàn)流程圖，如圖2所示。

圖2 基于DMCSO算法的路徑規(guī)劃實(shí)現(xiàn)流程Fig.2 Implementation Flow of Path Planning based on DMCSO Algorithm

4 實(shí)驗(yàn)仿真

4.1 DMCSO算法性能驗(yàn)證

為了驗(yàn)證DMCSO算法性能，采用4種經(jīng)典測(cè)試函數(shù)f1：Sphere、f2：Ackley、f3：Griewank和f4：Rastrigrin進(jìn)行測(cè)試，并選取基本CSO算法、量子粒子群優(yōu)化算法（QPSO）和改進(jìn)灰狼優(yōu)化算法（IGWO）[7]進(jìn)行對(duì)比試驗(yàn)。DMCSO算法參數(shù)設(shè)置如下：雞群規(guī)模P=300、χ=20、G=10、算法最大迭代次數(shù)Tmax=500。每種算法獨(dú)立運(yùn)行50次，評(píng)價(jià)指標(biāo)為求解成功率V、均值A(chǔ)v、標(biāo)準(zhǔn)差St和運(yùn)算時(shí)間T。4種經(jīng)典測(cè)試函數(shù)收斂曲線，如圖3～圖6所示。評(píng)價(jià)指標(biāo)對(duì)比結(jié)果，如表1所示。

表1 評(píng)價(jià)指標(biāo)對(duì)比結(jié)果Tab.1 Comparison Results of Evaluation Indexes

圖3 f1函數(shù)收斂曲線Fig.3 f1 Convergence Curve

圖4 f2函數(shù)收斂曲線Fig.4 f2 Convergence Curve

圖5 f3函數(shù)收斂曲線Fig.5 f3 Convergence Curve

圖6 f4函數(shù)收斂曲線Fig.6 f4 Convergence Curve

4.2 機(jī)器人路徑規(guī)劃實(shí)例仿真

采用DMCSO算法對(duì)水稻機(jī)器人路徑規(guī)劃問題進(jìn)行研究，將農(nóng)田抽象為二維平面內(nèi)的方形區(qū)域，障礙物等效為圓柱體及長方體，并在MATLAB平臺(tái)上對(duì)不同應(yīng)用場(chǎng)景進(jìn)行仿真。

情景1：設(shè)定Xstar(15，24)、Xend(46，54)，障礙物為圓柱體。

情景2：設(shè)定Xstar(10，35)、Xend(60，55)，障礙物為長方體。

分別采用文獻(xiàn)[1]和文獻(xiàn)[6]提出的路徑規(guī)劃方法進(jìn)行對(duì)比試驗(yàn)，每種方法獨(dú)立運(yùn)行10次，取平均路徑距離ˉL、平均規(guī)劃時(shí)間ˉT進(jìn)行對(duì)比分析，對(duì)比結(jié)果，如表2所示。不同規(guī)劃方法得到的路徑結(jié)果，如圖7～圖8所示。

表2 平均路徑距離、平均規(guī)劃時(shí)間對(duì)比Tab.2 Comparison of Average Path Distance and Average Planning Time

圖7 情景1下仿真比較Fig.7 Simulation Comparison under Scenario 1

圖8 情景2下仿真比較Fig.8 Simulation Comparison under Scenario 2

4.3 實(shí)例（結(jié)果）分析

（1）DMCSO具有較高的收斂精度。從圖3～圖6和表1可以看出，DMCSO算法無論是求解成功率、最優(yōu)解平均值，還是標(biāo)準(zhǔn)差都要好于QPSO算法和IGWO算法，而CSO算法表現(xiàn)最差，特別的，對(duì)于函數(shù)f4，DMCSO算法求解成功率達(dá)到了100%，而其他三種算法最好的求解成功率才只有16%。

（2）DMCSO具有較快的運(yùn)算速度。從圖3～圖6和表1可以看出，DMCSO算法同樣要快于其它3種算法。特別的，對(duì)于高維復(fù)雜函數(shù)f4，相比于CSO、QPSO和IGWO，DMCSO運(yùn)算速度分別提高了26.9%、13.1%和12.2%。

（3）基于DMCSO算法的路徑規(guī)劃具有更好地路徑長度和運(yùn)算時(shí)間。從表2及圖3～圖6可以看出，不同仿真情景下，得到的路徑長度、運(yùn)算時(shí)間要好于其他兩種方法，其中路徑長度降低了約（15.9～26.5）%，運(yùn)算時(shí)間降低了約（20.3～44.3）%，而且，得到的路徑具有更好地平滑度。

（4）之所以DMCSO算法具較好的優(yōu)化性能，是因?yàn)閯?dòng)態(tài)自確定模糊聚類的引入，克服了模糊聚類算法不能自動(dòng)確定聚類個(gè)數(shù)的缺陷，提高了個(gè)體學(xué)習(xí)對(duì)象選取的合理性科學(xué)性，進(jìn)而提升了算法全局深度搜索能力，并且MPI并行架構(gòu)的構(gòu)建，將算法迭代過程分布在多個(gè)線程中，很大程度降低了算法運(yùn)行時(shí)間。仿真結(jié)果有效驗(yàn)證了基于動(dòng)態(tài)自確定并行模糊聚類雞群優(yōu)化算法的機(jī)器人路徑規(guī)劃的方法可行性。

5 結(jié)語

提出了一種基于動(dòng)態(tài)自確定并行模糊聚類雞群優(yōu)化算法的水稻機(jī)器人路徑規(guī)劃方法。通過構(gòu)建路徑規(guī)劃模型、設(shè)計(jì)動(dòng)態(tài)自確定分類個(gè)數(shù)的核FCM和建立MPI并行架構(gòu)，有效提高了CSO算法求解高維復(fù)雜問題的優(yōu)化性能，為機(jī)器人路徑規(guī)劃問題提供了更有效的解決方法，仿真結(jié)果表明，所提路徑規(guī)劃方法更具可行性和合理性，路徑長度降低了約（15.9～26.5）%，運(yùn)算時(shí)間降低了約（20.3～44.3）%，具有一定的實(shí)際應(yīng)用價(jià)值。