毕业设计（论文）排课系统的遗传算法交叉算子实现

《毕业设计（论文）排课系统的遗传算法交叉算子实现》由会员分享，可在线阅读，更多相关《毕业设计（论文）排课系统的遗传算法交叉算子实现（23页珍藏版）》请在装配图网上搜索。

1、天 津 师 范 大 学本科毕业论文（设计）题目：排课系统的遗传算法交叉算子实现学 院：计算机与信息工程学院学生姓名： * * * 学 号： * 专 业： 计算机科学与技术 年 级： 指导教师： * 排课系统的遗传算法交叉算子实现摘要： 遗传算法，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位。所以本文以遗传算法为工具，对排课问题进行了深入的研究，设计了其中的交叉算子，在实际应用中有一定的意义。关键词：遗传算法；排课系统；交叉算子Implemen

2、tation of the Crossover of the Genetic Algorithm for Class Scheduling System Abstract:The genetic algorithm is the calculation model of genetic selection imitating Darwins natural selection of biological evolution process.Genetic algorithm as a new global optimization search algorithm, with its simp

3、le 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

4、 tool, design a crossover operator which has a certain 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 课程问题分析（

5、3）3.2.2 班级问题分析（3）3.2.3 教师问题分析（3）3.2.4 教室问题分析（3）3.2.5 时间问题分析（3）3.3 排课问题的软性约束（3）4 遗传算法的设计（7）4.1 遗传算法概述（4）4.2 遗传算法分析（4）4.2.1 遗传算法的基本思想（4）4.2.2 遗传算法基本算子（5）4.2.3 交叉的数据结构（8）4.2.4 适应度量（8）4.3 面向对象在排课系统中的应用（9）4.3.1 定义班级类（9）4.3.2 定义教室类（10）4.3.3 定义教师类（10）4.3.4 定义课程类（11）4.4 设定配置文件（12）5 运行调试（16）参考文献（18）致谢（19）19

6、1 绪论1.1 课题研究背景及意义21世纪后，世界跨入了一个以高科技为产业支柱的知识经济时代。知识经济的出现，预示着人类社会正在进入一个以智力资源为主要依托的经济时代。高校作为高级人才培养的阵地，必将迎来新的挑战。作为传播科学知识的高等学校，只有了解和掌握了文化知识、的科学技术前沿，才能培养出合格的人才，也将在激烈的竞争洪流中立于不败之地。高等院校培养学生的主要途径就是教学。在教学活动中，有一系列的教学管理工作。其中，教学计划的实施则是一个重要环节。课表是高校实施教学计划的时间安排，它对维护教学秩序，保证教学质量具有相当重要的作用。随着近几年各个高校的合并与扩招，我国的综合性大学和各个高校中在

7、校的学生数量的大大增加，对于高校教务部门来说，排课工作是非常令人头痛的事，经常会出现课程排列冲突，比如：一个教师在同一时间上两门课，有两个教师同时去了一个教室上不同的课程，有些教师在特定时间不可以上课。如果没有很好地解决这些冲突，必然产生教学混乱等现象。可见，排课算法的正确性、高效性是非常关键的。 1.2 课题主要研究内容由于排课问题是一个有约束的、多目标的、难解的组合优化问题，单纯采用数学算法或单一算法是很难解决排课的问题的。采用智能性和并行性的遗传算法对排课问题来进行求解，是求解该问题所有的方法中比较明智的选择。本文在相关的遗传算法和多目标优化理论的基础上，提出一个课表的随机生成和优化的算

8、法，该算法能够较大程度地反映实际排课的情况并且尽量达到多个目标最优的目的。本论文的研究内容有：详细的介绍遗传算法的产生、发展及特点，遗传算法的基本思想和基本操作，模式定理以及扩展的模式定理，应用遗传算法的关键等。说明排课问题中的几大要素和常用约束条件，分析排课问题中求解的难点和目标，给出排课问题完整的数学描述，并且提出本文求解排课问题方案中的总体思路。对于一个实际问题的算例，利用上述随机生成方案的算法和基于遗传算法的排课优化算法来进行求解，并对一些中间值进行跟踪分析，从实验的角度论述该算法的可行性。2 Microsoft visual C+ 6.0开发环境简介Visual C+是一个功能强大的

