葛 唱，錢(qián)素琴

改進(jìn)麻雀搜索算法的無(wú)人車(chē)路徑規(guī)劃

葛 唱，錢(qián)素琴

（東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海 201620）

針對(duì)麻雀搜索算法后期容易早熟，易陷入局部最優(yōu)后搜索能力下降的不足，提出了一種結(jié)合伯努利（Bernoulli）映射和禁忌搜索算法的改進(jìn)麻雀搜索算法。改進(jìn)麻雀搜索算法在初始化階段，使用Bernoulli映射初始化種群位置，取代傳統(tǒng)算法初始化階段采用隨機(jī)數(shù)的方式，優(yōu)化了種群分布不均，搜索范圍不足的問(wèn)題，同時(shí)當(dāng)超過(guò)一定迭代次數(shù)全局最優(yōu)值仍沒(méi)有更新時(shí)再次使用Bernoulli映射對(duì)種群進(jìn)行擾動(dòng)增強(qiáng)全局搜索能力，在算法進(jìn)入后期尋優(yōu)階段時(shí)使用禁忌搜索算法，應(yīng)用其禁忌準(zhǔn)則和特赦準(zhǔn)則的結(jié)構(gòu)實(shí)現(xiàn)良好的全局搜索能力。然后將該算法應(yīng)用到無(wú)人車(chē)全局路徑規(guī)劃問(wèn)題中，并進(jìn)行了實(shí)驗(yàn)驗(yàn)證其有效性。實(shí)驗(yàn)結(jié)果表明改進(jìn)后的麻雀搜索算法擁有更好的全局搜索能力和更高的精度。

無(wú)人車(chē)；路徑規(guī)劃；改進(jìn)麻雀搜索算法；混沌映射；禁忌算法

0 引言

隨著當(dāng)今社會(huì)科技水平的迅猛發(fā)展，自動(dòng)駕駛車(chē)輛已漸漸成為熱點(diǎn)話(huà)題。如今的自動(dòng)駕駛技術(shù)不僅只存在于實(shí)驗(yàn)室中，同時(shí)在近幾年隨著各個(gè)廠商的新車(chē)發(fā)布，成為各個(gè)廠商新車(chē)的賣(mài)點(diǎn)。自動(dòng)駕駛車(chē)輛可分為6個(gè)級(jí)別：無(wú)自動(dòng)化、駕駛員輔助、部分自動(dòng)化、條件自動(dòng)化、高度自動(dòng)化、全自動(dòng)化。如今實(shí)現(xiàn)部分自動(dòng)化級(jí)別的新車(chē)已成功上市，還有些廠商聲明已經(jīng)可以實(shí)現(xiàn)高度自動(dòng)化級(jí)別，而路徑規(guī)劃作為自動(dòng)駕駛車(chē)輛中極為重要的一環(huán)，如何更快更好地獲得最優(yōu)路徑也已成為當(dāng)前的研究熱點(diǎn)。路徑規(guī)劃問(wèn)題[1-2]主要是讓目標(biāo)對(duì)象在有多個(gè)障礙物的復(fù)雜環(huán)境中找到一條從起始點(diǎn)到目標(biāo)點(diǎn)的安全無(wú)碰撞路徑?，F(xiàn)在處理路徑規(guī)劃問(wèn)題的常用算法主要分為2大類(lèi)：傳統(tǒng)路徑規(guī)劃算法，如迪克斯特拉算法（Dijkstra）[3]、A*算法[4]、人工勢(shì)場(chǎng)法[5]等；部分群智能優(yōu)化算法，如蟻群算法[6-7]、粒子群算法[8-9]、遺傳算法[10]、麻雀算法等。

