基于遗传算法的排课系统设计 开题报告.docx

基于遗传算法的排课系统设计开题报告

第一篇：基于遗传算法的排课系统设计开题报告基于遗传算法的排课系统设计开题报告课题的意义每个新学期开始，对于学校教务科来说首要而急需完成的任务是：如何合理而高效的排课。其本质是将课程、教师和学生在合适的时间段内分配到合适的教室中。但由于涉及到的问题较多，同时学校扩招，学生和课程数量比以往大大增加，教室资源明显不足，在这种情况下排课很难在同时兼顾多重条件限制的情况下用人工方式排出令教师和学生都满意的课表。虽然排课问题很早以前就成为众多科研人员和软件公司的研究课题，但是真正投入使用的排课软件却很少。原因是多方面的，其中算法的选择是最关键的一个问题，S.Even等人在1975年的研究中证明了排课问题是一个NP-Complete问题，即若是用“穷举法”之外的算法找出最佳解是不可能的。然而由于穷举法成本太高，时间太长，根本无法在计算机上实现。如果假设一个星期有n个时段可排课，有m位教师需要参与排课，平均每位教师一个星期上k节课，在不考虑其他限制情况下，能够推出的可能组合就有nm*k种，如此高的复杂度是目前计算机所无法承受的。而遗传算法的出现正好解决了排课在算法上的问题，可以很有效的求出最优解。轻松而快速的解决了困扰教务科的一大难题，能在短时间内排出符合各项条件的课程表。国内外研究现状计算机排课问题是一个多目标，有限资源，带有模糊约束条件的组合规划问题，是计算机应用领域一个具有代表性的问题。20世纪60年代末，Gotlieb.C.C教授就对课程表问题进行了形式化描述。随后，此类研究发展起来。70年代中期，S.Even等人就论证了课表问题是NP完全类问题，将该问题理论化，同时也说明课表问题有其自身的理论化模型，即课表问题存在解。并且能找到解。但是根据计算和难解性理论，目前还没有解决NP完全类问题的多项式算法。到1979年，Schmit和Strohein在文献中就列出了300多篇已发表的文献。近年来研究这一问题的人员不断增多，国外的运筹学杂志几乎每年都有相关内容的文章那个发表，此外它还广泛的出现在计算机，应用数学，教育管理等杂志上。80年代初，我国的很多大学也开始研究排课系统软件。大体上说这些排课系统软件可以分为两大类：第一类以所谓班——教员模型为主，它是在Gotlieb.C.C工作的基础上发展起来的。主要讨论此模型的定义扩充，解的特性及分析，不断提出新的猜测和推论。基本模型变化不大，并且这类模型适合课程长度一致，无合班教室的情况，并不适合一般院校的实际情况。第二类事所谓的课程调度问题，多于图的节点的着色问题有关，模型一旦产生，它的变量往往太多，规模太大，此外根据具体的校情对模型提出的各式各样要求对模型影响较大，有的甚至没有具体的模型可寻。通过对资料的查阅发现以往对课程问题的研究多侧重于自动生成，难度较大实现不易，往往是理论研究上的工作多，而实际应用方面的工作很少。有一些实际的例子，也往往是特定条件下对实际情况简化得到的，至今还没有自动生成可课表系统的软件应用于实际。对计算机而言，不像人工编排那样可以对任何情况进行合理的取舍，因此不存在完全冲突的课表很难排出来。国内高校排课系统中，大连理工大学是从事此类软件开发较早单位。1987年该校开发了《教学组织管理及课程调度系统》1.00版本，之后在此基础上又推出了《教学组织管理及课程调度系统》2.00版本，1902年又推出了《教学组织管理及课程调度系统》2.01版本和安排考试补考的《考试调度系统》。1994年又推出了《教学调度系统》2.20版本。1998年年推出的在Windows下运行的3.00版，现在在各大高校使用比较多，反映较好的有大连理工大学开发的系统和清华大学开发的《综合教务排课系统》，以及北京大学开发上的一套比较新的排课管理系统。3毕业设计论文的主要内容1.遗传算法的形成及基本应用，遗传算法的基本实现技术和特点。2.排课中所要考虑的约束条件，课表编排的基本规则和课表编排中存在的矛盾和问题3.将遗传算法应用于排课系统；4.所采用的方法、手段以及步骤等1.详细了解课表编排中存在的矛盾和课表编排的规则，将其逐条列举出来，选取必须兼顾的重要的约束条件，2.分析学生，教师，课程，教室之间的关系建立概念模型和逻辑模型3.产生初试种群4冲突检测和消除：对各种冲突进行检测，如有冲突则消除它5计算适应度函数期望值6遗传操作包括选择交叉变异7可行课表的生成5.阶段进度计划第一周——第三周：查阅资料，学习遗传算法的基本理论，查阅相关文献完成开题报告第四周——第五周：详细学习遗产算法，并对所做课题进行详细构思第六周——第七周：完成英文资料的翻译第八周——第九周：分析调查排课问题所面临的具体问题和矛盾以及缩影可考虑的因素，分析找出座位乖蹇的约束条件第七周——第九周：对各个模块进行设