2011年数学建模B题 遗传算法优化平台设置matlab实现

建模B题 遗传算法优化平台设置matlab实现"/>

2011年数学建模B题 遗传算法优化平台设置matlab实现

最近做了2011年数学建模B题，老师要求用遗传算法实现，参考了高瑜隆的获奖论文《交巡警服务平台的设置与调度模型》，将文中提到的算法思路用代码实现了一下，由于MATLAB水平有限，遇到了很多问题，但所幸都一一解决了，代码做了详细注释，仅供学习交流使用。代码中首先利用题目提供的数据，得到了节点间最短距离矩阵，使用了FLOYD算法，最重要的是覆盖率函数。

%主函数
%构造加权邻接矩阵
%第一步算出路线节点间的距离；
load jiedian.txt
load daolu.txt
a=daolu;
b=jiedian;
dis=zeros(length(b));
for i=1:582for j=1:582if i==jdis(i,j)=0;elsedis(i,j)=inf;endend
end
for k=1:928x1=b(a(k,1),2);y1=b(a(k,1),3);x2=b(a(k,2),2);y2=b(a(k,2),3);dis(a(k,1),a(k,2))=sqrt((x1-x2)^2+(y1-y2)^2);
end
for m=1:582for n=1:582if(dis(m,n)~=inf&&dis(m,n)~=0)dis(n,m)=dis(m,n);endend
end
%floyd算法
t=dis;
path=zeros(n);
for k=1:nfor i=1:nfor j=1:nif t(i,j)>t(i,k)+t(k,j)t(i,j)=t(i,k)+t(k,j);path(i,j)=k;endendend
end
D=t;
NIND=100;%种群大小
N=582;%个体染色体长度
Chrom=Init(NIND,N);%生成初始种群
count=1;
max_count=2001;
while count<max_countNEWChrom = variation(Chrom); %这个函数的作用是将初始种群父代复制，子代变异，输出200条染色体的集合new_Chrom = sselect(NEWChrom,D);  %此函数的作用是对200条染色体计算覆盖率，选择出其中覆盖率较大的前100条Chrom=new_Chrom;  %更新种群sb(count)=fugai(select_again(Chrom,D),D);count=count+1;
end
max_individual = select_again(Chrom,D);%此函数的作用是选择出100条染色体中，最好的个体
max_coverage =fugai(max_individual,D); %此函数是用来计算最优个体的覆盖率
plot(sb)

function fugailv=fugai(individual,D)
%输入：一个个体,以及距离矩阵
%输出：它的覆盖率
cc=individual;
q=find(cc==1);
len=length(q);
ss1=1;
z1=[];
%第一个区可覆盖的节点数
ss1=1;
for v1=1:lenif q(v1)>=1&&q(v1)<=92z1(ss1)=q(v1);    %zn存放该区的平台编号ss1=ss1+1;end
end
xx1=length(z1);
zz1=[];
nn1=1;
for h1=1:xx1zz1(nn1,:)=D(z1(h1),1:92);  %zz表示n个平台到92个节点的距离nn1=nn1+1;
end
%%先提取出所有平台到节点的距离，存放在一个矩阵中，然后遍历每一个节点，如果此节点可以找到一个距离小于30的平台，count+1
count1=0; %表示i7区满足覆盖的节点数
for kk1=1:92if min(zz1(:,kk1))<=30count1=count1+1;end
end%第二个区的覆盖节点数
z2=[];
ss2=1;
for v2=1:lenif q(v2)>=93&&q(v2)<=165z2(ss2)=q(v2);ss2=ss2+1;end
end
xx2=length(z2);
zz2=[];
nn2=1;
for h=1:xx2zz2(nn2,:)=D(z2(h),93:165);  %zz表示n个平台到92个节点的距离nn2=nn2+1;
end
%%先提取出所有平台到节点的距离，存放在一个矩阵中，然后遍历每一个节点，如果此节点可以找到一个距离小于30的平台，count+1
count2=0; %表示i7区满足覆盖的节点数
for kk2=1:165-93+1if min(zz2(:,kk2))<=30count2=count2+1;end
end%第三个区的覆盖节点数
z3=[];
ss3=1;
for v3=1:lenif q(v3)>=166&&q(v3)<=319z3(ss3)=q(v3);ss3=ss3+1;end
end
xx3=length(z3);
zz3=[];
nn3=1;
for h=1:xx3zz3(nn3,:)=D(z3(h),166:319);  %zz表示n个平台到m个节点的距离nn3=nn3+1;
end
%%先提取出所有平台到节点的距离，存放在一个矩阵中，然后遍历每一个节点，如果此节点可以找到一个距离小于30的平台，count+1
count3=0; %表示i7区满足覆盖的节点数
for kk3=1:319-166+1if min(zz3(:,kk3))<=30count3=count3+1;end
end%第四个区覆盖的节点数
z4=[];
ss4=1;
for v4=1:lenif q(v4)>=320&&q(v4)<=371z4(ss4)=q(v4);ss4=ss4+1;end
end
xx4=length(z4);
zz4=[];
nn4=1;
for h=1:xx4zz4(nn4,:)=D(z4(h),320:371);  %zz表示n个平台到92个节点的距离nn4=nn4+1;
end
%%先提取出所有平台到节点的距离，存放在一个矩阵中，然后遍历每一个节点，如果此节点可以找到一个距离小于30的平台，count+1
count4=0; %表示i7区满足覆盖的节点数
for kk4=1:371-320+1if min(zz4(:,kk4))<=30count4=count4+1;end
end%第五个区的覆盖率
z5=[];
ss5=1;
for v5=1:lenif q(v5)>=372&&q(v5)<=474z5(ss5)=q(v5);ss5=ss5+1;end
end
xx5=length(z5);
zz5=[];
nn5=1;
for h=1:xx5zz5(nn5,:)=D(z5(h),372:474);  %zz表示n个平台到92个节点的距离nn5=nn5+1;
end
%%先提取出所有平台到节点的距离，存放在一个矩阵中，然后遍历每一个节点，如果此节点可以找到一个距离小于30的平台，count+1
count5=0; %表示i7区满足覆盖的节点数
for kk5=1:474-372+1if min(zz5(:,kk5))<=30count5=count5+1;end
end%第六个区的覆盖节点数
z6=[];
ss6=1;
for v6=1:80if q(v6)>=475&&q(v6)<=582z6(ss6)=q(v6);ss6=ss6+1;end
end
xx6=length(z6);
zz6=[];
nn6=1;
for h=1:xx6zz6(nn6,:)=D(z6(h),475:582);  %zz表示n个平台到92个节点的距离nn6=nn6+1;
end
%%先提取出所有平台到节点的距离，存放在一个矩阵中，然后遍历每一个节点，如果此节点可以找到一个距离小于30的平台，count+1
count6=0; %表示i7区满足覆盖的节点数
for kk6=1:582-475+1if min(zz6(:,kk6))<=30count6=count6+1;end
endCount=count1+count2+count3+count4+count5+count6;
fugailv=Count/582;
end

