crossover.m

遗传算法解决排课问题

% 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