排课系统的遗传算法交叉算子实现--本科毕业论文
天 津 师 范 大 学
本科毕业论文（设计）
题目：排课系统的遗传算法交叉算子实现
学 院：计算机与信息工程学院
学生姓名： ***
学 号： ********
专 业： 计算机科学与技术
年 级： 2008级
完成日期： 2012年4月
指导教师：
排课系统的遗传算法交叉算子实现
摘要：近年来随着各大高校的不断扩招和合并，由于教室有限，排课逐渐成为一个日益复杂的问题，课程的编排以及教室的合理利用为教学管理的工作加大了难度。遗传算法，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位。所以本文以遗传算法为工具，对排课问题进行了深入的研究，设计了其中的交叉算子，在实际应用中有一定的意义。
关键词：遗传算法；排课系统；交叉算子
Implementation of the Crossover of the Genetic Algorithm for
Class Scheduling System
Abstract: In recent years, with continuous enrollment and consolidation of the major colleges and universities, and there are not enough classrooms, the course scheduling is becoming an increasingly complex problems. The genetic algorithm is the calculation model of genetic selection imitating Darwin's natural selection of biological evolution process. Genetic algorithm as a new global optimization search algorithm, with its simple and universal, strong robustness, suitable for parallel processing and a wide range of notable features, established its position as one of the crucial smart calculation in the 21st century. So this article carries on in-depth research on Course Scheduling Problem by use of genetic algorithm as a tool, design a crossover operator which has a certain of significance in practical applications.
Key words: Genetic Algorithms; Scheduling System; Crossover operator
目 录
1 绪论.................................................................................................................... （1）
1.1 课题研究背景及意义................................................................................. （1）
1.2 课题主要研究内容..................................................................................... （1） 2 Microsoft visual C++ 6.0开发环境简介 .......................................................... （1） 3 排课系统的总体问题分析................................................................................ （2）
3.1 高校排课问题概述..................................................................................... （2）
3.2 排课问题的硬性约束................................................................................. （3）
3.2.1 课程问题分析...................................................................................... （3）
3.2.2 班级问题分析...................................................................................... （3）
3.2.3 教师问题分析...................................................................................... （3）
3.2.4 教室问题分析...................................................................................... （3）
3.2.5 时间问题分析...................................................................................... （3）
3.3 排课问题的软性约束................................................................................. （3） 4 遗传算法的设计................................................................................................ （4）
4.1 遗传算法概述............................................................................................. （4）
4.2 遗传算法分析............................................................................................. （4）
4.2.1 遗传算法的基本思想.......................................................................... （4）
4.2.2 遗传算法基本算子.............................................................................. （5）
4.2.3 交叉的数据结构.................................................................................. （8）
4.2.4 适应度量.............................................................................................. （8） 5 面向对象在排课系统中的应用........................................................................ （9）
5.1 定义班级类................................................................................................. （9）
5.2 定义教室类............................................................................................... （10）
5.3 定义教师类............................................................................................... （10）
5.4 定义课程类............................................................................................... （11）
5.5 设定配置文件........................................................................................... （11） 6 运行调试.......................................................................................................... （15） 参考文献.............................................................................................................. （17） 致谢...................................................................................................................... （18）
1 绪论
1.1 课题研究背景及意义
21世纪后，世界跨入了一个以高科技为产业支柱的知识经济时代。知识经济的出现，预示着人类社会正在进入一个以智力资源为主要依托的经济时代。高校作为高级人才培养的阵地，必将迎来新的挑战。作为传播科学知识的高等学校，只有了解和掌握了文化知识、的科学技术前沿，才能培养出合格的人才，也将在激烈的竞争洪流中立于不败之地。高等院校培养学生的主要途径就是教学。在教学活动中，有一系列的教学管理工作。其中，教学计划的实施则是一个重要环节。课表是高校实施教学计划的时间安排，它对维护教学秩序，保证教学质量具有相当重要的作用。 随着近几年各个高校的合并与扩招，我国的综合性大学和各个高校中在校的学生数量的大大增加，对于高校教务部门来说，排课工作是非常令人头痛的事，经常会出现课程排列冲突，比如：一个教师在同一时间上两门课，有两个教师同时去了一个教室上不同的课程，有些教师在特定时间不可以上课。如果没有很好地解决这些冲突，必然产生教学混乱等现象。可见，排课算法的正确性、高效性是非常关键的。
1.2 课题主要研究内容 由于排课问题是一个有约束的、多目标的、难解的组合优化问题，单纯采用数学算法或单一算法是很难解决排课的问题的。采用智能性和并行性的遗传算法对排课问题来进行求解，是求解该问题所有的方法中比较明智的选择。本文在相关的遗传算法和多目标优化理论的基础上，提出一个课表的随机生成和优化的算法，该算法能够较大程度地反映实际排课的情况并且尽量达到多个目标最优的目的。本论文的研究内容有：详细的介绍遗传算法的产生、发展及特点，遗传算法的基本思想和基本操作，模式定理以及扩展的模式定理，应用遗传算法的关键等。说明排课问题中的几大要素和常用约束条件，分析排课问题中求解的难点和目标，给出排课问题完整的数学描述，并且提出本文求解排课问题方案中的总体思路。对于一个实际问题的算例，利用上述随机生成方案的算法和基于遗传算法的排课优化算法来进行求解，并对一些中间值进行跟踪分析，从实验的角度论述该算法的可行性。
2 Microsoft visual C++ 6.0开发环境简介
Visual C++是一个功能强大的可视化软件开发工具。自1993年微软公司推出Visual C++1.0后，随着其新版本不断问世，Visual C++已经成为专业程序员进行软件开发首选的编译工具。
虽然微软公司推出了Visual C++7.0，但它的应用有很大的局限性，只适用于Windows 2000,Windows XP和Windows NT4.0。所以实际中，更多的是以Visual C++6.0
为平台。
Visual C++6.0不仅是一个C++编译器，而且是一个基于Windows系统的可视化集成开发环境。Visual C++6.0由许多的组件组成，包括编辑器、调试器及类向导Class Wizard、程序向导AppWizard等开发工具。 这些组件通过Developer Studio组件集成为和谐的开发环境。图2.1为操作窗口。
图2.1 VC操作窗口
3 排课系统的总体问题分析
3.1 高校排课问题概述
排课是高校教学管理当中十分重要却又相当复杂的一种管理工作，其实质就是给学校所设置的课程来安排时间和地点，使整个教学过程能有计划有秩序的来进行。编排课表是一个能够涉及到多种因素的组合规划问题，其要保证在课程安排中学生、教师、教室不能够产生冲突 (所谓的冲突，就是将需要上不同课程的两个或者多个班安排在同一时间段、同一教室，或者为同一个教师在同一时间安排多门课程等的情况)，并且还要满足教师的要求与资源限制等的约束条件。
目前，国内大部分中学仍然采用手工排课的方法。手工排课的主要手段是“摆牌”， 就是在一个空课表的版面上把有课名的牌摆在适当的课表的位置上，整个过程边摆边观察边调整，凭借摆牌的经验将各门课程摆在合理的位置上，最后才形成一个有效且
合理的课程表。这种手工的办法没有一定的规律，也没有理论指导，还没有数据模型，所以具有很大的盲目性。因此，要为众多的学生和众位教师安排出合理的课程表，则往往需要花费管理人员大量的时间，不仅工作量大，而且排出的课程表不宜调整。 近年来，随着中国教育体制改革不断的深入，学生人数不断上升，课程设置不断向着深度和广度发展，手工进行排课的缺点愈加突出。由于计算机运算速度快、处理能力强大，从而就很自然地进入到这一应用领域之中。用计算机来进行排课能够快速得到满足约束条件的合理结果，具有省人力、排课时间短和质量高等的优点，对于推动教育教学发展起到了非常重要的作用。
3.2 排课问题的硬性约束
3.2.1 课程问题分析
课程是由课程号来决定的，同一课程名称不一定就是同一课程，因为它们在教材采用以及教学要求上可能会有所不同。每门课程对教学资源以及教师都有一定的要求，比如英语听力课，可能就会要求教室安装语音装置。
3.2.2 班级问题分析
排课问题中将班级作为学习的一个排课要素，同一个班级指的是按照同一个教学计划进行学习的学生集合。
3.2.3 教师问题分析
一般情况下，同一个专业的某个课程会固定的由一个教师来进行授课，但是可能上某一门课程的班级较多，就可能由多名教师讲授同一门课程了。
3.2.4 教室问题分析
教室在排课问题中作为一个非常重要的教学资源来进行规划和分配，排课过程中就是把教室当作一个有限的空间分配给进行排课的对象。
3.2.5 时间问题分析
在学校的教学中，时间可以分为学年、学期、周、天。学校一般情况都会安排一个学期的课程表，而在课表上是以周来显示。时间在课程安排中也是当作一个有限的资源来分配给排课对象的。
3.3 排课问题的软性约束
除了上述的硬性约束，还有一些约束比如：某个教师希望或者不希望在某个时间段上课；体育课和自习课最好不要排在每天的第一二节课；同一门课程在一周内的分布尽可能的均匀等，这些要求称为软性约束，因为它们或者可以通过排课之外的方法，比如变更其他事务的日程安排来加以解决；或者只能尽可能的满足，而不可能全部都
满足。
4 遗传算法的设计
4.1 遗传算法概述
遗传算法是由John.H.Holland根据生物进化的模型提出的一种优化结果的算法，它是基于生物进化过程中的信息遗传的机制和自然选择中优胜劣汰的原则和搜索算法。该算法从一个种群开始，利用选择、交叉、变异等遗传算子来对种群进行不断的进化选择和淘汰，最后得到全局最优解或者近似最优解。根据其算法的特点，遗传算法非常适合于排课问题。
4.2 遗传算法分析
4.2.1 遗传算法的基本思想
遗传算法是从要解决的问题可能存在解集的一个种群(population)开始的，这个种群则是由经过基因(gene)和编码(coding)的一定数目的个体(individual)组成的。每个个体实际上就是染色体(chromosome)带有特征的实体。遗传物质的主要载体是染色体，即许多个基因的集合，其基因型就是某种基因的组合，它来决定个体的性状和外部表现。所以，开始时需要实现从表现型到基因型的映射也就是进行编码工作。第一代种群产生后，按照优胜劣汰的原理，逐代(generation)演化产生出越来越好的近似解。在每一代，根据问题域中每个个体的适应度(fitness)大小来挑选(selection)个体，并借助自然遗传学的遗传算子(genetic operators)来进行组合交叉(crossover)和变异(mutation)，产生出带有新的解集的种群。此过程将导致种群自然进化出一样的后代种群且比前代更加适应环境，末代种群的最优个体经过解码(decoding )后，可以用来作为问题的近似最优解。遗传算法利用自然进化模型，如选择、交叉、变异等。当计算开始，会随机的初始化一定数目的个体(Parent 1、Parent 2、Parent 3 , ...... ,Parent N)来形成初始的种群，并依次计算出各个个体的适应度函数，初始代(第一代)就产生了。如果没有满足优化的准则，就开始产生新一代的计算。为了继续产生下一代，按照适应度来选择个体，父代基因进行交叉(重组)从而产生子代。所有的子代按一定的概率发生变异，之后子代的适应度又会被重新计算，子代则被插入到种群中去代替父代，进而构成新的一代(children 1、children 2、children 3,„„)。以上所述过程循环执行，直到满足优化准则为止。
下面给出遗传算法的具体步骤，流程图参见图4.1：
第一步：选择编码的策略，把参数集合（可行解的集合）转换染色体结构空间； 第二步：定义适应度函数，便于计算适应值；
第三步：确定遗传策略，包括选择群体大小，选择、交叉、变异的方法以及确定交叉的概率、变异的概率等遗传参数；
第四步：随机产生初始化的群体；
第五步：计算群体中的个体或者染色体解码后的适应值；
第六步：按照遗传的策略，运用选择、交叉和变异算子作用于群体，形成下一代的群体；
第七步：判断群体性能是否能满足某一指标、或者是否已完成预定的迭代次数，不满足则返回第五步、或者修改遗传策略后再返回第六步。
图4.1 遗传算的流程图
4.2.2 遗传算法的基本算子
遗传算法包括三个基本的核心遗传算子：
1)选择算子
选择操作是从当前的种群中选择出较好的染色体个体，并且为个体交叉和变异的运算产生新的个体做好准备。随着候选的个体适应度的不断提高，被选中的概率也就随之变大，其后代在下一代中出现的数量也就相应增加，染色体在下一代中群众的分
布也就随之变广。
2)交叉算子
交叉又称为杂交或者交换。交叉操作利用部分匹配交叉法，要求选择两个随机的交叉点，用来确定一个匹配的段，在根据两个父个体中的两交叉点间的中间段所给出的映射关系来生成两个子代个体。这样的话，因为每个个体都是一个矩阵，先随机的选择某行，在依次的比较两个父个体在此行对应的每个元素。若两个父个体相对应的元素都有是0的情况，那么保持位置不变；若两个股个体相对应的元素都不为0（都含有课程对象），则在交换各自父个体中对应课程对象的位置。
这种交换方式能够避免班级和教师、教室之间的冲突，不会打乱班级元组的元素。 以下是交叉算子的程序段
// 利用染色体和指针返回给后代进行交叉操作
Schedule* Schedule::Crossover(const Schedule& parent2) const
{
//检查交叉操作的概率
if( rand() % 100 > _crossoverProbability ) //没有交叉，只是复制第一代 return new Schedule( *this, false ); //新的染色体对象，复制染色体的设置
Schedule* n = new Schedule( *this, true );
//班数 int size = (int)_classes.size(); vector cp( size ); //确定交叉点(随机) for( int i = _numberOfCrossoverPoints; i > 0; i-- ) { while( 1 ) { int p = rand() % size; if( !cp[ p ] ) { cp[ p ] = true;
}
}
}
hash_map::const_iterator it1 = _classes.begin(); hash_map::const_iterator it2 = parent2._classes.begin(); //通过结合父母代码的新代码
bool first = rand() % 2 == 0;
for( int i = 0; i
if( first ) {
//从第一个父代的染色体的类表插入新的类
n->_classes.insert( pair( ( *it1 ).first,
( *it1 ).second ) );
//复制类的所有时间空间插槽
} else { } //交叉点 if( cp[ i ] )
//改变原染色体 first = !first;
//插入第二个父类到新的染色体的类表
n->_classes.insert( pair( ( *it2 ).first,( *it2 ).second ) ); //复制类的所有时间空间插槽
for( int i = ( *it2 ).first->GetDuration() - 1; i >= 0; i-- )
n->_slots[ ( *it2 ).second + i ].push_back( ( *it2 ).first ); for( int i = ( *it1 ).first->GetDuration() - 1; i >= 0; i-- )
n->_slots[ ( *it1 ).second + i ].push_back( ( *it1 ).first );
}
}
it2++;
n->CalculateFitness(); //智能指针返回给后代 return n;
3)变异算子
变异操作的主要作用是来调整教师和班级时间的冲突。利用变异操作的局部随机搜索的能力，在运算结果接近最优解的时候，可以快速的向最优解收敛。虽然发生的概率比较小，但能够防止搜索得到的解陷入次优解中，能够保证种群的多样性。通过随机的变异还能确保生成不同的个体，进而能够使解在解空间中均匀的分布。 4.2.3 交叉的数据结构
两个class schedule杂交：将对应的两个hash map分成几部分(几部分需要定义参
数)，交替合成一个新的hash map，然后得到一个新的vector list.
图4.2交叉算子数据结构
4.2.4 适应度量
对一个课程编排，该编排中的每个课程班按下面规则赋值算法中的适应度量(Fitness)（取值范围0~7的整数）：
如果一个class用了一个满足class条件（起始到终止周内，隔周还是全周，等条件）
的空的room，则score (class):= score (class)+1;
如果一个class需要lab而安排的room是lab，或如果需要media而安排在有media的room，或class不需要lab和media，则score (class):= score (class)+1;
如果一个class被安排在一个座位充裕的room，则score (class):= score (class)+1; 如果一个class的professor此时刻没有别的class，则score (class):= score (class)+1; 如果一个class的group此时刻没有别的class，则score (class):= score (class)+1; 如果一个class在一个professor中意的section，则 score (class):= score (class)+1; 如果一个class在一个professor中意的学周，则 score (class):= score (class)+1; 其他情形：score(class)不变.
求和所有class的score: schedule_score=sum of score of all class
Fitness=schedule_score/(#classes*7) (fitness介于0和1之间float型，当=1时就找到满足所有条件的schedule)
5 面向对象在排课系统中的应用 5.1 定义班级类
class CourseClass; class StudentsGroup { private:
int _id;
//定义学生班ID //定义学生班名称 //定义学生数量 //类组出席列表
//存储学生组的数据
string _name;
int _numberOfStudents;
list _courseClasses;
public:
StudentsGroup(int id, const string& name, int numberOfStudents);
//初始化学生组数据
void AddClass(CourseClass* courseClass); inline int GetId() const { return _id; }
//绑定到类组 //返回学生班ID
inline const string& GetName() const { return _name; } //返回学生班名称 inline int GetNumberOfStudents() const { return _numberOfStudents; }
//返回学生班数量
inline const list& GetCourseClasses() const { return
// 返回类组出席列表参数
_courseClasses; }
inline bool operator ==(const StudentsGroup& rhs) const { return _id == rhs._id; }
// 比较代表学生团体的两个对象的编号
};
5.2 定义教室类
class Room { private:
static int _nextRoomId;
// ID计数器，用于自动分配的ID
private:
int _id;
// 房间编号 - 自动分配 // 教室名称 // 表明房间有电脑 // 教室座位数目
string _name; bool _lab;
int _numberOfSeats;
public:
Room(const string& name, bool lab, int numberOfSeats);
// 定义教室容量和教室ID
FALSE
inline int GetNumberOfSeats() const { return _numberOfSeats; }
// 返回教室
inline int GetId() const { return _id; }
// 返回教室 ID
// 返回教室名称
inline const string& GetName() const { return _name; } inline bool IsLab() const { return _lab; }
// 若有实验室返回TRUE，否则返回
的座位数
}; 5.3 定义教师类
class Professor { private:
int _id;
// 定义教授ID // 名字
static inline void RestartIDs() { _nextRoomId = 0; }
// 重置教室ID进行分配
string _name;
list _courseClasses; // 教授教的班列表
public:
Professor(int id, const string& name);
// 初始化教授数据
// 约束教授课程
void AddCourseClass(CourseClass* courseClass); inline int GetId() const { return _id; }
// 返回教授的ID
// 返回教授名字
inline const string& GetName() const { return _name; }
inline const list& GetCourseClasses() const { return
// 返回参考列出教授任教的班
_courseClasses; }
}; 5.4 定义课程类
inline bool operator ==(const Professor& rhs) const { return _id == rhs._id; }
// 比较两个代表教授ID的对象
class Course { private:
int _id;
// 课程ID //课程名
string _name;
public: };
5.5 设定配置文件
对象：
● 教师 (#prof tag) - 描述一位教授 ● 课程 (#course tag) - 介绍课程 ● 教室 (#room tag) - 描述一间教室
● 学生班 (#group tag) - 描述一个班的全体学生
● 课程班 (#class tag) - 描述一个课程班，约束它的授课教师，课程和学生班 对于每个对象，其开始以其自己的标签，结束以#end标记结束，每一个标签必须是在单独一行。在一个对象内，每一行只包含一个键和值对（属性）被一个“=”字符
Course(int id, const string& name); inline int GetId() const { return _id; }
//初始化过程 // 返回课程ID
// 返回课程名
inline const string& GetName() const { return _name; }
分隔开。每个属性应该指定一个时间，除了在#组对象中的组属性可以有多个。标签和键名能够识别大小写，这里是一个对象的属性列表：
1. #prof
◆ id (number, required) - 教授的ID ◆ .name (string, required) -教授名字 2. #course
◆ id (number, required) - 课程ID ◆ name (string, required) - 课程名 3. #room
◆ name (string, required) -教室名称 ◆ size (number, required) - 教室容纳人数
◆ lab (布尔变量, optional) - 表示，如果房间是一个实验室（有电脑），如果没有
指定，默认值是false。 4. #group
◆ id (number, required) - 学生班ID ◆ name (string, required) - 学生班名称 ◆ size (number, required) - 学生班人数 5. #class
◆ professor (number, required) - 教授ID；为一个班限定一个教授 ◆ course (number, required) - 课程ID; 为一个班限定一个课程
◆ group (number, required) - 学生班ID;约束学生班到一个课程班，每个课程班可
以绑定多个学生班
◆ duration (number, optional) - 上课时间（小时），如果没有指定，默认值是1。 ◆ lab (boolean, optional) - 是否这个课程班需要电脑;如果没有指定，默认值是
false。
下面给出各对象的变量列表
表5.1对象的变量列表
要注意，教授，学生组，课程对象必须定义之前，它们属于课程类对象。 配置文件举例：
#prof id = 1
name = 张少强
#end #prof id = 2
name = 孙德兵
#end #course id = 1
name = 高等数学
#end #course id = 2
name = 大学英语
#end #course id = 3
name = 信息导论
#end
#room name = 劝学A303 lab = true
size = 50
#end #room name = 劝学A213 lab = false
size = 60
#end #group id = 1
name = 计算机10-1 size = 19
#end #group id = 2
name = 计算机10-2 size = 19
#end #group id = 3
name = 计算机10-3 size = 19
#end #group id = 4
name = 计算机10-4 size = 19
#end #class
professor = 1 course = 1 duration = 2 group = 1 group = 2
#end #class
professor = 1 course = 1 duration = 2 group = 3 group = 4
#end #class
professor = 9 course = 1 duration = 3 group = 1 lab = true
#end #class
professor = 9 course = 1 duration = 3 group = 2 lab = true
#end 6 运行调试
如图6.1所示，是输入为17位教师，15门课程，六个班级，四间教室且容量分别为50，60各两间，通过遗传算法进行排课得出的最优结果的课程表。通过遗传算法进行优胜劣汰的选择到第2583代才得到最优解。
图6.1 运行结果
参考文献：
[1]黄海．基于遗传算法排课系统的设计与实现[J]．大众科技，2005，09：17-20．
[2]徐克圣，张素芳．一种基于遗传算法的自动排课系统设计[J]．计算机安全，2007，10：135-140．
[3]胡献华．基于遗传算法的自动排课问题的研究[D]．杭州：浙江工业大学，2004．
[4]江齐，兰竞．遗传算法在排课问题中的应用[J]．重庆大学学报（自然科学版），2005，11：79-85．
[5]陈本庆．遗传算法研究及其在排课问题中的应用[D]．成都：西南交通大学，2003．
[6]梁飞鸿．基于遗传算法的排课系统研究[J]．电脑与电信，2005，08：104-110．
[7] 唐勇，唐雪飞，王玲．基于遗传算法的排课系统[J]．计算机应用，2002，10：342-350．
[8]陆锋，李新．自动排课系统算法的设计与实现[J]．微机发展，2005，11：127-134．
[9]范玉玲．遗传算法在高校排课系统中应用的研究[D]．济南：山东师范大学，2004．
[10]赵光哲．基于遗传算法的大学排课问题的研究[D]．吉林：延边大学，2006．
17
致谢：
本人的学位论文是在我的指导教师张老师的亲切关怀和悉心指导下完成的。他严肃的科学态度，精益求精的工作作风，严谨的治学精神，深深地感染和激励着我。从课题的选择到设计和论文的最终完成，张老师都始终给予我不懈的支持和细心的指导。在此谨向张老师致以诚挚的谢意和崇高的敬意。
在此，我还要感谢在一起愉快的度过大学生活的可爱的同学们和尊敬的老师们，正是由于你们的帮助和支持，我才能克服一个一个的困难和疑惑，直至本文的顺利完成。在这里请接受我诚挚的谢意！谢谢你们！
18