基于蚁群算法的高校课程编排系统应用研究

《基于蚁群算法的高校课程编排系统应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、湖北工业大学硕士学位论文本文分析了蚁群算法的基本思想和原理，结合高校课程编排的自身特性找出适于优化课程编排系统的蚁群算法。就如何运用蚁群算法于课程编排中进行研究，提出课程优化策略、对程编排算法进行拓宽，并推广蚁群算法的运用面。1.2课题研究现状课程编排问题之所以成为困扰高校的一项重要工作之一是因为只有编排出适合高校自身特点的课程表才能保证基本的教学运行，才能维护教学的问题，而只有一份科学合理的课表才能调动师生的积极性、调节师生的压力，在有限的教学资源下，通过合理的安排，使各项教学工作都能有秩序、有计划的进行。高校扩招以后，学生数量急剧膨胀，教学基本资

2、源短缺，而每个高校有其自身的特点，如：学生多教师少、学生多教室少、学生实验室不足、等等。因为数据量大、约束条件多、以及课程表在教学执行过程中的动态性，决定了排课问题成为困扰各高校的难题。人工编排课表已经不可能完成，但是目前各个高校之间并没有一个能够解决众多问题，脱颖而出的一个被公认的软件。早在70年代课程编排问题就被证实是NP完全课题，他的难度是曾指数增长的，这一论断完全确立了课程编排问题的理论深度。目前，还没有一个大家通用的算法能很好的解决NP完全课题，很多NP完全课题不仅普遍而且还具有相当重要的意义。解决NP完全课题的方法目前的主要思路是考虑如何

3、降低计算的复杂程度,也就是说要建立一个模型，利用模型使求解问题的实际由指数增长转换到多项式增长，通过降低复杂度实现程序。20世纪50年代末，国外就开展了课程编排系统的研究，Gotlieb在1963年对课程编排问题进行了形式化的描述，创立了课程编排系统的数学模型。S.Even、eooper等人1976年证实了课程编排问题是一个NP完全课题。于是课程编排问题的学术地位被确立，其复杂性得到了学术界的普遍认可，复杂性提升至理论高度。事实证明课程编排问题是有限资源、多目标、多限制的组合规划问题。国内外众多软件公司和高校对课程编排系统进行了研究，取得了很多成果。

4、由于课程编排问题是一个NP完全课题，实际上大多数求解结果都不理想。90年代后，国外进行课程编排问题的研究有了很大的进步。如加拿大Montreal大学的JeanAubin、JacquesFerland、印度Vastapur大学的ArabindaTRipathy等，他们的研究都有一定的代表性。由于课程编排问题是多约束性，用数学方法描述往往使得课题规模呈指数剧烈增大。国外研究给我们了启示，解决数据量庞大的课程编排问题仅仅靠数学方法是无法做到的，运筹学中的分层规划思想能够把课题进行分解，这2湖北工业大学硕士学位论文是一个有望取得成果的途径。目前，国内的高校面

5、临更多的约束条件，教学资源紧张这是国外高校普遍没有考虑到的问题，他们设计的课程编排系统一般不考虑教学基本设施以及教师的缺乏，不能满足我国高校扩招以后目前的实际情况。国内众多软件公司和高校进行了积极的研究探索。80年代初我国的课程编排系统就开始了，比较代表性的有:清华大学的TSER(TitableSeheduler)系统、南京工学院的UTSS(UniversityTitableSehedulingSystem)系统和大连理工大学的智能教学组织管理课程调度等等，这些系统一般都是都是模拟了手工课程的编排方法，运用了启发式函数以班级为单位进行课程编排的。但是

6、各校的教学体制以及实际面临的教学困难不尽相同，教学周次和师生以及教学基本设施情况皆不相同，所以无法通用，不能得到大家一致的认同。当前，解决课程编排问题的方法比较公认的有：回溯算法、遗传算法、二分图及着色理论、模拟退火算法等等。然而，由于课程编排问题的复杂性，没有任何一种方法能够完全无冲突的排出一个科学合理的课表，并且无法考虑到各个高校的特殊性，所以课程编排软件难以推广，基本上难以完全交由计算机完成课程编排系统，各大高校一般都是自行开发各自适用的课程编排系统，由系统粗排以后再进行传统的手工排课调整。1.3本文研究内容本文旨在通过对基本蚁群算法进行分析研

7、究，提出能够优化课程编排问题的策略。通过研究蚁群算法的优劣势，建立与课程编排系统对应的模型，并对蚁群算法进行改进，运用改进以后的蚁群算法到高校的课程编排问题中，然后进行检测，从而验证该算法的可行性。并引入实验数据进行模拟课程编排，对相关的案例参数进行分析比较，最终为课程编排问题提供一种新的思路解决问题，同时拓宽蚁群算法的运用领域，彰显蚁群算法在处理多约束问题上的优越性。1.4本章结构第一章绪论主要介绍论文的选题的目的和意义，以及国内外研究现状、文章内容结构。第二章蚁群算法介绍主要介绍基本蚁群算法的原理，对蚁群算法进行全方面的仿真。第三章基于蚁群算法课

8、程编排系统研究详细描述了课程编排问题的多约束性课题，对课程编排系统做出双分图模型，并进行分析，最后给出基于蚁