国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

混合遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用

2023-11-28 06:13:54白曉蘭周文全張振朋
關(guān)鍵詞:柵格障礙物適應(yīng)度

白曉蘭,袁 錚,周文全,張振朋

(沈陽化工大學(xué)機(jī)械與動(dòng)力工程學(xué)院,沈陽 110142)

0 引言

移動(dòng)機(jī)器人通過路徑規(guī)劃算法得到一條或者多條滿足機(jī)器人當(dāng)前工作任務(wù)要求的最佳路徑,保障機(jī)器人可以在真實(shí)的環(huán)境下高效,安全的完成工作任務(wù)。評價(jià)路徑的好壞的指標(biāo)一般是指機(jī)器人有無碰撞、路徑的長短、計(jì)算時(shí)間的長短、能源損耗的大小等[1]。路徑規(guī)劃技術(shù)作為移動(dòng)機(jī)器人的核心技術(shù)之一,成為國內(nèi)外研究的熱門技術(shù)。主流的路徑規(guī)劃算法主要包括:以人工勢場法[2]、A*算法[3]、快速搜索隨機(jī)樹算法[4]等為主的傳統(tǒng)規(guī)劃算法和以粒子群算法、遺傳算法、人工魚群算法[5]等為主的智能仿生優(yōu)化算法。

智能仿生算法具有全局搜索能力強(qiáng)、運(yùn)算速度快、擴(kuò)展性強(qiáng)等特點(diǎn)。ZHANG等[6]采用可變周期余弦慣性權(quán)重,通過周期的不斷變化,非線性調(diào)整慣性參數(shù)的大小。MA等[7]提出了混合量子行為粒子群優(yōu)化算法。該算法改進(jìn)了組合導(dǎo)航下UUV的位置和姿態(tài)誤差傳遞模型,對導(dǎo)航誤差的進(jìn)行修正。XU等[8]提出了一種基于新的四次貝塞爾過渡曲線和改進(jìn)的粒子群優(yōu)化算法的移動(dòng)機(jī)器人平滑路徑規(guī)劃方法。創(chuàng)造了一條具有3個(gè)重疊控制點(diǎn)的四次貝塞爾過渡曲線。楊琛等[9]提出一種多目標(biāo)粒子群-蟻群無人艇路徑規(guī)劃算法,引入迭代因子和正切函數(shù)調(diào)整慣性參數(shù)和學(xué)習(xí)因子。張錚等[10]在種群初始化階段結(jié)合限制性均勻隨機(jī)搜索算法得到均勻節(jié)點(diǎn)庫,建立步長最大值。引入自適應(yīng)進(jìn)化判斷操作分析種群進(jìn)化狀態(tài),提高迭代效率和穩(wěn)定性。ZHAI等[11]引入模擬退火算法,有效地避免了搜索過程陷入局部最優(yōu)解的問題。馮豪博等[12]在適應(yīng)度函數(shù)中,加入顯性基因和隱性基因確保路徑的寬度適用于航行器集群。

然而,上述研究不僅未考慮機(jī)器人在實(shí)際運(yùn)動(dòng)環(huán)境中的現(xiàn)實(shí)問題,而且對于遺傳算法與粒子群算法的改進(jìn)主要通過改進(jìn)基本算法的操作或是簡單的融合,這增加了算法的計(jì)算時(shí)間。因此,本文提出了一種混合遺傳算法。考慮到路徑安全問題,該算法優(yōu)化障礙物參數(shù)和適應(yīng)度函數(shù),引入防碰撞距離與安全距離,加強(qiáng)了路徑安全性;通過構(gòu)建綜合評價(jià)值、迭代次數(shù)與慣性權(quán)重和交叉變異的關(guān)系,動(dòng)態(tài)調(diào)整慣性權(quán)重和自適應(yīng)的交叉變異概率;然后利用分群策略、等級交叉變異策略和人工勢場法來改進(jìn)交叉變異操作,增強(qiáng)算法搜索效率,加速收斂過程,提高算法對全局和局部特征的尋優(yōu)能力。

1 環(huán)境模型

1.1 建立環(huán)境模型

