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

普通本科毕业论文(设计)题目:学分制模式下基于遗传算法的排课系统的设计院别信息管理学院学生姓名王兆奇学号0031718年级2003级专业信息管理与信息系统指导教师凌传繁职称教授二OO七年五月论文独创性声明本人声明，所呈交的毕业论文是在导师指导下本人独立完成的研究成果。文中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成果。本文如违反上述声明，愿意承担以下责任和后果：1.交回学校授予的学位证书；2.学校可在相关媒体上对作者本人的行为进行通报；3.本人按照学校规定的方式，对因不当取得学位给学校造成的名誉损害，进行公开道歉；4.本人负责因论文成果不实产生的法律纠纷。论文作者签名：日期：年月日摘要排课问题是一个多约束、多目标的优化问题，其实质是时间表问题，已经被确认为NP完全问题。遗传算法作为一种随机搜索算法，利用群体搜索技术，对解决NP问题非常有效。本文将遗传算法应用于学分制模式下的排课系统中，通过对排课因素和约束条件的深入分析，制定了排课问题的优化目标，设计出了适合于遗传操作的编码模型，给出了合理的适应度值的计算方法。通过对初始种群进行选择、交叉、变异等过程不断进化，取得了优化的课表。在排课系统设计中，本文采用了面向对象的方法，设计了课表安排中的教室调度算法、基因填充算法、冲突检测算法，使得排课得以实现。利用真实的数据进行系统测试，并分析了各参数对遗传操作及结果的影响。【关键词】学分制模式；排课系统；遗传算法；多目标优化DesignoftheCourseArrangementSystemBasedonGeneticAlgorithmsinCreditModeWangZhaoqiAbstract：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\h1HYPERLINK\l"_Toc171269092"2遗传算法PAGEREF_Toc171269092\h2HYPERLINK\l"_Toc171269093"2.1遗传算法研究的内容PAGEREF_Toc171269093\h3HYPERLIN