奉行卓越设计
打造国际品质

各位读者大家好，好久没有介绍算法的推文了，感觉愧对了读者们热爱学习的心灵。于是，今天我们带来了一个神奇的优化算法——遗传算法！

它的优点包括但不限于：

• 遗传算法对所求解的优化问题没有太多的数学要求，由于他的进化特性，搜索过程中不需要问题的内在性质，对于任意形式的目标函数和约束，无论是线性的还是非线性的，离散的还是连续的都可处理。

• 进化算子的遍历性（各态历经性）使得遗传算法能够非常有效地进行概率意义的全局搜素。

• 遗传算法对于各种特殊问题可以提供极大的灵活性来混合构造领域特有的启发式，从而保证算法的有效性

看完了是不是顿时觉得遗传算法很强大呢？

其实遗传算法在我们之前的推文中就已经出现啦，在干货 | 遗传算法(Genetic Algorithm) （附代码及注释）以及干货 | 遗传算法(Genetic Algorithm) Java 详细代码及注释里你都可以学到遗传算法的相关知识。

这次我们要介绍的是遗传算法解决混合流水车间调度问题。需要注意的是，在以上两篇推文中求解的是连续优化问题，采用浮点数编码方式可以更好达到精度和空间要求（具体见两篇推文）。而本文求解的是离散优化问题，使用二进制编码和浮点数编码会存在精度误差，使用符号编码是更好的选择。符号编码法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集如｛A,B,C…｝、{1,2,3...}（数字仅表示为符号）、{A1、A2、A3...}等。本文采用了符号编码中的数字符号编码。

废话不多说，我们赶紧来学习一下这么niubility的算法吧~

遗传算法（Genetic Algorithm，GA）是一种模拟自然选择和生物进化过程的智能优化算法。在自然界中，自从达尔文提出“优胜劣汰，适者生存”物种进化理论之后，研究学者对生物进化的过程进行了长久而又深远的研究。物种通过母代的繁衍形成新的下一代个体，新一代个体中，大多数个体由于发生染色体交叉过程会与母代类似，少数个体由于发生了变异则与母代不同。大自然作为自然选择的执行者，在生存资源和外界环境的变化、个体不断进行竞争的过程中，将适应能力强的个体留下，而淘汰适应能力差的个体，这种自然选择的过程为人类提供了一种全新的解决问题的方式。

1965年，John H. Holland首次引用了生物的进化机制来解决问题，他的学生在论文中也首次提出“遗传算法”的概念。1975年， Holland概括性总结论述了遗传算法。几十年来，越来越多的研究学者加入到遗传算法的研究中，并取得了丰富的研究成果。随着研究的深入，遗传算法以其操作简单、容易实现等优点，逐渐应用于各个领域，不仅在函数优化、组合优化等方面有所建树，同时在应用层面如机器学习、生产调度、自动控制、图像处理、数据挖掘等方面也有很广泛的应用。

生物的进化是通过染色体来实现的，染色体上有着许多控制生物性状的基因，这些基因会在遗传过程中随着染色体的交叉进行重新组合，同时会以一定概率发生变异。遗传算法的基本思路与此类似，可以将待优化问题的求解看作生物努力适应环境的过程，问题的解对应生物种群中的个体，算法的搜索便是种群一代代进化最终形成稳定物种的过程。

遗传算法的结构框架可以简述如下：

1、初始化：依据每个种群的特征随机生成第一代种群的全部个体；

2、求个体适应度：计算每个个体的适应度；

3、选择过程：依据一定的选择规范，选出一部分优秀个体参与交叉和变异操作；

4、交叉过程：群体中两两配对，交换部分染色体基因，完成交叉操作；

5、变异过程：随机改变个体中的部分基因，来实现变异操作；

6、终止判断：若新一代种群满足终止条件，停止算法迭代，记录此时的最优解为问题的最优解；否则，迭代次数加1，返回步骤2；

附遗传算法的算法流程图：

混合流水车间调度问题（Hybrid Flow Shop Scheduling Problem,  HFSSP）也称为柔性流水车间调度问题，是经典流水车间调度的推广。它综合了经典流水车间和并行机两种调度的特点，符合实际生产的要求，具有很高的研究价值和应用背景。

下图简单表示了HFSSP问题，其中假设有c加工阶段，每个阶段i有c_i（i=1，2，…m）台机器。

本文中HFSSP考虑在一条流水线上进行生产。n个工件在包含c个阶段（机器中心）的流水线上进行加工。每个工件都要依次通过每个阶段。每个阶段至少有一台加工机器并且至少有一个阶段包含多台并行机器（若每阶段有且仅有一台加工机器，则称为经典流水车间调度问题Flow Shop Scheduling Problem, FSSP）。

已知各工件的加工时间，优化目标是如何确定工件的加工顺序以及每阶段工件在机器上的分配情况，使得最大完工时间极小化。

1）同一阶段中所有机器都相同；

2）每个工件可以在某阶段的任意一台机器上进行加工；

3）任意时刻每个工件至多在一台机器上加工；

