crossover.asv

遗传算法解决排课问题

% 2.3 计算个体的适应值
%遗传算法子程序
%Name:calfitvalue.m
%计算个体的适应值
function fitvalue=calfitvalue(objvalue)
global Cmin;
Cmin=0;
[px,py]=size(objvalue);
for i=1:px
if objvalue(i)+Cmin>0
temp=Cmin+objvalue(i);
else
temp=0.0;
end
fitvalue(i)=temp;
end
fitvalue=fitvalue';



% 2.4 选择复制
% 选择或复制操作是决定哪些个体可以进入下一代。
% 程序中采用赌轮盘选择法选择，这种方法较易实现。
% 根据方程 pi=fi/∑fi=fi/fsum ，选择步骤：
% 1）在第 t 代，由（1）式计算 fsum 和 pi 
% 2）产生 {0,1} 的随机数 rand( .)，求 s=rand( .)*fsum
% 3）求 ∑fi≥s 中最小的 k ，则第 k 个个体被选中
% 4）进行 N 次2）、3）操作，得到 N 个个体，成为第 t=t+1 代种群
%遗传算法子程序
%Name: selection.m
%选择复制
function [newpop]=selection(pop,fitvalue)
totalfit=sum(fitvalue);%求适应值之和
fitvalue=fitvalue/totalfit;%单个个体被选择的概率
fitvalue=cumsum(fitvalue); %如 fitvalue=[1 2 3 4]，则 cumsum(fitvalue)=[1 3 6 10] 
[px,py]=size(pop);
ms=sort(rand(px,1)); %从小到大排列，将"rand(px,1)"产生的一列随机数变成轮盘赌形式的表示方法，由小到大排列
fitin=1;  %fivalue是一向量，fitin代表向量中元素位，即fitvalue(fitin)代表第fitin个个体的单个个体被选择的概率
newin=1;  %同理
while newin<=px
if(ms(newin))<fitvalue(fitin)         %ms(newin)表示的是ms列向量中第"newin"位数值，同理fitvalue(fitin)
newpop(newin,:)=pop(fitin,:);      %赋值 ,即将旧种群中 的第fitin个个体保留到下一代(newpop)
newin=newin+1;
else
fitin=fitin+1;
end
end



% 2.5 交叉
% 交叉(crossover)，群体中的每个个体之间都以一定的概率 pc 交叉，即两个个体从各自字符串的某一位置
% （一般是随机确定）开始互相交换，这类似生物进化过程中的基因分裂与重组。例如，假设2个父代个体x1，x2为：
% x1=0100110
% x2=1010001
% 从每个个体的第3位开始交叉，交又后得到2个新的子代个体y1，y2分别为：
% y1＝0100001
% y2＝1010110
% 这样2个子代个体就分别具有了2个父代个体的某些特征。利用交又我们有可能由父代个体在子代组合成具有更高适合度的个体。
% 事实上交又是遗传算法区别于其它传统优化方法的主要特点之一。
%遗传算法子程序
%Name: crossover.m
%交叉

%********************改进交叉算子的方法**************
%与一般的遗传算法不同，才用三维编码形成的遗传基因是一个三维的小魔方，因此起交叉时交换的是这个三维坐标中的一个坐标才是最合理的，而一般的直接就是交换染
%色体的全部基因，这样不是不对，但是相对交叉基因的改变部分，那才是最好的
%***********具体步骤**********
%1：从待交叉个体集合中选择两个个体
%2：产生0-1之间随机数N，决定两个个体是否交叉
%3：定义交叉尝试次数N1
%4：产生1-2*班级数之间的随机数N2。其代表在交叉有冲突的情况下，重新尝试交叉的最大次数
%5：如果N1<N2,产生一个1-（班级数-1）之间的随机整数N3，其决定交叉点，将以N3为界限，个体一中r坐标大于N3的基因与个体二中相同位置基因交
%换基因值，如果冲突，N1=N1+1,重新执行第五步；否则将两个个体交叉后的新个体复制到下一代。
%如果N1>N2则表示交叉失败，将两个个体放回交叉个体集合，执行1


%一般的交叉算子
function [newpop]=crossover(pop,pc)
[px,py]=size(pop);
newpop=ones(size(pop));
for i=1:2:px-1
    if(rand<pc)
       cpoint=round(rand*26);%产生一个1-（班级数-1）之间的随机整数N3(班级数=26）
       for j=1:py
           [r,T,t]=bianma(j);  %解码
           if r==cpoint
           newpop(i,:)=[pop(i,1:j) pop(i+1,j+1:py)];    %个体一中r坐标大于N3的基因与个体二中相同位置基因交换基因值
           newpop(i+1,:)=[pop(i+1,1:j) pop(i,j+1:py)];
           end
       end
    else                   %交叉失败，将两个个体放回交叉个体集合
        newpop(i,:)=pop(i,:);
        newpop(i+1,:)=pop(i+1,:);
    end
end


% 2.6 变异
% 变异(mutation)，基因的突变普遍存在于生物的进化过程中。变异是指父代中的每个个体的每一位都以概率 pm 翻转，即由“1”变为“0”，
% 或由“0”变为“1”。遗传算法的变异特性可以使求解过程随机地搜索到解可能存在的整个空间，因此可以在一定程度上求得全局最优解。
%遗传算法子程序
%Name: mutation.m
%变异

%*********三维变异算子***************
%步骤：
%1：产生0-1之间随机数rand，判断是否需要变异
%2:产生1-t(t表示时间间隔，模型中都为t=40)之间随机整数mpoint,mpoint1，交换t坐标分别为mpoint,mpoint1，T,r坐标相同的基因块值
function [newpop]=mutation(pop,pm)
[px,py]=size(pop);
newpop=ones(size(pop));
for i=1:px
    if(rand<pm) %产生一随机数与变异概率比较
       mpoint=round(rand*40);
       if mpoint<=1
          mpoint=1;
       end
       mpoint1=round(rand*40);
       if mpoint1<=1
          mpoint1=1;
       end
       T1=0;
       t1=0;
       T2=0;
       t2=0;
       for j=1:py
           [r,T,t]=bianma(j);  %解码
              if r==mpoint
                  if j>1
                     T1=[T1,T];
                     t1=[t1,t];
                  else
                      T1=T;
                      t1=t;
                  end
              elseif r==mpoint1
                  if j>1
                     T2=[T2,T];
                     t2=[t2,t];
                  else
                      T2=T;
                      t2=t;
                  end
              end
       end
       Z1=[T1;t1];
       Z2=[T2;t2];   %现在得出了mpoint,mpoint1的所有有关基因的另外两个编码
        for j=1:length(Z1)
            jj=1; 
            while jj<length(Z2)+1
                if Z1(:,j)==Z2(:,jj)
                    pop(i,bianma1(mpoint,Z1(1,j),Z1(2,j)))=pop(i,bianma1(mpoint1,Z2(1,jj),Z2(2,jj)));
                    %交换t坐标分别为mpoint,mpoint1，T,r坐标相同的基因块值
                else
                    jj=jj+1;
                end
            end
        end
    end
    newpop(i,:)=pop(i,:);
end