基于柵格模型機器人路徑規(guī)劃的量子蟻群算法

張　晨，游曉明

(上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620)

?

基于柵格模型機器人路徑規(guī)劃的量子蟻群算法

張晨，游曉明

(上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620)

摘要針對復(fù)雜環(huán)境中移動機器人路徑規(guī)劃問題，提出了一種基于量子-蟻群算法(QACA)融合的路徑規(guī)劃算法。該算法的核心是在蟻群系統(tǒng)(ACS)中引入量子算法中的量子態(tài)矢量和量子旋轉(zhuǎn)門來分別表示和更新信息素，增加位置的多樣性,加快算法的收斂速度。通過仿真實驗表明，該算法可增加算法的隨機性，較傳統(tǒng)的蟻群算法具有更好的種群多樣性，更快的收斂速度和全局尋優(yōu)能力，即使在障礙物較復(fù)雜的環(huán)境下，也能迅速規(guī)劃出一條最優(yōu)路徑。

關(guān)鍵詞量子進(jìn)化算法；蟻群算法；復(fù)雜環(huán)境；柵格法；路徑規(guī)劃

目前，不少學(xué)者用改進(jìn)的遺傳算法、神經(jīng)網(wǎng)絡(luò)、隨機樹等方法對機器人路徑進(jìn)行規(guī)劃。但不少算法在一定程度上存在搜索空間大、算法復(fù)雜、效率較低等問題[1]。尤其是當(dāng)障礙物的數(shù)目增加或地形障礙趨于復(fù)雜時，不少路徑規(guī)劃算法的復(fù)雜度會大幅增加，甚至無法求解。如基于遺傳算法的機器人路徑規(guī)劃方法，該方法對路徑規(guī)劃環(huán)境中的路徑進(jìn)行編碼構(gòu)成遺傳個體，在進(jìn)行選擇、交叉、變異等遺傳操作時要加很多的約束條件。當(dāng)環(huán)境趨于復(fù)雜、障礙物數(shù)目增加時、約束條件就會很復(fù)雜，甚至無法求解。朱正等嘗試最優(yōu)最差螞蟻算法作路徑規(guī)劃，仿真結(jié)果表明可以很好地避免障礙物，快速找到一條機器人最優(yōu)移動路徑[2]。然而，要么復(fù)雜度過大，或沒有完全避免路徑死鎖問題。本文使陷入死鎖的螞蟻逐步逃逸，為更好的解決搜索效率低，收斂速度慢，提出了一種新的算法-量子蟻群算法，在蟻群算法的基礎(chǔ)上，將量子進(jìn)化算法中的態(tài)矢量和量子旋轉(zhuǎn)門引入蟻群算法，在該算法中態(tài)矢量和量子旋轉(zhuǎn)門分別表示和更新信息素，加快了算法的收斂速度及避免了早熟收斂。仿真實驗比較了在不同環(huán)境下本文算法與文獻(xiàn)[3]算法的搜索性能，另外分析了主要參數(shù)的確定規(guī)則，并作了仿真對比實驗。

1量子蟻群算法

1.1量子編碼特性

在經(jīng)典計算中，信息被編碼為位(bit)鏈。量子比特是量子計算中的基本信息單元，其是定義在二維復(fù)向量空間中的一個單位向量,該空間由一對特定的標(biāo)準(zhǔn)正交基{|0〉,|1〉}張成。即一個量子位除了可處于|0〉或|1〉,還可處于兩者之間的任意線性組合,這稱為疊加態(tài)[4]。一個量子位的疊加態(tài)可用二維Hilbert空間的單位向量|ψ〉來描述

|ψ〉=α|0〉+β|1〉

(1)

其中，α和β均是復(fù)數(shù),分別稱為量子態(tài)|0〉和|1〉的概率幅,代表對量子比特進(jìn)行測量時；|ψ〉為一種量子態(tài)的表示；α2和β3分別表示量子比特處于“0”態(tài)和“1”態(tài)的概率，且滿足歸一化條件[5]

α2+β2=1

(2)

1.2量子蟻群算法基本原理

定義ξ(ξ∈[0,π])為一個量子位的相位，ξ=arctan(β/α)，則第i(i=1,2,…,m)個量子位的相位為ξi=arctan(βi/αi)。用符號di表示第i個量子位概率幅αi和βi的商,di=βi/αi, 其中di的值代表此量子位的相位ξ在平面坐標(biāo)中所處的位置[6]。于是有m個量子位的個體j的概率幅可表示為

(3)

(4)

量子蟻群算法中的概率轉(zhuǎn)移規(guī)則是

(5)

其中，q為[0,1]區(qū)間內(nèi)的一隨機數(shù)；q0為[0,1]區(qū)間內(nèi)的一個常數(shù)。當(dāng)q>q0時，b′的選擇由轉(zhuǎn)移概率公式?jīng)Q定

