一、模型介绍
1.1 遗传算法
遗传算法(GA,Genetic Algorithm),也称为进化算法。遗传算法是受达尔文的进化论的启发,借鉴生物进化过程而提出的一种启发式搜索算法。其主要特点是直接对结构对象进行操作,因此不同于其他求解最优解的算法,遗传算法不存在求导和对函数连续性的限定,采用概率化的寻优方法,不需要确定的规则就能自动获取和指导优化的搜索空间,自适应地调整搜索方向。
以上是对遗传算法相对抽象的总结,为了更具体形象的解释遗传算法的一般原理,我们首先介绍一些生物学上的概念:
①种群:不同生物个体形成的群体,生物的进化以群体的形式进行,这样的一个群体称为种群;
②个体:组成种群的单个生物;
③基因:带有遗传信息的DNA片段,可以通俗的将基因理解为一段信息,这段信息决定的生物个体的性状;
④表现型:根据基因形成的个体的外部表现;
⑤适应度:生物个体对于生存环境的适应程度,越适应那么其得以存活和繁衍的概率就越大;
⑥遗传:通过繁殖过程,子代将从父母双方各获取一部分基因,形成新的自己的基因,这个过程中,会发生基因的复制、交叉,也会以较低的概率发生基因突变;
⑦自然选择:物竞天择,适者生存的自然淘汰机制。具体为对环境适应度高的个体参与繁殖的机会比较多,后代就会越来越多。适应度低的个体参与繁殖的机会比较少,后代就会越来越少;
⑧进化:种群通过代际繁衍不断适应生存环境的过程,在这个过程中,以对外界环境的适应度为评判标准,生物的性状不断得到改良。
了解了这些术语的含义,我们就可以进一步说说生物进化的过程了。由于自然选择是客观存在的,即生物只能改变自己去适应环境,那么在自然选择的过程中,适应度低的个体会被淘汰,适应度高的个体被保留,高适应度的父体与母体又有更高的概率繁衍出适应度高的子代,因此在一代又一代的繁衍之后,高适应度的个体在种群中所占的比例越来越大,种群就这样完成了进化。
现在我们要参考生物进化的过程来设计算法解决求最优解的问题。对此,遗传算法的思路是,将要解决的问题模拟成一个生物进化的过程,通过进化来寻找最优解。以我们题目中寻找多峰函数的最大值这个问题为例:
将(x, y)这一可能的解作为一个个体;将多峰函数的函数值f(x, y)作为个体的适应度;对(x, y)进行编码作为个体的基因;以适应度为标准不断筛选生物个体;通过遗传算子(如复制、交叉、变异等)不断产生下一代。如此不断循环迭代,完成进化。最终,根据设定的迭代次数,可得到最后一代种群,该种群中的个体适应度都较高,而多峰函数的最大值就有比较大的概率存在于这一群解中,以种群中适应度最高的个体作为问题的解,则可以说该解有比较高的概率就是我们希望求得的最优解。
文字述说终究还是不如图表好理解,因此还是看图吧(下图将本题与自然遗传联系了起来):
通过以上描述,我们不难看出,遗传算法不能保证一定能求得最优解,而只能以一定的概率求最优解。但是使用遗传算法时,我们可以不用关心具体如何去找最优解,要做的只是简单的否定一些表现不好的个体。这一优点也是遗传算法能够取得广泛应用的原因之一。
2.2、算法的流程
通过上文的阐述,对于如何模拟自然进化来求题中多峰函数的最优解已经比较明晰了。这里我将列出遗传算法的主要步骤,并一一解析:
第一步:随机产生一个种群,作为问题的初代解(通常,初代解可能与最优解相差较大,这是可以容忍的,只要保证初代解是随机产生的,以确保个体基因的多样性即可);
第二步:寻找一种合适的编码方案对种群中的个体进行编码,可以选择如浮点数编码或二进制编码等常用编码方案(需要指出的是,不同的编码方案直接影响后续遗传算子的实现细节);
第三步:以多峰函数的函数值 作为个体的适应度,计算种群中每个个体的适应度(算出的适应度将为后续的个体选择提供依据);
第四步:根据适应度的高低选择参与繁衍的父体与母体,选择的原则是适应度越高的个体越可能被选中(以此不断淘汰适应度低的个体);
第五步:对被选出的父体与母体执行遗传操作,即复制父体与母体的基因,并采用交叉、变异等算子产生出子代(在较大程度保留优秀基因的基础上,变异增加了基因的多样性,从而提高找到最优解的概率);
第六步:根据一定的准则判断是继续执行算法,还是找出所有子代中适应度最高个体作为解返回并结束程序(判断的准则可以是设定的解的阈值、指定的迭代次数等)。
二、部分代码
%————————主函数——————————
% Function: Program.m
% Description: 利用遗传算法实现产品自动排序
% Input: None
% Output: None
% Return: None
% Referred: SHL.m
% SHL模型
% Ini_Pop % 初始种群生成函数
% Decoding.m % 译码函数
% Fitness.m % 适应度函数
% Selection.m % 选择函数
% Crossover.m % 交叉函数
% Mutation.m % 变异函数
% Exchange.m % 种群间基因交换函数
% Draw.m % 绘图函数
% Variable: Num_Work % 装配线工位数
% Num_Pop1 % 初始种群1个数
% Num_Pop2 % 初始种群2个数
% Num_Exc % 交换基因数目
% Pro_C1 % 初始种群1交叉概率
% Pro_C2 % 初始种群2交叉概率
% Pro_M1 % 初始种群1变异概率
% Pro_M2 % 初始种群2变异概率
% Num_Gene % 繁衍代数
% Time % 各工位时间
% Matrix % 优先关系矩阵
% Pop1 % 初始种群1
% Pop2 % 初始种群2
% Pop11 % 迭代的种群1
% Dec_Pop1 % 译码后的种群1
% Fit_Pop1 % 种群1适应度
% Sel_Pop1 % 选择后的种群1
% Cro_Pop1 % 交叉后的种群1
% Mut_Pop1 % 变异后的种群1
% Pop12 % 种群1最优保留(用于种群间交叉)
% Pop21 % 迭代的种群2
% Dec_Pop2 % 译码后的种群2
% Fit_Pop2 % 种群2适应度
% Sel_Pop2 % 选择后的种群2
% Cro_Pop2 % 交叉后的种群2
% Mut_Pop2 % 变异后的种群2
% Pop22 % 种群1最优保留(用于种群间交叉)
% Pop00 % 每次迭代最优基因
% Dec_Pop00 % 每次迭代最优基因译码结果
% Others: None
clc % 清空Workspace, Command Window 和Figure
clear
close all
%Time=[2.80 9.52 3.26 3.61 4.18 6.34 6.12 2.07 3.14 2.17 5.24 3.31 2.13 5.04 9.87 2.75 3.19 5.64 3.39 14.55 1.09 5.02 1.21 3.48 6.72 1.98 3.91 5.57 5.14 7.94 3.12 5.36 2.88 1.38 4.23 3.61 3.74 2.88 4.58 2.97 5.73 5.94 4.51 1.52 5.31 2.22 4.49 4.28 3.61 8.32 7.13 4.08];
% Matrix=[0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1;
% 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;];
Time=[13.3 10.2 6.3 19.8 6.3 20.9 14.9 6.3 13.5 5.1 16.3 5.7 19.3 9.3 9.9 18.7 8.7 4.3 6.5 5.1 13.2 4.6 7.5 15.2 7.7 15.7 8.9 13.4 21.2 16.3 17.5 21.5];
Matrix=[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;];
% Time=[6 2 5 7 1 2 3 6 5 5 4];
% Matrix=[0 1 1 1 1 0 0 0 0 0 0;
% 0 0 0 0 1 0 0 0 0 0 0;
% 0 0 0 0 0 0 1 0 0 0 0;
% 0 0 0 0 0 0 1 0 0 0 0;
% 0 0 0 0 0 0 1 0 0 0 0;
% 0 0 0 0 0 0 0 1 0 0 0;
% 0 0 0 0 0 0 0 0 1 0 0;
% 0 0 0 0 0 0 0 0 0 1 0;
% 0 0 0 0 0 0 0 0 0 0 1;
% 0 0 0 0 0 0 0 0 0 0 1;
% 0 0 0 0 0 0 0 0 0 0 0;];
% Time=[3 2 4 3 6 6 6 2];
% Matrix=[0 1 1 1 1 1 1 1;
% 0 0 1 1 0 0 0 1;
% 0 0 0 1 0 0 0 1;
% 0 0 0 0 0 0 0 1;
% 0 0 0 0 0 1 1 1;
% 0 0 0 0 0 0 1 1;
% 0 0 0 0 0 0 0 1;
% 0 0 0 0 0 0 0 0];
% set(gcf,'outerposition',get(0,'screensize')); % 最大化显示图像
% 参数初始化
Num_Work=3; % 装配线工作站数
Num_Pop1=100; % 初始种群1个数
Num_Pop2=100; % 初始种群2个数
Num_Exc=5; % 交换基因数目
Pro_C1=0.8; % 初始种群1交叉概率
Pro_C2=0.2; % 初始种群2交叉概率
Pro_M1=0.2; % 初始种群1变异概率
Pro_M2=0.05; % 初始种群2变异概率
Num_Gene=100; % 繁衍代数
%[Time,Matrix]=SHL(); % 各工位时间及优先关系矩阵
% 产生初始种群
Pop1=Ini_Pop(Matrix,Num_Pop1); % 初始种群1
Pop2=Ini_Pop(Matrix,Num_Pop2); % 初始种群2
% 遗传算法的迭代计算
Pop11=Pop1;
Pop21=Pop2;
for i=1:1:Num_Gene
% 种群1迭代
Dec_Pop1=Decoding(Pop11,Time,Num_Work); % 译码
Fit_Pop1=Fitness(Dec_Pop1,Num_Work,Time,Pop11); % 求适应度
Sel_Pop1=Selection(Fit_Pop1,Num_Pop1,Pop11); % 选择
Cro_Pop1=Crossover(Sel_Pop1,Pro_C1); % 交叉
Mut_Pop1=Mutation(Cro_Pop1,Pro_M1,Matrix); % 变异
Pop12=Mut_Pop1; % 最优保留
Dec_Pop12=Decoding(Pop12,Time,Num_Work);
Fit_Pop12=Fitness(Dec_Pop12,Num_Work,Time,Pop12);
[a1 b1]=max(Fit_Pop1); % 将最坏基因的用最好的替代
[a2 b2]=min(Fit_Pop12);
Pop12(b2,:)=Pop11(b1,:); %种群2迭代
Dec_Pop2=Decoding(Pop21,Time,Num_Work); % 译码
Fit_Pop2=Fitness(Dec_Pop2,Num_Work,Time,Pop21); % 求适应度
Sel_Pop2=Selection(Fit_Pop2,Num_Pop2,Pop21); % 选择
Cro_Pop2=Crossover(Sel_Pop2,Pro_C2); % 交叉
Mut_Pop2=Mutation(Cro_Pop2,Pro_M2,Matrix); % 变异
Pop22=Mut_Pop2; % 最优保留
Dec_Pop22=Decoding(Pop22,Time,Num_Work);
Fit_Pop22=Fitness(Dec_Pop22,Num_Work,Time,Pop22);
[a3 b3]=max(Fit_Pop2);
[a4 b4]=min(Fit_Pop22);
Pop22(b4,:)=Pop21(b3,:);
% 种群1与种群2交叉
[Pop11,Pop21]=Exchange(Pop12,Pop22,Num_Exc,Time,Num_Work);
%求出每次迭代的最优结果,并画图显示
Dec_Pop01=Decoding(Pop11,Time,Num_Work);
Fit_Pop01=Fitness(Dec_Pop01,Num_Work,Time,Pop11);
[a01 b01]=max(Fit_Pop01);
Dec_Pop02=Decoding(Pop21,Time,Num_Work);
Fit_Pop02=Fitness(Dec_Pop02,Num_Work,Time,Pop21);
[a02 b02]=max(Fit_Pop02);
if a01>a02
Pop00=Pop11(b01,:);
Dec_Pop00=Decoding(Pop11(b01,:),Time,Num_Work);
else
Pop00=Pop21(b02,:);
Dec_Pop00=Decoding(Pop21(b02,:),Time,Num_Work);
end
Draw(Pop00,Dec_Pop00,i,Time); % 绘图函数
pause(0.0010); % 延时函数
if (max(Dec_Pop00)==52) % 判断迭代是否完成
msgbox({'迭代完成,迭代次数为',num2str(i)})
break;
end
end
%迭代完成后计算最终结果
Dec_Pop1=Decoding(Pop11,Time,Num_Work);
Fit_Pop1=Fitness(Dec_Pop1,Num_Work,Time,Pop11);
[a1 b1]=max(Fit_Pop1); Dec_Pop2=Decoding(Pop21,Time,Num_Work);
Fit_Pop2=Fitness(Dec_Pop2,Num_Work,Time,Pop21);
[a2 b2]=max(Fit_Pop2);
if a1>a2
Pop=Pop11(b1,:);
Dec_Pop=Decoding(Pop11(b1,:),Time,Num_Work);
else
Pop=Pop21(b2,:);
Dec_Pop=Decoding(Pop21(b2,:),Time,Num_Work);
end
Draw(Pop,Dec_Pop,i,Time);
save data % 保存结果
三、仿真结果
四、参考文献
[1]张鹏彬. 南华电机厂混流装配线产品排序问题的研究[D]. 安徽工业大学.