论文部分内容阅读
大学课程表问题(University Timetable Problem-UTP)长时间给各个学校的教学资源多个目标,多个课程,如何组合如何优化带来很大的困扰。这个问题的解决不但有利于我们对运筹学中多方向优化类问题的研究,而且对解决我国现阶段教育中教学资源相对匮乏、而学生又超负荷的现状具有更实际的应用价值。排课问题作为一个有多目标,并且具有相对约束的组合优化问题,而且已经被证明为一个NP完全问题。以生物界自然选择为基础,进化机制为手段,发展起来的高度并行、自己适应功能的随机搜索算法,称之为遗传算法,它是一种非常有效的解决NP完全组合问题的方法。我的论文主要研究的课题是运用遗传算法来求解优化课表问题。本文首先介绍了排课问题产生的背景、研究意义以及国内外的发展现状,提出了本论文的研究内容,然后详细阐述了遗传算法的概念、基本原理、运用遗传算法解决一般优化问题的步骤、运算过程、编程实现的框架及其运用。接着本文主要针对排课问题所需的资源,人力,物力,用遗传算法建立完整的数学模型。在上述基础上,本文针对排课问题设计了基因编码方案、染色体结构、选择、交叉、变异算子,并提出了个体适应度评价函数的计算方法。然后用面向对象程序设计的方法,编写完成了遗传算法解决排课问题的代码。最后,理论结合实际为基础,并分析遗传算法的一些实例,实验表明本文的算法具有可行性和实用价值。本文研究表明,盒子群的编码方式具有代表性,将许多课表冲突直接在编码方案中予以解决,提高了算法的执行效率和适应性。