【路徑規劃】基於matalb遺傳演算法機器人柵格地圖路徑規劃【含Matlab原始碼 022期】

一、簡介

採用柵格對機器人的工作空間進行劃分，再利用優化演算法對機器人路徑優化，是採用智慧演算法求最優路徑的一個經典問題。目前，採用蟻群演算法在柵格地圖上進行路徑優化取得比較好的效果，而利用遺傳演算法在柵格地圖上進行路徑優化在演算法顯得更加難以實現。\ 利用遺傳演算法處理柵格地圖的機器人路徑規劃的難點主要包括：1保證路徑不間斷，2保證路徑不穿過障礙。\ 用遺傳演算法解決優化問題時的步驟是固定的，就是種群初始化，選擇，交叉，變異，適應度計算這樣，那麼下面我就說一下遺傳演算法求柵格地圖中機器人路徑規劃在每個步驟的問題、難點以及解決辦法。

1、種群初始化

首先要知道遺傳演算法種群初始化的定義。遺傳演算法種群初始化是生成一定種群數量的個體，每個個體是一個可行解。這裡要注意是可行解，對於該問題也就是說是一個可行路徑，也就是說應該是一個從路徑起點到路徑終點的，且不經過障礙的路徑。怎樣進行初始化種群得到可行路徑是遺傳演算法求柵格路徑的第一個難點也是最大難點。

方法

路徑初始化可以分為兩步：第一步生成必經節點路徑，什麼是必經節點路徑？舉個例子，比如對於10*10的柵格，從左下角編號1到右上角編號100的路徑必經過第2行的一個點，第3行一個點……第9行的一個點，這是很顯然的，那麼我們在第二行的自由柵格中隨機取一個節點、第3行的自由柵格中取一個節點……第9行自由柵格取一個節點，那麼這就行程了一個必經點路徑，當然這個路徑也是間斷的。所以需要第二步，第二步就是連線這些間斷節點，而這個問題是該演算法中最難的問題，因為在連線路徑中，太難繞開障礙了，而且如果你繞開了障礙物，會發現失去了方向連不回來了。因此，在連線節點中採用中點連線法，但是中點，要取得有技巧，可在中點處取4或3個柵格，然後在這些柵格中找到自由柵格，等概率選擇，如果有最壞得情形，這些中點處柵格全都是障礙，則在這些柵格中等概率選擇一個作為路徑一點，因此該方法保證了路徑的連續性，但也有可能存在經過障礙的路徑，而這種障礙的路徑可以在適應度函式中進行懲罰。

上述初始化路徑的兩步結束後，進行簡化路徑操作，即如果路徑中有兩個相同的節點，則去掉相同節點之間的一段，這個很容易理解。

至此初始化路徑結束，你已經成功了一大步！

2、選擇

選擇和遺傳演算法的選擇是一樣的，無需特殊改動，就是根據適應度進行選擇。

3、交叉

交叉採用重複點交叉，這個也比較好理解，比如一條路徑為[1 12 13 24 25 36 45 56 ]，另一條路徑為[ 1 14 25 35 46 56]，這兩條路徑有一個公共節點25，進行交叉變成[1 12 13 24 25 35 46 56]和[1 14 25 36 45 56].

4、變異

變異的方法使用隨機生成選擇兩個節點，並去掉這兩個節點之間的路徑，之後採用上述的中帶你插入方法生成連續路徑。

5、適應度計算

適應度計算路徑長度和穿過障礙的個數，求和即可，這個比較間斷不多說，下面展示一下我寫的程式的效果。

二、原始碼

