《网格模拟淬火遗传算法在生产实习中调度.doc》由会员分享，可在线阅读，更多相关《网格模拟淬火遗传算法在生产实习中调度.doc（7页珍藏版）》请在三一文库上搜索。
1、网格模拟淬火遗传算法在生产实习中的调度蒋喆 （沈阳汽车工业学院 沈阳 110015）摘 要： 本文基于网格的模拟淬火遗传算法解决生产实习作业中的计划编制问题。我们建立了综合考虑学生学习成本与学院实习厂之间的多目标规划模型以及设计了基于网格的模拟淬火遗传算法计算模型。结合GA算法、最优个体保护法和SA算法，提出了模拟淬火遗传算法（MOSA)，建立了实习厂静态调度问题的模型及其基于MOSA的求解算法，。该算法首先对生产作业中样本数据进行数据挖掘，然后考虑学生实习和学校等因素构造模拟淬火遗传算法的适应度函数，在网格平台上初始化，进化操作，最后得出满意的运行计划表；通过仿真试验，证明了该方法的有效性和
2、实时性。关键词：模拟淬火遗传算法；生产实习；网格；调度中图分类号：TP Research on grid-based quench genetic algorithm and its application in Produce fieldwork Operating planingJiangZhe （The Automobile Industry College of Shenyang, ShenYang, 110015, P. R. China）Abstract: To solve the problem of produce fieldwork operation plan schedu
3、ling, this paper proposes a grid-based genetic algorithm. Firstly, we do data mining in the historical passenger flow samples of urban transportation by using produce fieldwork operating. Secondly, we construct the fitness function, coding method and constraint condition of genetic algorithm under c
4、onsidering the cost of students and operating loss of the college. Finally, we initialize the populations on the Grid platform, and then distribute the subpopulations to different Grid clusters and nodes for selection, crossover, and mutation, calculate the fitness of chromosome in diverse direction
5、s simultaneously and exchange the excellent chromosome between clusters or nodes in order to get the satisfactory operation plan quickly. Key words: quench gench algorithm； produce fieldwork; grid；scheduling4 / 7文档可自由编辑打印引 言 本课题得到辽宁省”十一五”教育科学规划项目（辽教函20068号）资助和沈阳市总工会科技计划（2009SR023427）资助蒋喆，男，1950年生，沈阳
6、人，博士。副教授 主要研究方向：决策支持系统、信息系统工程、网格计算。E-mail： 生产实习和教学实习是教学过程的重要基本环节，是全部教学的重要组成部分。演化算法中最普通的遗传算法（genetic algorithm，GA）是通过交互组合形成解集，然后根据目标方程值随机突变进行改进，形成“自然”选择，优胜劣汰。模拟淬火遗传算法一种演化算法。这种演化算法是由Kirkpatrick开发的模拟淬火算法(Simulated Annealing，SA)，模拟淬火算法能够处理非连续性方程和差分变量，而确定性优化方法无法实现，因此使得SA算法成为单目标和多目标优化问题的重要工具。运行生产实习和教学实习计划
7、编制优化模型是一个复杂的多目标规划问题，它必须兼顾学生和学校实习厂双方的利益，才能使得整个实习教学有规律有节奏的运行。本文提出了利用基于网格的模拟淬火遗传算法来求解运行计划编制的新方法，其中改进的模拟淬火遗传算法保证了生产实习和教学实习运行计划编制的有效性，而网格强大的计算平台则保证了生产实习和教学实习运行计划编制的实时性要求。新方法的基本思路运用模拟淬火遗传算法需要解决遗传染色体的编码问题。生产实习和教学实习计划的制定是学院实习厂日常运营工作的核心。这里，我们对这些课节进行可变长度的二进制编码来作为遗传的染色体，其中使用二进制符号0和1表示课节的优点在于编码等操作便于实现。首先对生产实习和教
8、学实习安排样本数据进行数据挖掘，得到与算法相关的历史样本数据，然后使用有序聚类fisher算法优化公交峰值曲线的方法合并历史样本数据中安排状况相近的课节。二进制编码长度作为对应染色体段的约束条件。运行计划的好坏取决于是否能够兼顾学生和学校实习厂双方的利益：对于学生来说实习时间短效果佳为好，而对于学校实习厂来说材料消耗少实习时间长好。加权最小值作为模拟淬火遗传算法的适应度函数来评价染色体优异性。网格服务器利用先前确定的编码方式将相关的历史样本数据编码，形成初始种群；等到集群内所有的子种群进化完成后选取适应度高的满意染色体提交到网格服务器，服务器查看适应度最高的染色体是否满足终止条件。最终染色体转
9、换成课节，并根据课节，得到实习功课表，即运行计划。整个的流程框图如下图所示。 图：基于网格的模拟淬火遗传算法解决运行计划编制问题的总体流程图运行计划编制模.模型假设针对学院实习厂实际情况做出如下假设：1) 只考虑单科课程，课程和课程之间不相互影响。2) 在制定实习计划之前实习原型系统有相关历史样本数据。.模型输入 为能更好地贴近公交运行实际情况，允许模型有如下的初始输入：1) K为课程。2) 为限制最大课节间隔；为限制最小课节间隔。3) 为实习教师限制最大课节总数。4) C为机床的可培训学生容量；J为实习厂可培训班级的容量。.模型变量 以下是模型中出现的相关变量定义：1) 为课节区间集。2)
10、为教师课节集。.模型构建1) 从样本数据中查找满足以下约束的K课程历史样本，即： (1)2) 分别累加分钟内历史样本的客流量。即公式： (2)3) 计算类直径类的直径记为,一般多采用“离差平方和”作为直径,即： (3) (5)4) 确定最优分段数，计算比值，当值比较大时,就说明分成段显然比分为段好。而且值接近于1时即可不必再往下分。5) 划分课节区间根据和，合并客流量类似相邻时段，可确定课节分区6) 获得各个课节分区的课节间隔约束取得所有历史样本数据的在各个课节分区的最大和最小课节间隔作为时段分区的发车间隔约束，即： (6)7) 获得各个时段区间的到达各个机床点的学生平均出勤率，即: (7)8
11、) 确定染色体编码长度将发车间隔的二进制编码作为染色体编码，编码位数由K时段区间的最大课节间隔决定，即： (8)其中表示取整9) 确定适应度函数第k个课节区间的派教师数由该课节区间的时间长度和课街间隔决定，即： (9)对于学生来说，就是学习时间少效果佳，为了方便计算，我们在这里将它折合成费用，即学生的平均学习成本最低，即： (10)对于学院实习厂来说，就是教学收入最高，即学费收入减去材料消耗。即： (11)适应度函数则是求两者的加权值的最小值，即： (12)其中(12) 确定约束条件每个课节区间必须满足该区间课节间隔约束，即： (13)课节总数应不大于限制最大课节数，即： (14)机床的出勤率
12、应不小于期望出勤率，即： (15)（16）3.5 模型求解3.5.1 网格处理首先网格服务器根据按照染色体编码方式对进行编码形成初始种群，再将初始种群划分成若干个子种群并分配到各个网格集群上，接下来网格集群根据其网格节点的处理能力将子种群分配到各个节点上：1）选择：根据各个个体适应度的概率决定其子孙遗留的可能性。若某个个体i的适应度为,则它被选取的概率为 2）重组：选择单点交叉（One-point Crossover）作为模拟淬火遗传算法的交叉运算，其基本过程如下：首先将群体中的 个体以随机方式组成 对配对个体组，然后对每个个体组以概率进行交叉运算。3）变异：变异运算采用均匀变异(Unifor
13、m Mutation)操作。3.5.2 染色体解码根据将最终染色体分为若干个区间，并利用以下二进制转换成转化成十进制的计算公式可得到各区间的发车间隔，即：= = (17)再根据始末班时间和计算得到发车时刻表，即： (18)4 仿真试验为了验证上述模型和算法的有效性和可靠性，我们进行了仿真试验。 4.1调度问题的MOSA实现算法 为了生成一个调度，需记录每台机床的调度情况，由于调度到每台机床上的工序经常变动，且数目无法顶先确定，因此采用如下数据结构记录机床调度情况struct schedule int op； float s-time；/工序的起始时间 float e-time.；/工序的终止时
14、间 struct schedule * next； 每台机床需一个链表，表头指针组成一个数组：strrust scliedule * machineTOTALMACHINE。 为便于染色体适应度值的计算，还需记录染色体中每个规划的开始时间和终止时间： float plan-start- t CH ROM LEN， f_plan_finish_tCH ROM- LEN。 由此，可方便地实现由染色体艺生成相应讲的方法，其过程如下： 1.初始化i的机床调度链表，machine-schedule,并从染色体的第一个规划orlplan-num开始处理； 2.检查i中所有规划是否处理完；若是，调度生成过程
15、结束，并返回最后规划的结束时间； 3.检查ork.op._machm中的m是否为1 4.检查ork.op_machm.op的m是否为PLAN-LENGTH,即第k个规划的最后一个操作是否已处理完,若是，则记录规划结束时，转步7；5.将该操作调度加入到它所分配的机床ork.op_machm.mach的链表*machine-schedule上； 6M=m+1;转步3，处理下一操作。Orkop-mach.machm； 7. k=k+1;转步2，处理i的下一规划。 4. 2 MOSA中优化目标评价 针对每一种调度方案，需建立优化目标的评价研算法求其优化评价函数，算法如下： 1.读取调度方案； 2.计算
16、F； 3.判断是否达到优化目标要求，如果达到要求，将评价值存入数据库，结束，否则，将评价值存入数据库，转向执行MOSA操作。4.3 MOSA中车间静态调度的实例 将基于MOSA算法的车间静态调度模型应用于学院实习厂的计划进行调度，生成实习厂的作业计划。 在3台机床上调度所示的4个零件，各零件的加工实现方式及相应的工艺路线约束见表1 表1.零件工艺路线约束零件序号零件代号工艺卖现31HB20611-3工艺实现1.：（1,6，1）（2,3，2,）（3，3,3）工艺实现2：（1，6,2)（2，4,3)（3，5，1）工艺实现3（1,8,3) (2,8,1）(3,5,2.) 2HB2061-5工艺实现1
17、：（4，4,3)（5,3，2) 工艺实现2：(4,4，1）（5,5,1）工艺实现3：(4,4，3）（5,6,3）3HB2062-8工艺实现1:C(6,4,2) (7,5,1) (8,2,3) 工艺实现2（6,6,3)（7,6,2）（8，4,1）工艺实现3：（6,7,1）(7,7,1）（8，5,1） 4HB2062-3工艺实现1:(9,3,3) (10,3,1) (12,2,1) 工艺实现2：（9,4,3)（10,5,3）（11，7,2）12,2,3）工艺实现3：（9,4,2.）(10,5,2）（11，9,1）(12,4，1） 5 结 语本文探讨了基于网格的模拟淬火遗传算法在生产实习和教学实习计
18、划编制中的应用，其中我们建立了综合考虑学生学习成本与学院实习厂之间的多目标规划模型以及设计了基于网格的模拟淬火遗传算法计算模型。结合GA算法、最优个体保护法和SA算法，提出了模拟淬火遗传算法（MOSA)，建立了实习厂静态调度问题的模型及其基于MOSA的求解算法，讨论了在3台机床上调度4.个加工零件的实例。通过仿真试验，对模型和算法的有效性进行了验证和分析，结果表明该模型和算法能较好地满足学院实习厂运行计划编制的有效性与实时性要求。 参 考 文 献：1 Chales J.Malmborg. A genetic algorithm for service level based vehicle s
19、cheduling. European Journal of Operational Research,1996,93:121-1342 Zhang Feizhou,Yang Dongkai,Chen Xiuwan. Intelligent scheduling of public traffic vehicles based on hybrid genetic algorithm. Intelligent Transportation Systems,2003.Proceedings 2003 IEEE Volume 2:1674-1678J. Herrera, E. Huedo, R. Montero, and I. Llorente. A grid-oriented genetic algorithm. In Advances in Grid