9、可视化软件开发工具。自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等开发工具。

10、这些组件通过Developer Studio组件集成为和谐的开发环境。下图1为操作窗口。图2.1 VC操作窗口3 排课系统的总体问题分析3.1 高校排课问题概述排课是高校教学管理当中十分重要却又相当复杂的一种管理工作，其实质就是给学校所设置的课程来安排时间和地点，使整个教学过程能有计划有秩序的来进行。编排课表是一个能够涉及到多种因素的组合规划问题，其要保证在课程安排中学生、教师、教室不能够产生冲突 (所谓的冲突，就是将需要上不同课程的两个或者多个班安排在同一时间段、同一教室，或者为同一个教师在同一时间安排多门课程等的情况)，并且还要满足教师的要求与资源限制等的约束条件。目前，国内大部分中学仍然

11、采用手工排课的方法。手工排课的主要手段是“摆牌”，就是在一个空课表的版面上把有课名的牌摆在适当的课表的位置上，整个过程边摆边观察边调整，凭借摆牌的经验将各门课程摆在合理的位置上，最后才形成一个有效且合理的课程表。这种手工的办法没有一定的规律，也没有理论指导，还没有数据模型，所以具有很大的盲目性。因此，要为众多的学生和众位教师安排出合理的课程表，则往往需要花费管理人员大量的时间，不仅工作量大，而且排出的课程表不宜调整。近年来，随着中国教育体制改革不断的深入，学生人数不断上升，课程设置不断向着深度和广度发展，手工进行排课的缺点愈加突出。由于计算机运算速度快、处理能力强大，从而就很自然地进入到这一应

12、用领域之中。用计算机来进行排课能够快速得到满足约束条件的合理结果，具有省人力、排课时间短和质量高等的优点，对于推动教育教学发展起到了非常重要的作用。3.2 排课问题的硬性约束3.2.1 课程问题分析课程是由课程号来决定的，同一课程名称不一定就是同一课程，因为它们在教材采用以及教学要求上可能会有所不同。每门课程对教学资源以及教师都有一定的要求，比如英语听力课，可能就会要求教室安装语音装置。3.2.2 班级问题分析排课问题中将班级作为学习的一个排课要素，同一个班级指的是按照同一个教学计划进行学习的学生集合。3.2.3 教师问题分析一般情况下，同一个专业的某个课程会固定的由一个教师来进行授课，但是可

13、能上某一门课程的班级较多，就可能由多名教师讲授同一门课程了。3.2.4 教室问题分析教室在排课问题中作为一个非常重要的教学资源来进行规划和分配，排课过程中就是把教室当作一个有限的空间分配给进行排课的对象。3.2.5 时间问题分析在学校的教学中，时间可以分为学年、学期、周、天。学校一般情况都会安排一个学期的课程表，而在课表上是以周来显示。时间在课程安排中也是当作一个有限的资源来分配给排课对象的。3.3 排课问题的软性约束除了上述的硬性约束，还有一些约束比如：某个教师希望或者不希望在某个时间段上课；体育课和自习课最好不要排在每天的第一二节课；同一门课程在一周内的分布尽可能的均匀等，这些要求称为软性

