前言

本篇文章主要記錄了蟻群算法在三維路徑規(guī)劃中實(shí)現(xiàn)的過程

一、蟻群算法簡(jiǎn)介

1 引言
在自然界中各種生物群體顯現(xiàn)出來的智能近幾十年來得到了學(xué)者們的廣泛關(guān)注，學(xué)者們通過對(duì)簡(jiǎn)單生物體的群體行為進(jìn)行模擬，進(jìn)而提出了群智能算法。其中， 模擬蟻群覓食過程的蟻群優(yōu)化算法(Ant Colony Optimization， ACO) 和模擬鳥群運(yùn)動(dòng)方式的粒子群算法(ParticleS warm Optimization，PSO) 是兩種最主要的群智能算法。
蟻群算法是一種源于大自然生物世界的新的仿生進(jìn)化算法，由意大利學(xué)者M(jìn).Dorigo，V.Mani ezzo和A.Color ni等人于20世紀(jì)90年代初期通過模擬自然界中螞蟻集體尋徑行為而提出的一種基于種群的啟發(fā)式隨機(jī)搜索算法。螞蟻有能力在沒有任何提示的情形下找到從巢穴到食物源的最短路徑，并且能隨環(huán)境的變化，適應(yīng)性地搜索新的路徑，產(chǎn)生新的選擇。其根本原因是螞蟻在尋找食物時(shí)，能在其走過的路徑上釋放一種特殊的分泌物――信息素2，隨著時(shí)間的推移該物質(zhì)會(huì)逐漸揮發(fā)，后來的螞蟻選擇該路徑的概率與當(dāng)時(shí)這條路徑上信息素的強(qiáng)度成正比。當(dāng)一條路徑上通過的螞蟻越來越時(shí)，其留下的信息素也越來越多，后來螞蟻選擇該路徑的概率也就越高，從而更增加了該路徑上的信息素強(qiáng)度。而強(qiáng)度大的信息素會(huì)吸引更多的螞蟻，從而形成一種正反饋機(jī)制。通過這種正反饋機(jī)制，螞蟻?zhàn)罱K可以發(fā)現(xiàn)最短路徑。

2 基本思想

蟻群算法在三維路徑規(guī)劃中實(shí)際情況是對(duì)每個(gè)方向的信息素進(jìn)行探索，選擇最合適的方向繼續(xù)前進(jìn)并對(duì)該方向上的信息素進(jìn)行更新，螞蟻的信息素隨時(shí)間衰減，精英螞蟻的信息素正反饋增強(qiáng)，讓之后蟻群更好的選擇最優(yōu)的路線，最終可以得到一條三維地形中兩點(diǎn)之間的最短路徑。

二、算法精講

1 實(shí)現(xiàn)過程

因?yàn)橐獙ふ胰S中兩點(diǎn)之間的最短路徑，為了加快收斂速度，添加一個(gè)初始化蟻群信息素的過程，在進(jìn)行信息素初始化的時(shí)刻為不同的點(diǎn)賦予了不同的選擇概率。即可以建立一個(gè)以終點(diǎn)為中心的概率球，直線距離終點(diǎn)越遠(yuǎn)的點(diǎn)其相應(yīng)的信息素濃度越低，其相應(yīng)的選擇該點(diǎn)的概率越小。初始化信息素濃度的公式（1）如下所示：

式中, pheromone(goal)為飛行環(huán)境中g(shù)oal位置的信息素濃度，a表示控制參數(shù)；Distanced表兩點(diǎn)之間的歐式距離；goal_end表示終點(diǎn)的位置。

通過上述的公式就可以生成一個(gè)以終點(diǎn)為中心，沿四周概率不斷降低的一個(gè)概率球。同時(shí)依據(jù)蟻群在搜索路徑的過程中，需要對(duì)周圍的信息素進(jìn)行嗅探并且有一定傾向選擇信息素濃度較高的位置，這里我采用的是設(shè)定一個(gè)啟發(fā)值函數(shù)對(duì)周圍上下左右等26個(gè)點(diǎn)進(jìn)行選擇，啟發(fā)值越高表示螞蟻下一個(gè)點(diǎn)的位置更傾向與這個(gè)位置，這就模擬螞蟻向信息素濃度高方向前進(jìn)下的傾向，同時(shí)信息素濃度隨時(shí)間而揮發(fā)。啟發(fā)值函數(shù)和信息素濃度揮發(fā)如公式(2),(3)所示：

式中, QFZ 為蟻群在一次行走周圍 26 個(gè)點(diǎn)中的啟發(fā)值，S 表示這 26 個(gè)點(diǎn)可否到達(dá)，到達(dá) S=1，
否 S=0；M 為加額外參數(shù)之后的兩點(diǎn)之間的歐式距離；D 為加額外參數(shù)之后 26 個(gè)點(diǎn)的高度

式中, pheromone(goal)為飛行環(huán)境中g(shù)oal位置的信息素濃度；M為加額外參數(shù)之后的兩點(diǎn)之間的歐式距離；decr表示信息素濃度揮發(fā)因子。

對(duì)信息素濃度進(jìn)行增強(qiáng)的公式如4所示:

式中, pheromone(goal)為飛行環(huán)境中g(shù)oal位置的信息素濃度；rou為適應(yīng)度對(duì)信息素更新的影響；fitness為通過函數(shù)計(jì)算的路徑適應(yīng)度。

2 算法流程圖

三、部分代碼（Matlab）

計(jì)算兩點(diǎn)之間的歐式距離

%計(jì)算兩點(diǎn)之間的歐式距離
function dist=distance(x1,y1,z1,x2,y2,z2)
dist=sqrt((x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2);

初始化信息素函數(shù)

function pheromone=initial_pheromone(pheromone,point_end)
%% 
%point_end   input       終點(diǎn)
%pheromone   output      信息素

for x=1:200
    for y=1:200
        for z=1:200
            pheromone(x,y,z)=5000/distance(x,y,z,point_end(1),point_end(2),point_end(3));
        end
    end
end

啟發(fā)值函數(shù)文章來源地址http://www.zghlxwxcb.cn/news/detail-420465.html

function qfz=CacuQfz(point_next,point_now,point_end,mapdata)
%% 該函數(shù)用于計(jì)算各點(diǎn)的啟發(fā)值（越大越好）
% point_next    input    下個(gè)點(diǎn)坐標(biāo)
% point_now     input    當(dāng)前點(diǎn)坐標(biāo)
% point_end     input    終點(diǎn)坐標(biāo)
% mapdata       input    地圖高度
% qfz           output    啟發(fā)值
%% 判斷下個(gè)點(diǎn)是否可達(dá)，不可達(dá)為0
if mapdata(point_next(2)

到了這里，關(guān)于蟻群算法的三維路徑規(guī)劃【Matlab】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！