Python实现基于遗传算法的排课优化

Python015

Python实现基于遗传算法的排课优化,第1张

排课问题的本质是将课程、教师和学生在合适的时间段内分配到合适的教室中，涉及到的因素较多，是一个多目标的调度问题，在运筹学中被称为时间表问题（Timetable Problem，TTP）。设一个星期有n个时段可排课，有m位教师需要参与排课，平均每位教师一个星期上k节课，在不考虑其他限制的情况下，能够推出的可能组合就有 种，如此高的复杂度是目前计算机所无法承受的。因此众多研究者提出了多种其他排课算法，如模拟退火，列表寻优搜索和约束满意等。

Github ： https://github.com/xiaochus/GeneticClassSchedule

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法的流程如下所示：

遗传算法首先针对待解决问题随机生成一组解，我们称之为种群（Population）。种群中的每个个体都是问题的解，在优化的过程中，算法会计算整个种群的成本函数，从而得到一个与种群相关的适应度的序列。如下图所示：

为了得到新的下一代种群，首先根据适应度对种群进行排序，从中挑选出最优的几个个体加入下一代种群，这一个过程也被称为精英选拔。新种群余下的部分通过对选拔出来的精英个体进行修改得到。

对种群进行修改的方法参考了生物DAN进化的方法，一般使用两种方法： 变异 和 交叉 。 变异 的做法是对种群做一个微小的、随机的改变。如果解的编码方式是二进制，那么就随机选取一个位置进行0和1的互相突变；如果解的编码方式是十进制，那么就随机选取一个位置进行随机加减。 交叉 的做法是随机从最优种群中选取两个个体，以某个位置为交叉点合成一个新的个体。

经过突变和交叉后我们得到新的种群（大小与上一代种群一致），对新种群重复重复上述过程，直到达到迭代次数（失败）或者解的适应性达到我们的要求（成功），GA算法就结束了。

算法实现

首先定义一个课程类，这个类包含了课程、班级、教师、教室、星期、时间几个属性，其中前三个是我们自定义的，后面三个是需要算法来优化的。

接下来定义cost函数，这个函数用来计算课表种群的冲突。当被测试课表冲突为0的时候，这个课表就是个符合规定的课表。冲突检测遵循下面几条规则：

使用遗传算法进行优化的过程如下，与上一节的流程图过程相同。

init_population ：随机初始化不同的种群。

mutate ：变异操作，随机对 Schedule 对象中的某个可改变属性在允许范围内进行随机加减。

crossover ：交叉操作，随机对两个对象交换不同位置的属性。

evolution ：启动GA算法进行优化。

实验结果

下面定义了3个班，6种课程、教师和3个教室来对排课效果进行测试。

优化结果如下，迭代到第68次时，课程安排不存在任何冲突。

选择1203班的课表进行可视化，如下所示，算法合理的安排了对应的课程。

制作分布图类似密度图，在python中利用pandas来提取分布数据是比较方便的。主要用到pandas的cut和groupby等函数。

官方文档链接

主要参数为x和bins。

x为数据源，数组格式的都支持，list，numpy.narray, pandas.Series。

bins可以为int，也可以为序列。

我们定义bins为一个序列，默认为左开右闭的区间：

对言值列按cats做groupby，然后调用get_stats统计函数，再用unstack函数将层次化的行索引“展开”为列。

G2在之前的文章中有介绍，文章 《python结合G2绘制精美图形》 。

一句话绘制出来，但具体的区间段难以区分出来。

bokeh是python的一个优秀的绘图工具包，与pandas结合的比较好。 bokeh文档

作者原文链接： python制作分布图

正常正规中考，考场及考号由机器派分，这个考场有来自各个班级的学生还有可能有其他学校的学生。考试的座位图，是在考试前几分钟才能确定的考试座位，一般每个考场的座位图也不同，每科考完都换新的座位图。通常教室分配学生30人，分四排，靠最前门为1号，后门是7号，旁边的是8号，再往前依次排位。每排7、8、7、8人，呈S型，最后一位是30号。那么11号就应该在第二排的第四行，如下图所示