4）每台机器某时刻只能加工一个工件；

5）工件的加工过程不允许中断。

对于种群中任一个体的编码，首先加工第一道工序，在空闲机器上按编码中工件顺序依次加工相应的工件；

加工第二道工序时，按照先完工先加工的原则，在空闲机器上优先加工当前可用工件（已在上一阶段完成加工），以此类推直到最后一个工件在最后一个阶段结束完工。

递推过程如下：

(1)式表示第1个工件第1道工序的加工时间等于该工件在第一阶段的完工时间；

(2)式表示第1个工件第k道工序完工的时间等于该工件紧前工序的完工时间加上当前工序的加工时间；

(3)式表示工件j第1道工序的完工时间，等于同一机器上紧前工件第1道工序的完工时间加上工件j第1道工序的加工时间；

(4)式表示工件j在阶段k的完工时间，等于工件j紧前工序的完工时间或同一机器紧前工件j-1的完工时间中的最大值加上工件j在阶段k的加工时间。

因此目标函数表示如下：

即求最后一个工件在最后一个阶段完工时间的最小值。

先将工件按照1-n的顺序编号，这里编码方式采用工件编号随机全排列的方法。编码代表了工件被处理的优先级，编码方式如下图所示（以7个工件为例），1号工件的编码顺序比4号工件编码顺序靠前，那么1号工件被处理的优先级就高于4号工件，因此，当有空闲机器时且满足加工条件时，优先考虑加工1号工件。

有时，也可以采用工件在第一阶段开始加工时间由小到大的顺序对给定的工件序列进行编码，通常是在非随机生成的初始种群中会用到。

解码过程是从编码到最大完工时间的映射。下面举例说明该编码的解码过程：

为了简便，假设有3个工件，2道工序，2台并行机。工件在各阶段的加工时间为：

首先根据编码的优先级顺序，先对工件2进行处理，此时可进行工序1加工的机器都空闲，因此把工件2默认放在工序1机器1上进行加工。

接下来处理第二优先级的工件，此时可加工工序1的空闲机器只有机器2，因此将工件1放在工序1机器2上进行加工。

工件3的加工需要比较工序1两台机器完工时间，从加工时间我们可以看出，p(1,1)=3,p(1,2)=6,因此1号工件最先加工完，机器2比机器1最先空闲，我们将工件3放在机器2上进行加工。

考虑工序2的加工时，我们按照先完工先生产的原则，优先加工工序1中先完工的工件，由图中可以看出，1号工件最先完工，且工序2中两台加工机器都空闲，因此将1号工件放在机器1上加工。

同样的，我们进行工件2和工件3第2道工序的加工，当最后一个工件最后一道工序加工完成之后，工序2机器1最晚完成加工，因此最大完工时间就是工序2机器1的完工时间，由已知的加工时间可知，

该问题的最大完工时间(Makespan)为p(1,1)+p(2,1)+p(2,3)=12

适应度函数作为评价个体优劣的标准，适应度越高，则个体越接近最优解，适应度越低，则个体解越差。本文将(5)式取倒数，作为适应度函数来进行计算,即

Fitness=1/Makespan

本文采用轮盘赌的方法来选择个体。根据适应度函数求解种群中全部个体的适应度，采用轮盘赌的方式重新选择个体。

设置种群的总数M，个体i适应度为

，那么个体i被选中的概率为

由该式可见，适应度高的个体被选中进入下一代的概率大，适应度低的个体被选中进入下一代的概率相对较小。

种群中的个体随机进行两两配对，配对成功的两个个体作为父代1和父代2进行交叉操作。

随机生成两个不同的基因点位，子代1继承父代2交叉点位之间的基因片段，其余基因按顺序继承父代1中未重复的基因；子代2继承父代1交叉点位之间的基因片段，其余基因按顺序继承父代2中未重复的基因。如图所示：

采用两点变异的方式，随机生成两个基因位，并交换两个基因位上的基因。

常见的遗传算法终止条件有：

1、迭代固定次数后取最优值

2、运行固定时间后取最优值

3、确定一个优化目标，达到优化目标后就停止

本文采用第一种方法

测试问题参数取值：

工件数量n：6

工序数量c：3

每道工序并行机器数量m:2

已知各工件各道工序的加工时间如下表所示：

GA的关键参数，一般通过正交实验来确定。本文取值如下：

种群个数N取200个，交叉概率0.6，变异概率0.05，种群迭代次数G为100。

下图是一次测试所得到的最优解，最优的加工顺序为4，5，1，2，6，3，最终所用的时间为25。

将运行结果以甘特图的形式表示出来，如下图所示。

欲直接下载代码文件，关注我们的公众号哦！查看历史消息即可！

ps.input文件输入格式如下

根据中各工件各工序的加工时间，在工程文件夹下新建“input.txt”文件，并按照如下格式输入到txt文件中。

2 4 6

4 9 2

4 2 8

9 5 6

5 2 7

9 4 3

-- the end --

本文作者：李涛，华中科技大学研究生一年级。