14、约束，因为它们或者可以通过排课之外的方法，比如变更其他事务的日程安排来加以解决；或者只能尽可能的满足，而不可能全部都满足。4 遗传算法的设计4.1 遗传算法概述遗传算法是由John.H.Holland根据生物进化的模型提出的一种优化结果的算法，它是基于生物进化过程中的信息遗传的机制和自然选择中优胜劣汰的原则和搜索算法。该算法从一个种群开始，利用选择、交叉、变异等遗传算子来对种群进行不断的进化选择和淘汰，最后得到全局最优解或者近似最优解。根据其算法的特点，遗传算法非常适合于排课问题。4.2 遗传算法分析4.2.1 遗传算法的基本思想遗传算法是从要解决的问题可能存在解集的一个种群(populati

15、on)开始的，这个种群则是由经过基因(gene)和编码(coding)的一定数目的个体(individual)组成的。每个个体实际上就是染色体(chromosome)带有特征的实体。遗传物质的主要载体是染色体，即许多个基因的集合，其基因型就是某种基因的组合，它来决定个体的性状和外部表现。所以，开始时需要实现从表现型到基因型的映射也就是进行编码工作。第一代种群产生后，按照优胜劣汰的原理，逐代(generation)演化产生出越来越好的近似解。在每一代，根据问题域中每个个体的适应度(fitness)大小来挑选(selection)个体，并借助自然遗传学的遗传算子(genetic operators

16、)来进行组合交叉(crossover)和变异(mutation)，产生出带有新的解集的种群。此过程将导致种群自然进化出一样的后代种群且比前代更加适应环境，末代种群的最优个体经过解码(decoding )后，可以用来作为问题的近似最优解。遗传算法利用自然进化模型，如选择、交叉、变异等。当计算开始，会随机的初始化一定数目的个体(Parent 1、Parent 2、Parent 3 , . ,Parent N)来形成初始的种群，并依次计算出各个个体的适应度函数，初始代(第一代)就产生了。如果没有满足优化的准则，就开始产生新一代的计算。为了继续产生下一代，按照适应度来选择个体，父代基因进行交叉(重组)

17、从而产生子代。所有的子代按一定的概率发生变异，之后子代的适应度又会被重新计算，子代则被插入到种群中去代替父代，进而构成新的一代(children 1、children 2、children 3,)。以上所述过程循环执行，直到满足优化准则为止。下面给出遗传算法的具体步骤，流程图参见图2：第一步：选择编码的策略，把参数集合（可行解的集合）转换染色体结构空间；第二步：定义适应度函数，便于计算适应值；第三步：确定遗传策略，包括选择群体大小，选择、交叉、变异的方法以及确定交叉的概率、变异的概率等遗传参数；第四步：随机产生初始化的群体；第五步：计算群体中的个体或者染色体解码后的适应值；第六步：按照遗传的策

18、略，运用选择、交叉和变异算子作用于群体，形成下一代的群体；第七步：判断群体性能是否能满足某一指标、或者是否已完成预定的迭代次数，不满足则返回第五步、或者修改遗传策略后再返回第六步。图4.1 遗传算的流程图4.2.2 遗传算法的基本算子遗传算法包括三个基本的核心遗传算子：1) 选择算子选择操作是从当前的种群中选择出较好的染色体个体，并且为个体交叉和变异的运算产生新的个体做好准备。随着候选的个体适应度的不断提高，被选中的概率也就随之变大，其后代在下一代中出现的数量也就相应增加，染色体在下一代中群众的分布也就随之变广。2) 交叉算子交叉又称为杂交或者交换。交叉操作利用部分匹配交叉法，要求选择两个随机

19、的交叉点，用来确定一个匹配的段，在根据两个父个体中的两交叉点间的中间段所给出的映射关系来生成两个子代个体。这样的话，因为每个个体都是一个矩阵，先随机的选择某行，在依次的比较两个父个体在此行对应的每个元素。若两个父个体相对应的元素都有是0的情况，那么保持位置不变；若两个股个体相对应的元素都不为0（都含有课程对象），则在交换各自父个体中对应课程对象的位置。这种交换方式能够避免班级和教师、教室之间的冲突，不会打乱班级元组的元素。以下是交叉算子的程序段/ 利用染色体和指针返回给后代进行交叉操作Schedule* Schedule:Crossover(const Schedule& parent2) c

20、onst/检查交叉操作的概率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() %

