一种基于GA－SA－TS算法的车间调度方法的研究

刘红军 赵 帅 赵 雷

(①沈阳理工大学机械工程学院，辽宁沈阳 110159;②北京城建设计研究总院有限责任公司，北京 100037)

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

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

1 车间调度问题的描述

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

(1)每台机器在每个时刻只能加工一个工件的一道工序;

(2)每道工序只能被一台机器加工;

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

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

(5)每个工件只能在上道工序加工完成后才能开始下一道工序的加工［1－2］。

2 改进的遗传算法

遗传算法［3］(GA －Genetic Algorithms)主要是借鉴了生物进化过程中“适者生存”的规律，并将算法的整个过程都与生物进化过程中的各种概念对应起来，例如:遗传算法中的解称为个体，算法中对解进行的编码称为染色体等。图1即为遗传算法的流程图。

模拟退火算法(SASimulated Annealing)是局部搜索算法的扩展，是以一定的接受概率选择邻域中的较优值，从而使SA成为一个全局最优算法。

禁忌搜索算法［4－5］(TS － Tabu Search)也是局部邻域搜索算法的推广。它的特点是采用了禁忌技术，即禁止重复前面的工作，从而跳出局部最优。

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

2.1 编码方式

运用到车间调度系统中的编码方式有:基于“串”的编码、基于位置“列表”的编码、基于工序的编码、基于工件的编码、基于偏好列表的编码、基于优先规则的编码、基于机器的编码和基于完成时间的编码等。针对车间调度的实际情况，本文选择的是基于工件的编码方式。这种编码方式把调度编码为工序的序列，每个基因代表一道工序。一般采用自然数来命名工序。由于基于工序的编码方式本身就能满足车间作业调度问题中的占用约束和顺序约束的关系，因此该编码方式常用于车间作业调度问题中。

2.2 适应度函数

遗传算法中，主要就是依靠对各染色体的适应度函数的数值来确定染色体的优劣。因而适应度函数的确定对于优化过程起着至关重要的作用。适应度值高的染色体被保留操作的几率就高，反之就低。本文将工件的加工时间作为调度的评定标准，即加工完成的时间越少越好，所以可视车间调度问题为最小值问题。根据适应度函数的种类，确定其适应度函数为

式中，cmax为一个适当的相对比较大的数，是f(x)的最大值估计［3］。

2.3 选择操作

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

(1)计算出个每条染色体所对应的适应度函数值fi;

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

(3)按照选择概率，从排序好的染色体群中按由高到低的顺序选择出n条染色体，并将这n条染色体完整的复制到下一代群体中。

2.4 模拟退火－交叉

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

接受概率计算公式为

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

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

Step1:令t0=k·Δ0(t0为模拟退火算法中的初始温度，k为充分大的数，可选取k=10，20，100，…，Δ0=max{f(i)|i∈D}－ min{f(i)|i∈D})。

Step2:从区域D中选取两条染色体 father1，father2。

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

Step4:对染色体father1、father2进行交叉操作，产生新的染色体son1、son2。

Step5:计算染色体 father1、father2、son1、son2 的适应度值。

Step6:根据Metropolis准则判定son1是否替代father1，son2是否替代 father2。

Step7:计算退温函数:tk=λ·tk－1(其中k＞0，0 ＜λ＜1，λ取值越接近1，温度下降越慢，所以可以取λ=0.95，0.9，…)，转至 Step3。

2.5 禁忌搜索－变异

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

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

禁忌搜索－变异的操作流程如下:

Step1:选择一组染色体进入禁忌搜索栈中等待操作。

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

Step3:由A1产生N个候选解(x1、x2、x3、…、xi)，形成一个以A1为基础的邻域。

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

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

Step5:判定是否满足终止条件(设定终止条件为:禁忌搜索次数n);如果满足转至 Step6，否则转至Step3。

Step6:判定禁忌搜索栈中的染色体是否全部完成禁忌搜索－变异操作，如果是，转至Step7，否则转至Step2。

Step7:输出禁忌搜索－变异操作的结果。

3 实际算例的仿真验证

下面就GA－SA－TS混合遗传算法的可操作性在某厂的加工车间进行了实际验证。实际参数如表1所示。