(6)

1.3信息素更新策略

信息素的更新分為螞蟻個體信息素的局部更新和蟻群信息素的全局更新。每只螞蟻在一次遍歷結(jié)束后，先按照式(7)進(jìn)行個體信息素的局部更新[7]

τ(t+1)=(1-ρ1)τ(t)+ρ1Δτij

(7)

當(dāng)所有的螞蟻對節(jié)點完成遍歷后，再進(jìn)行信息素的全局更新。只有當(dāng)前路徑最短的螞蟻能在其經(jīng)過的路徑上留下信息素，信息素更新的規(guī)則如下

(8)

1.4量子旋轉(zhuǎn)門自適應(yīng)調(diào)整策略

在量子算法中選用量子旋轉(zhuǎn)門來進(jìn)行更新操作，量子旋轉(zhuǎn)門的調(diào)整操作如下

(9)

其中，i=1,2,…,m;[αi,βi]T為第i個量子位的概率幅;θi為第i個量子位的旋轉(zhuǎn)角度，其大小和方向根據(jù)一個事先確定的調(diào)整策略,通過查表得到。文中θi的大小和方向通過式(10)自動調(diào)整[8]。

θi=Δθ×f(αi,βi)

(10)

1.5量子蟻群算法流程

(3)螞蟻按照狀態(tài)轉(zhuǎn)移規(guī)則式(5)和式(6)選擇下一個城市，并更新禁忌表；

(4)按照式(7)完成信息素的局部更新；

(5)判斷是否所有螞蟻完成遍歷，若是，轉(zhuǎn)向步驟(6),否則返回步驟(3)繼續(xù)遍歷下一個城市；

(6)記錄下本次迭代中的較優(yōu)解，使用3-opt法進(jìn)行局部優(yōu)化；

(7)應(yīng)用量子旋轉(zhuǎn)門規(guī)則更新反應(yīng)螞蟻各節(jié)點信息的量子信息強度；

(8)按照式(8)完成信息素全局更新，同時更新啟發(fā)因子和全局信息素?fù)]發(fā)系數(shù)；

(9)判斷是否連續(xù)若次出現(xiàn)搜索停滯現(xiàn)象，若是，重置信息素，否則轉(zhuǎn)向步驟(10)；

(10)判斷是否滿足收斂條件或最大迭代次數(shù)，若滿足，轉(zhuǎn)向步驟(11)，否則清空禁忌表并返回步驟(1)，直至達(dá)到收斂條件或最大迭代次數(shù)；

(11)輸出最優(yōu)路徑長度和最優(yōu)路徑。

2仿真實驗

為說明算法的優(yōu)越性，文中選用文獻(xiàn)[3]中朱正的改進(jìn)蟻群算法進(jìn)行測試，迭代次數(shù)為100次，實線為本算法尋找到的最優(yōu)路徑，虛線為文獻(xiàn)[3]尋找到的最優(yōu)路徑。從下圖可看出，本算法能快速，準(zhǔn)確的尋找到最優(yōu)路徑，雖在有些障礙物聚集處，選擇的路徑稍有偏差，可能是由于可選方向上最大信息素的搜索造成的。為不失一般性，文中又隨機測試了一些規(guī)模較為復(fù)發(fā)的地圖，每個算法迭代100次，參數(shù)設(shè)置如表1所示，圖1和圖2為算法對柵格地圖測試得到的結(jié)果。

表1　各參數(shù)設(shè)置

圖1　復(fù)雜環(huán)境1下兩種算法路徑比較

圖2　Z-型環(huán)境下兩種算法比較

由以上兩個實驗可看出，與文獻(xiàn)[3]和其他改進(jìn)蟻群算法相比，本算法顯示出了良好的快速求解性能，且在規(guī)模較大、環(huán)境復(fù)雜的情況下，解的質(zhì)量也顯示了較高的穩(wěn)定性。此外，還發(fā)現(xiàn)在起始點和目標(biāo)點之間只有一條通道客觀存在，無論路徑多么復(fù)雜，本算法均能迅速準(zhǔn)確的規(guī)劃出最優(yōu)路徑。表2為兩種算法實驗結(jié)果對比。

表2　兩種算法實驗結(jié)果對比

3參數(shù)選擇分析

3.1量子位個數(shù) 對算法性能影響

過大，影響算法的隨機性能和全局搜索能力，算法波動性較大，本文算法中m最優(yōu)為8或12，如圖3所示。

3.2Q對算法性能的影響

Q越大，有利于增強搜索時的正反饋性能，收斂速度越快，將導(dǎo)致算法的全局搜索能力變差，本算法中Q的值最優(yōu)為3，在50代左右處收斂，避免算法陷入局部最優(yōu)，如圖4所示。