本文采用柵格圖法模擬移動(dòng)機(jī)器人的工作場景。圖1為柵格地圖,在柵格地圖中,白色區(qū)域?yàn)檫\(yùn)動(dòng)區(qū)域,黑色區(qū)域?yàn)檎系K物區(qū)域,機(jī)器人在有限的二維空間中通過選取運(yùn)動(dòng)區(qū)域中柵格作為路徑節(jié)點(diǎn),并將若干個(gè)節(jié)點(diǎn)相連接后得到一條從起點(diǎn)到終點(diǎn)的不經(jīng)過障礙物區(qū)域的路徑。

圖1 柵格地圖

1.2 障礙物處理

為更好的發(fā)揮算法的性能,通常在模擬環(huán)境中會(huì)將機(jī)器人看作一個(gè)質(zhì)點(diǎn)。但是,在實(shí)際環(huán)境中如果忽略掉機(jī)器人自身的體積,會(huì)產(chǎn)生機(jī)器人和障礙物碰撞的可能,為確保路徑規(guī)劃的安全性,本文從機(jī)器人的長寬方向取長度的最大值并將最大值的1/2作為防碰撞距離添加到障礙物模型中,得到的新的障礙物模型如圖2所示。

圖2 新障礙物模型

1.3 編碼方式

為了減少算法的計(jì)算量,降低運(yùn)算時(shí)間并更好的適配融合算法,本文采用實(shí)數(shù)編碼的方式。圖3為柵格地圖編號(hào)。

圖3 地圖編號(hào)

編號(hào)An與坐標(biāo)(xn,yn)的關(guān)系為:

(1)

An=L*(xn-1/2)+(yn+1/2)

(2)

式中:L表示柵格地圖的行數(shù)。

2 適應(yīng)度函數(shù)

2.1 構(gòu)建適應(yīng)度函數(shù)

本文算法以路徑長度、路徑安全度、路徑平滑度和路徑拐點(diǎn)數(shù)量4個(gè)方面作為評價(jià)指標(biāo)得到的適應(yīng)度值函數(shù)F如式(3)所示。

(3)

式中:f為綜合評價(jià)函數(shù),其大小為綜合評價(jià)值;α1、α2、α3、α4分別為路徑長度、安全度、平滑度和拐點(diǎn)數(shù)量的權(quán)重參數(shù)。

2.2 路徑長度評價(jià)函數(shù)

路徑的總長度為f1,路徑長度的評價(jià)函數(shù)為路徑總長度的倒數(shù)。

(4)

2.3 路徑安全度評價(jià)函數(shù)

本文算法引入了安全距離da,要求路徑與障礙物之間的距離d必須大于安全距離da。本文路徑安全度評價(jià)函數(shù)f2如式(5)所示。

(5)

式中:d為路徑點(diǎn)與障礙物之間的距離。

2.4 路徑平滑度評價(jià)函數(shù)

在路徑拐點(diǎn)處的3個(gè)連續(xù)柵格為Aj-1、Aj、Aj+1,它們的坐標(biāo)分別為(xj-1,yj-1)、(xj,yj)、(xj+1,yj+1),利用余弦定理可以求出拐點(diǎn)處3個(gè)連續(xù)柵格的夾角的余弦值的大小。圖4為拐點(diǎn)處夾角的示意圖。

圖4 拐點(diǎn)處夾角

通過坐標(biāo)求夾角余弦值大小的公式為:

(6)

(7)

機(jī)器人在運(yùn)動(dòng)時(shí),轉(zhuǎn)彎的情況是不可避免地。當(dāng)轉(zhuǎn)角越大時(shí)路徑的平滑度就越大,轉(zhuǎn)角越小機(jī)器人轉(zhuǎn)彎的難度就越大,安全性低。因?yàn)橛嘞抑档拇笮≡赱0,π]內(nèi)是單調(diào)遞減的,所以本文在設(shè)計(jì)路徑平滑度評價(jià)函數(shù)時(shí)根據(jù)轉(zhuǎn)角θ的余弦值的大小設(shè)計(jì)獎(jiǎng)勵(lì)函數(shù),路徑平滑度評價(jià)函數(shù)如式(8)所示。

(8)

式中:cosθ為任意3個(gè)連續(xù)路徑節(jié)點(diǎn)的余弦值。

2.5 拐點(diǎn)評價(jià)函數(shù)

