基于蟻群算法的自動(dòng)循跡小車路徑規(guī)劃研究

蔣鳴東，朱榮軍

（安徽工業(yè)經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院，安徽 合肥 230051）

基于蟻群算法的自動(dòng)循跡小車路徑規(guī)劃研究

蔣鳴東，朱榮軍

（安徽工業(yè)經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院，安徽 合肥 230051）

本文通過對(duì)蟻群算法的初步應(yīng)用及研究，提出自動(dòng)化小車全局路徑規(guī)劃的自適應(yīng)算法，考慮小車體積及轉(zhuǎn)彎狀況，自動(dòng)擇選小車運(yùn)行最優(yōu)路徑。運(yùn)用仿真實(shí)驗(yàn)及分析，研究證明蟻群算法的智能規(guī)劃。

蟻群算法；路徑規(guī)劃；研究

近年來，最優(yōu)路徑規(guī)劃問題，伴隨著智能化小車的發(fā)展，越來越受到重視與發(fā)展?；谙伻核惴ǖ淖詣?dòng)循跡小車路徑規(guī)劃問題，許多專家學(xué)者提出多種優(yōu)化算法。智能循跡小車以單片機(jī)為微型控制器，它用紅外反射式的光電管探測路徑，并且用最短的時(shí)間完成路徑規(guī)劃的循跡問題。

1 蟻群算法的研究及應(yīng)用

蟻群算法也稱為螞蟻算法，它是用圖來尋找優(yōu)化路徑的一種機(jī)率型算法。這種算法由1992年提出，模擬螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。螞蟻算法也是一種模擬進(jìn)化算法，且具有諸多優(yōu)良品質(zhì)，對(duì)于PID控制器參數(shù)優(yōu)化設(shè)計(jì)的問題，相對(duì)于其他算法，蟻群算法更具有有效性和應(yīng)用價(jià)值[1]。

1.1 蟻群優(yōu)化算法

蟻群算法是從自然界得到的一種算法，螞蟻是一種群居生物，它們存在于一個(gè)群落中，他們的行為不是自己個(gè)人決定的，而是整個(gè)群落。所以通過它們的群居生活給我們帶來許多啟示。一些人發(fā)現(xiàn)它們螞蟻可以發(fā)現(xiàn)食物所在地和所在洞穴的最短距離。所以它們是怎么做到的呢？蟻群算法，是說明一群人工螞蟻通過復(fù)雜的離散問題去尋找一個(gè)最優(yōu)解。相互協(xié)作是其最重要的部分，它們彼此之間創(chuàng)立了一個(gè)機(jī)制，致使他們相互作用，相互交流，便順理成章的解決了問題。

經(jīng)過多次實(shí)驗(yàn)表明：螞蟻移動(dòng)過程中在地上釋放一種物質(zhì)被稱之為信息素，同時(shí)形成一種信息軌跡。螞蟻通過嗅覺聞到信息濃度大的路徑，從而使它們找到了最短距離。

1.2 蟻群算法的應(yīng)用

蟻群算法，是說明一群人工螞蟻通過復(fù)雜的離散問題去尋找一個(gè)最優(yōu)解。相互協(xié)作是其最重要的部分，它們彼此之間創(chuàng)立了一個(gè)機(jī)制，致使他們相互作用，相互交流，便順理成章的解決了問題人工螞蟻具有兩面性，一方面，它們像真的蟻群一樣通過彼此溝通，跟蹤信息素軌跡來尋找最佳路線；另一方面，它們具備一些一群無法具備的性質(zhì)及功能[2]。

螞蟻觀察到的范圍是一個(gè)方格世界，螞蟻有一個(gè)參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個(gè)方格世界，并且能移動(dòng)的距離也在這個(gè)范圍之內(nèi)。

每只螞蟻在自己能感知的范圍內(nèi)去尋找是否有食物，若有就直接過去。否則看是否還有信息素，并感知自己的感知范圍內(nèi)信息素的多少，從而指引蟻群的移動(dòng)。而且每只螞蟻的錯(cuò)誤率都非常小。

蟻群會(huì)隨著信息素最多地方移動(dòng)，當(dāng)周圍沒有信息素時(shí)，它們會(huì)朝著自己原來運(yùn)動(dòng)方向運(yùn)動(dòng)，而且為了防止原地繞圈，它會(huì)記住自己先前走的路線，避免自己找不到前進(jìn)的方向。

倘若螞蟻移動(dòng)路線受到阻礙，他會(huì)隨機(jī)找到另一個(gè)方向，并且如果有信息指引的話，會(huì)按照覓食規(guī)則行為。每只螞蟻在剛找到食物或者自己的洞穴散發(fā)的信息素最多，但隨著自己走的距離信息素會(huì)越來越少。

2 基于蟻群算法的小車循跡路徑規(guī)劃

2.1 循跡路徑規(guī)劃模型的建立

在我們處理實(shí)際問題時(shí)，我們要首先考慮既方便又節(jié)能。理論上，旅行商問題是車輛路徑問題的一個(gè)簡化，一個(gè)特例。例如：車輛路徑問題，它是一類交通運(yùn)輸優(yōu)化問題，存在各種VRP問題。其具體算法如下：通過車輛的幅度，使車輛總行程最短。

