基于遗传算法的课程表问题研究-应用数学专业论文.docxVIP

东北大学硕士学位论文 东北大学硕士学位论文 摘要 基于遗传算法的课程表问题研究 摘 要 课程表编排问题是时间表问题之一，也是一个解决时间和空间资源矛盾的 多因素优化决策问题，即对各类课程、教师、学生进行时空安排问题，这种安 排问题需要满足一定的约束条件集，如关于教室的位置与容量、时间间隔、特 定课程承接关系等方面的约束条件。目前各类学校都存在着学生数量、课程设 置增多，而相应的配套资源没有太大变化的情况。这就要求能充分利用已有的 资源，选择最合理的编排方案。近40年来，人们尝试着用各种方法求解此类 问题，如：整数规划、图着色、各种推理有哪些信誉好的足球投注网站方法、进化算法等等。 遗传算法是一种拟自然的、具有随机性的全局优化方法。近些年来，遗传 算法在求解复杂问题中发挥了重要的作用。同样，遗传算法也能有效的求解课 程表问题。 本文分析了课程表问题的发展状况；综述了遗传算法在数学基础、遗传操 作以及各领域的应用发展现状：根据大学授课形式的特点建立了大学课程表问题 的数学模型；给出了基于不同目标的遗传算法求解方法；提出教师和教室的两种 编码形式，为了提高解的质量和加快收敛速度又设计最佳时段一查找法，并将其嵌 入遗传算法中；对于利用教室编码的遗传算法提出了一种新的交叉算子；通过实 验验证了本文所提出的算法适合于所建模型的求解，是可行性和有效性。最后 给出了课程表问题进一步研究的方向。 关键词：时间表问题、课程表问题、遗传算法、编码、遗传操作、早熟收敛、 进化计算、数学模型 ，II 查!!垄兰翌主兰堡堕圭 查!!垄兰翌主兰堡堕圭 一———————垒坐!!坚 Research on Lecture Timetabling Problem Based on Genetic Algorithm Abstract Lecture timetabling problem is one of the timetabling problems．It perhaps is one of the greatest problems to be solved at the beginning of each term．Lecture timetabling problem is the problem of assigning times and place to many separate lectures tutorials ere．to sarisfy several constraints concerning capacities and locations of available rooms，free—time needs and other such consideration for lecturers，and relationships between particular courses．As educational institutions are challenged to grow in number and complexity with often no corresponding increase in resources due to usual budget constraints，their operations need to be streamlined more and more efficiency while minimizing resources usage．Over the last 40 years．many approaches and models have been proposed for dealing with a variety of the timetabling problems，such as integer programming，graph coloring， heuristics search methods and evolutionary algorithms． Genetic algorithm is a random optimization and search technique．It has been applied to a variety of complex problems．Lecture timetabling problem is could be solved by genetic algorithm quite successfully． In this paper,a brief introduction to some approa