function Chrom = Initpop(NIND,N)
%初始化种群
%输入
%MIND:种群大小
%N:个体染色体长度
%输出:
%初始种群
Chrom = zeros(NIND,N);  %用于存储种群
v=[ones(1,80),zeros(1,N-80)];
for i=1:NINDChrom(i,:) = v(randperm(N));  %随机生成初始种群，每个个体只包含0和1，且1的个数为80
endend

function Selch=variation(Chrom)
%%这个函数的作用是将初始种群父代复制，子代变异，输出200条染色体的集合
%输入
%Chrom是含有100条初始染色体的集合
%输出含有200条染色体的集合
a=[];
h=[];
for i=1:100a(i,:)=Chrom(i,:);h(i,:)=randperm(512,2);  %randperm函数，产生两个1—N区间上不重复的整数c=min(h(i,:));d=max(h(i,:));%变异Chrom(i,c:d)=fliplr(Chrom(i,c:d));%fliplr函数对行向量进行翻转；a(i+100,:)=Chrom(i,:);
end
Selch=a;end

function  output = untitled( NEWChrom,D )
%输入
%NEWChrom：包含200条染色体的种群
%%计算他们的覆盖率，选出其中覆盖率较大的前100条
%输出：前100条染色体的种群
[ns,nd]=size(NEWChrom);
cv=1;
cx=[];
for i=1:nscx(cv)=fugai(NEWChrom(i,:),D);  %计算种群的覆盖率，保存在cx中cv=cv+1;
end[mv mi]=max(cx);
%mv为最大值，mi为最大值索引，v(mi)=mv
[sv si]=sort(cx,2,'descend');
db=length(si);
sw=[];
for h=1:100sw(h,:)=NEWChrom(si(h),:);
end
output=sw;end

function [ max_individual ] = untitled3( new_Chrom ,D)
%输入
%NEWChrom：包含100条染色体的种群
%%计算他们的覆盖率，选出其中覆盖率最大的一条
%输出：覆盖率最大的个体
[ns,nd]=size(new_Chrom);
cv=1;
cx=[];
for i=1:nscx(cv)=fugai(new_Chrom(i,:),D);  %计算种群的覆盖率，保存在cx中cv=cv+1;
end[mv mi]=max(cx);
%mv为最大值，mi为最大值索引，v(mi)=mv
[sv si]=sort(cx,2,'descend');
db=length(si);
max_individual=new_Chrom(si(1),:);end

以上就是所有的代码了，这里再给出一段无向赋权图的实现代码，运行结果如下图所示：

下面一段代码是实现无向赋权图：
load jiedian.txt
load daolu.txt
a=daolu;
b=jiedian;
dis=zeros(length(b));
for i=1:582
for j=1:582
if i==j
dis(i,j)=1;
else
dis(i,j)=0;
end
end
end
for k=1:928
x1=b(a(k,1),2);
y1=b(a(k,1),3);
x2=b(a(k,2),2);
y2=b(a(k,2),3);
dis(a(k,1),a(k,2))=1;
end
for m=1:582
for n=1:582
if(dis(m,n)_{=inf&&dis(m,n)}=0)
dis(n,m)=dis(m,n);
end

end

end

Coordinates=cumcm2011B2(:,2:3);
gplot(dis,Coordinates,’-*’)
hold on
ax=[562,558,549,487,482,273,248,240,168,227,218,217,215,68,76,62,17,41,371,29,14,26,70,43];
for k=1:24
xxy(k,:)=b(ax(k),2:3);
end
x2=xxy(:,1);
y2=xxy(:,2);
plot(x2,y2,‘O’)
无向赋权图结果如下图所示:

欢迎留言评论，下载请注明出处。
其中的数据jiedian,daolu数据百度云链接：
链接：
提取码：rv5a