遗传算法

? 遗传算法（Genetic Algorithm，GA）是一种进化算法，其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则，它最初由美国Michigan大学的J. Holland教授于1967年提出。 ? 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。因此，第一步需要实现从表现型到基因型的映射即编码工作。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

? 遗传算法有三个基本操作：选择（Selection）、交叉（Crossover）和变异（Mutation）。 ? （1）选择。选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁衍子孙。根据各个个体的适应度值，按照一定的规则或方法从上一代群体中选择出一些优良的个体遗传到下一代种群中。选择的依据是适应性强的个体为下一代贡献一个或多个后代的概率大。 ? （2）交叉。通过交叉操作可以得到新一代个体，新个体组合了父辈个体的特性。将群体中的各个个体随机搭配成对，对每一个个体，以交叉概率交换它们之间的部分染色体。 ? （3）变异。对种群中的每一个个体，以变异概率改变某一个或多个基因座上的基因值为其他的等位基因。同生物界中一样，变异发生的概率很低，变异为新个体的产生提供了机会。

遗传算法的基本步骤：

1)编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的丌同组合便构成了丌同的点。 2)初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始进化。 3)适应度评估：适应度表明个体或解的优劣性。丌同的问题，适应性函数的定义方式也丌同。

4)选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择体现了达尔文的适者生存原则。 5)交叉：交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了其父辈个体的特性。交叉体现了信息交换的思想。 6)变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样， GA中变异发生的概率很低，通常取值很小。

?带约束（工序约束，开工时间约束，切换不同作业时间开销约束）的流水线调度问题介绍

在规划阶段，有不同的加工订单要安排在多条装配线上。许多零件制造商认为，首要目标是最小化这些订单的总加权延迟时间，次要目标是最小化最大完工时间。第一个目标确保客户满意，而第二个目标增加生产能力，无需进一步投资于昂贵的设备。调度问题的假设和约束如下:

基本假设

1、零件是分批生产的。每个批次由相同的零件组成，具有相同的准备时间和截止日期。批处理称为作业。对同一块板加工不同侧面(正面和背面)的工序视为不同工序。

2、只有在同一行上产生的上一个作业完成后才能开始新的作业，即不允许抢占。

3、装配线是不相关的，也就是说，不同的生产线完成同一项工作的过程时间是不同的。通过设备供应商提供的现有软件，可以很好地估算工艺时间。

4、为实际考虑，在生产环境中，背面作业(加工零件背面的作业)只能在相应的正面作业开始2小时后才能开始。2小时的时间是由调查的零件制造商规定的。

5、一个新的作业需要0.27小时(16分钟)的普通设置(过渡)时间(上传程序，调整组件馈线等)，除非在同一条生产线上的正面作业之后再加工一个背面作业需要2h的特殊过渡时间;

基本约束

1、加工时间：每个零件在每一台装配线上的装配时间不同的

2、工序约束：个别零件加工有先后次序要求，先完成某一样才能完成另一样零件的加工

3、开工时间约束：个别零件尚未准备好，需要再一定时间后才能进行加工

4、切换不同作业时间开销约束：切换某种作业时需要较长的准备时间

模型建立

假设总共有n个工作在K条装配线上调度。引入了每条装配线开始的虚拟作业J0和每条装配线结束的虚拟作业Jn+1。[1]

具体模型介绍请查阅引用文献1

在这里插入图片描述

遗传代码

%% Initialization   初始化
empty_particle.Position=[];
empty_particle.Cost=[];
empty_particle.Sol=[];
particle=repmat(empty_particle,nPop,1);

GlobalBest.Cost=inf;

BestCost=zeros(MaxIt,1);

for i=1: nPop
    %初始化种群
    particle(i).Position=  CreateRandomSolution(model);
    %评价
    [particle(i).Cost,particle(i).Sol] =CostFunction(particle(i).Position);
    %更新全局 最优
    if particle(i).Cost<GlobalBest.Cost
        GlobalBest=particle(i);
    end
end

for iter=1:MaxIt
    
    particle = Select(particle,[particle(:).Cost]);
    
    particle = Crossover(particle,pc);
    
    particle = Mutation(particle,pm);
    
    for i=1: nPop
        %评价
        [particle(i).Cost,particle(i).Sol] =CostFunction(particle(i).Position);
        %更新全局 最优
        if particle(i).Cost<GlobalBest.Cost
            GlobalBest=particle(i);
        end
    end
    
    x = GlobalBest;
    for it2=1:MaxIt2
        % Create Neighbor
        xnew.Position=CreateNeighbor(x.Position);
        [xnew.Cost, xnew.Sol]=CostFunction(xnew.Position);
        
        if xnew.Cost<=x.Cost
            % xnew is better, so it is accepted
            x=xnew;
            
        else
            % xnew is not better, so it is accepted conditionally
            delta=xnew.Cost-x.Cost;
            p=exp(-delta/T);
            
            if rand<=p
                x=xnew;
            end
            
        end
        
        % Update Best Solution
        if x.Cost<=GlobalBest.Cost
            GlobalBest=x;
        end
        
    end
    
    BestCost(iter) = GlobalBest.Cost;
    
    % Plot Solution
    figure(1);
    PlotSolution(GlobalBest.Sol,model);
    pause(0.01);
    
    disp(['iter = ' num2str(iter) ';BestCost = ' num2str(GlobalBest.Cost)]);
end


figure
plot(BestCost,'LineWidth',2);
xlabel('迭代次数');
ylabel('目标函数值');