什么专业研究生上遗传算法课 根据遗传算法的中职排课体系规划与完成

王涛

摘 要：文章从排课体系研讨现状动身，剖析了影响排课问题的要素、条件与求解方针，选用依据遗传算法处理排课问题的结构，并规划了依据遗传算法的排课体系。

要害词：遗传算法；中等工作校园；排课体系

中图分类号：G640 文献标识码：A 文章编号：1002-4107（2015）11-0066-02

一、排课体系研讨布景

在校园日常教育办理中十分重要，而又适当杂乱的作业就是排课，其本质就是为校园的每一门课程及与其对应的教师组织时刻和地址，从而使校园的日常教育作业能够有秩序地进行。

编列课程表是混合许多要素的规划标题，要确保教师、学生、教室三者之间没有抵触，并且要考虑教师的实践需求及资源的限制等条件。

排课问题现已被证明是NP完全问题[1]，是许多学者研讨的热门，研讨者首要运用理论研讨、启发式查找、专家体系求解等办法来处理这个问题。近年来最多的是运用遗传算法来求解这个问题。

教育排课功率低满足度低是校园教务人员最头痛的问题，其最大的困难是硬件条件的限制。教务人员很难在一起统筹硬件资源与软件资源的状况下快速编列任课教师、学生都满足的课表。

“穷举法”将一切的出路摆出，然后找到最佳的处理方案，但造价高，耗时长。如某一周有n个时刻段可组织课时，有m个教师需求排课，这些教师每个星期要上i堂课，假如运用穷举法咱们就能够得出一共有nm*i种组合成果，可见穷举法太繁复，不适合实践运用。

遗传算法是一种经过模仿天然进化进程查找最优解的办法[2]。本文企图以遗传算法来完成排课问题的最佳解。

本课题研讨的意图就是完成依据遗传算法的排课体系，满足日常教育需求。

二、遗传算法在排课体系中的运用

（一）排课问题描绘

在排课问题中将各种要素有序地组织在一周的时刻内且不发作抵触是咱们的首要任务，这些要素包括班级、教室、课程、教师、时刻。据此，咱们给出如下描绘。

校园有J间教室，B个班，K门课程，L位教师，S个时刻段。

1.教室表述为J（J1，J2，…，Jn）调集，不同教室包容的人数为（X1，X2…Xr）。

2.班级表述为B（B1，B2，…，Bn）调集，不同班级的人数为（K1，K2，…Kc）。

3.课程表述为K（K1，K2，…，Kn）调集，每门课对应Bi个班，1位教师，（1≤Bi

4.教师表述为L（L1，L2，…，Ln）调集，每位教师对应Km门课，Cn个班（1≤Km

5.时刻表述为S（S1，S2，…，Sn）调集，一般状况下一周有五天上课，依据工作高中的实践状况每天为6节课，即上午4节，下午2节，则时刻调集包括30个时刻段。例如11代表周一第一节课，12代表周一的第二节课，21代表周二的第一节课，按此推导，这些课节构成一个时刻调集P（11，12，13，…，56）。

（二）束缚条件

1.一张正确的课表应至少满足以下硬束缚条件。

（1）某一个教师、班级、教室在同一个时刻节点内不能组织两门课程。

（2）教室有必要容下上课的学生数，即Kc≤Xr。

2.硬性束缚是有必要满足的，不然教育无法正常进行

下去，但在实践教育傍边为了使教育效果更好还应当有些软束缚。这些条件在特别状况下也能够不满足，这些软束缚条件可能是：

（1）把重要理论课程组织在上午进行，把着手课程组织在下午进行，这样契合学生的注意力规则。

（2）在满足学生上课时刻要求的状况下尽可能满足教师对课程时刻的要求。

（3）一门课要在一周的几个涣散的时刻段进行，就是说每周三课时的课不能组织在一天上完，也不能组织在相邻的三天上完，要使学生有时刻预习消化，教师有时刻备课修改。

（4）教师每天的课不能太多，不然影响教育效果。

（5）同第（4）条，学生上课时刻不能一天是满课，一天又没有课的状况。

这些软性条件关于不同校园是不同的，笔者在这里列出的这些软性束缚条件首要是针对中等工作校园的实践教育需求，在笔者的排课体系中，仅仅给咱们界说的束缚条件给出一个处理方案，假如有其他的要求就需求别的考虑[3]。

三、遗传算法剖析

（一）遗传算法的循环进程

遗传算法的演算进程是模仿染色体穿插变异，生物进化筛选的进程。

（1）随机发作必定数意图初始种群。

（2）点评个别习惯度状况，假如个别契合习惯度条

件，则个别代表的解能够运用，输出成果完毕核算，不然转向下一步。