21、size;if( !cp p )cp p = true;break;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 _classes.insert( pair( ( *it1 ).first, ( *it1 ).second ) );/复制类的所有时间空间插槽for( int i = ( *it1 ).first-GetDu

22、ration() - 1; i = 0; i- )n-_slots ( *it1 ).second + i .push_back( ( *it1 ).first );else/插入第二个父类到新的染色体的类表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 );/交叉点if(

23、 cp i )/改变原染色体first = !first;it1+;it2+;n-CalculateFitness();/智能指针返回给后代return n;3) 变异算子变异操作的主要作用是来调整教师和班级时间的冲突。利用变异操作的局部随机搜索的能力，在运算结果接近最优解的时候，可以快速的向最优解收敛。虽然发生的概率比较小，但能够防止搜索得到的解陷入次优解中，能够保证种群的多样性。通过随机的变异还能确保生成不同的个体，进而能够使解在解空间中均匀的分布。4.2.3 交叉的数据结构两个class schedule杂交：将对应的两个hash map分成几部分(几部分需要定义参数)，交替合成一个新的

24、hash map，然后得到一个新的vector list.图4.24.2.4 适应度量对一个课程编排，该编排中的每个课程班按下面规则赋值算法中的适应度量(Fitness)（取值范围07的整数）：如果一个class用了一个满足class条件（起始到终止周内，隔周还是全周，等条件）的空的room，则score (class):= score (class)+1;如果一个class需要lab而安排的room是lab，或如果需要media而安排在有media的room，或class不需要lab和media，则score (class):= score (class)+1;如果一个class被安排在一个

25、座位充裕的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;其他情形

26、：score(class)不变.求和所有class的score: schedule_score=sum of score of all classFitness=schedule_score/(#classes*7) (fitness介于0和1之间float型，当=1时就找到满足所有条件的schedule)4.3 面向对象在排课系统中的应用4.3.1 定义班级类class CourseClass;/存储学生组的数据class StudentsGroupprivate:/定义学生班IDint _id;/定义学生班名称string _name;/定义学生数量int _numberOfStudent

27、s;/类组出席列表list _courseClasses;public:/初始化学生组数据StudentsGroup(int id, const string& name, int numberOfStudents);/绑定到类组void AddClass(CourseClass* courseClass);/返回学生班IDinline int GetId() const return _id; /返回学生班名称inline const string& GetName() const return _name; /返回学生班数量inline int GetNumberOfStudents()

28、const return _numberOfStudents; / 返回类组出席列表参数inline const list& GetCourseClasses() const return _courseClasses; / 比较代表学生团体的两个对象的编号inline bool operator =(const StudentsGroup& rhs) const return _id = rhs._id; ;4.3.2 定义教室类 class Roomprivate:/ ID计数器，用于自动分配的IDstatic int _nextRoomId;private:/ 房间编号 - 自动分配in

29、t _id;/ 教室名称string _name;/ 表明房间有电脑bool _lab;/ 教室座位数目int _numberOfSeats;public:4.3.3 定义教师类 class Professorprivate:/ 定义教授IDint _id;/ 名字string _name;/ 教授教的班列表list _courseClasses;public:/ 初始化教授数据Professor(int id, const string& name);/ 约束教授课程void AddCourseClass(CourseClass* courseClass);/ 返回教授的IDinline i

30、nt GetId() const return _id; / 返回教授名字inline const string& GetName() const return _name; / 返回参考列出教授任教的班inline const list& GetCourseClasses() const return _courseClasses; / 比较两个代表教授ID的对象inline bool operator =(const Professor& rhs) const return _id = rhs._id; ;4.3.4 定义课程类 class Courseprivate:/ 课程IDint

31、_id;/课程名string _name;public:/初始化过程Course(int id, const string& name);/ 返回课程IDinline int GetId() const return _id; / 返回课程名inline const string& GetName() const return _name; ;4.4 设定配置文件对象：l 教师 (#prof tag) - 描述一位教授l 课程 (#course tag) - 介绍课程l 教室 (#room tag) - 描述一间教室l 学生班 (#group tag) - 描述一个班的全体学生l 课程班 (#

32、class tag) - 描述一个课程班，约束它的授课教师，课程和学生班对于每个对象，其开始以其自己的标签，结束以#end标记结束，每一个标签必须是在单独一行。在一个对象内，每一行只包含一个键和值对（属性）被一个“=”字符分隔开。每个属性应该指定一个时间，除了在#组对象中的组属性可以有多个。标签和键名能够识别大小写，这里是一个对象的属性列表：1.#profu id (number, required) - 教授的IDu .name (string, required) -教授名字2.#courseu id (number, required) - 课程IDu name (string, req

33、uired) - 课程名3.#roomu name (string, required) -教室名称u size (number, required) - 教室容纳人数u lab (布尔变量, optional) - 表示，如果房间是一个实验室（有电脑），如果没有指定，默认值是false。u 4.#groupu id (number, required) - 学生班IDu name (string, required) - 学生班名称u size (number, required) - 学生班人数5.#classu professor (number, required) - 教授ID；为一