G=（V，A，d）是一個(gè)完全有向權(quán)圖，其中V={v0，v1，v2，...，vn}是頂點(diǎn)集合，A={(vi，vj):i≠ j}是連接頂電弧的集合。頂點(diǎn)v0表示庫房，而V中其余的頂點(diǎn)則表示為城市或客戶，與?。╲i，vj）相關(guān)聯(lián)的非負(fù)權(quán)值dij表示vi和vj之際的距離（或者為旅行時(shí)間，或旅行費(fèi)用）。對(duì)每一個(gè)客戶vi而言，都有一個(gè)確定非負(fù)需求qi和一個(gè)非負(fù)時(shí)間§i，并使其滿足：

·每個(gè)客戶被一輛車車輛訪問的次數(shù)只有一次；

·所有車輛從庫房出發(fā)，最后返回庫房；

·對(duì)每一條車輛路徑，其總需求量都不能超過車輛的載重量Q；

·對(duì)每一條車輛路徑，其路徑長度不超過一個(gè)給定的上界L。

2.2 蟻群算法設(shè)計(jì)

步驟一：nc=0（nc為迭代步數(shù)或搜索次數(shù)）；每條邊邊上的t=c（常數(shù)），并且△t=0；放置m個(gè)螞蟻n個(gè)城市上。

步驟二：將各螞蟻的初始出發(fā)點(diǎn)置于當(dāng)前解集tabu中；對(duì)每個(gè)螞蟻k（k=1，...，m），按概率移至下一個(gè)城市就j；將城市就j置于tabu中。

步驟三：經(jīng)過n個(gè)時(shí)刻，螞蟻k可走完所有的城市，玩成一次循環(huán)。計(jì)算每個(gè)螞蟻?zhàn)哌^的總路徑長度L，更新找到的最短路徑。

步驟四：更新每條邊上的信息量t（s+n）。

步驟五：對(duì)每一條邊置△tt=0；nc=nc+1。

步驟六：若nc＜預(yù)定的選代次數(shù)NCMAX，則轉(zhuǎn)步驟二；否則，打印最短路徑，終止整個(gè)程序。

2.3 蟻群算法小車循跡

VRP問題是以最小為目標(biāo)，一般VPR問題可描述若干車輛從配送中心出發(fā)，到不同地理位置送貨，然后返回配送中心，其中一次配送距離的最大行駛距離。要求合理安排車輛，得到最優(yōu)解。

從蟻?zhàn)逅惴òl(fā)現(xiàn)至現(xiàn)在，已經(jīng)有無數(shù)的成功過的例子解決各種組合最優(yōu)解。因此可分為：靜態(tài)組合優(yōu)化問題和動(dòng)態(tài)組合優(yōu)化問題。

靜態(tài)組合優(yōu)化問題，就是一旦一個(gè)被給出，所有內(nèi)容也就確定下來，并且也不會(huì)隨機(jī)改變。

3 總結(jié)

本文首先回顧了蟻群算分的過程和基本的蟻群算法，再介紹了一群算法再每個(gè)有代表性的問題中的基本解決方法。然后分析了基于蟻群算法的自動(dòng)循跡小車路徑規(guī)劃的問題。在介紹了國內(nèi)研究的一個(gè)基本狀況的同時(shí)也介紹了國外的研究現(xiàn)狀，對(duì)本文的研究內(nèi)容和背景進(jìn)行了闡述。

傳統(tǒng)的蟻群算法，由于一些原因，在某些應(yīng)用時(shí)，給那些沒用過的使用者來說有許多不方便的情況。所以提出了一些其他的算法——基于時(shí)間模型的蟻群算法。時(shí)間蟻群算法和普通的蟻群算法一樣，作為一種新型的智能優(yōu)化方法具有許多優(yōu)點(diǎn)，但也有許多不足，為此需將它兩相結(jié)合，形成互補(bǔ)狀態(tài)，用于一些應(yīng)用中。

總得來說，蟻群算法是通過信息素的累積和更新而收斂于最優(yōu)路徑。

[1]王燁 .基于Android系統(tǒng)的智能導(dǎo)航小車設(shè)計(jì)控制科學(xué)與工程[D].天津:天津大學(xué).2013.

[2]高攀龍 .基于網(wǎng)絡(luò)控制的四輪驅(qū)動(dòng)巡檢小車的設(shè)計(jì)與應(yīng)用.控制工程.南昌: 南昌大學(xué).2014.

The car of automatic tracking path planning based on ant colony algorithm

JIANG Ming-dong， ZHU Rong-jun

(Anhui Technical College of Industry and Economy， Hefei Anhui 230051)

Based on ant colony algorithm preliminary application and research， put forward adaptive algorithm for global path planning of automated car， consider car volume and turning condition， automatic，the car running optimal path. Using the simulation experiment and analysis， the research proves that the ant colony algorithm of intelligent planning.

Ant colony algorithm; Path planning; Research

P441+.3

A

10.3969/j.issn.1672-7304.2016.05.016

1672–7304(2016)05–0033–02

安徽工業(yè)經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院質(zhì)量工程特色專業(yè)項(xiàng)目“電子信息工程技術(shù)”（項(xiàng)目編號(hào)：2013YTSZY01）。

（責(zé)任編輯：張時(shí)瑋）

蔣鳴東（1981-），男，安徽合肥人，研究方向：計(jì)算機(jī)技術(shù)、計(jì)算機(jī)控制。