排课问题的本质是将课程、教师和学生在合适的时间段内分配到合适的教室中，涉及到的因素较多，是一个多目标的调度问题，在运筹学中被称为时间表问题（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班的课表进行可视化，如下所示，算法合理的安排了对应的课程。
遗传算法（GA）是最早由美国Holland教授提出的一种基于自然界的“适者生存，优胜劣汰”基本法则的智能搜索算法。遗传算法也是借鉴该基本法则，通过基于种群的思想，将问题的解通过编码的方式转化为种群中的个体，并让这些个体不断地通过选择、交叉和变异算子模拟生物的进化过程，然后利用“优胜劣汰”法则选择种群中适应性较强的个体构成子种群，然后让子种群重复类似的进化过程，直到找到问题的最优解或者到达一定的进化（运算）时间。
在很多实际工程问题中，我们的优化目标不止一个，而是对多个目标函数求一个综合最优解。例如在物流配送问题中，不仅要求配送路径最短，还可能需要参与运输车辆最少等。
多目标优化问题的数学模型可以表达为：
多目标优化问题通常具有如下特点：
对于多目标优化问题，传统方法是将原问题通过加权方式变换为单目标优化问题，进而求得最优解。该方法具有两大问题：
遗传算法具有多点多方向搜索的特征，在一次搜索中可以得到多个Pareto最优解，因此更适合求解多目标优化问题。
而当前用于求解多目标优化问题的遗传算法一般有两种思路：
NSGA-II(nondominated sorting genetic algorithm II)是2002年Deb教授提出的NSGA的改进型，这个算法主要解决了第一版NSGA的三个痛点：
针对这三个问题，在NSGA-II中，Deb提出了快速非支配排序算子，引入了保存精英策略，并用“拥挤距离”(crowding distance)替代了共享(sharing)。
在介绍NSGA-II的整体流程之前，我们需要先了解快速非支配排序和拥挤距离的定义。
解的支配关系与Pareto最优解
下图表示了解之间的支配和强支配关系：
下图表示了一个最小化问题解集中的Pareto最优解和Pareto弱最优解：
快速非支配排序步骤
快速非支配排序就是将解集分解为不同次序的Pareto前沿的过程。
它可以描述为：
DEAP实现
DEAP内置了实现快速非支配排序操作的函数 tools.emo.sortNondominated
tools.emo.sortNondominated(individuals, k, first_front_only=False)
参数：
返回：
拥挤距离的定义
在NSGA II中，为了衡量在同一个前沿中各个解质量的优劣，作者为每个解分配了一个拥挤距离。其背后的思想是 让求得的Pareto最优解在objective space中尽量分散 。也就有更大可能让解在Pareto最优前沿上均匀分布。
DEAP实现
DEAP中内置了计算拥挤距离的函数 tools.emo.assignCrowdingDist
tools.emo.assignCrowdingDist(individuals)
参数：
返回：
比较操作
根据快速非支配排序和拥挤距离计算的结果，对族群中的个体进行排序：
对两个解 ，
在每个迭代步的最后，将父代与子代合为一个族群，依照比较操作对合并后族群中的个体进行排序，然后从中选取数量等同于父代规模的优秀子代，这就是NSGA-II算法中的精英保存策略。
DEAP实现
DEAP内置了实现NSGA-II中的基于拥挤度的选择函数 tools.selNSGA2 用来实现精英保存策略：
tools.selNSGA2(individuals, k, nd='standard')
参数：
返回：
这里选用ZDT3函数作为测试函数，函数可表达为：
其Pareto最优解集为
这里为了方便可视化取 。
下图给出了该函数在Decision Space和Objective Space中的对应：
其pareto最优解在Objective Space中如下图红点所示：
将结果可视化：
得到：
可以看到NSGA-II算法得到的Pareto最优前沿质量很高：最优解均匀分布在不连续前沿的各个线段上；同时在最优前沿以外没有个体存在。
