用遗传算法求解排课问题

用遗传算法求解排课问题

作者：董富江 杨德仁

来源：《教育界》2011年第08期

【摘要】遗传算法是解决排课问题的新途径；介绍了一种遗传算法求解排课问题的染色体设计，适应度函数设计，交叉和变异操作。 一、概述

排课是一个NP完全的时间表问题（TTP），传统的算法面临这种问题显得捉襟见肘。由于适用于大规模、并行问题，并具有自组织、自适应等智能特征，所以遗传算法为机械化解决这个问题开辟了新途径。时间表调度可以被看做确定性的约束满足问题，因此解决排课问题可以通过给系统中所有变量赋值，满足相应的约束条件。本文的算法设计按照这个思路进行。 二、算法设计 （一）染色体设计

染色体（chromosome）由课程班的集合表示。一个课程班由课程（c）、星期（d）、时间（t）、教师（p）、教室（r）、层次（l）和一个学生列表（s）组成。因此染色体可如下表示：

Chrom={（ci，di，ti，pi，ri，li，si）│i=1，…N} 其中相关变量的具体解释如下：

c是课程的集合中的一个元素，具有名称、周理论学时和实验学时等属性； d取值范围为1-5，表示星期一到星期五；

t取值范围为整数1-6，7-10中连续两个或者三个间隔，例如1-3，7-8（t也可以是时间段，例如8：00-10：00）； l是指学生的专业和学期； p是教师的工号；

r是一个结构体，包含教室的编号，类型和容量等；

龙源期刊网 http://www.qikan.com.cn

s为了简化问题，s取课程班的学生人数。

于是染色体可以用一个N*7矩阵来表示（N是课程数）： c1,d1,t1,p1,r1,l1,s1, … … … … … … … cN,dN,tN,pN,rN,lN,sN （二）约束条件

排课需要考虑许多约束条件，诸如教师数量、学生数量、教室的数量和类型、课程的理论和实验学时等。这些约束条件可以分为如下两种类型：

硬约束：是指不可破坏的约束，例如同一名教师不能在同一个时间上两门以上课； 软约束：这种约束即使破坏，排课方案仍可接受，例如同一名教师在同一天在两个连续时间槽有课。

一个排课问题的约束可以用C来表示，其中C是断言的集合{C1，C2，…，Cn}。通常这些断言作为参数，并尽量被满足来获得问题的解决。如果某一断言Ci未被满足，则给其指派一个惩罚ai，惩罚的大小依赖于约束的类型和重要性。实验中使用的约束的例子如下： ：同一个教室在同一个时间只能有一门课 ：同一门课的两个时间槽不能在同一天

于是对于任意两个染色体（ci，di，ti，pi，ri，li）和（cj，dj，tj，pj，rj，lj），它们违反以上约束的情形表示为：

=（di=dj）&（ti=tj）&（pi=pj） =（ci=cj）&（di=dj） （三）适应度函数设计

对于基因上的每一个约束条件C，计算函数： 1如果约束被破坏 f（c）=

龙源期刊网 http://www.qikan.com.cn

0约束没有被破坏

总适应度的计算方法如下：

其中ai代表约束Ci的权重。可以看出为了较好的解决问题，应使适应度函数最小化。为了简化问题对于硬约束我们使用一个常量α，对于软约束使用一个常量β，这样一来适应度函数为：

（四）选择操作

选择是指在群体中选择生命力强的个体产生新群体的过程。这里采用最佳保留选择的方法，这种方法的步骤是：

首先采用轮盘赌方法进行选择操作： Step1计算每一个个体的适应度f（Ci） Step2计算整个种群的适应度的和

Step3计算每一个个体进入下一代的概率f（Ci）/

其次是将当前群体中适应度最高的个体完整复制到下一代中。这种方法的优点是能够保证算法结束时得到的结果是历代出现过的最高适应度的个体。

（五）交叉操作交叉操作的步骤是：选择两个染色体中的行号相同的两行；随机交换它们的d值、t值或者r值。交叉在算法中起着关键作用，是产生新个体的主要方法，能够使群体分布扩充。

（六）变异操作变异操作的方法是：随机选取染色体矩阵中的某些行，然后把它们的日期d或时间槽t，或者教室r的值进行修改，要注意的是修改要遵守相关的约束。变异操作能够改变个体的结构，维持群体的多样性，有利于防止出现早熟现象。 三、结束语

遗传算法的应用日益广泛，但是研究表明因为实际情形诸如约束条件的不同，解决各种时间表问题的方案也不相同，遗传算法在实际应用的时候需要根据实际情况作出必要的变形和改进，设计适合实际情形的目标函数、交叉和变异操作，使问题得到较好的解决。

【参考文献】

龙源期刊网 http://www.qikan.com.cn

［1］雷英杰等.MATLAB遗传算法工具箱及应用.西安电子科技大学出版社，第1版，2005.

［2］张文修等.遗传算法的数学基础.西安交通大学出版社，第2版，2003.

项目名称：“基于遗传算法的医学院校排课系统”，校级项目。

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文