一种基于混合遗传算法的车间生产调度的研究

刘红军，赵 帅

LIU Hong-jun, ZHAO Shuai

（沈阳理工大学 机械工程学院，沈阳 110168）

0 引言

随着科学技术的不断发展与提高，社会节奏的不断加快，将科学的管理调度技术与车间生产调度紧密结合起来，在现代加工车间中已得到了普遍应用。而如何将科学技术与车间生产调度更好的融合到一起，成为了当今科学领域普遍重视的一个问题。车间调度问题实质上就是研究在已有的资源条件和一定的约束条件下，对加工任务进行的加工时间、机器和顺序等的合理分配，从而使生产加工达到最优化的状态。

对于运用到车间调度中的算法现在普遍采用的是：遗传算法（GA）、模拟退火算法(SA) 、禁忌搜索算法(TS)、蚁群优化算法(ant colony optimization algorithms)和人工神经网络(artificial neural networks)等优化算法。虽然这些算法都能够在车间调度中应用，但是对于以上各种算法，在单独的使用过程中都会有一定的局限性，比如遗传算法可能出现早熟收敛，而禁忌搜索对于初始种群的选取和领域的结构有着较高的要求，如果初始种群过小，可能会无法得到最优解等。

本文针对遗传算法的局部搜索能力差、易限于局部最优等缺点，提出了一种适合运用于车间调度系统研究中的混合遗传算法（GA-SA-TS），即将模拟退火算法、禁忌搜索算法与遗传算法结合使用。这种算法的核心在于：在遗传算法的交叉机制中引入模拟退火算法的思想，形成模拟退火-交叉机制，从而避免遗传本身易早熟的缺点。在变异机制中使用禁忌搜索算法的思想，形成禁忌搜索-变异机制，以此解决遗传算法变异压力问题。通过这些方面的改进，提高了遗传算法的优化效率。

1 车间调度问题的描述

车间调度问题就是研究N(N1,N2,...,NN)个工件在M(M1,M2,...,MM)台机器上进行加工，每个工件具有一定数量的工序J(J1,J2,...,JJ)，每道工序可以在若干台机器上加工，加工的过程按照工件的工艺顺序完成。工件在加工的过程中要遵循以下约束：

1）每台机器在每个时刻只能加工一个工件的一道工序；

2）每道工序只能被一台机器加工；

3）每个工件按给定的工艺路线和指定的次序在机器上进行加工；

4）每个工件在每台机器上开始加工后不可停止，直到完成该道工序的加工；

5）每个工件只能在上道工序加工完成后才能开始下一道工序的加工[1]。

车间调度主要是针对工件的加工，研究在尽可能满足一些约束条件(如交货期、工艺路线、资源情况)的前提下，通过下达生产指令，安排其组成部分使用哪些生产资源、其加工时间及加工的先后顺序等，从而获得产品制造时间或成本的最优化[2]。

2 改进的遗传算法

遗传算法（GA-genetic algorithms）是Holland教授在20世纪70年代初期首先提出的。GA主要是借鉴了生物进化过程中的“适者生存”的规律，并将算法的整个过程都与生物进化过程的各概念对应了起来，例如：遗传算法中的解称为个体，算法中对解进行的编码称为染色体，算法中的适应度函数值称为适应性，根据条件选定的一组解称为种群等等。图1为遗传算法的流程图。

图1 遗传算法流程图

模拟退火算法（SA-simulated annealing）作为局部搜索算法的扩展，是以一定的接受概率选择邻域中的较优值，从而使其成为一个全局最优算法。SA是基于固体退火的原理，固体加热到一定的温度后，其内部的分子在某个空间中自由运动，随着温度的不断下降，固体内部的分子会逐渐停留在不同的状态，而当温度降到最低点时，固体内部的分子会以一种新的状态重新排列。

禁忌搜索算法（TS-tabu search）是局部邻域搜索算法的推广，它的特点是采用了禁忌技术，即禁止重复前面的工作。TS用一个禁忌表将已经遍历过的局部最优点或达到局部最优的一些过程记录下来，以便在后面的搜索中不再或者有选择的对已经记录在禁忌表中的数据进行搜索操作，从而跳出局部最优点。