34、个班限定一个教授u course (number, required) - 课程ID; 为一个班限定一个课程u group (number, required) - 学生班ID;约束学生班到一个课程班，每个课程班可以绑定多个学生班u duration (number, optional) - 上课时间（小时），如果没有指定，默认值是1。u lab (boolean, optional) - 是否这个课程班需要电脑;如果没有指定，默认值是false。下面给出各对象的变量列表表4.1：对象的变量列表对象标签#tag变量1变量2变量3变量4变量5教师#profProf IDProf Name课程#c

35、ourseCourse IDCourse Name教室#roomRoom NameRoom SizeLab学生班#groupGroup IDGroup NameGroup Size课程班#classProf IDCourse IDGroup ID课程时长Lab要注意，教授，学生组，课程对象必须定义之前，它们属于课程类对象。配置文件举例：#profid = 1name = 张少强#end#profid = 2name = 孙德兵#end#courseid = 1name = 高等数学#end#courseid = 2name = 大学英语#end#courseid = 3name = 信息导论#

36、end#roomname = 劝学A303lab = truesize = 50#end#roomname = 劝学A213lab = falsesize = 60#end#groupid = 1name = 计算机10-1size = 19#end#groupid = 2name = 计算机10-2size = 19#end#groupid = 3name = 计算机10-3size = 19#end#groupid = 4name = 计算机10-4size = 19#end#classprofessor = 1course = 1duration = 2group = 1group =

37、2#end#classprofessor = 1course = 1duration = 2group = 3group = 4#end#classprofessor = 9course = 1duration = 3group = 1lab = true#end#classprofessor = 9course = 1duration = 3group = 2lab = true#end5 运行调试如图所示，是输入为17位教师，15门课程，六个班级，四间教室且容量分别为50，60各两间，通过遗传算法进行排课得出的最优结果的课程表。通过遗传算法进行优胜劣汰的选择到第2583代才得到最优解。图5

38、.1 运行结果参考文献： 1黄海基于遗传算法排课系统的设计与实现J大众科技，2005，09 2徐克圣，张素芳一种基于遗传算法的自动排课系统设计J计算机安全，2007，10 3胡献华基于遗传算法的自动排课问题的研究D杭州：浙江工业大学，2004 4江齐，兰竞遗传算法在排课问题中的应用J重庆大学学报（自然科学版），2005，11 5陈本庆遗传算法研究及其在排课问题中的应用D成都：西南交通大学，2003 6梁飞鸿基于遗传算法的排课系统研究J电脑与电信，2005，08 7 唐勇，唐雪飞，王玲基于遗传算法的排课系统J计算机应用，2002，10 8陆锋，李新自动排课系统算法的设计与实现J微机发展，2005

39、，11 9范玉玲遗传算法在高校排课系统中应用的研究D济南：山东师范大学，2004 10赵光哲基于遗传算法的大学排课问题的研究D吉林：延边大学，2006致谢：本人的学位论文是在我的指导教师张老师的亲切关怀和悉心指导下完成的。他严肃的科学态度，精益求精的工作作风，严谨的治学精神，深深地感染和激励着我。从课题的选择到设计和论文的最终完成，张老师都始终给予我不懈的支持和细心的指导。在此谨向张老师致以诚挚的谢意和崇高的敬意。在此，我还要感谢在一起愉快的度过大学生活的可爱的同学们和尊敬的老师们，正是由于你们的帮助和支持，我才能克服一个一个的困难和疑惑，直至本文的顺利完成。在这里请接受我诚挚的谢意！谢谢你们！