基于改进遗传算法的路径规划MATLAB实现.doc

. . . . .
基于遗传算法的路径规划MATLAB实现
主程序：
clear all;
close all;
t=23; %过程点个数=t－1
s=500; %种群规模
pc=0.90; %交叉概率
pm=0.20; %变异概率
pop=zeros(s,t);
for i=1:s
pop(i,1:t-1)=randperm(t-1);
end
for k=1:1:2000 %进化代次数k
if mod(k,10)==1
k
end
pop=lujingdis(pop);
c=15;%选择淘汰个数
pop=lujingselect(pop,c);
p=rand;
if p>=pc
pop=lujingcross(pop);
end
if p>=pm
pop=lujingmutate(pop);
End

end
pop

min(pop(:,t))
J=pop(:,t);
fi=1./J;
[Oderfi,Indexfi]=sort(fi); %安排fi从小到大
BestS=pop(Indexfi(s),:); %使BestS=E(m),m即是属于max(fi)的Indexfi
I=BestS;
x=[2 3 6 10 14 17 22 20 23 25 30 28 25 21 29 16 18 15 9 11 6 5 ];
y=[5 26 14 29 27 24 28 22 26 30 30 17 13 15 4 13 3 1 6 2 2 7];
%过程点坐标
% x=[1 2 3 4 6 9 11 10 8 9 6 4]; %12个过程点的坐标
% y=[1 2 3 4 8 10 11 9 5 2 1 2];
for i=1:1:t-1
x1(i)=x(I(i));
y1(i)=y(I(i));
end
x(t)=x(I(1));
y(t)=y(I(1));
a = [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1];%31*31栅格
%a = [1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 1 0 0
1 0 1 0 0 1 1 1 1 1
0 0 1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 0 0 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 0 0 1 1];%11*11栅格
b = a;
b(end+1,end+1) = 0;
colormap([0 0 0;1 1 1]),pcolor(b)
axis image xy;%绘制栅格图
hold on;
figure(1);
plot(x,y,'-or');

适应度函数程序：lujingdis.m
function [pop]=qiujuli(pop)
[s,t]=size(pop);
for i=1:1:s
dd=0;
for j=1:1:t-2
dd=dd+lujingcalculate(pop(i,j),pop(i,j+1));
end
pop(i,t)=dd;
End

距离计算程序：lujingcalculate.m
function [d]=juli(m,n)
x=[2 3 6 10 14 17 22 20 23 25 30 28 25 21 29 16 18 15 9 11 6 5 ];
y=[5 26 14 29 27 24 28 22 26 30 30 17 13 15 4 13 3 1 6 2 2 7];
%x=[1 2 3 4 6 9 11 10 8 9 6 4];
% y=[1 2 3 4 8 10 11 9 5 2 1 2];
d=sqrt((x(m)-x(n))^2+(y(m)-y(n))^2)；

选择算子程序：lujingselect.m
function [pop]=select(pop,k)
[s,t]=size(pop);
m11=(pop(:,t));
m11=m11';
mmax=zeros(1,k);
mmin=zeros(1,k);
num=1;
while num<k+1
[a,mmax(num)]=max(m11);
m11(mmax(num))=a;
num=num+1;
end
num=1;
while num<k+1
[b,mmin(num)]=min(m11);
m11(mmin(num))=a;
num=num+1;
end
for i=1:k
pop(mmax(i),:)=pop(mmin(i),:);
End

交叉算子程序：lujingcross.m
function [pop]=cross(pop)
[s,t]=size(pop);
pop1=pop;
for i=1:2:s
m=randperm(t-3)+1;
crosspoint(1)=min(m(1),m(2));
crosspoint(2)=max(m(1),m(2));
for j=1:crosspoint(1)
while find(pop(i,crosspoint(1)+1:crosspoint(2))==pop(i,j))
zhi=find(pop(i,crosspoint(1)+1:crosspoint(2))==pop(i,j));
y=pop(i+1,crosspoint(1)+zhi);
pop(i,j)=y;
end
end
for j=crosspoint(2)+1:t-1
while find(pop(i,crosspoint(1)+1:crosspoint(2))==pop(i,j))
zhi=find(pop(i,crosspoint(1)+1:crosspoint(2))==pop(i,j));
y=pop(i+1,crosspoint(1)+zhi);
pop(i,j)=y;
end
end
end
[pop]=lujingdis(pop);
for i=1:s
if pop1(i,t)<pop(i,t)
pop(i,:)=pop1(i,:);
end
End

变异算子程序：lujingmutate.m
function [pop] = mutate(pop)
[s,t]=size(pop);
pop1=pop;
for i=1:2:s
m=randperm(t-3)+1;
mutatepoint(1)=min(m(1),m(2));
mutatepoint(2)=max(m(1),m(2));
mutate =round((mutatepoint(2)-mutatepoint(1))/2-0.5);
for j=1:mutate
zhong=pop(i,mutatepoint(1)+j);
pop(i,mutatepoint(1)+j)=pop(i,mutatepoint(2)-j);
pop(i,mutatepoint(2)-j)=zhong;
end
end
[pop]=lujingdis(pop);
for i=1:s
if pop1(i,t)<pop(i,t)
pop(i,:)=pop1(i,:);
end
end

6 / 6