表1 工厂实际加工参数

通过MATLAB实际仿真，得到一条最优染色体为:

［5 2 5 3 1 3 4 2 4 1 5 1 2 2 4 3 2 5 3 1 3 4 4 5 1］

其对应甘特图如图2所示。

按照该染色体解码后的参数，在车间实际加工以上5个工件仅需耗费30个单位时间。而该车间以往加工这批任务是凭借工人的经验进行调度，一般需耗费37～40个单位时间。通过这个实例仿真可以看出，运用GA－SA－TS混合遗传算法求解车间调度中的实际问题不但可行，还能减少加工用时。

在设定循环次数相等的情况下，对该例分别进行了混合遗传算法和遗传算法的仿真运算。如图3b所示为该例在使用遗传算法的过程中交叉和变异机制到达过的值。在相同初始条件的情况下，交叉机制中得到了最小值为31，但该结果在变异机制中产生了变化，使得相对最优值31丢失，并且在变异的过程中，搜索的范围任停留在32～47之间，陷入局部最优，导致最终结果为32。

图3a所示为该例在使用GA－SA－TS混合遗传算法运算过程中模拟退火－交叉机制和禁忌搜索－变异机制分别到达过的值。可以看出，在初始条件相同的情况下，混合遗传算法在交叉机制中得到的最优值为30;并且将其传递到了变异机制中进行操作，使得变异机制在操作的过程中搜索范围由交叉机制中的30～55缩小到30～35，且在搜索的过程中多次到达了最优值30，并输出。出现这样的情况是由于模拟退火－交叉机制在操作的过程中通过Metropolis准则将交叉所得的最优值记录下来，避免了最优值的遗失，并将最优值传递给变异机制进行操作。而禁忌搜索－变异机制通过基本变异方法，产生了一个以原有染色体为基础的邻域，从而提升了寻得最优解的可能性，扩大了搜索范围。同时，每一条变异所得的染色体都进行特赦准则的判定，最终在所有变异的染色体中得到一条相对最优的染色体，而不是单纯的进行变异操作。这样的变异机制不但提高了遗传算法的搜索能力，而且对每条变异的染色体和原始染色体都进行了优胜劣汰的操作，缩小了搜索范围，因此避免了优秀个体在变异机制中的遗失。

4 结语

基于对遗传算法易早熟和搜索能力差等缺点的考虑，本文提出了一种以遗传算法为主体，融模拟退火算法和禁忌搜索算法思想于其中的混合遗传算法(GASA－TS)。即在遗传算法的交叉机制中融入模拟退火算法的思想，形成模拟退火－交叉机制。在遗传算法的变异机制中融入禁忌搜索算法的思想，形成禁忌搜索－变异机制。通过将SA、TS融入到GA的操作中，使得遗传算法的交叉和变异机制中都对染色体进行了优胜劣汰的操作，而不是待交叉和变异操作全部完成后再对染色体进行优劣评定，从而避免了优秀个体在交叉和变异操作过程中的遗失。并且通过对车间调度生产的实际算例仿真对以上论点进行了论证，通过仿真的结果可以看出，运用这种混合遗传算法，对于解决车间调度系统的问题是可行的，并且较单纯的使用GA算法而言，在解的质量方面有所提高。

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

［2］何燕.基于遗传算法的车间调度优化及其仿真［D］.武汉:武汉理工大学，2006.

［3］邢文训，谢金星.现代优化计算方法［M］.北京:清华大学出版社，2007.

［4］GLOVER F.Future paths for integer programming and links to artificial intelligence［J］.Computers and Operations Research，1986(13):533－549.

［5］GLOVER F.Tabu search:partⅠ［J］.ORSA Journal on Computing，1989(1):190－206.

［6］METROPOLIS N，ROSENBLUTH A，ROSENBLUTH M，et al.Equation of state calculations by fast computing machines［J］.Journal of Chemical Physics，1953(21):1087 －1092.

［7］雷英杰，张善文，李续武，等.MATLAB遗传算法工具箱及应用［M］.西安:西安电子科技大学出版社，2009.

［8］董宗然，周慧.禁忌搜索算法评述［J］.软件工程师，2010(3):96－98.