matlab改进遗传算法路径规划
本人刚接触编程，想知道matlab运行遗传算法后的路径总是弯弯曲曲的，如何改进代码才能删掉不必要的转向点，让路径变得更加平滑一点。
用的是栅格化方法，原始图片
运行后结果
想尽可能减少如下这样的转向点
其中代码如下
main.m
clc
clear
% 基于遗传算法的栅格法机器人路径规划
%%
%数据输入
clear
clc
I=imread('666.jpg'); %读入图片
I = rgb2gray(I); %将图片转为灰度图
a=20;
b=20;
l=1; %网格边长
B = imresize(I,[a/l b/l]);% 将数字矩阵转为规定的大小
G=floor(B/255);
G=~G;
G=flipud(G);
Grid=double(G);
DrawMap(Grid);
start_num = 0; % 起点编号
end_num = 399; % 终点序号
NP = 200; % 种群数量
max_gen = 50; % 最大进化代数
pc = 0.8; % 交叉概率
pm = 0.2; % 变异概率
a = 1; % 路径长度比重
b = 7; % 路径顺滑度比重
z = 1;
new_pop1 = {}; % 元胞数组，存放路径
[y, x] = size(Grid);
% 起点所在列（从左到右编号1.2.3...）
start_column = mod(start_num, x) + 1;
% 起点所在行（从上到下编号行1.2.3...）
start_row = fix(start_num / x) + 1; %Y = fix(X) 将 X 的每个元素朝零方向四舍五入为最近的整数
% 终点所在列、行
end_column = mod(end_num, x) + 1;
end_row = fix(end_num / x) + 1;
%% 种群初始化step1，必经节点,从起始点所在行开始往上，在每行中挑选一个自由栅格，构成必经节点
pass_num = end_row - start_row + 1; %每条路径的节点个数
pop = zeros(NP, pass_num);%生成种群数量*节点个数的矩阵，用于存放每个个体的路径
for i = 1 : NP %每个个体（每行）循环操作：
pop(i, 1) = start_num; %每行第一列都为起点(存入起点的编号)
j = 1;
% 此for循环用于寻找除去起点和终点所在行以外每行中的自由栅格
for row_i = start_row+1 : end_row-1 %栅格的第二行到倒数第二行循环
j = j + 1;
% 存放栅格里当前行中的自由栅格序号
free = [];
for column_i = 1 : x %从第一列到第二十列中
% 栅格对应的序号
num = (column_i - 1) + (row_i - 1) * x;
% 如果该栅格为非障碍物
if Grid(row_i, column_i) == 0
% 把此栅格的编号加入free矩阵中
free = [free num];
end
end % 栅格一行里的自由栅格查询结束，自由栅格的编号存在了向量中
free_num = length(free);
% 产生小于等于本行自由栅格数量的一个随机整数
index = randi(free_num); %X = randi(imax) 返回一个介于 1 和 imax 之间的伪随机整数标量。
% 将栅格中当前行的自由栅格矩阵free中第index个栅格编号作为当前种群的第j个节点
pop(i, j) = free(index);
end %该个体的每一行的路径节点产生完成,存入了pop的第i行中
pop(i, end) = end_num; %pop的每行第最后一列都为终点(存入终点的编号)
%% 种群初始化step2将上述必经节点联结成无间断路径
single_new_pop = generate_continuous_path(pop(i, :), Grid, x);
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, Grid, 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);
min_path_value(1, i) = path_value(1, m);
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(Grid);
[~, 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')
平滑度cal_path_smooth.m
% 计算路径平滑度函数
function [path_smooth] = cal_path_smooth(pop, x)
[n, ~] = size(pop);
path_smooth = zeros(1, n);
for i = 1 : n
single_pop = pop{i, 1};
[~, m] = size(single_pop);
for j = 1 : m - 2
% 点i所在列（从左到右编号1.2.3...）
x_now = mod(single_pop(1, j), x) + 1;
% 点i所在行（从上到下编号行1.2.3...）
y_now = fix(single_pop(1, j) / x) + 1;
% 点i+1所在列、行
x_next1 = mod(single_pop(1, j + 1), x) + 1;
y_next1 = fix(single_pop(1, j + 1) / x) + 1;
% 点i+2所在列、行
x_next2 = mod(single_pop(1, j + 2), x) + 1;
y_next2 = fix(single_pop(1, j + 2) / x) + 1;
%path_smooth(1, i) = path_smooth(1, i) + abs(atan(abs(x_now - x_next1)/abs(y_now - y_next1))-atan(abs(x_next2 - x_next1)/abs(y_next2 - y_next1)));
%a2 = (x_now - x_next1)^2 + (y_now - y_next1)^2;
%b2 = (x_next2 - x_next1)^2 + (y_next2 - y_next1)^2;
c2 = (x_now - x_next2)^2 + (y_now - y_next2)^2;
%angle = (a2 + c2 - b2) / (2 * sqrt(a2) * sqrt(c2));
if c2 < 8 && c2 > 4
path_smooth(1, i) = path_smooth(1, i) + 5;
elseif c2 <= 4 && c2 > 1
path_smooth(1, i) = path_smooth(1, i) + 30;
elseif c2 <= 1
path_smooth(1, i) = path_smooth(1, i) + 5000;
end
end
end
路径长度cal_path_value.m
% 计算路径长度函数
function [path_value] = cal_path_value(pop, x)
[n, ~] = size(pop);
path_value = zeros(1, n);
for i = 1 : n
single_pop = pop{i, 1};
[~, m] = size(single_pop);
for j = 1 : m - 1
% 点i所在列（从左到右编号1.2.3...）
x_now = mod(single_pop(1, j), x) + 1;
% 点i所在行（从上到下编号行1.2.3...）
y_now = fix(single_pop(1, j) / x) + 1;
% 点i+1所在列、行
x_next = mod(single_pop(1, j + 1), x) + 1;
y_next = fix(single_pop(1, j + 1) / x) + 1;
if abs(x_now - x_next) + abs(y_now - y_next) == 1
path_value(1, i) = path_value(1, i) + 1;
else
path_value(1, i) = path_value(1, i) + sqrt(2);
end
end
end
交叉crossover.m
%交叉操作
%输入变量：pop：父代种群，pc：交叉的概率
%输出变量：newpop：交叉后的种群
function [new_pop] = crossover(pop, pc)
[px,~] = size(pop);
% 判断路径点数是奇数或偶数
parity = mod(px, 2);
new_pop = {};
for i = 1:2:px-1
singal_now_pop = pop{i, 1};
singal_next_pop = pop{i+1, 1};
[lia, lib] = ismember(singal_now_pop, singal_next_pop);
[~, n] = find(lia == 1);
[~, m] = size(n);
if (rand < pc) && (m >= 3)
% 生成一个2-m-1之间的随机数
r = round(rand(1,1)*(m-3)) +2;
crossover_index1 = n(1, r);
crossover_index2 = lib(crossover_index1);
new_pop{i, 1} = [singal_now_pop(1:crossover_index1), singal_next_pop(crossover_index2+1:end)];
new_pop{i+1, 1} = [singal_next_pop(1:crossover_index2), singal_now_pop(crossover_index1+1:end)];
else
new_pop{i, 1} =singal_now_pop;
new_pop{i+1, 1} = singal_next_pop;
end
if parity == 1
new_pop{px, 1} = pop{px, 1};
end
end
图片处理DrawMap.m
%创建具有障碍物的栅格地图
%矩阵中1代表黑色栅格
function G = DrawMap(G)%函数声明
b = G;
b(end+1,end+1) = 0;
colormap([1 1 1;0 0 0]); % 创建颜色
pcolor(0.5:size(G,2) + 0.5, 0.5:size(G,1) + 0.5, b); %赋予栅格颜色
set(gca, 'XTick', 1:size(G,1), 'YTick', 1:size(G,2));%设置坐标
axis image xy; % 沿每个坐标轴使用相同的数据单位，保持一致
generate_continuous_path.m
% 将必经节点联结成无间断路径
function [single_new_pop] = generate_continuous_path(single_pop, G, x)
i = 1;
single_new_pop = single_pop;
[~, single_path_num] = size(single_new_pop);
while i ~= single_path_num
% 点i所在列（从左到右编号1.2.3...）
x_now = mod(single_new_pop(1, i), x) + 1;
% 点i所在行（从上到下编号行1.2.3...）
y_now = fix(single_new_pop(1, i) / x) + 1;
% 点i+1所在列、行
x_next = mod(single_new_pop(1, i + 1), x) + 1;
y_next = fix(single_new_pop(1, i + 1) / x) + 1;
% 初始化最大迭代次数
max_iteration = 0;
% 判断点i和i+1是否连续,若不连续插入值
while max(abs(x_next - x_now), abs(y_next - y_now)) ~= 1
x_insert = floor((x_next + x_now) / 2);
y_insert = floor((y_next + y_now) / 2);
% 插入栅格为自由栅格
if G(y_insert, x_insert) == 0
% 栅格序号
num_insert = (x_insert - 1) + (y_insert - 1) * x;
% 插入新序号
single_new_pop = [single_new_pop(1, 1:i), num_insert, single_new_pop(1, i+1:end)];
% 插入栅格为障碍物栅格
else
% 往左走
if G(y_insert, x_insert - 1) == 0 && ((x_insert - 2) + (y_insert - 1) * x ~= single_new_pop(1, i)) && ((x_insert - 2) + (y_insert - 1) * x ~= single_new_pop(1, i+1))
x_insert = x_insert - 1;
% 栅格序号
num_insert = (x_insert - 1) + (y_insert - 1) * x;
% 插入新序号
single_new_pop = [single_new_pop(1, 1:i), num_insert, single_new_pop(1, i+1:end)];
% 往右走
elseif G(y_insert, x_insert + 1) == 0 && (x_insert + (y_insert - 1) * x ~= single_new_pop(1, i)) && (x_insert + (y_insert - 1) * x ~= single_new_pop(1, i+1))
x_insert = x_insert + 1;
% 栅格序号
num_insert = (x_insert - 1) + (y_insert - 1) * x;
% 插入新序号
single_new_pop = [single_new_pop(1, 1:i), num_insert, single_new_pop(1, i+1:end)];
% 向上走
elseif G(y_insert + 1, x_insert) == 0 && ((x_insert - 1) + y_insert * x ~= single_new_pop(1, i)) && ((x_insert - 1) + y_insert * x ~= single_new_pop(1, i+1))
y_insert = y_insert + 1;
% 栅格序号
num_insert = (x_insert - 1) + (y_insert - 1) * x;
% 插入新序号
single_new_pop = [single_new_pop(1, 1:i), num_insert, single_new_pop(1, i+1:end)];
% 向下走
elseif G(y_insert - 1, x_insert) == 0 && ((x_insert - 1) + (y_insert - 2) * x ~= single_new_pop(1, i)) && ((x_insert - 1) + (y_insert-2) * x ~= single_new_pop(1, i+1))
y_insert = y_insert - 1;
% 栅格序号
num_insert = (x_insert - 1) + (y_insert - 1) * x;
% 插入新序号
single_new_pop = [single_new_pop(1, 1:i), num_insert, single_new_pop(1, i+1:end)];
% 其他情况舍去此路径
else
%break_pop = single_new_pop
single_new_pop = [];
break
end
end
x_next = x_insert;
y_next = y_insert;
max_iteration = max_iteration + 1;
if max_iteration > 20000
single_new_pop = [];
break
end
end
if isempty(single_new_pop)
break
end
[~, single_path_num] = size(single_new_pop);
i = i + 1;
end
mutation.m
% 变异操作
% 函数说明
% 输入变量：pop：种群，pm：变异概率
% 输出变量：newpop变异以后的种群
function [new_pop] = mutation(pop, pm, G, x)
[px, ~] = size(pop);
new_pop = {};
for i = 1:px
% 初始化最大迭代次数
max_iteration = 0;
single_new_pop = pop{i, 1};
[~, m] = size(single_new_pop);
% single_new_pop_slice初始化
single_new_pop_slice = [];
if(rand < pm)
while isempty(single_new_pop_slice)
% 生成2-（m-1）的两个随机数,并排序
mpoint = sort(round(rand(1,2)*(m-3)) + [2 2]);
single_new_pop_slice = [single_new_pop(mpoint(1, 1)-1) single_new_pop(mpoint(1, 2)+1)];
single_new_pop_slice = generate_continuous_path(single_new_pop_slice, G, x);
%max_iteration = max_iteration + 1;
if max_iteration >= 100000
break
end
end
if max_iteration >= 100000
new_pop{i, 1} = pop{i, 1};
else
new_pop{i, 1} = [single_new_pop(1, 1:mpoint(1, 1)-1), single_new_pop_slice(2:end-1), single_new_pop(1, mpoint(1, 2)+1:m)];
end
% single_new_pop_slice再次初始化
single_new_pop_slice = [];
else
new_pop{i, 1} = pop{i, 1};
end
end
轮盘selection.m
% 用轮盘堵法选择新的个体
% 输入变量：pop元胞种群，fitvalue：适应度值
% 输出变量：newpop选择以后的元胞种群
function [new_pop] = selection(pop, fit_value)
%构造轮盘
[px, ~] = size(pop);
total_fit = sum(fit_value);
p_fit_value = fit_value / total_fit;
p_fit_value = cumsum(p_fit_value); % 概率求和排序
% 随机数从小到大排列
ms = sort(rand(px, 1));
fitin = 1;
newin = 1;
while newin <= px
if(ms(newin)) < p_fit_value(fitin)
new_pop{newin, 1} = pop{fitin, 1};
newin = newin+1;
else
fitin = fitin+1;
end
end
以上代码都是在各位兄弟那里总结的，想知道如何改进代码才能使路径平滑，转折点少？
另外图片我已经自己处理了灰度和栅格化，能否把DrawMap那页代码删掉?目前删掉会导致运行不了，如何解决？
在使用遗传算法进行路径规划时，可能会出现路径弯曲的问题，这是由于算法搜索到的局部最优解并不是全局最优解，导致路径出现了折返的情况。为了解决这个问题，可以尝试以下方法：
1,调整遗传算法参数
可以尝试调整遗传算法的参数来寻找更优的路径，如增加种群数量、迭代次数、交叉概率和变异概率等参数。这些参数的调整需要综合考虑问题的复杂程度、时间和计算资源等因素。
2,引入路径平滑因素
在适应度函数中引入路径平滑因素，以减少路径折返。例如可以在适应度函数中增加路径的曲率、速度、加速度等因素，以惩罚过于弯曲的路径，鼓励算法搜索到平滑的路径。
3,应用路径平滑算法
在遗传算法的结果基础上，应用路径平滑算法，对路径进行优化。例如可以采用贝塞尔曲线、三次样条曲线等方法对路径进行平滑处理，从而达到去掉不必要转向点的目的。
4,增加随机性
增加算法的随机性，可以让算法有更大的搜索空间，有助于避免局部最优解的出现。例如可以增加一定的随机因素，如随机交叉点、随机变异率等，以增加算法的多样性。
需要注意的是，在改进遗传算法的过程中，应该充分考虑问题的特点，不断调整和优化算法，以达到更好的效果。同时也需要注意算法的时间和计算资源的消耗，尽可能提高算法的效率。
不知道你这个问题是否已经解决, 如果还没有解决的话:- 你可以看下这个问题的回答https://ask.csdn.net/questions/221229
- 除此之外, 这篇博客: 时域分析瞬时自相关算法、频域分析复倒频分析法、调制域分析过零检测算法以及时频分析小波换算法matlab仿真中的 1.3 调制域分析法 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
调制域分析法是对测量得到的信号载波幅度、信号载波频率和信号相位等信息进行运算分析，进而得到能够反映信号调制信息的特征参数的分析方法。调制域分析法可以对各种复杂脉内调制信号进行有效分析，并且对脉内无意调制信息也有一定的分析能力。
如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^