移動(dòng)機(jī)器人在運(yùn)動(dòng)過程中遇到拐點(diǎn)時(shí)會(huì)存在速度變化,因此路徑中的多余拐點(diǎn)會(huì)增加移動(dòng)機(jī)器人的能耗。為減少路徑中多余拐點(diǎn)的數(shù)量,本文設(shè)置了針對拐點(diǎn)數(shù)量的懲罰函數(shù),當(dāng)拐點(diǎn)數(shù)量越少,綜合評價(jià)函數(shù)的值越高。路徑拐點(diǎn)數(shù)量評價(jià)函數(shù)為:

(9)

3 混合算法的設(shè)計(jì)

3.1 改進(jìn)粒子群算法

3.1.1 傳統(tǒng)粒子群算法

傳統(tǒng)粒子群算法通過仿真粒子群來模擬鳥群覓食行為。在解空間中存在n個(gè)粒子,每個(gè)粒子具備速度和位置兩個(gè)屬性[14]。每個(gè)粒子通過式(10)和式(11)迭代更新自身速度和位置,在達(dá)到最大迭代次數(shù)Tmax時(shí)結(jié)束算法。

(10)

(11)

3.1.2 改進(jìn)慣性權(quán)重ω

本文提出一種依靠迭代次數(shù)和綜合評價(jià)值來動(dòng)態(tài)調(diào)整慣性權(quán)重ω值的方法。按照迭代次數(shù)的大小分為兩種情況:①當(dāng)粒子迭代次數(shù)未達(dá)到最大迭代次數(shù)的一半時(shí),不考慮綜合評價(jià)值的影響。②當(dāng)粒子迭代次數(shù)達(dá)到最大迭代次數(shù)的一半時(shí),將綜合評價(jià)值作為主要因素。如果粒子的綜合評價(jià)值大于平均值,降低慣性權(quán)重ω的大小來增強(qiáng)粒子局部尋優(yōu)的能力。如果粒子的綜合評價(jià)值低于平均值,增加慣性權(quán)重ω的大小來增強(qiáng)粒子全局尋優(yōu)的能力,ω的動(dòng)態(tài)調(diào)整公式為:

(12)

式中:ωm代表最大慣性權(quán)重,ωs代表最小慣性權(quán)重,Ti表示粒子i迭代次數(shù),Tmax表示最大迭代次數(shù),fi為粒子i的綜合評價(jià)值,fa為綜合評價(jià)平均值,fmax表示最大綜合評價(jià)值,fmin表示最小綜合評價(jià)值。

3.2 改進(jìn)遺傳算法

本文提出了一種將遺傳算法與粒子群算法融合的方法:首先,計(jì)算粒子的適應(yīng)度值,評估粒子群質(zhì)量;其次,將改進(jìn)粒子群算法中的粒子根據(jù)分群策略分為一等種群、二等種群、三等種群;最后,對粒子執(zhí)行交叉操作,再次計(jì)算粒子的適應(yīng)度值。其中,分群策略就是通過比較粒子的適應(yīng)度值進(jìn)而將種群排序并分類的方法,具體的種群分類方法如圖5所示。

圖5 分群策略

3.2.1 交叉操作

前文中,種群跟據(jù)分群策略分為一等種群、二等種群、三等種群。在此基礎(chǔ)上本文提出了一種等級交叉策略來改進(jìn)交叉操作,具體操作步驟為:

步驟1:三等種群個(gè)體在執(zhí)行交叉操作時(shí),均采用兩點(diǎn)交叉的方法,在選擇交叉點(diǎn)時(shí)為了保證路徑的連續(xù)性,兩個(gè)個(gè)體的交叉點(diǎn)需編號(hào)相同或互在鄰域內(nèi),結(jié)束交叉操作后,對新個(gè)體和父代個(gè)體按照適應(yīng)度值大小排序,僅保留適應(yīng)度值最優(yōu)的個(gè)體;

步驟2:二等種群個(gè)體與種群內(nèi)部個(gè)體或與一等種群個(gè)體通過單點(diǎn)交叉執(zhí)行交叉操作;

步驟3:一等種群內(nèi)部采用單點(diǎn)交叉方式執(zhí)行交叉操作并保留父代個(gè)體。交叉操作如圖6和圖7所示。

圖6 兩點(diǎn)交叉操作

3.2.2 變異操作

