geneticdsm.m

使用遗传算法、模拟退火算法求解设计结构矩阵

%用于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:[e-mail]
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