遗传算法应用于排课问题中的教师安排最优化第23计算机应用与软件。23,No。6Jun。2006遗传算法应用于排课问题中的教师安排最优化(上海体育运动技术学院上海)摘要介绍由计算机根据教师的意愿,利用遗传算法自动进行排课,最大限度地满足教师的愿望,对资源作出优化合理的安排。而且,利用Excel实现排课的遗传算法。排课分为教师安排和课程时间的安排两部分。本篇论述教师安排。关键词排课教师安排遗传算法(,。China),。。。
s。—ment。uling。´。gs。。引言有关排课问题有许多算法。它可以通过线性规划,知识库,目标规划等来实现。本文介绍的是利用遗传算法来解决排课问题,达到满足教师的优先选择,合理地使用资源。整个算法是在Excel中用VBA来实现的。所以只要有Excel就可以实现排课问题的遗传算法。排课问题可以分成两步:教师安排和课程时间安排。本文主要讨论教师的安排。数学模型在教师的安排中,要考虑教师对课程的优先选择和教师工作量的合理分配。根据这些要求构建出遗传算法的适应度函数。
根据(Yen—,2002),作适当的调整,得到如下公代表系里面某年级某班的课程,{C。,C,…,C}表示整个系的课程的集合。代表教师(=1,2,…,P),共有P教师。W。={C,C。-,C},它是老师选择教的全部课程的集合,按老师教学效果依次排列,C是效果最好的,C6次之,是效果最差的。教学效果由职称级别,该课程教学次数,愿意程度的加权和组成。为了保证每一课都有老师任教,这里假设,每一课至少有一个老师选择愿意教授。C在。中的教学效果值由如下函数表示:。r(c:J/fc(1)´【0/fc其中是职称值,职称高的取值高,职称低的取值低;是教师曾担任C课程的次数;D是教师担任C课程的愿意程度;or,是正权数视实际要求而定其相对的大小,++nPJo;maxJ=。厂(C,)?&(i;1,2,…,n;=1,2,…,P)(2)其中占=1,这是为了保证每门课程只有一个老师任教。为了考虑合理的安排教师的工作量,对教师工作量不满和工作量过多设置惩罚函数:这里取B:老师的最少课时数;U:老师的最大课时数;:课程C。的课时数。为了保证教师工作量的合理安排,每个教师的总课时数必须在本人最大工作量和最小工作量之间,即满足如下不等式:为了保证教师不超过工作量,则所有教师的最大工作量的总和要大于总课时数,即:收稿日期:2004—07—26。
顾运筠,硕士,主研领域:软件应用。计算机应用与软件2006一)>U(6)0ifB(QJ(U7,:』(一(BTj+D))´(sTj+D)(7)【y((+0)一)>(+O)其中为教师的实际工作量,O为教师的平均工作量中超出教师最小工作量的部分。在实际的计算中,为了简化程序排课算法 java 遗传算法应用于排课问题中的教师安排最优化,假设所有的。取值相同,所有的。取值相同。权数,卢,满足不等式:,卢>。遗传算法的适应度函数为:F=Jo—J。(8)遗传算法描述遗传算法是根据生物染色体自然进化的模型,它仿照染色体的基因在进化的过程中进行选择,交叉,变异生成下一代种群。计算开始时对种群进行初始化,并计算每一个个体的适应度函数,生成第一代。如果生成的种群不满足优化条件,则按照适应度选择个体,父代进行交叉或变异生成子代。然后子代取代父代,再生成下一个子代。这一过程循环执行,直到满足优化准则为止。3。1基因表示教师安排问题相应的遗传算法的个体基因由图1教师安排的基因个体图示(Wang,2002)3。2初始种群的选取和杂交的特点—II兰兰垒!些些I教师安排的遗传算法杂变图示如图2所示,在本遗传算法中,选取一组基因作为种群。每个个体中,同一课程的一组基因码作为一个基因片段,每个基因片段中保证只有一个基因码的值为1,其余的值为0。
为了包括每个基因片段的所有可能性,在种群中,使得每个基因片段的可能取值至少出现一次。如:C课程可由排课算法 java,,。,6位老师教,则它所对应的基因片段取值可以为:10000,01000,00100,00010,00001。在所构造的初始种群中,要保证这五种可能取值都出现。为了保证每个基因片段中不会同时有两个以上的基因码的值为1,每次做杂交时,断点都在基因片段的分隔处,即保证基因片段的完整性,不在基因片段的中间把它断开。3。3适应度函数适应度函数为公式(8)。3。4计算过程1)编码:根据基因表示进行编码。2)产生初始种群。3)计算适应度函数。4)遗传操作:进行交叉生成子代种群。5)计算子代的适应度函数,满足优化条件,则输出结果;反之,返回4)。实例计算结果和分析在Excel中用VBA实现这一遗传算法。利用Excel的表格特点,把数据输入Excel的工作表中,如表1和表2。然后利用VBA从Excel的工作表中读取数据,进行计算,并按照要求,把计算结果生成各种容易读取的报表,直接在Excel中以报表的形式表示出来。这里利用表1数据进行计算,3分钟内就能得出结果。每次计算的结果都不一样,可以把几次计算的结果进行比较,选取最满意的结果。
表3显示了求得的一次计算结果。在遗传算法进行杂交时,分别采用了单点杂交,两点杂交和多点杂点),结果两点杂交的效果最好。由结果可以知道,使用Excel中的VBA编制的遗传算法,能很好地满足教师的意愿,它是一种有效,方便,快捷的计算方法。如对该程序感兴趣欢迎联系。课程和对应的课时课程C1C26"课时 课程29C30 课时 课程" 课时 教师对课程的选择意向(巧表示某教师,Ci 表示某课程,数字一1。1—7 表示教师的意愿,一1 示该课程只能由该教师教,从1—7依次表示教师意愿逐渐降低) T1 一 T16""34_," 丁2～ ´"32 , 0_, , 7" /´ (。
,刀 刀´ /´ I´ 四 /C40 ( 教师安排的遗传算法的计算结果(数据项中括号中的值为教师的意愿) 教师课程(意愿)总课时教师课程(意愿)总课时 n63(一1)。c8(2)(3)排课算法 java,06(2)。c4o(4)l0 挖r,44(一1),c2(2),c6(3)(3)。638(4),cA1(1)。c,42(2)l6 73c1(1)(3),631(1)7 c4(4)。C14(1),Cl5(2)(1),c7(2)10 巧C13(1),C16(2)8n509(1),c10(2)8 6"25(1),O2(4)(I),C18(2)6 了´7630(1)。
c35(3)9n76"29(1),c39(6)6 633(1),CA3(6)(1),C12(2)9 丁96"22(1),6"24(3)(1),6"21(3)。C34(5)7 n0C23(1),6"27(3),C28(410 函数值183。33 参考文献 [1]Yen—。 。,25(2OO3),39-50。[2]王小平,曹立明,遗传算法——理论,应用与软件实现,西安:西安交 通大学出版社,2002。1。 [3]张文修,粱怡,遗传算法的数学基础,西安:西安交通大学出版社, 2Ooo。5。 [4]。Badri。Atwo—[fac— uhy-—time]。— seal~h,94(1996),16—28。
[5],。—based time—。—,12(1999),8l~93。 [6]。Abdri,。Davis,。— swo~h,—: 。。Vo1。25,No,4, PP。303—316,1998。 [7]。Pa~the —lem。Socio—Econ。Plann。。 N0。3。PP。245—256,1995。 (上接第37 结论通过在Linux 平台上设计并实现了支持IPv6 的动态数据包 调度机制DPSM,提供了EF 数据流较低的抖动,较低丢包率的 服务质量,并能维持一个稳定的端对端延迟需求。
通过试验验 证了系统对于数据包抖动具有较好的抑制作用。 参考文献 [1]徐轶铭,"在IPv6 的 网络上具有 调整的延迟 变化率减小机制",中山大学硕士学位论文,2003:13—96。 [2],D。P。,eta1。In。nts: 一based , 。2004,: Press:497—510。 [3],eta1。,Areal—?per- , ence,2004,::77～84。 (上接第41 算法改进的若干建议度代价最小控制策略后,还可以进一步提高系统处理速度。
但 是,如果涉及到工程项目处理工序之间的参数传递控制,异步方 式执行其它应用程序就会导致异常。本文介绍的异步方式作业 调度算法中,情形1)和2)控制相对简单,而3)的控制实施则相 对较复杂。例如,当作业调度关系较复杂,并且n 值很大的时 候,可以利用反馈网络算法自动计算n 个作业的相关矩阵R 强该算法的自适应性。参考文献 [1]严蔚敏着,数据结构,清华大学}』I 网络程序设计,科学…版社,2003。8。[3]焦李成编着,神经网络it 算,凹安电于科技大学出版社,1993 往往达上千万条记录,为进一步的研究打下了良好的基础。参考文献 [I], [2],(´l/k(11)/。 [3]ect, [4], 一124。ibm。/oss/linux/ //。 [5]。Bovet,,,2ndE— ,O´,2002。
(上接第64 电话,采用芯片实现的税控机等。。在产品研发过程 中,我们提出了很多应用,设计了很多算法,这些算法从原理上 看应当是在各种计算平台上都通用的,比如通用菜单系统,中文 处理系统,日历和汁算器等等,但是,由于开发平台各异,开发语 言也完全不同,其结果自然是重复开发。我们希望能够实现原 程序的通用。C 是一种比较通用的嵌人式语言,但C 不是平台 无关的语言,它与芯片有紧密的联系,如寄存器,存储器等都是 与硬件相关的。而JAVA 足一种真正意义上的平台无关语言系 统,通过虚拟机,其源程序只+l-x~虚拟机编程,底层对JAVA 程序是透明的,这可以实现算法的重用机制。这促使我们开展对JAVA 虚拟机的研究,并在一个具体的产品(信息电话)中实 现它。本文就是我们在研发过程中幕于我们对JAVA 的理解而 形成的,是我们开发虚拟机的理论准备工作。 参考文献 [1]。。 [2]ation,。 [3]sun 公司java 主页,URL:java。
sun。eom。 [4]SUN 公司J2ME 资料,,/index。jsp。 二作室着,深入嵌入式jave虚拟机,中国铁道出版社,2003。 [6] 技术专区,URL:— works/cn/java。 [7],,URL:w。jcp。 org/en/jsr/al1。 『8]。 [9],URL:java。sun。corn/ //。 异步方式执行其它应用程序的效率是很高的,加入作业调[10]WABA 虚拟机资 料。URL:,www。?com