本文提出的混合遗传算法（GA-SA-TS）是基于遗传算法的整体流程，在其交叉机制中引入模拟退火算法的思想，在变异机制中引入禁忌搜索算法的思想。从而改善遗传算法的局部搜索能力差的特点，进一步提高优化质量和搜索效率，弥补单一算法在优化方面的不足，达到取长补短的作用。

2.1 编码方式

运用到车间调度系统中的编码方式有：基于“串”的编码、基于位置“列表”的编码、基于工序的编码、基于工件的编码、基于偏好列表的编码、基于优先规则的编码、基于机器的编码和基于完成时间的编码等。

针对车间调度的实际情况，本文选择的是基于工件的编码方式。这种表达法把调度编码为工序的序列，每个基因代表一道工序。一般采取用自然数来命名工序。由于基于工序的编码方式本身就能满足车间作业调度问题中的占用约束和顺序约束关系，因此基于工件的编码经常被用于车间作业调度问题中。

2.2 适应度函数

遗传算法主要就是依靠对各染色体的适应度函数的数值来确定染色体的优劣。因而适应度函数的确定对于优化过程起着至关重要的作用。适应度值高的染色体被保留操作的几率就高，反之就低。

本文将工件的加工时间作为调度的评定标准，即加工完成的时间越少越好，所以车间调度问题为最小值问题，而根据适应度函数的种类，可确定其适应度函数为：

式中，cmax为一个适当的相对比较大的数，是f(x)的最大值估计，可以是一个合适的输入值[3]。

2.3 选择操作

选择操作是在群体中选择生命力强的个体产生新的群体的过程。通过对每条染色体进行选择概率的计算，选择概率较高的个体被保留下来遗传到下一代进行操作的概率就高，反之就低。选择操作算子包括轮盘赌选择、随机竞争选择、最佳保留选择、无回放随机选择、确定性选择、柔性分段选择、均匀排序、稳态复制和复制评价等，本文选择最佳保留选择算子进行选择操作，因为这种算子能够保证迭代终止结果为历代最高适应度个体。选择操作的基本流程为：

2）将各条染色体按照计算出的fi进行由高到低的排序；

3）按照种群操作数目n的要求，从排序好的染色体群中按由高到低的顺序选择出n条染色体，并将这n条染色体完整的复制到下一代群体中。

2.4 模拟退火-交叉

本文通过对模拟退火算法的研究，提出一种模拟退火-交叉机制，所谓模拟退火-交叉，就是在遗传算法的交叉机制中引用模拟退火的思想，完成遗传算法中的交叉操作。而模拟退火算法之所以成为全局寻优算法是因为其采用了Metropolis准则，该准则也被称为接受准则，其内容为：

接受概率计算公式为：

设初始状态为i，该状态的能量为Ei，然后从i的邻域N(i)中随机选一个新状态j，新状态的能量为Ej。如果Ei≥Ej，那么接受当前状态i为新状态；如果Ei＜Ej，则随机产生一个数ς∈(0,1)，如果ς＜Pij，就以j取代i成为当前状态。再重复以上新状态的产生过程，直到系统趋于能量较低的平衡状态。

本文提出的模拟退火-交叉机制就是借鉴了以上的思想，其具体操作流程如下：

就全国而言，通商口岸以外地区的新式教育在清末新政期间仍然处于起步阶段。而以上海为中心的通商口岸城市新式教育的推进明显，特别是工商实业各门类的技能教育及高等院校的设立，“清末十年间，上海至少就培养了13万多名新学学生”。[11]

2）从区域D中选取两条染色体father1，father2；

3）判断是否满足终止条件（终止条件可以分为零度法，循环总数控制法，基于不改进规则的控制法，接受概率控制法，邻域法，Lundy和Mees法，Aarts和van Laarhoven法等[3]。本文选择循环总数控制法，即给定一个温度下降次数K，当温度迭代次数达到该值时，停止运算），若满足则退出交叉操作，输出结果；否则转至4）；

4）对染色体father1，father2进行交叉操作，产生新的染色体son1，son2；

5）计算染色体father1，father2，son1，son2的适应度值；

6）根据Metropolis准则判定son1是否替代father1，son2是否替代father2；

7）计算退温函数：tk=λ.tk-1(其中k＞0，0＜λ＜1，λ取值越接近1，温度下降越慢，所以可以取λ=0.95,0.9,...)，转至3）。

