?一、鯨魚算法及柵格地圖簡(jiǎn)介
1 鯨魚算法
一種元啟發(fā)式優(yōu)化算法，模擬座頭鯨狩獵行為的元啟發(fā)式優(yōu)化算法。目前的工作與其他群優(yōu)化算法相比的主要區(qū)別在于，采用隨機(jī)或最佳搜索代理來(lái)模擬捕獵行為，并使用螺旋來(lái)模擬座頭鯨的泡泡網(wǎng)攻擊機(jī)制。該算法具有機(jī)制簡(jiǎn)單、參數(shù)少、尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn)，在經(jīng)濟(jì)調(diào)度、最優(yōu)控制、光伏系統(tǒng)、圖像分割等方面得到廣泛的應(yīng)用。
2.1 算法基本原理
座頭鯨有特殊的捕獵方法，這種覓食行為被稱為泡泡網(wǎng)覓食法；標(biāo)準(zhǔn) WOA 模擬了座頭鯨特有的搜索方法和圍捕機(jī)制，主要包括：圍捕獵物、氣泡網(wǎng)捕食、搜索獵物三個(gè)重要階段。WOA 中每個(gè)座頭鯨的位置代表一個(gè)潛在解，通過(guò)在解空間中不斷更新鯨魚的位置，最終獲得全局最優(yōu)解。
(1)圍捕獵物（Encircling prey）
鯨魚的搜索范圍是全局解空間，需要先確定獵物的位置以便包圍。由于最優(yōu)設(shè)計(jì)在搜索速度中的位置不是先驗(yàn)已知的，因此WOA算法假定當(dāng)前的最佳候選解是目標(biāo)獵物或接近最優(yōu)解。在定義了最佳搜索代理之后，其他搜索代理將嘗試向最佳搜索代理更新它們的位置。
(2)氣泡網(wǎng)捕食：
座頭鯨捕食主要有兩個(gè)機(jī)制:包圍捕食和氣泡網(wǎng)捕食。采用氣泡網(wǎng)捕食時(shí)，座頭鯨與獵物間的位置更新用對(duì)數(shù)螺旋方程表達(dá).
(3)搜索獵物：
為保證所有鯨魚能在解空間中充分搜索，WOA 根據(jù)鯨魚彼此之間的距離來(lái)更新位置，達(dá)到隨機(jī)搜索的目的。因此，當(dāng)|A| ≥ 1|時(shí)，搜索個(gè)體會(huì)游向隨機(jī)鯨。
2.2 算法基本流程
標(biāo)準(zhǔn) WOA 主要依靠系數(shù)向量 A 選擇搜索獵物的路徑，并利用概率 p 決定最終捕食機(jī)制。
步驟 1：設(shè)置鯨魚數(shù)量 N 和算法的最大迭代次數(shù) tmax，初始化位置信息；
步驟 2：計(jì)算每條鯨魚的適應(yīng)度，找到當(dāng)前最優(yōu)鯨魚的位置并保留，即 ；
步驟 3：計(jì)算參數(shù) a、p 和系數(shù)向量 A、C。判斷概率 p 是否小于 50%，是則直接轉(zhuǎn)入步驟 4，否則采用氣泡網(wǎng)捕食機(jī)制：利用式（2-1）進(jìn)行位置更新；
步驟 4：判斷系數(shù)向量 A 的絕對(duì)值是否小于 1，是則包圍獵物：按式（1-2）更新位置；否則全局隨機(jī)搜索獵物：按式（3-1）更新位置；
步驟 5：位置更新結(jié)束，計(jì)算每條鯨魚的適應(yīng)度，并與先前保留的最優(yōu)鯨魚的位置比較，若優(yōu)于，則利用新的最優(yōu)解替換;
步驟 6：判斷當(dāng)前計(jì)算是否達(dá)到最大迭代次數(shù)，如果是，則獲得最優(yōu)解，計(jì)算結(jié)束，否則進(jìn)入下一次迭代，并返回步驟 3。
WOA算法首先隨機(jī)初始化一組解,在每次迭代中，搜索代理根據(jù)隨機(jī)選擇的搜索代理或到目前為止獲得的最優(yōu)解更新它們的位置。將 a 參數(shù)由 2 隨迭代次數(shù)降為 0，從而由探索逐步到利用。當(dāng) |A|>1 時(shí)選擇隨機(jī)搜索代理，|A|< 1時(shí)選擇最優(yōu)解更新搜索代理位置。根據(jù) p 的值，WOA可以在螺旋運(yùn)動(dòng)和圓環(huán)運(yùn)動(dòng)之間進(jìn)行切換。最后，通過(guò)滿足終止準(zhǔn)則來(lái)終止WOA算法。
2 柵格地圖
2.1 柵格法應(yīng)用背景
路徑規(guī)劃時(shí)首先要獲取環(huán)境信息， 建立環(huán)境地圖， 合理的環(huán)境表示有利于建立規(guī)劃方法和選擇合適的搜索算法，最終實(shí)現(xiàn)較少的時(shí)間開銷而規(guī)劃出較為滿意的路徑。一般使用柵格法在靜態(tài)環(huán)境下建立環(huán)境地圖。
2.2 柵格法實(shí)質(zhì)
將AGV的工作環(huán)境進(jìn)行單元分割， 將其用大小相等的方塊表示出來(lái)，這樣?xùn)鸥翊笮〉倪x取是影響規(guī)劃算法性能的一個(gè)很重要的因素。柵格較小的話，由柵格地圖所表示的環(huán)境信息將會(huì)非常清晰，但由于需要存儲(chǔ)較多的信息，會(huì)增大存儲(chǔ)開銷，同時(shí)干擾信號(hào)也會(huì)隨之增加，規(guī)劃速度會(huì)相應(yīng)降低，實(shí)時(shí)性得不到保證；反之，由于信息存儲(chǔ)量少，抗干擾能力有所增強(qiáng)，規(guī)劃速隨之增快，但環(huán)境信息劃分會(huì)變得較為模糊，不利于有效路徑的規(guī)劃。在描述環(huán)境信息時(shí)障礙物所在區(qū)域在柵格地圖中呈現(xiàn)為黑色，地圖矩陣中標(biāo)為1，可自由通行區(qū)域在柵格地圖中呈現(xiàn)為白色，地圖矩陣中標(biāo)為0。路徑規(guī)劃的目的就是在建立好的環(huán)境地圖中找到一條最優(yōu)的可通行路徑，所以使用柵格法建立環(huán)境地圖時(shí)，柵格大小的合理設(shè)定非常關(guān)鍵。
2.3 10乘10的靜態(tài)環(huán)境地圖
10乘10的靜態(tài)環(huán)境地圖代碼
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%建立環(huán)境地圖%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function DrawMap(map)
n = size(map);
step = 1;
a = 0 : step :n(1);
b = 0 : step :n(2);
figure(1)
axis([0 n(2) 0 n(1)]); %設(shè)置地圖橫縱尺寸
set(gca,'xtick',b,'ytick',a,'GridLineStyle','-',...
'xGrid','on','yGrid','on');
hold on
r = 1;
for(i=1:n(1)) %設(shè)置障礙物的左下角點(diǎn)的x,y坐標(biāo)
for(j=1:n(2))
if(map(i,j)==1)
p(r,1)=j-1;
p(r,2)=i-1;
fill([p(r,1) p(r,1) + step p(r,1) + step p(r,1)],...
[p(r,2) p(r,2) p(r,2) + step p(r,2) + step ],'k');
r=r+1;
hold on
end
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%柵格數(shù)字標(biāo)識(shí)%%%%%%%%%%%%%%%%%%%%%%%%%%%%
x_text = 1:1:n(1)*n(2); %產(chǎn)生所需數(shù)值.
for i = 1:1:n(1)*n(2)
[row,col] = ind2sub([n(2),n(1)],i);
text(row-0.9,col-0.5,num2str(x_text(i)),'FontSize',8,'Color','0.7 0.7 0.7');
end
hold on
axis square
建立環(huán)境矩陣，1代表黑色柵格，0代表白色柵格，調(diào)用以上程序，即可得到上述環(huán)境地圖。
map=[0 0 0 1 0 0 1 0 0 0;
1 0 0 0 0 1 1 0 0 0;
0 0 1 0 0 0 1 1 0 0;
0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 1 0 0 1 0;
1 0 0 0 0 1 1 0 0 0;
0 0 0 1 0 0 0 0 0 0;
1 1 1 0 0 0 1 0 0 0;
0 0 0 0 0 1 1 0 0 0;
0 0 0 0 0 1 1 0 0 0;];
DrawMap(map); %得到環(huán)境地圖
2.4 柵格地圖中障礙柵格處路徑約束
移動(dòng)體柵格環(huán)境中多采用八方向的移動(dòng)方式，此移動(dòng)方式在完全可通行區(qū)域不存在運(yùn)行安全問(wèn)題，當(dāng)
移動(dòng)體周圍存在障礙柵格時(shí)此移動(dòng)方式可能會(huì)發(fā)生與障礙物柵格的碰撞問(wèn)題，為解決此問(wèn)題加入約束
條件，當(dāng)在分別與障礙物柵格水平方向和垂直方向的可行柵格兩柵格之間通行時(shí)，禁止移動(dòng)體采用對(duì)
角式移動(dòng)方式。
約束條件的加入，實(shí)質(zhì)是改變柵格地圖的鄰接矩陣，將障礙柵格(數(shù)字為“1”的矩陣元素)的對(duì)角柵格
設(shè)為不可達(dá)， 即將對(duì)角柵格的距離值改為無(wú)窮大。其實(shí)現(xiàn)MATLAB代碼如下：
代碼：
%約束移動(dòng)體在障礙柵格對(duì)角運(yùn)動(dòng)
%通過(guò)優(yōu)化鄰接矩陣實(shí)現(xiàn)
%%%%%%%%%%%%%%%%%% 約束移動(dòng)體移動(dòng)方式 %%%%%%%%%%%%%%%%%
function W=OPW(map,W)
% map 地圖矩陣 % W 鄰接矩陣
n = size(map);
num = n(1)*n(2);
for(j=1:n(1))
for(z=1:n(2))
if(map(j,z)==1)
if(j==1) %若障礙物在第一行
if(z==1) %若障礙物為第一行的第一個(gè)
W(j+1,j+n(2)*j)=Inf;
W(j+n(2)*j,j+1)=Inf;
else
if(z==n(2)) %若障礙物為第一行的最后一個(gè)
W(n(2)-1,n(2)+n(1)*j)=Inf;
W(n(2)+n(1)*j,n(2)-1)=Inf;
else %若障礙物為第一行的其他
W(z-1,z+j*n(2))=Inf;
W(z+j*n(2),z-1)=Inf;
W(z+1,z+j*n(2))=Inf;
W(z+j*n(2),z+1)=Inf;
end
end
end
if(j==n(1)) %若障礙物在最后一行
if(z==1) %若障礙物為最后一行的第一個(gè)
W(z+n(2)*(j-2),z+n(2)*(j-1)+1)=Inf;
W(z+n(2)*(j-1)+1,z+n(2)*(j-2))=Inf;
else
if(z==n(2)) %若障礙物為最后一行的最后一個(gè)
W(n(1)*n(2)-1,(n(1)-1)*n(2))=Inf;
W((n(1)-1)*n(2),n(1)*n(2)-1)=Inf;
else %若障礙物為最后一行的其他
W((j-2)*n(2)+z,(j-1)*n(2)+z-1)=Inf;
W((j-1)*n(2)+z-1,(j-2)*n(2)+z)=Inf;
W((j-2)*n(2)+z,(j-1)*n(2)+z+1)=Inf;
W((j-1)*n(2)+z+1,(j-2)*n(2)+z)=Inf;
end
end
end
if(z==1)
if(j~=1&&j~=n(1)) %若障礙物在第一列非邊緣位置
W(z+(j-2)*n(2),z+1+(j-1)*n(2))=Inf;
W(z+1+(j-1)*n(2),z+(j-2)*n(2))=Inf;
W(z+1+(j-1)*n(2),z+j*n(2))=Inf;
W(z+j*n(2),z+1+(j-1)*n(2))=Inf;
end
end
if(z==n(2))
if(j~=1&&j~=n(1)) %若障礙物在最后一列非邊緣位置
W((j+1)*n(2),j*n(2)-1)=Inf;
W(j*n(2)-1,(j+1)*n(2))=Inf;
W(j*n(2)-1,(j-1)*n(2))=Inf;
W((j-1)*n(2),j*n(2)-1)=Inf;
end
end
if(j~=1&&j~=n(1)&&z~=1&&z~=n(2)) %若障礙物在非邊緣位置
W(z+(j-1)*n(2)-1,z+j*n(2))=Inf;
W(z+j*n(2),z+(j-1)*n(2)-1)=Inf;
W(z+j*n(2),z+(j-1)*n(2)+1)=Inf;
W(z+(j-1)*n(2)+1,z+j*n(2))=Inf;
W(z+(j-1)*n(2)-1,z+(j-2)*n(2))=Inf;
W(z+(j-2)*n(2),z+(j-1)*n(2)-1)=Inf;
W(z+(j-2)*n(2),z+(j-1)*n(2)+1)=Inf;
W(z+(j-1)*n(2)+1,z+(j-2)*n(2))=Inf;
end
end
end
end
end
2.5 柵格法案例
下面以Djkstra算法為例， 其實(shí)現(xiàn)如下：
map=[0 0 0 1 0 0 1 0 0 0;
1 0 0 0 0 1 1 0 0 0;
0 0 1 0 0 0 1 1 0 0;
0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 1 0 0 1 0;
1 0 0 0 0 1 1 0 0 0;
0 0 0 1 0 0 0 0 0 0;
1 1 1 0 0 0 1 0 0 0;
0 0 0 0 0 1 1 0 0 0;
0 0 0 0 0 1 1 0 0 0;];
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%建立環(huán)境矩陣map%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
DrawMap(map); %得到環(huán)境地圖
W=G2D(map); %得到環(huán)境地圖的鄰接矩陣
W(W==0)=Inf; %鄰接矩陣數(shù)值處理
W=OPW(map,W); %優(yōu)化鄰接矩陣
[distance,path]=dijkstra(W,1,100);%設(shè)置起始柵格，得到最短路徑距離以及柵格路徑
[x,y]=Get_xy(distance,path,map); %得到柵格相應(yīng)的x，y坐標(biāo)
Plot(distance,x,y); %畫出路徑
運(yùn)行結(jié)果如下：
其中函數(shù)程序：
DrawMap(map) 詳見建立柵格地圖
W=G2D(map) ； 詳見建立鄰接矩陣
[distance， path] =dijkstra(W， 1， 100) 詳見Djk stra算法
[x， y] =Get_xy(distance， path， map) ；
Plot(distance， x， y) ；
?二、部分源代碼
clc
clear
close all
tic
%% 地圖
G=[0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0;
0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0;
0 0 0 0 1 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0;
0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0;
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0;
1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0;
1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 1 1 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0;
0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0;];
for i=1:20/2
for j=1:20
m=G(i,j);
n=G(21-i,j);
G(i,j)=n;
G(21-i,j)=m;
end
end
%%
S = [1 1];
E = [20 20];
G0 = G;
G = G0(S(1):E(1),S(2):E(2));
[Xmax,dimensions] = size(G);
dimensions = dimensions - 2;
X_min = 1;
%% 參數(shù)設(shè)置
max_gen = 200; % 最大迭代次數(shù)
num_polution = 50; % 種群數(shù)量
fboj=@(x)fitness(x,G,X_min,Xmax);
?三、運(yùn)行結(jié)果
?四、matlab版本及參考文獻(xiàn)
1 matlab版本
2014a
2 參考文獻(xiàn)
[1]陳云霽，范道生，劉新宇. “基于正弦余弦算法的自主導(dǎo)航機(jī)器人路徑規(guī)劃研究.” 自動(dòng)化學(xué)報(bào)，2012年，38(8): 1465-1474.
[2]陳云霽，范道生，劉新宇. “基于正弦余弦算法的機(jī)器人路徑規(guī)劃實(shí)驗(yàn)研究.” 科技通報(bào)，2011年，27(11): 68-71.
[3]張銀紅，楊琳. “基于正弦余弦算法的柵格地圖機(jī)器人路徑規(guī)劃研究.” 計(jì)算機(jī)技術(shù)與發(fā)展，2012年，22(7): 12-15.
[4]劉江波，吳天一. 《柵格地圖機(jī)器人路徑規(guī)劃算法及其應(yīng)用》. 清華大學(xué)出版社，2016年.文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-763386.html
3 備注
簡(jiǎn)介此部分摘自互聯(lián)網(wǎng)，僅供參考，若侵權(quán)，聯(lián)系刪除文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-763386.html
到了這里，關(guān)于【路徑規(guī)劃】鯨魚算法柵格地圖機(jī)器人最短路徑規(guī)劃【含Matlab源碼 3613期】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
