中可以对这个定义进行稍微调整，即模型中的连线必须符合上述定义，但是并不是说只要符合上述定义的线我们都要画。因为会有一些线比较相近，我们都画出来的意义不大。
所以你需要的数据有：
障碍物各个顶点坐标，根据障碍物顶点坐标得到的图
障碍物图画好后，此时需要对障碍的顶点之间进行连线，这个时候需要的数据为：连线的两个顶点为一组序号，有多少条连线就有多少组序号。
得到上述障碍物顶点的连线后，相邻的
连线中点则构成一条路径。而哪些连线中点进行连接是由我们自己设定的，这时需要的数据为一个矩阵，
1表示两连线中点相连，
0表示两连线中点不相连。可以得到下图。
得到上述路径图后，遍可以进行
Dijkstra路径规划了
2.
Dijkstra路径规划
进行
Dijkstra路径规划其实就是上述第三步中得到连线中点的连线进行路径规划，此时需要的数据就是连线中点的坐标，中点连接矩阵（
0表示不相连，
1表示相连）。
关于
Dijkstra路径规划具体是怎么做的，这个可参考其他博客，这是个很经典的问题，其他博客中有很详细的介绍。在此不做赘述。
得到的路径规划图如下
3.
遗传算法路径规划
我们对这个问题进行回顾，这个问题是先进行
Dijkstra路径规划再进行遗传算法规划的，而
Dijkstra进行路径规划时的路径是由连线中点构成的。得到的
Dijkstra最优路径也是由中点连线构成的路径。所以再用遗传算法进行路径优化时，其实是在改边连线点的位置（之前是中点的连线），即现在不再是中点的连线了，而是某个点的连线，具体是哪个点我们需要用遗传算法求出来。因此基于上述工作，我们编写遗传算法程序求得点的位置。
%%%% 遗传算法求图论二维路径规划（先Dijkstra）
%%%% by 圆 一个有心的人在用心做事
%%%% 2019-08-01
%%%% 如有问题请联系 QQ530807088(已满)/3171304690
新浪微博:MATLAB圆创工作室
% ======================= 高 端 定 制 · 华 丽 分 割
======================
clc
clear
close all
%% 输入数据
data = xlsread('数据.xlsx',1);
L = xlsread('数据.xlsx',2);
sign = xlsread('数据.xlsx',3);
sign(isnan(sign)) = 0;
position = data(:,1:2);
tag = data(:,3);
% 起点和终点
S = [20,180];
T = [160,90];
%% 绘图
figure
plot([0,200],[0,200],'.');
box on
hold on
xlabel('m')
ylabel('m')
title('遗传算法二维空间路径规划')
% 绘制障碍
NB = length(unique(tag));
% 障碍物数量
for i = 1 : NB
id = find(tag == i);
fill(position(id,1),position(id,2),[0,0,0]);
hold on
end
% 绘制起点终点
plot([S(1),T(1)],[S(2),T(2)],'r.');
text(S(1) + 2,S(2),'S');
text(T(1) + 2,T(2),'T');
% 描绘线及中点
mid = zeros(size(L));
%
所有连线中点的位置
for i = 1 : size(L,1)
% 障碍物顶点（包括边界交点）连线
plot([position(L(i,1),1),position(L(i,2),1)],
[position(L(i,1),2),position(L(i,2),2)],'b--');
% 连线中点
mid(i,:) = (position(L(i,1),:) +
position(L(i,2),:)) / 2;
plot(mid(i,1),mid(i,2),'rx');
text(mid(i,1)+2,mid(i,2),strcat('v',num2str(i)));
end
% 描绘可行路径
m = size(sign,1);
mid = [S; mid; T];
for i = 1:m
for j = i+1 : m
%
中点与中点相连
if sign(i,j) == 1
plot([mid(i,1),mid(j,1)],[mid(i,2),mid(j,2)],'color','black','Linewidth',2,'LineStyle','-');
end
end
end
% 计算距离
W = ones(size(sign))*10000;
for i = 1 : m
for j = 1 : m
if sign(i,j) == 1
W(i,j) =
sqrt(sum((mid(i,:) - mid(j,:)).^2));
end
end
end
[distance,path] = DijkstraPlan(W,1,m);
plot(mid(path,1),mid(path,2),'color','yellow','LineWidth',2,'LineStyle','--');
Pmid = path;
Pmid(end) = [];
Pmid(1) = [];
Pmid = Pmid - 1;
%
Dijkstra路径经过的中点序号
dim = length(Pmid);
%% 经过中点的两端点
lines = zeros(dim, 4);
for i = 1 : dim
lines(i,1:2) = position(L(Pmid(i),1),:);
% 中点的端点1
lines(i,3:4) = position(L(Pmid(i),2),:);
% 中点的端点2
end
K = 10;
%
线段10等分
%% 遗传算法
NP= 50;
% 种群大小
maxgen = 100;
% 最大进化代数
Pc= 0.8;
% 交叉概率
Pm= 0.2;
% 变异概率
Gap= 0.9;
% 代沟(Generation
gap)
%% 初始化种群
X = zeros(NP,dim);
for i = 1 : NP
X(i,:) = randi(K, 1, dim);
end
%% 遗传进化
gen=1;
for i = 1 : NP
Fx(i) = Fitness(X(i,:),lines,K,S,T);
% 计算目标函数值
end
bestLength = min(Fx);
while gen <= maxgen
gen
% 记录各代最优值
bestLength = min(Fx);
FG(gen) = bestLength;
% 各代最短路径
% 计算适应度
fit = 1./(Fx+1);
%
将求最短路径转为最大值fit
% 选择
XSel = Select(X,fit,Gap);
% 交叉操作
XSel = Cross(XSel,Pc);
% 变异
XSel = Mutate(XSel,Pm,K);
% 重插入子代的新种群
X = Reins(X,XSel,fit);
% 计算路线长度
for i = 1 : NP
Fx(i) =
Fitness(X(i,:),lines,K,S,T);
% 计算路线长度
end
% 更新迭代次数
gen=gen+1 ;
end
%% 画出最优解的路线图
[minLength,minInd]=min(Fx);
gbest = X(minInd,:);
%%
for i = 1 : dim
Px(i,:) = lines(i,1:2) + gbest(i) / K
*
(lines(i,3:4) - lines(i,1:2));
end
P = [S; Px; T];
% 最优路径经过的点坐标
figure(1)
plot(P(:,1),P(:,2),'r-.','LineWidth',3)
figure(2)
plot(FG,'b-')
xlabel('迭代次数')
ylabel('路径长度')
title('遗传算法优化迭代曲线')