（3）依据习惯度挑选再生个别。

（4）依照必定的穿插概率和穿插办法生成新的个别。

（5）依照必定的变异概率和变异办法生成新的个别。

（6）由（4）和（5）发作新的种群，在判别习惯度。如图1所示。

图1 遗传算法示意图

以下是遗传算法的伪代码。

BEGIN：

I = 0；

Initialize P（I）；

Fitness P（I）；

While（not Terminate-Condition）

{I + +：GA-Operation P（I）；Fitness P（I）；}END.

（二）染色体编码

在排课体系的完成进程中首先要处理的是将实践的课表变成虚拟的编码，就是如何将课表转化为染色体，使它能够进行遗传操作。在前人的办法中，常将染色体规划成浮点数或二进制编码，在实践中，将每个教师的课表规划成一个独自的染色体，结构如下面表述。

教师ID班级ID课程ID教室上课时刻组织。

在本规划中染色体用十进制数来编码，例如：某一位教师编号为1234，要上“工作生涯规划”这门课，这门课的编号为7025，周学时为3，班级为01201、01202，上课时刻是随机发作的，教室要挑选大于两班总人数的，以此编码生成的染色体为：“12340120101202702502204

213451”其间02204代表上课教室，213451代表上课时刻是周二第一节、周三第四节、周五第一节。

运用上面的编码方法，对染色体的后11位进行穿插操作，这样教师课程受影响，教师课表内含其他教师课程的状况都不会发作，也使得演化后的染色体编码愈加合理。不过发作排课课表的好坏还需求习惯度函数进行判别。

作业中习惯度值就是课程编列人员对课表的希望。因而，把这些希望转化为具体数值就显得很重要，它是完成智能化的要害。

依照排课体系的要求，个别习惯度点评函数的规划是一种奖惩并存的机制[4]。具体来说就是咱们规划了奖赏机制，比方教师在某个时刻段上课比较便利，假如刚好有这么一个解，那么咱们就奖赏这个个别，该个别习惯度值即加大了。相反赏罚（减去一个权值）的状况有，假如个别中有存在不满足硬束缚的条件，那么就对该个别进行赏罚。有些解是咱们不需求的，为了能够优先进化更好的解，因而它的习惯度值需求下降。比方说在同一时刻某个教师被组织了两门不一样的课在一个个别中，这就违反了硬束缚条件；归纳上述对排课多方针的剖析，则选用以下习惯度的函数：

fitness_value+reward_value-conflict_penalty_value=fitness

其间，reward_value表明奖赏值，偏好设置依据教师偏好时刻设置来指定分别为很满足（奖赏+20）、还能够（奖赏+10）、没有定见（奖赏+0）、不满足（奖赏-10）、十分不满足（奖赏-20）；fitness_value表明习惯度的根底值，它是一个习惯度函数的初始值，引进此值是为防止全体习惯度值为负在依据奖惩形式状况下：Conflict_penalty_value代表抵触赏罚值，包括了任课教师与时刻的抵触，教室和时刻的抵触还有班级和时刻的抵触，在相关类中该值的设定现已被指定。在主动排好的课表中如其间的组织契合教师的喜爱，并是教师事前设定好那么就直接对相应的成果进行奖赏相应的值，就是说成果习惯度值的凹凸，取决于教师是否满足。以此类推不契合教师希望的教师不满足，它的习惯度值天然就低。假如在程序中呈现班级在同一时刻上多门课的状况、教师同一时刻上多门课的状况、教室同一时刻多班级运用的状况、教室类型与课程需求不契合的状况，这些都需求设定相应的赏罚值，在习惯度上减去相应的值。确保这样的成果不会呈现在生成的课表上。

排课体系的规划运用了前台界面操作与后台数据库处理相结合的方法。使得日常的办理操作和数据库中数据的存储相区别开来，使得两者不会发作过错的搅扰，增加了各个用户的独立性。这样的结构给软件的开发和保护带来了便利。

因为本体系尚在完善阶段，存有瑕疵，如在安全功能方面，在线同享方面等。这也鼓励笔者在往后的学习作业中要逐渐地完善提高。排课体系为确保以优质的课表供师生运用，仍需严厉的测验。

参考文献：

[1]吴金荣.解课程表问题的分支定界算法[D].北京：我国

科学院数学与体系科学研讨院，2002.

[2]胡顺仁，邓毅，王铮.依据高校排课体系中的图论问题研

究[J].核算机工程与运用，2002，（4）.

[3]刘继清，陈传波.模仿退火算法在排课中的运用[J].武

汉船只工作技术学院学报，2003，（6）.

[4]李增智，王云岚，陈靖.课程表问题的一种混合型模仿退

火算法[J].西安交通大学学报，2003，（4）.