2.5 禁忌搜索-变异

采用了禁忌技术是禁忌搜索算法的一大特点，所谓禁忌，就是禁止重复之前的工作。为了避免局部搜索过早陷入局部最优的缺点，禁忌搜索算法用一个禁忌表将已经到达过的局部最优点或者到达局部最优的过程记录下来，以便在后面的搜索中不再或者有选择的对禁忌表中的这些点进行搜索，从而跳出局部最优。禁忌搜索是在一个染色体所产生的邻域中进行寻优搜索操作的，而产生的邻域中的染色体是否替代原有染色体，需要运用特赦准则（也成为藐视准则）进行判定。特赦准则保证了搜索过程在全部候选解被禁或是有优于当前最优解的候选解（或状态）被禁时，能够释放特定解（或状态）。从而实现高效的全局优化搜索[4]。

本文通过对禁忌搜索算法的研究，提出一种禁忌搜索-变异机制，所谓禁忌搜索-变异，就是在遗传算法的变异机制中融入禁忌搜索的思想。

禁忌搜索-变异的操作流程如下：

1）选择一组染色体进入禁忌搜索栈中等待操作；

2）从禁忌搜索栈中选出一条染色体A1，并令Abest=A1，将禁忌表中内容清零；

3）由A1产生N个候选解（x1,x2,x3,...,xi），形成一个以A1为基础的邻域；

4）计算出3）产生的邻域中所有染色体的适应度函数f，然后根据特赦准则判定新产生的染色体是否替代原有染色体，成为Abest，本文设定的特赦准则为：

如果f(Abest)≥f(xi)，则Abest值不变，并同时将xi放入禁忌表中，禁忌长度设为L=n；如果f(Abest)＜f(xi)，则Abest=xi，同时将原来的Abest的值放入禁忌表中，禁忌长度设为L=n；

5）判定是否满足本文提出的终止条件：禁忌搜索次数n；如果满足转至6），否则转至3）；

6）判定禁忌搜索栈中的染色体是否全部完成禁忌搜索-变异操作，如果是，转至7），否则转至2）；

7）输出禁忌搜索-变异操作的结果。

3 经典算例的研究

以MATLAB2010a为开发语言，对10个不同规模的经典车间调度问题运用GA-SA-TS混合遗传算法进行了算例仿真，并将运行得到的结果与一些相关权威文献得到的结果进行了数据比对，结果如表1所示。

表1 经典算例运行结果比对

通过比对表格中的数据可知，运用GA-SA-TS算法对这些经典算例进行运算除了LA21得到的结果比TS得到的结果稍大一点以外，其余算例的结果都是目前出现的数据中的最优值。所以通过运算结果可知，运用GA-SA-TS算法到车间调度系统中进行优化运算是可行的。

4 结论

基于对遗传算法易早熟和搜索能力差等缺点的考虑，本文提出了一种以遗传算法为主体，融模拟退火算法和禁忌搜索算法思想于其中的混合遗传算法（GA-SA-TS）。即在遗传算法的交叉机制中融入模拟退火算法的思想，形成模拟退火-交叉机制。在遗传算法的变异机制中融入禁忌搜索算法的思想，形成禁忌搜索-变异机制。并通过对车间调度生产的经典算例仿真得到的数据可知，运用这种混合遗传算法，对于解决车间调度系统的问题，不但提高了运算的效率，较单纯的GA、SA、TS算法而言，在解的质量方面也有所提高。

[1]陶思南,傅鹂,蔡斌.一种求解车间作业调度的自适应混合遗传算法[J].计算机系统应用,2010,4(19):53-57.

[2]何燕.基于遗传算法的车间调度优化及其仿真[D].湖北:武汉理工大学,2006.

[3]雷英杰,张善文,李续武,周创明.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2009.

[4]董宗然,周慧.禁忌搜索算法评述.技术:96-98.

[5]Corce F D,Tadei R,Volta G.A genetic algorithm for the job shop problem[J].Computers and Operations Research,1995,22:15-24.

[6]Laarhoven P V,Aarts E, Lenstra J K.Job shop scheduling by simulated annealing[J].Operations Research,1992,40:113-125.

[7]Amico M D,Trubian M.Applying tabu search to the job shop scheduling problems[J].Annual Operations Research,1993,40:231-252.