function [global_min] = iGA1(k,m,C,q,G,pop_size,num_iter,pcross,pmut)
%采用传统顺序交叉算子，单次2-opt变异算子
%各初始值及参数如下：
C=[0 4 6 7.5 9 20 10 16 8;
4 0 6.5 4 10 5 7.5 11 10;
6 6.5 0 7.5 10 10 7.5 7.5 7.5;
7.5 4 7.5 0 10 5 9 9 15;
9 10 10 10 0 10 7.5 7.5 10;
20 5 10 5 10 0 7 9 7.5;
10 7.5 7.5 9 7.5 7 0 7 10;
16 11 7.5 6 7.5 9 7 0 10;
8 10 7.5 15 10 7.5 10 10 0];
K=9;
m=2;
q=8;
G=[0 1 2 1 2 1 4 2 2];
pop_size=30;
num_iter=30;
pcross=0.8;
pmut=0.05;
%--------------------------------------------------------------------------
k=K-1;
num_brks=m-1;
pop_rte = zeros(pop_size,k);
pop_brk = zeros(pop_size,num_brks);
for i = 1:pop_size
pop_rte(i,:) = randperm(k)+1;
pop_brk(i,:) = randbreaks(pop_rte(i,:),G,q,k);
end
new_pop_rte = zeros(pop_size,k);
new_pop_brk = zeros(pop_size,num_brks);
global_min=Inf;
total_dist = zeros(1,pop_size);
total_cost=zeros(1,pop_size);
dist_history=zeros(1,num_iter);
for iter=1:num_iter
if global_min~=67.5
for p = 1:pop_size
d = 0;cost=zeros(1,m);yuesu=zeros(1,m);
p_rte = pop_rte(p,:);
p_brk = pop_brk(p,:);
rng = [[1 p_brk+1];[p_brk k]]';
for s = 1:m
d = d + C(1,p_rte(rng(s,1)));
for i= rng(s,1):rng(s,2)-1
d = d + C(p_rte(i),p_rte(i+1));
end
d = d + C(p_rte(rng(s,2)),1);
for j=rng(s,1):rng(s,2)
cost(s)=cost(s)+G(1,p_rte(j));
end
yuesu(s)=max((cost(s)-q),0);
end
total_dist(p) = d;
total_cost(p)=total_dist(p)+100000*max(yuesu);%目标函数
end
%选择
[min_cost,index]=min(total_cost);
dist_history(iter)=min_cost;
if min_cost<global_min
global_min=min_cost;
end
new_pop_rte(1,:)=pop_rte(index,:);
new_pop_brk(1,:)=pop_brk(index,:);
fit=zeros(1,pop_size);%适应度函数
for i=1:pop_size
f=2*min_cost/(total_cost(i));
fit(i)=f;
end
F=sum(fit); %轮盘赌
p=zeros(1,pop_size);
for i=1:pop_size
p(i)=fit(i)/F;
end
p=cumsum(p);
tmp_pop = zeros(1,pop_size);
for i =1 :pop_size
r = rand;
for j = 1:length(p)
if(r < p(j))
tmp_pop(i) = j;
break;
end
end
end
%生成新种群
for s=2:pop_size
new_pop_rte(s,:)=pop_rte(tmp_pop(s-1),:);
new_pop_brk(s,:)=pop_brk(tmp_pop(s-1),:);
end
%交叉
for p=1:2:pop_size
parent_num= randperm(pop_size);
parents = parent_num(1:2);
parent1=new_pop_rte(parents(1),:);
parent1_brk=new_pop_brk(parents(1),:);
parent2=new_pop_rte(parents(2),:);
parent2_brk=new_pop_brk(parents(2),:);
[new_pop_rte(p,:),new_pop_rte(p+1,:)]=OX(parent1,parent1_brk,parent2,parent2_brk,pcross,k,C,G,q,m);
end
%变异
for p=1:pop_size
parent_num= randperm(pop_size);
parents = parent_num(1);
[new_pop_rte(p,:),new_pop_brk(p,:)]=mutation(new_pop_rte(parents,:),new_pop_brk(parents,:),pmut,k,C,G,q,m);
end
pop_rte=new_pop_rte;
pop_brk=new_pop_brk;
% plot(iter,global_min,'*');
% hold on
continue
end
disp(iter)
break
end
end
function breaks=randbreaks(pop_rte,G,q,k)
d=0;w=1;
pop_rte=randperm(k)+1;
while d<q
d=d+G(1,pop_rte(w));
w=w+1;
end
if d>q
breaks=w-2;
elseif d==q
breaks=w-1;
elseif d<q
breaks=w;
end
end
function [new_pop_rte,new_pop_brk]=mutation(pop_rte,pop_brk,pmut,k,C,G,q,m)
if rand<pmut
cost1=fit(pop_rte,pop_brk,k,m,C,G,q);
mut= randperm(k);
cmut= sort(mut(1:2));
pop_rte1=pop_rte;
pop_brk1=pop_brk;
a=pop_rte1(cmut(1));
pop_rte1(cmut(1))=pop_rte1(cmut(2)-1);
pop_rte1(cmut(2)-1)=a;
cost2=fit(pop_rte1,pop_brk1,k,m,C,G,q);
if cost1>cost2
new_pop_rte=pop_rte1;
new_pop_brk=pop_brk1;
else
new_pop_rte=pop_rte;
new_pop_brk=pop_brk;
end
else
new_pop_rte=pop_rte;
new_pop_brk=pop_brk;
end
end
function [rte1,rte2]=OX(Pop_rte1,Pop_brk1,Pop_rte2,Pop_brk2,pcross,k,C,G,q,m)
if rand<pcross
startXorPoint=mod(ceil(rand(1)*10),length(Pop_rte1) );
if startXorPoint==0
startXorPoint=startXorPoint+1;
end
xorLength=mod(floor(rand(1)*10),length(Pop_rte1));
endXorPoint=startXorPoint+xorLength;
while(endXorPoint>length(Pop_rte2) )
xorLength=mod(floor(rand(1)*10),length(Pop_rte1));
endXorPoint=startXorPoint+xorLength;
end
for randParent=1:2
if randParent==1
firstParent=Pop_rte1;
subString=Pop_rte1(startXorPoint:endXorPoint);
protoChild=zeros(1,length(Pop_rte1) );
protoChild(startXorPoint:endXorPoint)=subString;
if randParent==1
secondParent=Pop_rte2;
for p=1:length(subString)
[i,j]=find(secondParent==subString(p));
secondParent(j)=[];
end
else
secondParent=Pop_rte1;
for p=1:length(subString)
[i,j]=find(secondParent==subString(p));
secondParent(j)=[];
end
end
if startXorPoint~=1
protoChild(1:startXorPoint-1)=secondParent(1:startXorPoint-1);
end
if endXorPoint~=length(Pop_rte1)
protoChild(endXorPoint+1:length(Pop_rte1))=secondParent(startXorPoint:length(secondParent)) ;
end
offspring=protoChild;
new_pop_rte1=offspring;
else
firstParent=Pop_rte2;
subString=Pop_rte2(startXorPoint:endXorPoint);
protoChild=zeros(1,length(Pop_rte1) );
protoChild(startXorPoint:endXorPoint)=subString;
if randParent==1
secondParent=Pop_rte2;
for p=1:length(subString)
[i,j]=find(secondParent==subString(p));
secondParent(j)=[];
end
else
secondParent=Pop_rte1;
for p=1:length(subString)
[i,j]=find(secondParent==subString(p));
secondParent(j)=[];
end
end
if startXorPoint~=1
protoChild(1:startXorPoint-1)=secondParent(1:startXorPoint-1);
end
if endXorPoint~=length(Pop_rte1)
protoChild(endXorPoint+1:length(Pop_rte1))=secondParent(startXorPoint:length(secondParent)) ;
end
offspring=protoChild;
new_pop_rte2=offspring;
end
end
cost=zeros(1,4);b=zeros(1,4);
cost(1)=fit(Pop_rte1,Pop_brk1,k,m,C,G,q);
cost(2)=fit(Pop_rte2,Pop_brk2,k,m,C,G,q);
cost(3)=fit(new_pop_rte1,Pop_brk1,k,m,C,G,q);
cost(4)=fit(new_pop_rte2,Pop_brk2,k,m,C,G,q);
[b,index]=sort(cost);
a=index(1:2);
switch a(1)
case 1
rte1=Pop_rte1;
case 2
rte1=Pop_rte2;
case 3
rte1=new_pop_rte1;
case 4
rte1=new_pop_rte2;
end
switch a(2)
case 1
rte2=Pop_rte1;
case 2
rte2=Pop_rte2;
case 3
rte2=new_pop_rte1;
case 4
rte2=new_pop_rte2;
end
else
rte1=Pop_rte1;
rte2=Pop_rte2;
end
end
function [cost]=fit(new_pop_rte,new_pop_brk,k,m,C,G,q)
d = 0;cost=zeros(1,m);yuesu=zeros(1,m);
p_rte = new_pop_rte;
p_brk = new_pop_brk;
rng = [[1 p_brk+1];[p_brk k]]';
for s = 1:m
d = d + C(1,p_rte(rng(s,1)));
for i= rng(s,1):rng(s,2)-1
d = d + C(p_rte(i),p_rte(i+1));
end
d = d + C(p_rte(rng(s,2)),1);
for j=rng(s,1):rng(s,2)
cost(s)=cost(s)+G(1,p_rte(j));
end
yuesu(s)=max((cost(s)-q),0);
end
cost=d+100000*max(yuesu);
end
