基于MATLAB实现
数据来源：2020年大学生服务外包竞赛A类12题
核心算法代码
function [XX,Ri,Li,S] = Code_TiMu(A,Huo,n,maxroad,Size)
tic
q = Size(1);
for i = 1:length(A)
B(A(i,1)+1,A(i,2)+1) = A(i,3);
end
B(B==0) = inf;
for i = 1:length(B)
for j = 1:length(B)
[C(i,j),D{i,j}] = myfloyd(B,i,j);
end
end
% 遗传算法初值
% n 客户数
% q 载重上限
% maxroad 最大里程限制
sizepop = 10*n; % 种群规模
maxgen = 100*n; % 迭代次数
% 生成初值
for i = 1:sizepop
pop{i,:} = randperm(n);
pop_b{i,:} = DNA_BM(pop{i,:},n,q,Huo);
[F] = DNA_FZ(pop_b{i,:},Huo,C,maxroad,q);
pop_s(i,1) = F;
end
Fina_s = max(pop_s);
Y = Fina_s;
X = pop{pop_s==Fina_s,1};
% 迭代
for gen = 1:maxgen-1
% 变异
for i = 1:sizepop
pop1 = pop{i};
pop2 = unidrnd(length(pop1));
pop3 = unidrnd(length(pop1));
dna3 = pop{i};
dna3(pop3) = pop1(pop2);
dna3(pop2) = pop1(pop3);
dna4 = DNA_BM(dna3,n,q,Huo);
[F] = DNA_FZ(dna4,Huo,C,maxroad,q);
if F > pop_s(i,1)
pop{i,:} = dna3;
pop_b{i,:} = dna4;
pop_s(i,1) = F;
end
end
% 优胜
Fina_s(gen+1,1) = max(pop_s);
X = pop_b{pop_s==Fina_s(gen+1,1),1};
Y = Fina_s(gen+1,1);
if mod(gen,maxgen/5) == 0
fprintf(‘%d/%d\n’,gen,maxgen)
end
end
% 其他参数
[~,Ri,Li] = DNA_FZ(X,Huo,C,maxroad,q);
XX = 0;
for i = 1:length(X)
XX = [XX X{i} 0];
end
for i = 1:length(Li)
for j = 1:length(Size)
if Li(i) <= Size(j)
S(i) = Size(j);
end
end
end toc end function [XX,Ri,Li,S] = Code_CeShi_1(B,Huo,n,maxroad,Size) tic q = Size(1); B(B==0) = inf; for i = 1:length(B) for j = 1:length(B) [C(i,j),D{i,j}] = myfloyd(B,i,j); end end sizepop = 10*n; maxgen = 100*n; for i = 1:sizepop pop{i,:} = randperm(n); pop_b{i,:} = DNA_BM(pop{i,:},n,q,Huo); [F] = DNA_FZ(pop_b{i,:},Huo,C,maxroad,q); pop_s(i,1) = F; end Fina_s = max(pop_s); Y = Fina_s; X = pop{pop_s==Fina_s,1}; for gen = 1:maxgen-1 for i = 1:sizepop pop1 = pop{i}; pop2 = unidrnd(length(pop1)); pop3 = unidrnd(length(pop1)); dna3 = pop{i}; dna3(pop3) = pop1(pop2); dna3(pop2) = pop1(pop3); dna4 = DNA_BM(dna3,n,q,Huo); [F] = DNA_FZ(dna4,Huo,C,maxroad,q); if F > pop_s(i,1)
pop{i,:} = dna3;
pop_b{i,:} = dna4;
pop_s(i,1) = F;
end
end
Fina_s(gen+1,1) = max(pop_s);
X = pop_b{pop_s==Fina_s(gen+1,1),1};
Y = Fina_s(gen+1,1);
if mod(gen,maxgen/5) == 0
fprintf(‘%d/%d\n’,gen,maxgen)
end
end
[~,Ri,Li] = DNA_FZ(X,Huo,C,maxroad,q);
XX = 0;
for i = 1:length(X)
XX = [XX X{i} 0];
end
for i = 1:length(Li)
for j = 1:length(Size)
if Li(i) <= Size(j)
S(i) = Size(j); end end end toc end function [XX,Ri,Li,S] = Code_CeShi_2(A,Huo,n,maxroad,Size) tic q = Size(1); for i = 1:size(A,1) for j = 1:size(A,1) B(i,j) = sqrt((A(i,1)-A(j,1))^2+(A(i,2)-A(j,2))^2); end end B(B==0) = inf; for i = 1:length(B) for j = 1:length(B) [C(i,j),D{i,j}] = myfloyd(B,i,j); end end sizepop = 10*n; maxgen = 100*n; for i = 1:sizepop pop{i,:} = randperm(n); pop_b{i,:} = DNA_BM(pop{i,:},n,q,Huo); [F] = DNA_FZ(pop_b{i,:},Huo,C,maxroad,q); pop_s(i,1) = F; end Fina_s = max(pop_s); Y = Fina_s; X = pop{pop_s==Fina_s,1}; for gen = 1:maxgen-1 for i = 1:sizepop pop1 = pop{i}; pop2 = unidrnd(length(pop1)); pop3 = unidrnd(length(pop1)); dna3 = pop{i}; dna3(pop3) = pop1(pop2); dna3(pop2) = pop1(pop3); dna4 = DNA_BM(dna3,n,q,Huo); [F] = DNA_FZ(dna4,Huo,C,maxroad,q); if F > pop_s(i,1)
pop{i,:} = dna3;
pop_b{i,:} = dna4;
pop_s(i,1) = F;
end
end
Fina_s(gen+1,1) = max(pop_s);
X = pop_b{pop_s==Fina_s(gen+1,1),1};
Y = Fina_s(gen+1,1);
if mod(gen,maxgen/2) == 0
fprintf(‘%d/%d\n’,gen,maxgen)
end
end
[~,Ri,Li] = DNA_FZ(X,Huo,C,maxroad,q);
XX = 0;
for i = 1:length(X)
XX = [XX X{i} 0];
end
for i = 1:length(Li)
for j = 1:length(Size)
if Li(i) <= Size(j) S(i) = Size(j); end end end toc end function [XX,Ri,Li,S] = Code_Rand(n,maxroad,Size) tic q = Size(1); A = [0 0]; for i = 1:n A(i+1,1) = rand()*20-10; A(i+1,2) = rand()*20-10; Huo(i,1) = rand()*2; end for i = 1:size(A,1) for j = 1:size(A,1) C(i,j) = sqrt((A(i,1)-A(j,1))^2+(A(i,2)-A(j,2))^2); end end sizepop = 10*n; maxgen = 100*n; for i = 1:sizepop pop{i,:} = randperm(n); pop_b{i,:} = DNA_BM(pop{i,:},n,q,Huo); [F] = DNA_FZ(pop_b{i,:},Huo,C,maxroad,q); pop_s(i,1) = F; end Fina_s = max(pop_s); Y = Fina_s; X = pop{pop_s==Fina_s,1}; for gen = 1:maxgen-1 for i = 1:sizepop pop1 = pop{i}; pop2 = unidrnd(length(pop1)); pop3 = unidrnd(length(pop1)); dna3 = pop{i}; dna3(pop3) = pop1(pop2); dna3(pop2) = pop1(pop3); dna4 = DNA_BM(dna3,n,q,Huo); [F] = DNA_FZ(dna4,Huo,C,maxroad,q); if F > pop_s(i,1)
pop{i,:} = dna3;
pop_b{i,:} = dna4;
pop_s(i,1) = F;
end
end
Fina_s(gen+1,1) = max(pop_s);
X = pop_b{pop_s==Fina_s(gen+1,1),1};
Y = Fina_s(gen+1,1);
if mod(gen,maxgen/5) == 0
fprintf(‘%d/%d\n’,gen,maxgen)
end
end
[~,Ri,Li] = DNA_FZ(X,Huo,C,maxroad,q);
XX = 0;
for i = 1:length(X)
XX = [XX X{i} 0];
end
for i = 1:length(Li)
for j = 1:length(Size)
if Li(i) <= Size(j) S(i) = Size(j); end end end toc end function dna2 = DNA_BM(dna1,n,q,Huo) % DNA编码 k = 1; a1 = 1; dna2 = {}; for j = 2:n if sum(Huo(dna1(a1:j))) > q
dna2{k} = dna1(a1:j-1);
k = k + 1;
a1 = j;
end
end
dna2{k} = dna1(a1:end);
end
function [Z,Ri,Li,M] = DNA_FZ(dna2,Huo,C,maxroad,q)
Ri = zeros(1,length(dna2));
Li = zeros(1,length(dna2));
M = 0;
for i = 1:length(dna2)
dna3 = dna2{i};
pop1 = [0 dna3 0];
for j = 1:length(pop1)-1
Ri(i) = Ri(i) + C(pop1(j)+1,pop1(j+1)+1);
end
if Ri(i) > maxroad
M = M + 1;
end
Li(i) = sum(Huo(dna3));
end
R = sum(Ri)/sum(sum(C));
L = mean(Li)/q;
Z = 1/((1-L)+R) – M*9;
end
function [dist,mypath]=myfloyd(a,sb,db)
% 输入：a—邻接矩阵(aij)是指i 到j 之间的距离，可以是有向的
% sb—起点的标号；db—终点的标号
% 输出：dist—最短路的距离；% mypath—最短路的路径
n=size(a,1);
path=zeros(n);
for i=1:n
for j=1:n
if a(i,j)~= inf
path(i,j)=j; %j 是i 的后续点
end
end
end
for k=1:n
for i=1:n
for j=1:n
if a(i,j)>a(i,k)+a(k,j)
a(i,j)=a(i,k)+a(k,j);
path(i,j)=path(i,k);
end
end
end
end
dist=a(sb,db);
mypath=sb; t=sb;
while t~=db
temp=path(t,db);
mypath=[mypath,temp];
t=temp;
end
end