c % 基於遺傳演算法的柵格法機器人路徑規劃 clc; clear all close all; % 輸入資料,即柵格地圖 G= [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 0 0 0 1 1 0 0 0; 0 1 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0; 0 0 0 0 0 0 1 1 1 0 0 1 1 1 0 1 0 0 0 0; 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 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 1 1 1 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0 0 0; 0 1 1 1 0 0 1 1 0 0 1 0 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 0 0 1 0 1 1 1 1 0 0 0 0 0 0; 0 0 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 0 1 1 1 0 0 0 0 1 1 1 1 0; 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0; 0 0 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0; 0 0 1 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0; 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0; 0 0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 0 1 1 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]; ​ p_start = 0; % 起始序號 p_end =399; % 終止序號 NP = 200; % 種群數量 max_gen = 2000; % 最大進化代數 pc = 0.5; % 交叉概率 pm = 0.5; % 變異概率 a = 1; % 路徑長度比重 b = 7; % 路徑順滑度比重 %init_path = []; z = 1; new_pop1 = {}; % 元包型別路徑 [y, x] = size(G); % 起點所在列（從左到右編號1.2.3...） xs = mod(p_start, x) + 1; % 起點所在行（從上到下編號行1.2.3...） ys = fix(p_start / x) + 1; % 終點所在列、行 xe = mod(p_end, x) + 1; ye = fix(p_end / x) + 1; ​ % 種群初始化step1，必經節點,從起始點所在行開始往上，在每行中挑選一個自由柵格，構成必經節點 pass_num = ye - ys + 1; pop = zeros(NP, pass_num); min_value=1000; for i = 1 : NP pop(i, 1) = p_start; j = 1; % 除去起點和終點 for yk = ys+1 : ye-1 j = j + 1; % 每一行的可行點 can = []; for xk = 1 : x % 柵格序號 no = (xk - 1) + (yk - 1) * x; if G(yk, xk) == 0 % 把點加入can矩陣中 can = [can no]; end end can_num = length(can); % 產生隨機整數 index = randi(can_num); % 為每一行加一個可行點 pop(i, j) = can(index); end pop(i, end) = p_end; %pop % 種群初始化step2將上述必經節點聯結成無間斷路徑 single_new_pop = generate_continuous_path(pop(i, :), G, x); %init_path = [init_path, single_new_pop]; if ~isempty(single_new_pop) new_pop1(z, 1) = {single_new_pop}; z = z + 1; end end ​ % 計算初始化種群的適應度 % 計算路徑長度 path_value = cal_path_value(new_pop1, x); % 計算路徑平滑度 path_smooth = cal_path_smooth(new_pop1, x); fit_value = a .* path_value .^ -1 + b .* path_smooth .^ -1; ​ mean_path_value = zeros(1, max_gen); min_path_value = zeros(1, max_gen); % 迴圈迭代操作 for i = 1 : max_gen % 選擇操作 new_pop2 = selection(new_pop1, fit_value); % 交叉操作 new_pop2 = crossover(new_pop2, pc); % 變異操作 new_pop2 = mutation(new_pop2, pm, G, x); % 更新種群 new_pop1 = new_pop2; % 計算適應度值 % 計算路徑長度 path_value = cal_path_value(new_pop1, x); % 計算路徑平滑度 path_smooth = cal_path_smooth(new_pop1, x); fit_value = a .* path_value .^ -1 + b .* path_smooth .^ -1; mean_path_value(1, i) = mean(path_value); [~, m] = max(fit_value); if min(path_value)<min_value min_value=min(path_value); min_path_value(1, i) = min(path_value); else min_path_value(1, i) = min_value; end end % 畫每次迭代平均路徑長度和最優路徑長度圖 figure(1) plot(1:max_gen, mean_path_value, 'r') hold on; title(['a = ', num2str(a)', '，b = ',num2str(b)','的優化曲線圖']); xlabel('迭代次數'); ylabel('路徑長度'); plot(1:max_gen, min_path_value, 'b') legend('平均路徑長度', '最優路徑長度'); min_path_value(1, end) % 在地圖上畫路徑 [~, min_index] = max(fit_value); min_path = new_pop1{min_index, 1}; figure(2) hold on; title(['a = ', num2str(a)', '，b = ',num2str(b)','遺傳演算法機器人運動軌跡']); xlabel('座標x'); ylabel('座標y'); DrawMap(G); [~, min_path_num] = size(min_path); for i = 1:min_path_num % 路徑點所在列（從左到右編號1.2.3...） x_min_path(1, i) = mod(min_path(1, i), x) + 1; % 路徑點所在行（從上到下編號行1.2.3...） y_min_path(1, i) = fix(min_path(1, i) / x) + 1; end hold on; plot(x_min_path, y_min_path, 'r')

三、執行結果

四、備註

版本：2014a