變異操作是指在種群的某個(gè)個(gè)體中,基因點(diǎn)發(fā)生突變以提高種群多樣性,防止陷入局部最優(yōu)解的行為。本文提出了一種等級變異策略優(yōu)化變異操作。為快速提高三等種群的個(gè)體的質(zhì)量,對個(gè)體中的路徑點(diǎn)采取多點(diǎn)變異的方式。對一等種群和二等種群中的個(gè)體采用單點(diǎn)變異的方式。由于傳統(tǒng)的變異操作是在變異點(diǎn)的8鄰域內(nèi)隨機(jī)變化,因此本文引入人工勢場法來限制變異的方向。人工勢場法就是將機(jī)器人的工作場景設(shè)計(jì)成勢力場,機(jī)器人在受到目標(biāo)點(diǎn)產(chǎn)生的引力和障礙物產(chǎn)生的斥力的作用下運(yùn)動(dòng)。式(13)~式(15)分別表示勢場中的引力、斥力與合力。

Faat(x)=-η(q-qg)

(13)

(14)

F=Faat+Freq

(15)

式中:q為當(dāng)前點(diǎn),qg為目標(biāo)點(diǎn),ρ0為障礙物影響距離,ρ(q)為當(dāng)前點(diǎn)當(dāng)障礙物的距離,合力F為矢量。

當(dāng)變異點(diǎn)附近存在障礙物時(shí),根據(jù)人工勢場法可以得到一個(gè)合力的方向。從圖8中我們可以看出個(gè)體進(jìn)行變異操作時(shí)按照合力方向會(huì)得到新的路徑點(diǎn)(圖中灰色區(qū)域),變異后的路徑(圖中深灰色虛線所示)會(huì)跳出障礙物群。通過這種方式進(jìn)行變異操作的個(gè)體得到的路徑更短更安全,更容易跳出局部最優(yōu)解。

圖8 變異操作示意圖

3.2.3 自適應(yīng)調(diào)整概率參數(shù)

傳統(tǒng)遺傳算法中,交叉概率Pc和變異概率Pm通常為固定值,對于加快種群收斂,提高跳出局部最優(yōu)的能力有限。因?yàn)橐坏确N群的種群質(zhì)量較高,二等、三等種群的質(zhì)量較低,所以本文將一等種群和二等、三等種群分開,限制一等種群的交叉與變異概率,增加二、三等種群的交叉與變異概率。本文設(shè)計(jì)的自適應(yīng)交叉變異概率的具體表達(dá)式為:

(16)

(17)

式中:Pcm為最大交叉概率,Pcs為最小交叉概率,fj為個(gè)體j的綜合評價(jià)值,Pmm為最大變異概率,Pms為最小變異概率。

3.3 混合算法步驟

混合遺傳算法(PA-GA)的具體步驟為:

步驟1:利用柵格圖法建立二維地圖模型,標(biāo)記地圖的起點(diǎn)與終點(diǎn);

步驟2:初始化改進(jìn)粒子群算法參數(shù)值;

步驟3:通過式(3)求出群體最大綜合評價(jià)值和最小綜合評價(jià)值;計(jì)算粒子個(gè)體適應(yīng)度值;

步驟4:根據(jù)式(10)和式(11)更新個(gè)體和群體最優(yōu)位置,通過式(12)計(jì)算慣性權(quán)重ω的值;

步驟5:將種群根據(jù)分群策略分類;

步驟6:根據(jù)式(16)和式(17)計(jì)算交叉和變異概率,執(zhí)行交叉和變異操作;

步驟7:再次計(jì)算粒子的適應(yīng)度值,求出最大適應(yīng)度值和最小適應(yīng)度值;

步驟8:判斷是否滿足收斂條件,若不滿足,則回到步驟4。若滿足,則終止算法。

4 仿真驗(yàn)證

為了驗(yàn)證本文所提出的PA-GA算法的穩(wěn)定性和高效性,本文在MATLAB軟件上建立仿真環(huán)境模型,對PA-GA算法、基本GA算法、基本PSO算法和GA-PSO算法進(jìn)行測驗(yàn),通過對測驗(yàn)結(jié)果進(jìn)行對比分析進(jìn)而驗(yàn)證該算法的尋優(yōu)能力。測試環(huán)境為Windows11 64位操作系統(tǒng),MATLAB R2020b軟件,處理器為Intel i7-12700H。

4種算法的粒子群或種群規(guī)模為50,最大迭代次數(shù)Tmax為100,PA-GA算法中主要參數(shù)如表1所示。

表1 PA-GA算法參數(shù)