圖3　不同 值下算法收斂曲線圖

圖4　不同 值下算法的收斂曲線圖

4結(jié)束語

傳統(tǒng)的蟻群算法，路徑精度不夠高，算法的搜索效率較低，若只依靠信息素和距離信息是難以找到一條從起始點到目標(biāo)點的優(yōu)化路徑，并容易陷入死鎖。本文提出了一種復(fù)雜環(huán)境下路徑規(guī)劃的量子蟻群算法。給出了新的信息素表達(dá)規(guī)則，增加最優(yōu)路徑上信息量的隨機性，同時采用量子旋轉(zhuǎn)門對信息素進(jìn)行更新，加快了算法的收斂速度，且對路徑轉(zhuǎn)移規(guī)則進(jìn)行了合理的改進(jìn)，提高了算法的搜索能力，使螞蟻對最優(yōu)路徑更為敏感，更好地適應(yīng)信息素環(huán)境。仿真結(jié)果表明，與傳統(tǒng)算法相比，該算法具有更高的精度、速度快、穩(wěn)定性高、效果好等特點，即使在復(fù)雜環(huán)境下，只要客觀要求合理，該算法便能快速的規(guī)劃出安全的最優(yōu)路徑。

參考文獻(xiàn)

[1]趙俊生,李躍光,張遠(yuǎn)平.一種改進(jìn)的量子蟻群算法及其應(yīng)用[J].計算機應(yīng)用與軟件,2010,27(7):133-135.

[2]孫波,陳衛(wèi)東,席裕庚.基于粒子群優(yōu)化算法的移動機器人全局路徑規(guī)劃[J].控制與決策,2005,20(9):1052-1055.

[3]朱正,劉士榮,張波濤.一種基于改進(jìn)蟻群算法的移動機器人全局路徑規(guī)劃方法[C].北京：中國自動化學(xué)會控制理論專業(yè)委員會:d卷,2011.

[4]魏唯,歐陽丹彤,呂帥,等.動態(tài)不確定環(huán)境下多目標(biāo)路徑規(guī)劃方法[J].計算機學(xué)報,2011,34(5):836-846.

[5]Fatemeh K P,Ehsan S. Mobile robots path planning using ant colony optimization and fuzzy logic algorithms in unknown dynamic environments[C].Hongkong: International Conference on Control,Automation,Robotics and Embeded Systems,2013.

[6]柳長安,鄢小虎,劉春陽,等.基于改進(jìn)蟻群算法的移動機器人動態(tài)路徑規(guī)劃方法[J].電子學(xué)報,2011,39(5):1220-1224.

[7]劉徐迅,曹陽,陳曉偉.基于移動機器人路徑規(guī)劃的鼠群算法[J].控制與決策,2008,23(9):1060-1064.

[8]Han Kuk-Hyun,Kim J H.Genetic quantum algorithm and its application to combinatorial optimization problems[C]. Piscataway, USA:Proceeding. of IEEE Conference on Evolutionary Computation, IEEE Press, 2000.

[9]朱慶保.動態(tài)復(fù)雜環(huán)境下的機器人路徑規(guī)劃螞蟻預(yù)測算法[J].計算機學(xué)報,2005,28(11):1898-1905.

Improved Quantum ant Colony Algorithm of Path Planning for Mobile Robot Based on Grid Model

ZHANG Chen, YOU Xiaoming

(College of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China)

AbstractFor mobile robot path planning in complex environments, an ant colony algorithm based on quantum (QACA) is proposed to plan the optimal collision-free path. The core of the algorithm is the introduction of the quantum state vector of quantum algorithm to respect the pheromone and quantum revolving gate to update the pheromone in ant colony system (ACS), in order to increase the diversity of position and to speed up the convergence speed of the algorithm. Simulation comparison shows that the algorithm can increase the randomness of the algorithm with better population diversity, higher convergence speed and better global optimization ability than the traditional ant colony algorithm, and can quickly find a optimal path planning even in the very complex environment.

Keywordsquantum evolutionary algorithm; ant colony algorithm; complex environment; grids; path planning

收稿日期:2015- 11- 6

基金項目:國家自然科學(xué)基金資助項目(61075115)；上海市教委科研創(chuàng)新重點基金資助項目(12ZZ185)；上海市學(xué)科專業(yè)建設(shè)基金資助項目(XKCZ1212)；創(chuàng)新課題資助項目(14KY0210)

作者簡介:張晨(1990-)，女，碩士研究生。研究方向：嵌入式系統(tǒng)與智能算法。游曉明(1963-)，女，博士，教授。研究方向：智能信息處理理論及應(yīng)用等。

doi:10.16180/j.cnki.issn1007-7820.2016.07.001

中圖分類號TP301.6

文獻(xiàn)標(biāo)識碼A

文章編號1007-7820(2016)07-001-04