遗传算法结合模拟退火算法处理一般flow shop 调度

摘　要：调度问题属于组合数学范畴，也是所谓的NP-hard问题，随着任务与资源量的扩大，由其组合所生成的可行方案也急剧暴涨，而遗传算法作为一种非确定性的拟生态随机优化算法在调度问题上得到了广泛的应用。

关键词：Flow shop 遗传算法 模拟退火
　　调度的任务是根据生产目标和约束，为每个加工对象确定具体的加工路线、时间、机器和操作等。优良的调度策略对于提高生产系统的最优性、提高经济效益都有着极大的作用。
　　1 一般flow shop调度问题
　　Flow shop调度问题(Flow shop scheduling problem，简称FSP)，是许多实际流水线生产调度问题的简化模型，也是一个典型的NP-hard问题。Flow shop调度研究m台机器上n个工件的流水加工过程，每个工件在各机器上加工顺序相同，同时约定每个工件在每台机器上只加工一次，每台机器每次在某一时刻只能够加工一个工件，各工件在各机器上所需的加工时间和准备时间己知，要求得到某调度方案使得某项指标最优。
　　3用基本遗传算法处理一般flow shop调度
    遗传算法(Genetic Algorithm,简称GA)起源于对生物系统所进行的计算机模拟研究，是美国Michigan大学的J．Holland教授及其学生受到生物进化论启发，而创造出的基于生物遗传和进化机制的适于复杂系统优化的自适应概率优化技术。
　　GA是基于“适者生存”的一种高度并行、随机和自适应优化算法，它将问题的求解表示成“染色体”的适者生存过程，通过“染色体”群(population)的一代代进化、包括复制(reproduction)、交叉(crossover)和变异(mutation)等操作，最终收敛到“最适应环境”的个体、从而求得问题的近似最优解或满意解。
　　3.1基本遗传算法
　　1. 编码：
　　对于flow shop流水线调度问题，由于该问题可以用工件的顺序来表示染色体，所以我们采用十进制编码，将每个个体表示成一个m x n的矩阵，即工件加工顺序矩阵，并记为S，表示第k台机器上第i个被加工的工序号。
　　具体来说，若以7个工件7台机器的flow shop流水线调度问题为例，则工件加工顺序矩阵。
　　2. 初始种群的生成：
　　设定初始种群，并以此为起点一代代的进化直到按照某种进化终止准则终止。生成初始种群是群体性操作算法，在对解空间变量进行编码后，紧接着就要随机产生N条染色体，构造遗传算法的初始群体。考虑搜索效率和质量等因素，在生成初始种群时，一方面要求尽量使初始种群分散地分布于解空间（防止收敛于局部最优解），另一方面可以采用一些简单方法或规则快速产生一些解作为GA的初始个体。
　　3. 个体适应度函数：
　　适应度函数(Fitness Function)也称为评价函数，是根据目标函数确定的用于区分群体中个体好坏的标准，是算法演化过程的驱动力。
　　由于适应度函数总是非负的，任何情况下都希望其值越大越好。而目标函数可能有正有负，即有时求最大值，有时求最小值，因此需要在目标函数与适应度函数之间进行交换。由解空间中某一点的目标函数值到搜索空间中对应个体的适应度函数值的转换方法基本上有以下三种:
　　（1）直接将待解的目标函数转化适应度函数。
　　（2）将目标函数转化为最大值的形式，并映射为适应度函数。
　　（3）以目标函数的倒数作为适应度函数。
　　4. 遗传算子设计
　（1）选择操作：
　　选择操作是模仿自然界“优胜劣汰、适者生存”的原则，从父代种群中选择出优良个体，使它有机会保留用以繁殖后代，从而提高遗传算法的全局收敛性和计算效率。
　　选择操作的主要方法有：适应度比例选择法、基于排名的选择法等。
　我们采用的是适应度比例法（赌轮盘选择），该方法中个体选择概率与其适应度值成比例。
　　（2）交叉操作：
　　交叉又被称为重组或配对，它结合父代染色体的特征，组合出新的染色体，以便对解空间进行有效搜索，同时又降低对有效模式的破坏概率。设交叉概率为，较大时可以增强算法开辟搜索区域的能力，但会增加优良子代被破坏的可能性；较低时又会使搜索陷入迟钝状态。研究结果表明，应取为0.25～1.00之间。
　　（3） 变异：
　　当交叉操作产生的后代适配值不再进化且没有达到最优时，就意味着算法存在早熟收敛。这种现象的根源在于有效基因的缺损，变异操作在一定程度上克服了这种情况，有利于增加种群的多样性，同时修复和补充选择、交叉过程中丢失的遗传基因。　
　　3.2给出仿真实例
　　由于许多研究工作者针对FSP问题设计了若干典型问题，用于测试和比较不同方法的优化性能。其中包括。设定遗传算法的种群大小Num=20，最大迭代次数maxgen=1000，交叉概率（cross rate）=0.8，变异概率（mute rate）=0.08，并采用细胞（cell）结构存储种群，经过选择、交叉、变异后得到的运行结果为：最小的加工完成时间是T=7465。