基本GA算法、基本PSO算法和GA-PSO算法的主要參數(shù)如表2所示。

表2 GA、PSO、GA-PSO算法參數(shù)

路徑仿真實(shí)驗(yàn)在20×20的柵格地圖中進(jìn)行。為增強(qiáng)仿真結(jié)果的可靠性,本文對上述4中算法分別測驗(yàn)了50次,記錄每種算法的最短運(yùn)行時(shí)間、最短路徑和平均運(yùn)算時(shí)間。路徑仿真實(shí)驗(yàn)的數(shù)據(jù)如表3所示,路徑圖如圖9所示。

(a) PA-GA算法 (b) GA-PSO算法

(c) GA算法(d) PSO算法

表3 仿真結(jié)果對比

從表3中可以看出,本文提出的PA-GA算法的最短運(yùn)行時(shí)間為2.384 2 s,相較于傳統(tǒng)GA算法的最短運(yùn)算時(shí)間提升了約16.4%。平均運(yùn)行時(shí)間為2.374 1 s,相較于PSO算法的平均運(yùn)算時(shí)間提升了約12.7%。規(guī)劃的最短路徑為30.384 8,相較于其他3種算法分別提升了約25.4%、21.6%和11.3%。綜合結(jié)果來看PA-GA算法的尋優(yōu)能力更強(qiáng)。

圖10為4種算法的迭代收斂過程,從圖中可以看出,PA-GA算法在迭代20次左右就已經(jīng)收斂,而GA-PSO算法、GA算法和PSO算法則分別在迭代26次、30次和32次收斂。從上述結(jié)果中可以看出PA-GA算法的搜索能力更強(qiáng),收斂速度更快。

(a) PA-GA算法 (b) GA-PSO算法

(c) GA算法(d) PSO算法

5 結(jié)論

本文針對移動(dòng)機(jī)器人在實(shí)際運(yùn)行過程中存在的安全及能耗問題,提出了一種結(jié)合粒子群算法、遺傳算法與人工勢場法的PA-GA算法。該算法在構(gòu)造適應(yīng)度函數(shù)時(shí)考慮到路徑拐點(diǎn)、安全距離以及路徑平滑度等實(shí)際情況中存在的問題,利用獎(jiǎng)勵(lì)函數(shù)和懲罰函數(shù)對上述問題加以約束;通過多種改進(jìn)策略對交叉和變異操作進(jìn)行調(diào)整,改進(jìn)慣性權(quán)重的影響,優(yōu)化了算法的全局尋優(yōu)能力和局部尋優(yōu)能力。由于機(jī)器人的實(shí)際運(yùn)動(dòng)場景一般為動(dòng)態(tài)環(huán)境,因此在后續(xù)的研究中需要進(jìn)一步驗(yàn)證該算法在動(dòng)態(tài)環(huán)境中的尋優(yōu)能力。

猜你喜歡
柵格障礙物適應(yīng)度
改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法
基于鄰域柵格篩選的點(diǎn)云邊緣點(diǎn)提取方法*
高低翻越
SelTrac?CBTC系統(tǒng)中非通信障礙物的設(shè)計(jì)和處理
基于空調(diào)導(dǎo)風(fēng)板成型工藝的Kriging模型適應(yīng)度研究
中國塑料(2016年11期)2016-04-16 05:26:02
不同剖面形狀的柵格壁對柵格翼氣動(dòng)特性的影響
基于CVT排布的非周期柵格密度加權(quán)陣設(shè)計(jì)
土釘墻在近障礙物的地下車行通道工程中的應(yīng)用
少數(shù)民族大學(xué)生文化適應(yīng)度調(diào)查
動(dòng)態(tài)柵格劃分的光線追蹤場景繪制
同心县| 惠来县| 鲁山县| 灵丘县| 天全县| 江都市| 武威市| 习水县| 莱西市| 东乌| 阿图什市| 禹州市| 乐都县| 尚志市| 资兴市| 江口县| 灵川县| 九寨沟县| 龙陵县| 黔西县| 太湖县| 金寨县| 柳河县| 缙云县| 阿巴嘎旗| 塘沽区| 城固县| 新乡县| 林甸县| 洪江市| 卢龙县| 柳州市| 灵寿县| 通许县| 泽库县| 长兴县| 德庆县| 西和县| 道真| 景谷| 宜宾县|