%用于DSM聚合的遺傳算法
function [result,pp]=geneticDSM(a,pc,pm,popsize,stringlength)
%a是初始設計結構矩陣
% 測試用例
% 0 1 0 0 0 0 0 0 0 0 
% 1 0 0 1 0 0 0 0 0 0
% 0 0 0 0 0 0 0 0 0 1
% 0 1 0 0 1 0 1 0 0 0
% 0 0 0 1 0 0 1 1 0 0
% 0 0 0 0 0 0 0 0 0 1
% 0 0 0 1 1 0 0 1 0 1
% 0 0 0 0 1 0 1 0 0 0
% 0 0 0 0 0 0 0 0 0 1
% 0 0 1 0 0 1 1 0 1 0
%pc交叉概率0.6
%pm變異概率0.01
%popsize種群數量
%stringlength城市數目
% hnust ginger 
% e-mail:crystallove321@sina.com
pop=initial(popsize,a,stringlength);
var_best=[];
for i=1:400 %遺傳終止于400代
    newpop=section(pop,popsize,stringlength);
    newpop=crossover_ox(newpop,pc,popsize,stringlength,a);
    newpop=mutation(newpop,pm,stringlength,popsize);
    var_best=[var_best,mean(newpop(:,stringlength+1))];
    pop=newpop;
end

[bestindividual,index,pp]=best(pop,a,stringlength);
result=bestindividual;
figure(1)
plot(var_best);
figure(2)
draw_ginger(pp,a,index,stringlength);

%-----------適應值計算函數-------------%
% V是行向量V=1,3,2,4,6,5,7,8,9的一種排列
function newfit=minFKS(V,a) %a是初始設計結構矩陣n*n 求最小反饋數
    [x,y]=size(a);
    newfit=0;
    for i=1:x
        for j=1:y
            if a(x(i,j+1),x(i,j)~=0
                newfit=newfit+x(i,j+1)-x(i,j);
            end
        end
    end

%--------------初始化種群-----------------%
function pop=initial(popsize,a,stringlength) %popsize種群數量
pop=zeros(popsize,stringlength+1);
for i=1:popsize
pop(i,1:stringlength)=randperm(stringlength); %采用實數編碼方式初始種群
pop(i,stringlength+1)=distance(a(pop(i,1:stringlength),);
end
%---------------選擇算子--------------------%
function newpop=section(pop,popsize,stringlength) %錦標賽選擇算子
tt=1;
while tt<=popsize
tmb=[unidrnd(popsize),unidrnd(popsize)];
if pop(tmb(1),stringlength+1)<pop(tmb(2),stringlength+1)
newpop(tt,=pop(tmb(1),;
else
newpop(tt,=pop(tmb(2),;
end
tt=tt+1;
end
%-----------------------交叉算子-----------------------%
%采用由Davis提出OX算子—通過從一個親體中挑選一個子序列旅行并保存另一個親體的城市相對次序來構造后代
%例如，兩個親體（切割點以“|”標記）
%p1=（1 2 3 | 4 5 6 7 | 8 9）p2=（4 5 2 | 1 8 7 6 | 9 3）變為
%o1=（2 1 8 | 4 5 6 7 | 9 3）o2=（2 3 4 | 1 8 7 6 | 5 9）
function newpop=crossover_ox(newpop,pc,popsize,stringlength,a)
for i=1:2:popsize-1
if rand<pc
cpoint1=unidrnd(stringlength-1);
cpoint2=unidrnd(stringlength-1);
X=sort([cpoint1,cpoint2]);
temp_1=newpop(i,X(1)(2));
temp_2=newpop(i+1,X(1)(2));
temp1=newpop(i,1:stringlength);
temp2=newpop(i+1,1:stringlength);
for j=1:length(temp_1)
k=find(temp2==temp_1(j));
temp2(k)=[];
end
for j=1:length(temp_2)
k=find(temp1==temp_2(j));
temp1(k)=[];
end
newpop(i,1:stringlength)=[temp2(1(1)-1),temp_1,temp2(X(1):end)];
newpop(i+1,1:stringlength)=[temp1(1(1)-1),temp_2,temp1(X(1):end)];
newpop(i,stringlength+1)=distance(a(newpop(i,1:stringlength),);
newpop(i+1,stringlength+1)=distance(a(newpop(i+1,1:stringlength),);
else
newpop(i,=newpop(i,;
newpop(i+1,=newpop(i+1,;
end
end
%--------------------變異算子------------------%
function newpop=mutation(newpop,pm,stringlength,popsize)%采用倒置變異算法
for i=1:popsize
if pm>rand
p1=unidrnd(stringlength-1);
p2=unidrnd(stringlength-1);
if p1<p2
newpop(i,1:stringlength)=[newpop(i,1:p1-1),fliplr(newpop(i,p1:p2)),newpop(i,p2+1:stringlength)];
elseif p1==p2
newpop(i,1:stringlength)=[fliplr(newpop(i,1:p1-1)),newpop(i,p1),fliplr(newpop(i,p1+1:stringlength))];
elseif p1>p2
newpop(i,1:stringlength)=[fliplr(newpop(i,1:p2)),newpop(i,p2+1:p1-1),fliplr(newpop(i,p1:stringlength))];
end
end
end
%------------------計算最大適應值-----------------%
function [bestindividual,index,pp]=best(newpop,a,stringlength)
[px,py]=size(newpop);
tt=newpop(1,py);
for i=2:px
if newpop(i,py)<tt
tt=newpop(i,py);
end
end
bestindividual=tt;
[index_x,index_y]=find(newpop==tt);
index=index_x;
pp=a(newpop(index_x(1),1:stringlength),;

%------------------畫圖函數-------------------%
function draw_ginger(pp,a,index,stringlength)
scatter(pp(:,1),pp(:,2),'r*');
hold on
plot([pp(1,1),pp(stringlength,1)],[pp(1,2),pp(stringlength,2)])
hold on
for i=2:stringlength
x0=pp(i-1,1);
y0=pp(i-1,2);
x1=pp(i,1);
y1=pp(i,2);
xx=[x0,x1];
yy=[y0,y1];
plot(xx,yy)
hold on
end