基于新型免疫遗传算法的高校排课仿真研究

《基于新型免疫遗传算法的高校排课仿真研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第29卷第2期计算机仿真2012年2月文章编号：1006—9348(2012)02—0386—06基于新型免疫遗传算法的高校排课仿真研究孙彤，郭倩倩(郑州轻工业学院计算机与通信工程学院，河南郑州450002)摘要：研究高校排课问题，关系到高校教学质量的提高和教学资源的充分利用，随着高校教学的深入改革和高校的扩招，优化排课的高效解决就变得更加迫切。通过深入分析高校排课问题，建立了排课问题的数学优化模型，构建了它的基本求解过程。针对高校排课问题的特点，引入遗传算法来加以解决，设计了多种改进方案，包括：新的二进制编码方案、初始种群生成方案、适应度函数设计方案

2、、免疫策略、白适应交叉概率和自适应变异概率设计方案。仿真结果表明新型算法能满足高校排课问题的多重约束条件，能更有效地解决高校排课问题。关键词：高校排课问题；遗传算法；二进制编码；免疫策略中图分类号：TP391．9文献标识码：ASimulationonUTPBasedonNewImmuneGASUNTong，GUOQian—qian(SchoolofComputerandCommunicationEngineering，ZhengzhouUniversityofLightIndustry，ZhengzhouHenan450002，China)ABSTRACT：U

3、niversityTimetablingProblem(UTP)relatestotheimprovementofteachingquMityandthesuffi-cientutilizationofteachingresourcesinuniversities．Withthefurtherreforminteachingandgrowingexpansionofre—cruitmentscale，UTPhasbecomeaproblemtobesolvedurgently．Inthispaper，UTPwasanalyzeddetailedly，anopt

4、imizationmathematicalmodelofUTPwasestablished．andtheframeworkstructuretosolveU，rPWaSfounded．Ac—cordingtocharacteristicsofU11P，GAwasintroduced，avarietyofimprovedschemesweredesigned，whichincludenewbinarycodescheme，initialpopulationdesignscheme，fitnessfunctiondesignscheme，immunizations

5、trategy，a-daptivecrossoverprobabilityandadaptivemutationprobabilitydesignscheme．Simulationresultssho‘rthatthepro-posedGAcansatisfymultipleconstraintconditionsandresolveUrI'Pmoreeffectively．KEYWORDS：UTP；GA；Binarycode；Immunizationstrategy1引言排课是教务工作中一项繁重的任务，它关系着高校的整体教学质量和教学资源的利用，随着高校学生

6、规模和课程数量的剧增，这一作用变得更加明显，从而使得高校迫切需要一个有效的排课方法来解决这个问题¨J。对于这个问题，国外在20世纪50年代末就进行了研究。1963年Gotlieb在他的文章中提出了排课问题的数学模型心]，并利用匈牙利算法解决了三维线性运输问题，它标志着排课问题的研究正式进入神圣的科学殿堂，但实践中遇到的困难使人们对排课问题的题解是否存在产生了疑问。1976年S．Even在论文OnThecomplexityoftimetableandmuhicommodityflowproblemsSIAM收稿日期：2011—03—08修回日期：2011—04—

7、29---——386·--——JournalonComputing¨1、Cooper等人在TheComplexityofTim-etableConstructionProblems【41中，证明了排课问题是NP完全的，这既回答了排课在实践中遇到困难的原因，同时又宣布利用计算机解决排课问题无法实现，因为计算机难解性理论研究指出，现代计算机尚未找到解决NP完全问题的多项式算法。S．Even的论证正式确立了排课问题的学术地位，把人对课表编排复杂性的认识提高到了理论的高度。80年代初，我国开始研究排课问题，所用方法从模拟手工排课到运用人工智能构建专家系统或决策支持系统

8、都有。南京工学院的urI’ss(AUn