為了進(jìn)一步增強(qiáng)算法的性能，學(xué)者們已經(jīng)提出各種策略結(jié)合現(xiàn)有的方法來(lái)更好地解決路徑規(guī)劃問(wèn)題。付興武等人將粒子群算法和天牛須算法結(jié)合，降低了收斂值，有效地縮短了路徑長(zhǎng)度[11]。王輝等人引入新的距離啟發(fā)函數(shù)因子、調(diào)整狀態(tài)轉(zhuǎn)移概率等對(duì)傳統(tǒng)蟻群進(jìn)行優(yōu)化改進(jìn)，并將其應(yīng)用到存取車(chē)的路徑規(guī)劃問(wèn)題中，得到了更強(qiáng)的全局搜索性能和更快的收斂速度[12]。麻雀搜索算法是2020年提出的一種新型群智能優(yōu)化算法，主要受到麻雀的覓食行為和覓食過(guò)程中的警戒行為的啟發(fā)，具有收斂速度快、局部搜索能力強(qiáng)、參數(shù)少等特點(diǎn)，在圖像處理、機(jī)器人控制、路徑規(guī)劃等領(lǐng)域均有一定的研究。湯安迪等人對(duì)傳統(tǒng)麻雀搜索算法進(jìn)行改進(jìn)，采用了立方映射初始化種群，并使用反向?qū)W習(xí)策略引入精英粒子，增強(qiáng)了種群的多樣性，擴(kuò)大搜索區(qū)域范圍，并應(yīng)用到無(wú)人機(jī)的航跡規(guī)劃問(wèn)題中[13]。綜合現(xiàn)有的研究成果，本文提出了一種結(jié)合伯努利（Bernoulli）映射與禁忌搜索算法的改進(jìn)麻雀搜索算法：使用Bernoulli映射初始化種群位置，取代傳統(tǒng)算法初始化階段采用隨機(jī)數(shù)的方式，并且與湯安迪等人采用的立方映射相比，Bernoulli映射遍歷性更強(qiáng)，在整個(gè)環(huán)境建模中分布更均勻，優(yōu)化了種群分布不均、搜索范圍不足的問(wèn)題；同時(shí)當(dāng)超過(guò)一定迭代次數(shù)全局最優(yōu)值仍沒(méi)有更新時(shí)，再次使用Bernoulli映射對(duì)種群進(jìn)行擾動(dòng)，增強(qiáng)算法的全局搜索能力和收斂速度，降低算法陷入局部最優(yōu)而無(wú)法跳出的可能性，并在后期尋優(yōu)階段引入禁忌算法進(jìn)一步提高算法的精度；最后將該算法引入無(wú)人車(chē)路徑規(guī)劃中。

1 麻雀搜索算法

2 對(duì)麻雀搜索算法的改進(jìn)

傳統(tǒng)的麻雀算法在麻雀種群初始化階段采用的是生成隨機(jī)數(shù)的方式進(jìn)行初始化種群位置，導(dǎo)致種群中麻雀的位置良莠不齊，同時(shí)不能遍歷環(huán)境中的所有位置，導(dǎo)致其收斂速度較低。所以本文提出在種群初始化階段引入Bernoulli映射。Bernoulli映射屬于混沌映射的一種，常被用來(lái)產(chǎn)生混沌序列，其具有非線性、遍歷性、隨機(jī)性等特征，在優(yōu)化領(lǐng)域替代隨機(jī)數(shù)初始化種群，會(huì)影響算法的整個(gè)過(guò)程，同時(shí)能獲得比隨機(jī)數(shù)更好的尋優(yōu)效果。Bernoulli映射的數(shù)學(xué)表達(dá)式可表示為

不僅在種群的初始化階段引入混沌映射，在麻雀搜索算法進(jìn)行迭代更新的過(guò)程中，當(dāng)全局最優(yōu)值超過(guò)10次未進(jìn)行更新時(shí)，便會(huì)認(rèn)為該種群在某一位置停留過(guò)久有陷入局部最優(yōu)的嫌疑，便會(huì)再次采用Bernoulli映射對(duì)整個(gè)種群進(jìn)行擾動(dòng)，減小其落入局部最優(yōu)而無(wú)法跳出的概率，即提高了全局搜索能力。

在算法的后期尋優(yōu)階段引入禁忌算法，應(yīng)用其禁忌準(zhǔn)則和特設(shè)準(zhǔn)則的結(jié)構(gòu)，在迭代的過(guò)程中不斷求解給定初始解的領(lǐng)域解，并從中挑選出質(zhì)量較好的作為候選解，最后根據(jù)候選解更改禁忌表。

通過(guò)引入禁忌算法可以進(jìn)一步提高整體的全局搜索能力和尋優(yōu)能力，能更好地提高最優(yōu)路徑的精度。

3 環(huán)境建模

圖1 環(huán)境模型

對(duì)于該算法中的評(píng)價(jià)函數(shù)，本文采用該路徑的長(zhǎng)度作為標(biāo)準(zhǔn)，即

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

圖2 3種算法進(jìn)行50次實(shí)驗(yàn)結(jié)果對(duì)比

