下载文档原格式
基于遗传算法的高校智能排课系统作者：夏小云高武军来源：《电脑知识与技术·学术交流》2008年第28期摘要：新形势高校的发展，高校教务管理中的排课问题显得更为复杂。
排课问题是一个典型的组合优化和不确定性调度问题，也是一个完全问题。
该文根据高校实际情况，从遗传算法的基本理论着手，研究如何利用遗传算法解决高校排课中的资源冲突、课表优化等问题，并引用了哈希表和时间粒度的概念，对传统遗传算法染色体的编码模式进行了有益修正，增强了模式的灵活性。
实验证明，遗传算法能够简化程序的复杂度和减少生成最佳课表的时间。
达到了较高的师生满意度。
关键词：排课；遗传算法；哈希图；时间粒度；适应度函数中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)28-0175-03The Making Class Schedule System of High School Based on Genetic AlgorithmsXIA Xiao-yun1, GAO Wu-jun2(1.Faculty of Information Engineering,Jiangxi University of Science and Technology, Ganzhou 341000, China;2.Faculty of Science, Jiangxi University of Science and Technology, Ganzhou 341000, China)Abstract: As the ongoing development in the higher education institutions, the class arrangement model in the management system is also becoming more and more complicated. Course Scheduling is a typical portfolio optimization and uncertainty of scheduling problems, but also a complete problem. Based on the actual situation in high school. In addition, on the basis of GA basic theory, studies how to utilize GA to solve the conflict problem that aroused in schedule arranging system and improve schedule arrangement. We quoted a hash table and time granules, and amend the traditional genetic algorithm chromosome coding models, enhance the flexibility of the model. The practice has proved that GA can simplify the program complexity and shorten the time in generating new perfect schedule. And the curriculum schedule induced by the time code meet the satisfaction of students and teaching staff exactly.Key words: making class schedule; genetic algorithms; hash map; time granules; fitness function1 引言随着高校规模的扩大，学生人数也逐渐增加，高效教务部门排课问题也变得越来越复杂。
基本遗传算法【精品毕业设计】（完整版）遗传算法1、遗传算法⽣物学基础和基本理论达尔⽂⾃然选择学说认为，⽣物要⽣存下去，就必须进⾏⽣存⽃争。
⽣存⽃争包括种内⽃争、种间⽃争以及⽣物跟⽆机环境之间的⽃争三个⽅⾯。
在⽣存⽃争中，具有有利变异(mutation)的个体容易存活下来，并且有更多的机会将有利变异传给后代;具有不利变异的个体就容易被淘汰，产⽣后代的机会也少得多。
因此，凡是在⽣存⽃争中获胜的个体都是对环境适应性⽐较强的。
达尔⽂把这种在⽣存⽃争中适者⽣存，不适者淘汰的过程叫做⾃然选择。
达尔⽂的⾃然选择学说表明，遗传和变异是决定⽣物进化的内在因素。
遗传是指⽗代与⼦代之间，在性状上存在的相似现象。
变异是指⽗代与⼦代之间，以及⼦代的个体之间，在性状上或多或少地存在的差异现象。
在⽣物体内，遗传和变异的关系⼗分密切。
⼀个⽣物体的遗传性状往往会发⽣变异，⽽变异的性状有的可以遗传。
遗传能使⽣物的性状不断地传送给后代，因此保持了物种的特性，变异能够使⽣物的性状发⽣改变，从⽽适应新的环境⽽不断地向前发展。
⽣物的各项⽣命活动都有它的物质基础，⽣物的遗传与变异也是这样。
根据现代细胞学和遗传学的研究得知，遗传物质的主要载体是染⾊体(chromsome),染⾊体主要是由DNA(脱氧核糖核酸)和蛋⽩质组成，其中DNA⼜是最主要的遗传物质。
现代分⼦⽔平的遗传学的研究⼜进⼀步证明，基因(gene)是有遗传效应的⽚段，它储存着遗传信息，可以准确地复制，也能够发⽣突变，并可通过控制蛋⽩质的合成⽽控制⽣物的性状。
⽣物体⾃⾝通过对基因的复制(reproduction)和交叉(crossover)，即基因分离、基因⾃由组合和基因连锁互换)的操作使其性状的遗传得到选择和控制。
同时，通过基因重组、基因变异和染⾊体在结构和数⽬上的变异产⽣丰富多采的变异现象。
需要指出的是，根据达尔⽂进化论，多种多样的⽣物之所以能够适应环境⽽得以⽣存进化，是和上述的遗传和变异⽣命现象分不开的。
基于遗传算法的高校网上排课系统引言随着高校规模的不断扩大，学生的日益增多，教学任务的繁重性、复杂性也日益增加。
而传统的手工排课方法效率低下，产生的错误率高，往往需要大量的人力、物力来保证排课的质量。
因此，建立一种高效、优化的高校网上排课系统，能够大大提高排课效率，降低人力和物力成本，同时也能提高排课的准确性和灵活性。
本文基于遗传算法设计了一种高校网上排课系统，该系统利用遗传算法对排课过程进行优化，避免人工排课的低效性和错误性。
系统需求分析1. 系统功能（1）对每个教学班级的课程安排进行合理分配。
（2）合理分配教师的时间和地点，保证每位教师的授课任务得以顺利完成。
（3）将实验室、讲授教室等教学场所进行合理规划，以充分满足教学任务的需求。
（4）根据教学安排，进一步生成教学进度表和考试安排表。
2. 用户需求（1）学生：能够根据自己的学习计划方便地查看本学期的课程表和考试安排表。
（2）教师：能够根据自己的授课计划方便地查看所需上课的时间和地点。
（3）管理员：能够方便地进行教学班级信息的管理，包括教学班级的添加、修改和删除等。
系统设计1. 数据库设计系统通过关系型数据库进行存储，设计如下。
教室表包含了教室的编号、名称、容纳人数、类型等信息。
课程表包含了课程的编号、名称、学分、学时等信息。
教师表包含了教师的编号、名称、职称、任职时间等信息。
班级表包含了班级的编号、名称、人数、开班时间等信息。
课程安排表包含了教学班级和课程、教师以及时间和地点等信息。
2. 模块设计系统包括了登录模块、班级管理模块、课程管理模块、教师管理模块、教室管理模块、排课模块、课程表模块、考试安排模块等模块，模块之间可以相互跳转，方便用户在系统中进行操作。
3. 排课算法设计系统采用遗传算法对排课过程进行优化。
我们知道，遗传算法是一种模拟进化过程的算法，通过模拟不断进化的过程，逐步优化初始解。
具体的实现过程如下：（1）首先，生成足够的随机课程安排表，作为种群。
自然计算大作业一．二进制编码在遗传算法中，首先要将数据进行编码，这里采用二进制的方式进行编码。
第一步，我们根据题目的介绍可以得知该函数含有两个变量，以及各自的定义域。
在二进制编码中，我们首先要先计算它的编码长度。
计算公式如下: $${2^{{m_j} - 1}} < ({b_j} - {a_j})*precision \le {2^{{m_j}}} - 1$$其中precision为精度，如小数点后5位，则precision=10^5，mj为编码长度，${x_j} \in [{a_j},{b_j}]$二．二进制解码解码即编码的逆过程:$${x_j} = {a_j} + {\rm{decimal}}(substrin{g_j}) \times \frac{{{b_j} - {a_j}}}{{{2^{{m_j}}} - 1}}$$三．种群初始化编码完成后，开始对种群初始化，为了简便采用随机地方式进行初始化。
初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。
GA以这N个串结构数据作为初始点开始进化。
def rand_init(self):for i in range(self.code_x1_length):self.code_x1 += str(random.randint(0, 1))for i in range(self.code_x2_length):self.code_x2 += str(random.randint(0, 1))四．适应度评估适应度表明个体或解的优劣性。
不同的问题，适应度函数的定义方式也不同。
def decoding(self, code_x1, code_x2):self.x1 = self.bounds[0][0] + int(code_x1, 2) * (self.bounds[0][1] - self.bounds[0][0]) / (2 ** self.code_x1_length - 1)self.x2 = self.bounds[1][0] + int(code_x2, 2) * (self.bounds[1][1] - self.bounds[1][0]) / (2 ** self.code_x2_length - 1)五．选择选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。
