蔣鳴東，朱榮軍

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

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

蔣鳴東，朱榮軍

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

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

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

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

1 蟻群算法的研究及應用

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

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

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

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

1.2 蟻群算法的應用

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

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

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

蟻群會隨著信息素最多地方移動，當周圍沒有信息素時，它們會朝著自己原來運動方向運動，而且為了防止原地繞圈，它會記住自己先前走的路線，避免自己找不到前進的方向。

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

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

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

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

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

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

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

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

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

2.2 蟻群算法設(shè)計

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

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

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

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

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

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

2.3 蟻群算法小車循跡

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

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

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

3 總結(jié)

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

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

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

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

[2]高攀龍 .基于網(wǎng)絡(luò)控制的四輪驅(qū)動巡檢小車的設(shè)計與應用.控制工程.南昌: 南昌大學.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)濟職業(yè)技術(shù)學院質(zhì)量工程特色專業(yè)項目“電子信息工程技術(shù)”（項目編號：2013YTSZY01）。

（責任編輯：張時瑋）

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