從圖中可以看出：傳統(tǒng)麻雀搜索算法和粒子群算法在進(jìn)行50次最優(yōu)路徑的搜索中，結(jié)果有很大的波動(dòng)，表明傳統(tǒng)麻雀搜索算法和粒子群算法在求解路徑規(guī)劃問(wèn)題中容易陷入局部最優(yōu)，導(dǎo)致最終的結(jié)果偏離全局最優(yōu)而使最終結(jié)果產(chǎn)生較大的偏差；而改進(jìn)的麻雀搜索算法每一次的搜索結(jié)果相差不大，可以看出改進(jìn)后的算法具有更好的全局搜索能力和更好的精度。3種算法進(jìn)行50次實(shí)驗(yàn)的數(shù)據(jù)對(duì)比結(jié)果如表1所示。

表1 3種算法50次實(shí)驗(yàn)數(shù)據(jù)對(duì)比

從表1的數(shù)據(jù)可以看出，不論是最優(yōu)值、均值還是方差，改進(jìn)麻雀搜索算法都是最好的。尤其在方差的數(shù)據(jù)對(duì)比中可以看出，改進(jìn)的麻雀搜索算法特別穩(wěn)定，說(shuō)明改進(jìn)后的算法在尋優(yōu)過(guò)程中能找到更好的結(jié)果，同時(shí)體現(xiàn)了改進(jìn)后的算法在全局搜索能力上的優(yōu)越性。同時(shí)在均時(shí)一欄可以看出改進(jìn)麻雀搜索算法在加入混沌映射和禁忌算法后增加了大量的計(jì)算量，但實(shí)際效率并沒(méi)有與其他2種算法相差太多。圖3、圖4及圖5分別為傳統(tǒng)麻雀搜索算法、改進(jìn)麻雀搜索算法和粒子群算法的一次尋優(yōu)結(jié)果，圖6為3種算法迭代次數(shù)與適應(yīng)度值對(duì)比圖。

圖3 傳統(tǒng)麻雀搜索算法結(jié)果

圖4 改進(jìn)麻雀搜索算法結(jié)果

圖5 粒子群算法結(jié)果

圖6 適應(yīng)度值對(duì)比

圖中粒子群算法、傳統(tǒng)麻雀搜索算法和改進(jìn)麻雀搜索算法的適應(yīng)度值分別為155.3165、163.3408150.7585m，可以看出，改進(jìn)后的麻雀算法擁有更快的收斂速度和更好的適應(yīng)度值。因?yàn)楦倪M(jìn)的麻雀算法在種群初始化階段引入了Bernoulli映射，使得初始化的種群擁有更好的位置，可以盡快地趨向全局最優(yōu)值；而且在迭代的過(guò)程中能夠減小陷入局部最優(yōu)的可能，從而獲得更好的全局最優(yōu)結(jié)果。

5 結(jié)束語(yǔ)

針對(duì)無(wú)人車(chē)的路徑規(guī)劃問(wèn)題，本文提出了一種結(jié)合Bernoulli映射和禁忌算法的改進(jìn)麻雀搜索算法：在傳統(tǒng)算法的初始化種群階段采用Bernoulli映射，使種群位置不僅保留了隨機(jī)數(shù)初始化種群的隨機(jī)性，同時(shí)使得種群具有更豐富的多樣性，能更好地遍歷二維環(huán)境；在算法迭代過(guò)程中找到的全局最優(yōu)值超過(guò)10次迭代過(guò)程都沒(méi)有發(fā)生變化時(shí)，懷疑算法會(huì)陷入局部最優(yōu)，此時(shí)再次采用Bernoulli映射對(duì)種群進(jìn)行擾動(dòng)，使算法避免陷入局部最優(yōu)而影響最終的結(jié)果；同時(shí)在后期的尋優(yōu)階段，采用禁忌算法能夠使結(jié)果進(jìn)一步優(yōu)化。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的麻雀搜索算法擁有更快的收斂速度、更好的全局搜索能力和更高的精度，相較于粒子群算法和傳統(tǒng)麻雀搜索算法，不僅效率更高，同時(shí)避免了陷入局部最優(yōu)的可能，可以獲得更短的路徑。

[1] HOSSAIN M A, FERDOUS I. Autonomous robot path planning in dynamic environment using a new optimization technique inspired by bacterial foraging technique[J]. Robotics and Autonomous Systems, 2015, 64: 137-141.

