针对置换流水车间调度问题的基本特征和传统遗传算法易早熟的缺陷，设计了改进遗传算法来求解此问题。采用NEH和Palmer启发式算法进行种群初始化，以提高初始解的质量；根据Metropolis准则对染色体进行选择操作，避免陷入局部最优；在变异过程中引入禁忌算法，避免迂回搜索；在算法迭代过程中引入了保优机制，避免丢失优秀染色体的基因信息；采用自适应终止准则，以保证解的质量。基于典型Benchmark算例的仿真实验结果表明，算法在求解质量和收敛速度方面明显优于NEH算法和种群经过初始优化的传统遗传算法。
522009,45(36) Computer Engineering and Applications计算机工程与应用 PSK= PoP-Q (2) 步骤1参数设置:种群大小POP;交叉概率P;变异概率 Pn;温控参数λ;禁忌表长度为L;禁忌表容量为C;保优比例 P;根据公式T=△n(p0)计算初温;终止准则参数d 从式(2)中可以看出最大加工时间最短的染色体进入下 代的机会更大 步骤2初始化:用NEH和 Palmer启发式算法对初始种群 中的2条染色体进行初始化,剩下的POP-2条染色体通过随 34交叉算子 机方式产生,设置k:=0。 对进行选择后得到的染色体实施交叉操作,对于此问题不 步骤3进行适应度计算,如果满足终止准则(采用自适应 能使用匹配交叉法(PMX)、边组合交叉法单点交叉法、两点交终止准则,即如果算法在连续迭代d次之内,解的质量始终没 叉法等,因为这些交叉方式会导致染色体中基因的重复和丢有提高,则终止迭代),则输出最优染色体;否则,令k:=k+1,转 失。针对此问题使用另外两种交叉算子,第一种使用线性序号 步骤 交叉法(L0X),这种交叉法可以保证交叉后的染色体对应问题 步骤4保存步骤3中的部分优秀染色体(假设保存数量 的一个可行解,同时也能尽量保留各个基因的相对位置和各条为m,这m条染色体直接转步骤6,进行交叉操作),同时将该 染色体的顶端优势;第二种交叉算子采用如下的交叉过程首次迭代的最优染色体存入一个数组。 先随机产生交叉点的位置,第一个后代Y'的前一小段基因选 步骤5选择染色体 择父代Y1的前一小段基因,然后在Y2中剔除掉这一小段基 步骤51根据式(1)计算每条染色的初始概率PS 因,Y2中剩下的基因保持顺序不变,构成Y1的后一段基因。 步骤52根据式(2)计算每条染色体的修正概率PS 例如染色体Y1和染色体Y2的基因编码分别是 步骤53利用滚动轮策略选择POP-m条染色体,使其进 13852764“和“32418765”,随札选取的交叉点是从第3个交叉入交又过程。 点之后开始交叉,那么从Y2中剔除掉“138”之后,得到的基因 步骤6交叉 片段为“24765”,所以交叉后的染色体Y为“13824765”。采用 步骤6.1对步骤5中保留的m条染色体和步骤5.3中选 同样的方法Y2为“32418576”。 择的POPm条染色体,利用前文所述的两种交叉算子进行交叉 在进行交叉操作时,同时采用上述的两种交叉操作,其过 步骤6.2利用 Metropolis准则对交叉前后的染色体进行 程是:产生随机数mn,mn∈0,1然后将m与05比较,如果选择,从而组成下一代种群。 rωn≤0.5,则采用第一种交叉算子;否则采用第二种交叉算子 步骤7利用基于禁忌搜索算法的变异算子对染色体进彳 对于此问题,在交叉操作后采用模拟退火算法中的变异操作。 Metropolis准则来选择子代,这样不但可以加快收敛速度,同时 步骤8将变异后的染色体作为新的种群,转步骤3。 也可以保证种群的多样性,其具体步骤是:随机选择两条染色 体Y1和Y2进行交叉,经交叉操作后产生两条新的染色体Y14数值实验 和Y2,分别计算交又前的染色体与其对应的交又后的染色体41实验设计 的目标值之差△E,如第一条染色体△E=f(Y1)-(Y1),其接受新 文献[指出传统遗传算法对NEH算法的性能改进幅度较 解的概率为: 小,有时甚至劣于NEH算法,而模拟退火算法和禁忌搜索算法 1,当△E≤0时 2(△E),当△E>0时 (3)亦没有明显优于NEH算法。基于此结论,实验将该文提出的 NP-lGA算法分别与NEH算法和NP-GA算法进行比较,其 然后产生0,1的随机数 random,将 random与P进行比中,NP-GA算法是指采用NEH算法和 Palmer算法进行初始化 较,根据其比较结果约定是否接受子代染色体。迭代过程之中, 的普通遗传算法(采用IOX交叉法)。实验从解的质量、解的稳 初始温度根据 Kouvelis与 Chiang在1992年提出的公式T= 定性和算法的收敛速度这三个方面对上述三种算法进行比较 NP-GA算法使用的参数为:种群大小POP=150;交叉概率 丛/ln(po)来决定,参数Δ为初始种群中最优染色体和最差染色 P=0.85;变异概率P=0.15。NP-IGA算法中的种群大小、交叉 体目标值之差;p为最差状态相对最优状态的接受概率,考虑概率、变异概率与NPGA取相同值,温控参数A=0.7。禁忌表 到优化结果的质量和算法的收敛性,po取0.1 长度为L=10,蔡忌表容量为C=10,每一次变异均使用禁忌搜 3.5变异算子 索算法迭代30次;保优比例P=0.02。各算法每轮迭代均独立 禁忌搜索算法具有防止迂回搜索和寻求全局最优解的特运行20次,仿真结果取平均值。 点。针对禁忌搜索的这一特点,将需要变异的染色体作为禁忌 为了验证NP-IGA算法的可行性和有效性,首先选取OR- 搜索的输入,把禁忌搜索得到的解作为经过变异的新个体,这 Library提供的31个国际标准算例中较为典型的15个算例作 里以染色体本身作为禁忌对象,采用两点置换法作为当前解的为第一组算例,对于该组算例OR- Library提供了各个算例的 邻域,从中选择部分优秀解作为候选解,以目标函数值作为藐最优值,这些最优值是由不同文献的研究结果采集而来。为了 视准则。 进一步验证算法的有效性,选取 Taillard测试问题集中较为 3.6算法步骤 典型的5个算例作为第二组算例,该组算例中各工件的各道工 基于以上论述,提出的改进遗传算法步骤描述如下 序的加工时间是在均匀分布的基础上,通过随机生成方式在区 NP-IGA 间[1,99产生的。 涂雪平,施灿涛,李铁克:求解置换流水车间调度问题的改进遗传算法 2009,45(36)53 42实验结果分析 在算法求解效率方面,除了规模为50×10的算例所用吋间 (1)第一组算例 在18s以外,NP-IGA算法均在15s之内结束迭代,找到表2 表1为针对第一组算例的NEH算法、NPGA、 NP-IGA算中对应的满意解 法得到的仿真结果表。表中S。为算例的最优目标值;S为各个 为了使选择的算例更具代表性,选择屮等规模的算例,即 算法得到的最优目标值;σ表示各个算法得到的目标值与算表2中规模为mxn=20×20的算例来验证该文提出的NP-GA 例最优目标值之间的偏差,用公式表示为:0=Sn3×10% 算法的收敛性。参数设置为上文提到的参数值。图2表示NP GA和NP-IGA的适应值随迭代次数的变化对比图,从图2中 从表1中可以看出,NP-IGA算法能达到最优解的个数为10可以看出NP-IGA算法的收敛性明显优于NP-GA 个,而NP-GA算法能达到最优解的算例只有7个,NEH算法 420 能达到最优解的个数只有1个。并且通过对每一个算例的仿真 2400 NP-IG NP-GA 结果比较,NP-IGA算法优于NP-GA算法和NEH算法。同时 2380 根据表中各种算法对应的σ可以看出 NP-IGA算法求得的解 2340 的稳定性明显优于NP-GA和NEH算法。 2320 2300 在算法求解效率方面,对于所选的Carl-Car8算例,三种 2280 算法均在1s内找到最优解。由于Hell、Rec37算例的机器数 260 2240 和工件数目较多,所以花费的时间较长,但是该文提出的NP 1529435771859911312714I iteration number IGA算法均在20s之内达到终止条件,找到表1中的对应的满 图2NP-IGA和NP-GA适应值随迭代次数变化对比图 意解;对于剩下的所选算例,NP-IGA算法所花费的时间均不 超过5s。 5结论 表1第一组算例对应的各算法仿真结果比较表 置换流水车间调度问题是典型的NP难问题,而现实中又 NEH NP-GA NP-IGA 存在大量该问题的实例,对该问题求解算法的研究具有重要意 Problem Scale( mxn) S 0 car111×5703870380703807038 义。针对置换流水车间调度问题的特点和遗传算法的缺陷,提 出了一种求解置换流水车间调度问题的改进遗传算法。为提高 13×4716673662.937166071660 12×5731273991.197312073120 初始解的质量,采用两种目前效果最为理想的启发式算法进行 10×6772078351.497720077200 种群初始化;为保证种群的多样性和加快收敛速度,根据模拟 50587733.158505085050 退火算法的 Metropolis准则接受子代染色体;为避免迂回搜 Lar 836685642.378366083660 索,使用基丁禁忌算法的变异算子进行变异操作;同时在迭代 Hell 100×10 5135191.175150.395150.39 过程中还引入了保优机制,使部分优秀解跳过选择过程,直接 Hel2 20×10 1351414.441371481350 Recor 20×5 124713034.491247012470 进行交叉操作。最后通过基于OR- Library和 Taillard的 Reco 20×10156616263.8315700.2615660 Benchmark问题的仿真实验,验证了该算法具有良好的收敛性 Rec1320×15193020023.7319330.1619300 和全局寻优能力,同时在解的质量、解的稳定性和算法的收敛 Rec1930×102093213144021060.6220960.14 速度三个方面均明显优于NEH算法和采用NEH和 Palmer启 30×15251326445.2125330.8025180.20 发式算法进行初始优化的传统遗传算法。 Rec3150×10304531734.2030670.7230580.43 Rec37 75×20495152275.57514298050421.80 参考文献: (2)第二组算例 「王凌,邓大钟求解置换加工调度问题的一种改进遺传算法J系统 对于所选的第二组算例,各算法针对各算例的仿真结果见 工程理论与实践,2004,24(6):74-77. 表2。表中的 Upperbound列所对应的值就是 Taillard流水作业2 Li Su-en, Zhu yun-lng;, Li xiao- ing earliness/tardiness flow 调度冋题标准测试厍中给出的最好解对应的目标值;表中的 shop scheduling under uncertainty [C]/The 17th IEEE International σr表示各个算法对应的目标值与标准测试库中所给的最好解 Conference on Tools with Artificial Intelligence, Hong Kong, Chi- 对应的目标值之间的偏差。从表2中也可以明显看出文中提到 na,2005:499-506 的NP-IGA算法对应的σ明显小于NEH和NP-GA算法,这[3 I Hall l a Approximability of flow shop scheduling[Cy/The4 I st An 表明NP-IGA针对第二组算例的求解结果明显优于NEH和 nual Symposium on Foundations of Computer Science. Milwaukee NPGA算法;同时结合第一组算例,共同说明了NP-IGA算法 Wisconsin. 2005: 82-91 对广泛的置换流水车间调度问题都是有效、可行的。 4]王笑容,吴铁军 flow-shop问题的蚁群优化调度方法肌系统工程 表2第二组算例对应的各算法仿真结果比较表 理论与实践,2003,23(5):65-67 5]刘延风,刘三阳基于蚁群优化的置换流水车间调度J系统工程与 Problem 电子技术,2008,30(9):1690-1692 Scale(mxn) Initial seed Upper bound Lower bound NEH NP-GA NP-IGA 20×5873654221 1278 0.6260.2410.041 16 Maiza M, Hentous H, Labed A. An efficient heuristic for scheduling 20×10587595453 158 5.05714520.137 a flow-shop to minimize the makespan criterion[ Cy/The l lth IEEE 2297 l9114.9191.1890.18l Symposium on Computers and Communications, Cagliari, Sardinia, I 50×513280420582724 67-0.441 taly,2006:536-540 50×1019589488632991 29074.8142.8571.079 下转70页)