学分制模式下基于遗传算法的排课系统的设计.doc

普通本科毕业论文(设计)

题目:学分制模式下基于遗传算法
的排课系统的设计

院别信息管理学院
学生姓名王兆奇学号0031718
年级2003级专业信息管理与信息系统
指导教师凌传繁职称教授

二OO七年五月

论文独创性声明
本人声明，所呈交的毕业论文是在导师指导下本人独立完成的研究成果。文中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成果。
本文如违反上述声明，愿意承担以下责任和后果：
1.交回学校授予的学位证书；
2.学校可在相关媒体上对作者本人的行为进行通报；
3.本人按照学校规定的方式，对因不当取得学位给学校造成的名誉损害，进行公开道歉；
4.本人负责因论文成果不实产生的法律纠纷。

论文作者签名：日期：年月日

摘要
排课问题是一个多约束、多目标的优化问题，其实质是时间表问题，已经被确认为NP完全问题。遗传算法作为一种随机搜索算法，利用群体搜索技术，对解决NP问题非常有效。
本文将遗传算法应用于学分制模式下的排课系统中，通过对排课因素和约束条件的深入分析，制定了排课问题的优化目标，设计出了适合于遗传操作的编码模型，给出了合理的适应度值的计算方法。通过对初始种群进行选择、交叉、变异等过程不断进化，取得了优化的课表。
在排课系统设计中，本文采用了面向对象的方法，设计了课表安排中的教室调度算法、基因填充算法、冲突检测算法，使得排课得以实现。利用真实的数据进行系统测试，并分析了各参数对遗传操作及结果的影响。
【关键词】学分制模式；排课系统；遗传算法；多目标优化
DesignoftheCourseArrangementSystemBasedonGeneticAlgorithmsinCreditMode
WangZhaoqi
Abstract：
Theproblemofcoursearrangementisanoptimizationproblemwithmulti-constraintsandmulti-objective,whichisactuallyatimetableproblemandhasbeenprovedtobeaNP-completedproblem.Asaramdomsearchingalgorithm,thegeneticalgorithm(GA)usingcolonysearchingtechnologyisverysuitableforNP-completedproblem.
ThisthesisusesGAforthecoursearrangementsystemwithcreditmode.Theroughanalyzingdeeplythefactorsandconstraintsofcoursearrangement,theoptimizationobjectivesofcoursearrangementaredeterminedfirst.Thenthecodingmodeforgeneticoperationsisdesignedandthecomputationmethodforreasonablefitnessisgiven.Anoptimizedcoursetableisgottenthroughtheoperationsofselection,recombinationandmutationontheinitialcolony.
Basedontheobject-orientedmethod,thisdesignmakesuseofclassroomschedulealgorithm,geneticfillalgorithmandconflictdetectingalgorithmtoarrangecourse.Theexperimentsarecarriedoutusingrealdatatoanalysetheinfluenceofallparametersonthegeneticoperationsandresults.

Keywords：
CreditMode;CourseArrangementSystem;GeneticAlogrithm;Multi-objectiveOptimization
目录
TOC\o"1-3"\h\zHYPERLINK\l"_Toc171269091"1引言 PAGEREF_Toc171269091\h1
HYPERLINK\l"_Toc171269092"2遗传算法 PAGEREF_Toc171269092\h2
HYPERLINK\l"_Toc171269093"2.1遗传算法研究