[2] ZHU D, YAN M. Survey on technology of mobile robot path planning[J]. Control and Decision, 2010, 25(7): 961-967.

[3] 陳亞琳, 莊麗陽(yáng), 朱龍彪. 基于改進(jìn) Dijkstra 算法的泊車(chē)系統(tǒng)路徑規(guī)劃研究[J]. 現(xiàn)代制造工程, 2017(8): 63-67.

[4] BING F, LIN C, ZHOU Y, et al. An improved algorithm for the industrial robot path planning with high success rate and short length[J]. Robotics and Autonomous Systems,2018,106:26-37.

[5] SONG J H, DAI T, LIU Y J. Path planning of mobile robots based on improved artificial potential field method[J]. Computer Engineering & Science,2017,39(7):1328-1332.

[6] HOSSEIN Y, MARKID, ZAKEROLHOSSEINI, et al. Unsupervised probabilistic feature selection using ant colony optimization[J]. Expert Systems with Applications,2016,53:27-42.

[7] LEE J. Heterogeneous-ants-based path planner for global path planning of mobile robot applications[J]. International Journal of Control, Automation and Systems, 2017,15(4):1754-1769.

[8] LIN Q Z, LIU S B, ZHU Q L, et al. Particle swarm optimization with a balanceable fitness estimation for many objective optimization problems[J]. IEEE Transactions on Evolutionary Computation,2018,22(1):32-46.

[9] MO H, XU L. Research of biogeography particle swarm optimization for robot path planning[J]. Neurocomputing, 2015, 148: 91-99.

[10] ELHOSENY M, THARWAT A, HASSANIEN A E, et al. Bezier curve based path planning in a dynamic field using modified genetic algorithm[J]. Journal of Computational Science, 2018,25: 339-350.

[11] 付興武, 胡洋. 基于改進(jìn)粒子群算法的三維路徑規(guī)劃[J].電光與控制,2021,28(3):86-89.

[12] 王輝, 王景良, 朱龍彪, 等. 基于改進(jìn)蟻群算法的泊車(chē)系統(tǒng)路徑規(guī)劃[J]. 控制工程, 2018, 25(2):254-258.

[13] 湯安迪, 韓統(tǒng), 徐登武, 等. 基于混沌麻雀搜索算法的無(wú)人機(jī)航跡規(guī)劃方法[J]. 計(jì)算機(jī)應(yīng)用, 2021, 41(7): 2128-2136.

Path planning of unmanned vehicle based on improved sparrow search algorithm

GE Chang, QIAN Suqin

（College of Information Science and Technology, Donghua University, Shanghai 201620, China）

An improved sparrow search algorithm based on Bernoulli mapping and tabu search algorithm is proposed to solve the problem that sparrow search algorithm is easy to be premature and fall into local optimization. In the initialization phase of the improved sparrow search algorithm, Bernoulli map is used to initialize the population position, instead of the random number method used in the initialization phase of the traditional algorithm, which optimizes the problems of uneven population distribution and insufficient search range. At the same time, when the global optimal value is not updated after a certain number of iterations, Bernoulli map is used again to disturb the population to enhance the global search ability. The tabu search algorithm is used when the algorithm enters the later optimization stage, and its structure of tabu criteria and Amnesty criteria is applied to achieve good global search ability. Then the algorithm is applied to the global path planning problem of unmanned vehicles, and experiments are carried out to verify its effectiveness. The experimental results show that the improved sparrow search algorithm has better global search ability and higher accuracy.

unmanned vehicle; path planning; improved sparrow search algorithm; chaotic mapping; tabu search

TP273

A

2095-4999(2022)06-0107-05

葛唱，錢(qián)素琴.改進(jìn)麻雀搜索算法的無(wú)人車(chē)路徑規(guī)劃[J].導(dǎo)航定位學(xué)報(bào), 2022, 10(6): 107-111.（GE Chang, QIAN Suqin.Path planning of unmanned vehicle based on improved sparrow search algorithm[J]. Journal of Navigation and Positioning, 2022, 10(6): 107-111.）

10.16547/j.cnki.10-1096.20220614.

2022-06-14

葛唱（1998—），男，遼寧大連人，碩士研究生，研究方向?yàn)闊o(wú)人車(chē)軌跡跟蹤與路徑規(guī)劃。

錢(qián)素琴（1971—），女，上海人，碩士，副教授，研究方向?yàn)榍度胧较到y(tǒng)和人工智能。