基于遗传和禁忌搜索算法的排课系统研究与实现

《基于遗传和禁忌搜索算法的排课系统研究与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、厦门大学硕士学位论文基于遗传和禁忌搜索算法的排课系统研究与实现姓名：叶碧虾申请学位级别：硕士专业：软件工程指导教师：陈金柱20090601摘要排课问题是学校教学管理中十分重要而又复杂的管理工作之一，随着课程的增多，学生人数的增加，在教室资源有限的情况下，要在短期内排出一张令所有教师和班级都满意的课表难度相当大，它是一个有约束的、多目标的组合优化问题，并且已被证明是一个NP完全问题。本文分析了大学课表问题的一般性质以及各种求解方案的优势和不足，并针对目前国内高校的教学实际设计了大学课表问题的模型。该模型考虑了教学实际

2、中所涉及的一般因素和约束，由于遗传算法是一种适合求解带有多参数、多变量、多目标和在多区域但连通性较差的NP—HARD优化问题的智能优化算法，所以本文考虑用遗传算法来解决排课问题，但是遗传算法具有早熟的现象，很快收敛到局部最优而非全局最优解，因此结合了局部搜索方法之一的禁忌搜索算法，用遗传算法结合禁忌搜索算法来解决排课问题，对比比较和计算分析，取得了良好的效果。本文主要进行了以下几个方面的研究工作：l、系统讨论了排课问题中的影响因素、主要约束条件、求解目标和难点，用数学模型描述了排课问题。2、设计了排课系统的数据结构

3、，并对一些子算法进行研究。3、研究染色体编码和遗传算子，并在变异阶段用禁忌搜索算法来实现，形成一个多目标的优化排课算法。4、以VS2005为开发工具，SQLSERVER2000为数据库实现了GA(GeneticAlgorithm)结合TS(TabuSearch)的智能排课系统，分析显示该系统能完成预期要求，结果令人满意。关键词：排课问题；遗传算法；禁忌搜索AbstractCurriculumarrangementisoneofthemostimportantandcomplicatedproblemsinthesc

4、hoolmanagement．Withmoreandmorelessons，studentsandthelimitedresourcesintheclassroomcircumstances，itwouldbedifficultinashorttimetoarrangetheschedulewhichallteachersandclassesweresatisfied．Itisabinding，multi—objectivecombinatorialoptimizationproblem，andhasbeenpro

5、vedtobeaNPcompleteproblem．Thisthesisanalyzesthenatureofuniversitycurriculumproblems，船well勰thestrengthsandweaknessesoftheproblemsolving．Italsodesignsamodelforthecurriculumarrangementintheuniversity．Thismodeltakesintoaccountthegeneralfactorsandconstraintsintheac

6、tualsituation．Asgeneticalgorithmsaresuitableforsolvingwithmanyparameters，manyvariables，manygoalsandinmanyregionswithpoorconnectivityNP·HARDproblem．Optimizesmartoptimizationalgorithm，thisthesisconsidertheuseofgeneticalgorithmstosolvetheproblemofarrangement，butt

7、hegeneticalgorithmhasprecociousphenomenon，itCanquicklyconvergethelocaloptimumratherthanglobaloptimalsolution，SOWecombinethetabusearchalgorithmwhichisoneofthelocalsearchmethods．GAcombinedwithTStosolvetheproblemhasachievedgoodresults．Thisthesisconcludesthefollow

8、ingresearchworks：1．Thesystemcompletelydiscussestheinfluencefactors，themainconstraints，objectivesanddifficultiesofcurriculumarrangementproblem，andUSeSmathematicalmodeltocompletelyde