基于计算智能的排课算法设计与实现

关键词：排课系统　智能计算　遗传算法

 1　计算智能简述

计算机智能的定义的字面解释是多种智能方法的集合。他拥有非同一般的能力和推理的不确定性并能在不精确的环境中学习，是更有效的计算工具，以及建筑智能化系统的方法。目前已经在信息数据的处理、管理层的重要决策、智能控制、以及故障诊断等等领域得到广泛的应用。其中，最重要的几种方法是模糊系统、人工神经网络、遗传算法。在处理实际问题时，尽量通过优势互补，协同工作，只有通过这样，建筑建筑智能化系统的高性能才会得以实现。

智能系统的研究己经有40多年了,已经拥有硬，软件和传感器技术作支持，最重要的相关计算工具的突出作用。传统的计算方法需要通过清析的描述待求解问题,而计算智能允许不精确和不确定性，试图找到准确的或不准确的陈述近似解，从而得到易于操作、稳健性、低成本的更好的融合，解决了实际的问题。

遗传算法是在 20 世纪六七十年代由美国 Michigan 大学的 Holland 教授及其学生和同事共同发展起来的，是一种模拟生物界的自然进化规律而形成的一种基于全局的直接优化搜索算法，并且是一种进化算法。遗传算法是一个不断寻找最优点的过程，它始终让整个群体保持进化状态。

2　排课系统开发的意义

如何进行课程编排是在高校教学管理中非常重要的内容之一，并且是最为复杂的管理任务，其实质是为教学课程设置一套适当的教学时间和空间，使整个教学可以有计划、有秩序地进行。课表编排属于一类涉及多种因素的组合规划合理性安排问题，他要保证在安排课程中，使得学生与教师，以及与教室不发生任何的种类的矛盾（即上不同课程的两个以上班级在同一时间使用同一教室，或同一教师在同一时间段安排了多门课程等多种情况），并且要满足教师的要求和教室规划等管理条件。其一，必须详细了解学校各个学科课程信息以及教师信息。通常指以下事项：课程编排的时间，班级以及相关课程教师姓名。其二，排课系统的开发提供方便的检阅和查找功能。可以查看学生全部课程的信息，可以根据教室、教师，时间等信息提供课程查询。其三，可以对课程信息和教师信息进行删除和编辑。方便管理层对课程进行变动管理，或根据具体出现的情况手工排课，并实现尽可能的自动排序功能。

3　系统开发管理

3.1　排课要求属性

（1）准确性，要求准确地反映时间表和教室里每门课程和任课教师的相关信息，满足以下几点基本要求：同一个教师（班或教室）同一时间被安排只能一门课 ；合班上程的不同学生应安排相同时间相同教室上该门课；一个班学生分开上某门同课程应安排在相同时间；教室安排不得超过教室资源容量。

（2）容理性，要求严格按照教学规律要求进行课表的编排，在学生更好的掌握知识的前提下，保障教学质量，主要表现在：一个班级的课表是均衡的，每天上课的课时数是均衡的，且整个学期每周安排的课时数也应基本均衡相等；每门课程的时间安排是均衡的，保持同一门课在一周内两次课之间的间隔应基本相等，该课的周课时数也应相同；一些较复杂的的重要课程一般安排在上午。

（3）普遍性，要求对各方因素导致而提出的要求应尽量给与满足：同步上课是指满足教改上的要求即某班级的某些课程安排在统一时间上课；需要某课程安排在指定时间上课或者选修；需要某教师（或某教室）只被安排在特定时间或特定的周次内上课。

（4）特定性：教室或者教室的临时课程调整安排必须经由管理员排课统一调度，若无提前要求，按默认安排；教师与系统管理员的权限的分配要不同编排的课表仅满足准确性要求是没有实用价值的，还应同时满足容理性、普遍性、特定性的要求。

3.2　排课算法实现

排课问题的难点在于多约束不确定性的解决方案的实现。排课问题因为要受到各种不确定的人为、空间、时间等条件的约束，使得在前提条件相同下，某一课程在课表的可排位置并不唯一。基于以上原因本系统采用了采用了回溯算法进行自动排课。

（1）回溯法的前进限制条件（这样可以避免回溯的次数）：尽量把相同班级的课安排在集中的位置教室；为了降低后期手动调整产生较大矛盾，全校班级的课时间与空间安排应该尽量分散；尽量避免同一班级在一个集中时间段上课； 教室的容量和班级的人数尽量相贴近。

（2）回溯法的回溯条件：上课班级无法在空闲空间教师中找到符合要求的空闲时间安排。在遗传算法的作用下，基于前进条件进行前进排他选择，选取优先的具有优选机制的基因样本节点，再根据回溯条件进行样本迭代更替，最终得出最有解得课表条件，通知满足合理性与适用性以及限制性的要求。

4　实现难点

该排课系统在开发过程中，他的正确性往往不是其成功的决定因素，反而是在数据排他以及适用性方面比较难以把握，因此需要注意：教师和管理员对于本系统的权限的设置应当不相同；在课程设置上面，某段时间可能学校规定不可以安排课程；在教师课程时间安排上，某个教师允许其提出在满足正常教学要求下的特定时间安排，增加整个系统对于教师排课的人性化处理；手动与自动排课的相结合，解决正常性与个别性的冲突。

5　结论

排课问题是每个高校都必须要面对的一个实际教学问题，其解决的优选与否，直接影响了整个学校的教学秩序是否能够正常的运行。因此，排课系统的开发具有非常重要的意义。回溯算法是遗传算法的一种改进变异，对计算复杂度的消耗较少，且与分枝定界法同时使用时，对于所求解在解答树中层次较深的问题有较好的效果。将其应用于排课系统的开发能够快速地得到满足排课限定条件的结果，并且能够提供选择方案供管理人员手动调课时使用，消除了某些不能由计算机处理，不确定因素引起的问题，实现管理决策的科学化，对推动教学的发展也可以起到非常重要的作用。

参考文献：

[1]张智星,孙春在,水谷英二.神经一模糊与软计算[M].西安:西安交通大学出版社,2000.

[2]钱敏平,龚光鲁.从数学角度看计算智能[J].科学通报,1995(16).

[3]王凌.智能优化算法及其应用[M].北京:清华大学出版社,2001.

[4]王煦法.遗传算法及其应用[J].小型微型计算机系统,1995,16(2):59-64.

[5]王宏生,孟国艳.人工智能及其应用[M].北京:国防工业出版社,2009.