　　甘特图是一种十分有效的工具，该图将即将要做的工作绘制在一条时间轴(横轴)上，将在机器上加工的工件绘制在纵轴上。所以，为了更好地描述结果，我们绘制了如下的甘特图（图-1）。

　　    图-1  flow shop 甘特图-1

工件号  颜色具体表示工件1  红色　工件2  蓝色　工件3  白色　工件4  紫色　工件5  黄色　工件6  墨绿色　工件7  绿色　　　
　　　　 表1 颜色—工件对应表
    通过甘特图-1可知，在机器1上的工件按“1—7—5—4—2—6—3”的顺序连续加工，流水线没有停顿。 各工件从在机器1上按不同的顺序加工，直到在机器7上完成整个流水线过程，所用的时间是7465。由于基本遗传算法存在的缺陷，我们将结合模拟退火算法进行改进，以期得到更优的调度策略和时间安排方法。
　　4用基于模拟退火的改进遗传算法处理flow shop 调度问 题
　　4.1模拟退火遗传算法
    在模拟退火算法的运行过程中溶入遗传算法，称为模拟退火遗传算法。因为GA的复制对当前种群外的解空间无探索能力，个体分布“畸形”时交叉的进化能力有限、小概率变异很难增加种群的多样性．在收敛准则设计不好的情况下，GA经常会出现进化缓慢或“早熟”收敛现象。所以，将模拟退火算法结合遗传算法，先通过遗传算法找到一个较优解，然后将这个较优解运用于模拟退火算法，通过控制初温来控制搜索行为，以便得到一个更优解。而控制温度的高低可控制突变能力的强弱，高温下的强突跳性有利于避免陷入局部极小，低温下的趋化性有利于提高局部搜索能力，控制降温速率可控制突跳能力的下降幅度，控制抽样次数可控制各温度下搜索能力。
　　4.2仿真实现及结果分析
　　我们以Carlier设计的Car类典型问题中的7个工件7台机器的流水车间调度问题（Car7）作为用模拟退火遗传算法解决flow shop流水线调度问题的仿真实例。
　　首先，我们根据基于模拟退火的改进遗传算法，利用matlab软件编写出针对carlier设计的Car7类典型问题的遗传算法求解程序。
　　我们将这个较优解运用于模拟退火算法，并设定某固定温度下的最大迭代次数iter_max=10000，固定温度下目标函数值允许的最大连续未改进的次数m_max=100，最低温度设为tau=1e-5。设置好初始温度后，由模拟退火算法产生邻域解，并判优，输出满足条件的最优解。最后，经过运行模拟退火遗传算法求解程序，得到的结果为：
　最小的加工完成时间是T=7177。
　　5基本遗传算法和模拟退火遗传算法的对比的总结
从两种算法流程图和Car7的仿真结果可知：
　　（1）基本遗传算法采用了生物进化论的思想，通过选择复制、交叉、变异来生成最优解；模拟退火遗传算法则是在基本遗传算法的基础上，设置初始温度，搜索邻域解，直到生成新的最优解。
　　（2）遗传算法在搜索过程中基本不利用外部信息，仅以适应度函数为依据，利用种群中每个个体的适应度值进行搜索;引入模拟退火后，其退火温度控制着求解过程向最小值的优化方向进行，同时它又以概率 接收劣质解，因此算法可以跳出局部极值点。
参考文献：
　[1] 王凌等，《车间调度及其遗传算法》，北京：清华大学出版社，2003
　[2] 雷英杰，张善文等，《MATLAB遗传算法工具箱及应用》，西安电子科技大学出版社，2006年4月
　[3]何燕，《基于遗传算法的车间调度优化及其仿真》2006年5月
　[4] 冯红娟，《基于遗传算法的车间作业调度问题研究》2007年 本文链接：http://www.qk112.com/lwfw/jsjlw/jisuanjiyingyong/241656.html