。1234 北京科技大学学报 第32卷 交叉、多点交叉和均匀交叉以及基于排序的均匀交 为个体适应度和种群最大适应度之差的线性关系， 叉.对于单点交叉、多点交叉和均匀交叉，由于产生 而文献[10]则提出将算法中的交叉率和变异率参 子代种群个体中可能存在非法的调度方案，需要一 数设计为个体适应度和种群最大适应度之差的指数 些额外的修补技术，导致算法的效率较低.基于排 关系，并且验证了这种指数关系取得了较好的效果. 序的均匀交叉虽然能满足工件车间调度问题的求 对于SSP设T为个体的完工时间，T和 解，但模板中0和1是均匀产生的，使得在交叉过程 分别为种群中的最大完工时间和最小完工时间. 中难于保留较长的模式，而这对于算法的收敛是非 当个体的完工时间越靠近T则其变异率应该越 常不利的. 大，而当个体的完工时间越靠近m其变异率应该 本文采用的交叉算子就是在基于排序的均匀交 越小，本文采用的基于指数关系的变异率曲线是对 叉算子的基础上，改进模板中0和1的产生方式 文献[10的改进，其形式为 针对工件工厂调度问题，采用工件集合过滤方式来 MutE 承担上述模板的作用.因此，称本文采用的交叉算 MaMut e hr T e-1 Ta≠Tn 子为基于排序的工件过滤交叉算子，其计算过程如 下所示 MaxMutr Tax-m h 设一个四工件三机器的SS某次迭代中两个 式中，MaMu为最大变异率.与文献[10]所不同 个体的编码为 的是，曲线适应于种群中的所有个体，而不是仅仅适 =(132312132444), 用于均值以上的个体，而且在曲线的具体形式上也 P2=(112433412432). 是不同的. 随机产生一个工件编号的排列Num=(23l 2算法实现 4),并产生两个不同的随机整数P09和P0②根据 Po和Po2从Nu中取出相应的工件编号集合. 改进遗传算法的执行过程与传统遗传算法的执 例如，当P09=2P02=3时，取出的工件集合为 行过程大致相同.其改进的方面包括基于排序的适 Se lNum=(3I).然后以该工件集合来过滤父代并 应度分配，基于排序的工件过滤交叉算子和基于指 交叉产生子代，对应的子代Q和2对应的子代 数关系的变异率曲线 C2分别如下： q=(133113“, 3结果分析 C2=(113313). 实验评测基于Lawrence提出的各种benc 其中，*表示过滤掉的基因.再将2中多余的 mak其中电1到5是10×5（即10个工件和5 个体{24按照2中的顺序插入到Q中，将日中 个机器的问题)规模的问题：06到0是15×5 多余的个体{24}按照中的顺序插入到C②中. 规模的问题：间1到5是20×5规模的问题：6 0=(132314134242), 到20是10X10规模的问题：22和②4是15× 2=(112233214434). 10规模的问题；128是20×10规模的问题；马2是 1.5变异算子 30×10规模的问题.本算法的结果与文献[15-16 遗传算法中的变异算子，是指以一定概率随机 的传统遗传算法的结果进行比较. 改变染色体上的某些位，形成一个新的个体.本文 实验参数为：种群数Nd=30迭代次数Max 采用的变异算子与大多数JSS的求解一样，采用基 Ga=300选择比例PeSe=0.9.交叉率Xow= 于工件对交换的方法，其中交换的位置是随机产生 0.8最大变异率MaMu-0.4实验环境为Matb 的 65.1.实验结果如表1所示.在表1中，传统遗传 1.6自适应性 算法记录为GA,本文改进遗传算法为GA2特别 遗传算法中的自适应性体现为算法执行过程中 展示了G2算法的五次实验结果，并计算了所寻优 动态修改交叉率和变异率.一般来说，交叉率应设 值的均值.由表1可以看出，改进遗传算法比传统 置为一个较大的值，从而可以更多地在种群各个个 遗传算法的寻优能力更强.而且在电5.6、08 体之间交换信息.本文关注的自适应性主要是动态 09闯0冉3.间4和5的测试中，己经完全找 修改变异率，设计一种基于指数关系的变异率曲线. 到了己知最优值，在闭1、电7冉1和2测试中， 文献[9]提出将算法中的交叉率和变异率参数设计 也有数次找到己知最优值.北 京 科 技 大 学 学 报 第 32卷 交叉、多点交叉和均匀交叉以及基于排序的均匀交 叉 .对于单点交叉、多点交叉和均匀交叉, 由于产生 子代种群个体中可能存在非法的调度方案, 需要一 些额外的修补技术, 导致算法的效率较低.基于排 序的均匀交叉虽然能满足工件车间调度问题的求 解, 但模板中 0和 1是均匀产生的, 使得在交叉过程 中难于保留较长的模式, 而这对于算法的收敛是非 常不利的. 本文采用的交叉算子就是在基于排序的均匀交 叉算子的基础上, 改进模板中 0和 1 的产生方式 . 针对工件工厂调度问题, 采用工件集合过滤方式来 承担上述模板的作用.因此, 称本文采用的交叉算 子为基于排序的工件过滤交叉算子, 其计算过程如 下所示 . 设一个四工件三机器的 JSSP.某次迭代中两个 个体的编码为 P1 =( 132312132444), P2 =( 112433412432) . 随机产生一个工件编号的排列 JNum=( 2, 3, 1, 4), 并产生两个不同的随机整数 Pos1 和 Pos2, 根据 Pos1和 Pos2从 JNum中取出相应的工件编号集合 . 例如, 当 Pos1 =2, Pos2 =3 时, 取出的工件集合为 SelJNum=( 3, 1) .然后以该工件集合来过滤父代并 交叉产生子代, P1对应的子代 C1和 P2对应的子代 C2分别如下 : C1 =( 13 ＊ 31 ＊ 13 ＊＊＊＊ ), C2 =( 11 ＊＊ 33 ＊ 1 ＊＊ 3 ＊ ) . 其中, ＊表示过滤掉的基因 .再将 P2中多余的 个体{2, 4}按照 P2中的顺序插入到 C1中, 将 P1中 多余的个体 {2, 4}按照 P1中的顺序插入到 C2中 . C1 =( 132314134242), C2 =( 112233214434) . 1.5 变异算子 遗传算法中的变异算子, 是指以一定概率随机 改变染色体上的某些位, 形成一个新的个体.本文 采用的变异算子与大多数 JSSP的求解一样, 采用基 于工件对交换的方法, 其中交换的位置是随机产生 的 . 1.6 自适应性 遗传算法中的自适应性体现为算法执行过程中 动态修改交叉率和变异率.一般来说, 交叉率应设 置为一个较大的值, 从而可以更多地在种群各个个 体之间交换信息 .本文关注的自适应性主要是动态 修改变异率, 设计一种基于指数关系的变异率曲线 . 文献[ 9]提出将算法中的交叉率和变异率参数设计 为个体适应度和种群最大适应度之差的线性关系, 而文献[ 10] 则提出将算法中的交叉率和变异率参 数设计为个体适应度和种群最大适应度之差的指数 关系, 并且验证了这种指数关系取得了较好的效果. 对于 JSSP, 设 Ti为个体 i的完工时间, Tmax和 Tmin分别为种群中的最大完工时间和最小完工时间. 当个体的完工时间越靠近 Tmax, 则其变异率应该越 大, 而当个体的完工时间越靠近 Tmin, 其变异率应该 越小 .本文采用的基于指数关系的变异率曲线是对 文献 [ 10]的改进, 其形式为 Mutr= MaxMutr e-e ( Tmax-Ti) /( Tmax-Tmin) e-1 , Tmax≠Tmin MaxMutr, Tmax =Tmin 式中, MaxMutr为最大变异率 .与文献 [ 10] 所不同 的是, 曲线适应于种群中的所有个体, 而不是仅仅适 用于均值以上的个体, 而且在曲线的具体形式上也 是不同的 . 2 算法实现 改进遗传算法的执行过程与传统遗传算法的执 行过程大致相同.其改进的方面包括基于排序的适 应度分配 、基于排序的工件过滤交叉算子和基于指 数关系的变异率曲线. 3 结果分析 实验评测基于 Lawrence [ 14] 提出的各种 bench￾mark.其中 la01到 la05是 10 ×5(即 10个工件和 5 个机器的问题 ) 规模的问题;la06 到 la10 是 15 ×5 规模的问题;la11到 la15是 20 ×5规模的问题;la16 到 la20是 10 ×10规模的问题 ;la22和 la24是 15 × 10规模的问题;la28是 20 ×10规模的问题;la32是 30 ×10规模的问题 .本算法的结果与文献 [ 15--16] 的传统遗传算法的结果进行比较 . 实验参数为:种群数 Nind=30, 迭代次数 Max￾Gen=300, 选择比例 PerSel=0.9, 交叉率 Xovr= 0.8, 最大变异率 MaxMutr=0.4.实验环境为 Matlab 6.5.1.实验结果如表 1所示 .在表 1中, 传统遗传 算法记录为 GA1, 本文改进遗传算法为 GA2.特别 展示了 GA2算法的五次实验结果, 并计算了所寻优 值的均值 .由表 1可以看出, 改进遗传算法比传统 遗传算法的寻优能力更强 .而且在 la05、la06、la08、 la09、la10、la13、la14 和 la15的测试中, 已经完全找 到了已知最优值, 在 la01、la07、la11和 la12测试中, 也有数次找到已知最优值. · 1234·