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

蔣鳴東，朱榮軍

（安徽工業經濟職業技術學院，安徽 合肥 230051）

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

蔣鳴東，朱榮軍

（安徽工業經濟職業技術學院，安徽 合肥 230051）

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

蟻群算法；路徑規劃；研究

近年來，最優路徑規劃問題，伴隨著智能化小車的發展，越來越受到重視與發展。基于蟻群算法的自動循跡小車路徑規劃問題，許多專家學者提出多種優化算法。智能循跡小車以單片機為微型控制器，它用紅外反射式的光電管探測路徑，并且用最短的時間完成路徑規劃的循跡問題。

1 蟻群算法的研究及應用

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

1.1 蟻群優化算法

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

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

1.2 蟻群算法的應用

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

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

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

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

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

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

2.1 循跡路徑規劃模型的建立

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

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

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

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

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

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

2.2 蟻群算法設計

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

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

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

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

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

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

2.3 蟻群算法小車循跡

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

從蟻族算法發現至現在，已經有無數的成功過的例子解決各種組合最優解。因此可分為：靜態組合優化問題和動態組合優化問題。

靜態組合優化問題，就是一旦一個被給出，所有內容也就確定下來，并且也不會隨機改變。

3 總結

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

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

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

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

[2]高攀龍 .基于網絡控制的四輪驅動巡檢小車的設計與應用.控制工程.南昌: 南昌大學.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

安徽工業經濟職業技術學院質量工程特色專業項目“電子信息工程技術”（項目編號：2013YTSZY01）。

（責任編輯：張時瑋）

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