cover_image

基于遗传算法实现排课算法

希沃魔方后端团队 好奇de悟空
2024年04月11日 02:08

背景

实施走班制教学会造成教学班与行政班交错的情况, 课表的安排更加复杂, 对教学资源的需求会增加, 课表编排的约束条件也更加苛刻, 这种情况下实施走班制教学困难重重. 单纯手动排课不仅费时费力, 而且不能保证遵循所有的约束条件, 排出的课表难以满足教师和学生的需求. 课表安排是否合理, 对学校教学质量有着较大的影响, 因此需要一种高效智能的排课方法来求解走班制度下的排课问题.

近些年的解决方案有遗传算法 (Genetic Algorithm, GA)、模拟退火算法、蚁群算法、禁忌搜索算法以及混合算法等, 本文介绍一种基于遗传算法的排课实现方式.

遗传算法介绍

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型, 是一种通过模拟自然进化过程搜索最优解的方法.通过模拟自然界中选择、交叉、变异等遗传进化现象, 采用概率化的寻优方法, 不需要确定的规则就能自动获取和指导优化的搜索空间, 自适应地调整搜索方向.

遗传算法过程图解

图片

生物学相关术语

为了更好的理解遗传算法, 需要先了解一些生物学相关术语, 只需理解即可:

  • 基因型(genotype)：性状染色体的内部表现.

  • 表现型(phenotype)：染色体决定的性状的外部表现，或者说，根据基因型形成的个体的外部表现.

  • 进化(evolution)：种群逐渐适应生存环境，品质不断得到改良。生物的进化是以种群的形式进行的.

  • 适应度(fitness)：度量某个物种对于生存环境的适应程度.

  • 选择(selection)：以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程.

  • 复制(reproduction)：细胞分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因.

  • 交叉(crossover)：两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交,

  • 变异(mutation)：复制时可能（很小的概率）产生某些复制差错，变异产生新的染色体，表现出新的性状.

  • 编码(coding)：DNA中遗传信息在一个长链上按一定的模式排列,遗传编码可看作从表现型到基因型的映射.

  • 解码(decoding)：基因型到表现型的映射.

  • 个体（individual）：指染色体带有特征的实体.

  • 种群（population）：个体的集合，该集合内个体数称为种群.


基因编码

编码是应用遗传算法时要解决的首要问题, 也是设计遗传算法时的一个关键步骤. 编码方法影响到交叉算子、变异算子等遗传算子的运算方法, 很大程度上决定了遗传进化的效率.

目前主流的共有三种编码方式: 二进制编码法、浮点编码法、符号编码法.

二进制编码

类似人有AGCT四种碱基序列一样, 计算机中的编码也可以用01两种碱基进行编码形成一条染色体, 一条足够长的二进制染色体就能表示个体的所有特征, 如:

图片

二进制编码的优点: 编码、解码操作简单易行且交叉、变异等遗传操作便于实现.

二进制编码的缺点: 对于一些连续函数的优化问题, 由于其随机性使得其局部搜索能力较差, 对于一些高精度的问题, 当解迫近于最优解后, 由于其变异后表现型变化很大, 可能会远离最优解.

浮点编码


二进制编码虽然简单明了, 但是对于高精度问题的求解可能达不到要求, 提升编码长度虽然能够提升精度, 但是也会加大解码的难度.

所谓浮点编码, 就是将基因的每个特征用一定范围内的浮点数表示, 对应的交叉、遗传等操作算子的计算结果也必须保证计算后的基因特征值不能超过这个浮点数的范围. 如:

图片

浮点数编码方法有下面几个优点:

  • 适用于在遗传算法中表示范围较大的数

  • 适用于精度要求较高的遗传算法

  • 便于较大空间的遗传搜索

  • 改善了遗传算法的计算复杂性，提高了运算交率

  • 便于遗传算法与经典优化方法的混合使用

  • 便于设计针对问题的专门知识的知识型遗传算子

  • 便于处理复杂的决策变量约束条件


符号编码

符号编码法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集如｛A,B,C…｝

符号编码的主要优点是:

  • 符合有意义积术块编码原则

  • 便于在遗传算法中利用所求解问题的专门知识

  • 便于遗传算法与相关近似算法之间的混合使用



适应度函数

适应度函数也称评价函数, 是根据目标函数确定的用于区分群体中个体好坏的标准. 适应度函数总是非负的, 而目标函数可能有正有负, 故需要在目标函数与适应度函数之间进行变换.

评价个体适应度的一般过程为:
  1. 对个体编码串进行解码处理后, 可得到个体的表现型;
  2. 由个体的表现型可计算出对应个体的目标函数值;
  3. 根据最优化问题的类型, 由目标函数值按一定的转换规则求出个体的适应度;


选择函数

遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取那些个体, 以便遗传到下一代群体. 在自然界中, 越强大的个体越有可能获得繁衍的机会, 并将自己的优良基因遗传到下一代, 但这并不意味着弱势的个体就没有丝毫机会. 在遗传算法中, 同样也要模拟这种概率关系.

常用的几种选择算子如下:

1. 轮盘赌选择: 这是一种回放式随机采样方法. 每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值和的比例. 选择误差比较大;
2. 随机竞争选择: 每次按轮盘赌选择一对个体, 然后让这两个个体进行竞争, 适应度高的被选中, 如此反复, 直到选满为止;
3. 最佳保留选择: 首先按轮盘赌选择方法执行遗传算法的选择操作, 然后将当前群体中适应度最高的个体结构完整地复制到下一代群体中, 即保留精英个体;

图片

如上图所示, 适应度越高的个体, 在轮盘中所占的面积越大, 相应的被选中的概率也就越大, 但同时适应度低的个体也有被选中的可能.


染色体交叉

遗传算法的交叉操作, 是指对两个相互配对的染色体按某种方式相互交换其部分基因, 从而形成两个新的个体.
交叉就是将两个染色体进行基因片段的交叉, 以二进制编码个体的交叉过程为例, 交叉的过程如下图所示:

图片


染色体变异

遗传算法中的变异运算, 是指将个体染色体编码串中的某些基因座上的基因值用该基因座上的其它等位基因来替换, 从而形成新的个体. 对于二进制编码, 只需要将随机一个基因位置进行取反操作, 如:

图片

染色体变异的方式有很多种, 如:

  • 基本位变异: 对个体编码串中以变异概率、随机指定的某一位或某几位基因上的值做变异运算
  • 均匀变异: 分别用符合某一范围内均匀分布的随机数, 以某一较小的概率来替换个体编码串中各个基因上的原有基因值
  • 边界变异: 随机的取基因座上的两个对应边界基因值之一去替代原有基因值
  • 非均匀变异: 对原有的基因值做一随机扰动, 以扰动后的结果作为变异后的新基因值. 对每个基因座都以相同的概率进行变异运算之后, 相当于整个解向量在解空间中作了一次轻微的变动


袋鼠蹦跳

假设现在发生了世界末日, 海水发生倒灌, 生活在珠穆朗玛峰附近的袋鼠（初始化一个袋鼠种群）遇到了生存危机, 只有不断向山顶蹦跳的袋鼠才能幸存下来.

袋鼠能否跳到更高的山体受到很多因素的影响, 如腿部肌肉更发达的袋鼠比不发达的有更大的可能跳到更高的山体, 皮毛更厚的袋鼠抗寒性更好, 能够在更高的山体存活下来, 也更有机会向上跳一跳....但无论是哪种因素, 最终的结果是袋鼠会被分布在不同高度的山体上, 袋鼠的位置就是其基因的表现型, 在模拟过程中, 只需对袋鼠的位置进行编码即可.

我们用能否跳到更高山体来评判袋鼠的适应度, 由于我们只需要考虑袋鼠的位置（基因编码的时候位置是袋鼠优良特征的表现形式）, 因此适应度函数也会比较简单, 只需输入袋鼠的位置, 换算成袋鼠的山体海拔即可. 适应度低的袋鼠很容易就被倒灌的海水给淹死淘汰了.

幸存下来的袋鼠就可以获得繁衍的权利, 有可能将自己的优良基因传承下来, 使得下一代有更大的可能跳到更高的山头.

袋鼠种群在进化的过程中, 可能会发生基因突变, 如原本皮毛都很薄的父母产生的下一代突变后, 皮毛会变得更厚（也有可能变得更薄）.

在经过N次种群迭代后, 最终有部分袋鼠成功跳到了珠穆朗玛峰顶, 得以幸存繁衍.


问题实例

图片


区间内函数图像如下所示:

图片

接下来通过遗传算法来解决上述问题, 首先先回顾一下遗传算法的过程:

‍

图片

1. 初始化种群

private List<Individual> initPopulation(int populationSize, int features, int acuration, double pm) {    List<Individual> population = Lists.newArrayList();
    for (int i = 0; i < populationSize; i++) {        population.add(new Individual(features, acuration, pm));    }
    return population;}
public Individual(int features, int acuration, double pm) {    Random random = new Random();
    // 初始化个体DNA    this.DNA_FEATURES = features;    this.DNA_FEATURE_LENGTH = acuration;    this.DNA_LENGTH = acuration * features;    this.PM = pm;    this.DNA = initDNA(features, acuration);
    // 初始化个体适应度    this.fitness = fitness();}
private int[][] initDNA(int features, int accuration) {    int[][] dna = new int[features][accuration];    for (int i = 0; i < features; i++) {        for (int j = 0; j < accuration; j++) {            dna[i][j] = RANDOM.nextInt(2);        }    }    return dna;}

初始化种群的时候遵循随机的原则, 每一个个体的基因都是随机生成的, 这样每一个个体都随机的分布在坐标轴的各个位置.

2. 选择&交叉

选择、交叉是遗传算法中非常重要的步骤, 通过这一步, 种群才能完成一次次的进化.
选择算法采用轮盘赌, 交叉采用随机定点交叉.
private Individual select(List<Individual> population) {    // 种群个体被选中的概率    double[] rates = new double[population.size()];
    // 个体适应度之和    double sum = population.stream().mapToDouble(Individual::getFitness).sum();    for (int i = 0; i < population.size(); i++) {        double rate = population.get(i).getFitness() / sum;
        rates[i] = i == 0 ? rate : rates[i - 1] + rate;    }
    double randomRate = new Random().nextDouble();    for (int i = 0; i < population.size(); i++) {        if (randomRate <= rates[i]) {            return population.get(i);        }    }
    // impossible    return null;}

public Individual across(Individual individual, int crossPoint) {    Individual child = new Individual(DNA_FEATURES, DNA_FEATURE_LENGTH, PM);
    // 交叉    for (int p = 0; p < crossPoint; p++) {        int i = p / DNA_FEATURE_LENGTH;        int j = p % DNA_FEATURE_LENGTH;        child.DNA[i][j] = this.DNA[i][j];    }
    for (int p = crossPoint; p < DNA_LENGTH; p++) {        int i = p / DNA_FEATURE_LENGTH;        int j = p % DNA_FEATURE_LENGTH;        child.DNA[i][j] = individual.DNA[i][j];    }
    // 重新计算适应度    child.fitness = child.fitness();
    return child;}

3. 基因变异

在进化过程中, 种群的各个个体都有一定的概率（比较小）发生基因突变, 基因突变有助于遗传算法跳出局部最优解.

public void mutation() {    int point = RANDOM.nextInt(DNA_LENGTH);
    for (int p = point; p < DNA_LENGTH; p++) {        int i = p / DNA_FEATURE_LENGTH;        int j = p % DNA_FEATURE_LENGTH;
        this.DNA[i][j] = this.DNA[i][j] == 0 ? 1 : 0;    }}


如此反复N次后, 种群中的个体就会集中到最优解附近.

public void start(int populationSize, int features, int acuration, int maxGeneraion) {    List<Individual> population = initPopulation(populationSize, features, acuration, PM);    System.out.println("----------种群初始化完成----------");
    for (int i = 1; i <= maxGeneraion; i++) {        // 新种群        List<Individual> newPopulation = Lists.newArrayList();
        for (int j = 0; j < populationSize; j++) {            // 随机交叉概率            double pc = new Random().nextDouble();            Individual father = select(population);            Individual mother = select(population);
            if (pc < this.PC) {                Individual child = cross(father, mother);                // 随机变异概率                double pm = new Random().nextDouble();                if (pm < PM) {                    child.mutation();                }                newPopulation.add(child);            }        }
        // 新种群替代旧种群        population = newPopulation;    }}

4. 适应度函数

遗传算法需要通过适应度函数判断个体的优劣程度,遗传算法中种群个体分布变化如下所示:

图片

走班排课的基本问题

排课问题属于调度问题的研究范畴, 其核心任务是将课程、班级、教师、教室资源不冲突地安排在各个授课时间段, 并保证其能够满足教务老师事先设定好的各种约束条件, 且使结果达到最优或者近似最优.

排课问题的数学模型描述为,  课程集合 ：

图片

班级集合：

图片

教师集合：

图片

教室集合：

图片

时间段集合：

图片

在排课前, 需要设置每个课程的开课计划, 每个课程每周上课的课时, 确定课程、班级、教师、教室的关系, 即某个老师的课程在某个班级的某个教室上课, 寻找满足约束的授课时间进行匹配, 并确保教学资源之间相互不冲突, 此即为排课问题的求解过程, 他们组成一个授课集合 ：

图片

其中：

图片

约束条件

课表安排时不仅要考虑课表各元素在时间、空间上是否合理, 还需要考虑是否满足教务老师设定 的一些约束条件, 在保证课表不冲突的基础上尽量安排合理, 使教学资源得到最优化组合配置, 并 保证教学工作能够正常进行. 约束条件可分为硬约束条件和软约束条件.

硬约束条件指在排课过程中所必须遵循的条件, 课表只有契合硬约束条件才能保证排课资源不 会冲突, 具体如下:

1.同一个班级在同一个授课时段至多只能安排 1 门课程, 即：

图片

2.同一个教室在同一个授课时段至多只能安排一门课程, 即：

图片

3.同一位教师在同一个授课时段至多只能安排一门课程, 即：

图片


软约束条件指教务老师在排课前设置的一些规则，排课过程中并非必须符合这些规则，但这些规则会对排课的合理性和用户的满意度产生较大影响, 课表在多大程度上符合这些规则会影响到课表的优 劣程度. 如:
1. 同一门课程每周的课时安排尽量分散
2. 早读、晚自习应排在第一节和最后一节
3. 教师倾向于上午、下午上课
4. 上午有限安排主课
5. ......

算法设计

遗传算法是一种通过模拟自然界中生物进化的过程来随机全局寻优的一种算法. 遗传算法克服了传统搜索算法不适用于解决非线性复杂问题的缺点, 具有搜索能力强和运用范围广的特点 , 可用于求解组合优化问题, 应用在排课问题上也有着不错的效果.

基因编码

以教师编号、课程编号、班级编号、教室编号和授课时段构成 1 个元组作为遗传算法的基因, 每个基因可看作班级课表中的 1 个课表单元, 基因结构如下图所示:

图片

例如基因编码`1001-2001-3001-4001-0101`, 表示周一第一节课, 编号为`1001`的老师在编号为`4001`的教室给编号为`3001`的班级上编号为`2001`的课程. 在K12场景中, 教师、课程、班级、教室都是确定好的, 因此只需要关注授课时间的安排即可. 基因编码代码表示如下:

// 教师public record Teacher(String teacherId, String teacherName) {}
// 教室public record Room(String roomId, String roomName) {}
// 班级public record Clazz(String clazzId, String clazzName, Room room) {}
// 课程public record Course(String courseName, Teacher teacher, Clazz clazz) {}


初始化种群

遗传算法以初始种群作为迭代的起点, 为了保证种群的多样性, 采用完全随机的方案生成初始种群中的个体, 并且不考虑课表中资源是否冲突.

根据学校所有课程的开课计划`CoursePlan`和作息表`TimetablePlan`生成对应的基因, 由于每个基因表示课表中的一个单元格, 这里用课节`Lesson`表示. 所有的基因构成一个个体`Individual`, 每个个体都是一个完整的课表.

种群初始化流程如下图所示:

图片

适应度函数


在遗传算法中, 适应度是描述个体 (课表) 优劣性的重要指标. 在算法迭代过程中将根据个体适应度大小进行优胜劣汰. 考虑到课表的特殊性, 适应度函数针对违反硬约束条件和软约束条件的课表执行不同程度的惩罚措施.

此处软约束条件以课程安排是否均匀以及是否满足早读、晚自习是否分别在第一节课和最后一节课进行考虑.

1.课程安排均匀度是衡量课程在 1 周中的上课时段中分布的均匀度, bc表示. 每一 门课程应当尽量均匀地分布在 1 周内, 避免某一门课程过于集中地安排在 1 周的某段时间. 课程安排均匀度bc的计算公式如下:

图片

其中, D表示课程每周需要上课的天数,Pi表示当天该课程安排的课时数,p'表示该课程每天的标准课时数，则据此可以求出该课表的课程安排均匀度：

图片

其中, C表示所有的课程总数.f1越大, 表示课程分布越均匀.

2.有些特殊的课程, 如早读、晚自习等, 会安排在每天的第一节课和最后一节课, 属于老师对课程安排的特殊需求, 不满足不影响排课的正确性, 但是会对排课的体验带来影响. 用Sc表示这类特殊课程的满意度, 计算公式如下:

图片

其中, D表示课程每周需要上课的天数,Pi表示当天该课程满足特殊要求的次数则, 据此可以求出该课表的课程满意程度:

图片

3.惩罚度是判断课表是否违反了硬约束条件和软约束条件, 若违反则降低适应度, 违反次数越多则适应度降低越多. 此处用 β 表示惩罚度, 其相应公式为:

图片

其中, α1和α2为惩罚因子，α1 < 1,α2 < 1,且α1 < α2 (优先消除硬约束冲突). hard_vios违反硬约束条件的次数,soft_vios为违反软约束条件的次数.α1 和 α2的取值对进化效果有不可忽视的影响, 取值过小时会使适应度跃升较大进而导致其他因素对整体适应度的影响过小, 取值过大则对适应度值的惩罚过小.

综上, 排课算法的适应度函数的公式为：

图片

其中, w1和w2为权值，且w1 + w2 = 1.

选择算子

选择操作模拟了自然界中优胜劣汰、适者生存的现象. 算法选取一部分个体来产生下一代中的个体, 其余个体则被淘汰.

操作算子的设计结合了最佳保留策略和轮盘赌算法, 为避免每一代中的最优个体在后面的遗传 操作中被破坏, 首先将其复制到下一代中, 然后再使用轮盘赌算法对其余个体进行选择. 适应度越高 的个体, 其基因遗传到下一代的概率越大.

使用轮盘赌算法, 个体被选中的概率为个体自身的适应度在种群中所有个体的适应度之和的占 比, 与个体适应度大小的值成正比. 个体被选中的概率的计算公式为：

图片


其中, f(xi)为每个个体的适应度, N为种群规模. 选择算子代码表示如下:

private Individual select(List<Individual> individuals) {    double[] rates = new double[individuals.size()];    double sum = individuals.stream().mapToDouble(Individual::getFitness).sum();
    for (int i = 0; i < individuals.size(); i++) {        double rate = individuals.get(i).getFitness() / sum;        rates[i] = i == 0 ? rate : rates[i - 1] + rate;    }
    double randomRate = new Random().nextDouble();    for (int i = 0; i < individuals.size(); i++) {        if (randomRate <= rates[i]) {            return individuals.get(i);        }    }
    // impossible    return null;}

交叉算子

交叉操作是指 2 个个体按照一定的交叉概率互相交换部分基因, 从而产生新个体的过程. 交叉操作在遗传算法中起着极其重要的作用, 是算法执行过程中产生新个体最主要的方法. 交叉操作对提升算法的全局搜索能力起着关键作用.

为了避免优良基因在交叉中被破坏, 因此会保留下种群中的精英个体.
List<Individual> newPopulation = population.stream()        .sorted((a, b) -> Double.compare(b.getFitness(), a.getFitness()))        .limit(elitismCount)        .collect(Collectors.toList());
// 交叉for (int j = elitismCount; j < populationSize; j++) {    if (Math.random() < crossoverRate) {        Individual individual1 = select(population);        Individual individual2 = select(population);        assert individual1 != null;        assert individual2 != null;
        newPopulation.add(individual1.crossover(individual2));    } else {        newPopulation.add(select(population));    }}

变异算子

变异操作模拟了自然界物种进化过程中的基因突变, 依据较小的变异概率将染色体中的一些基因替换成其他基因, 从而产生 1 个新个体. 变异操作是遗传算法执行过程中产生新个体的辅助方法, 它提高了算法的局部搜索能力, 同时能够保证种群多样性.

在排课的场景中, 课程、老师、班级这三者是固定的关系, 能够变动的是上课的场地、时间（节次和周次）, 因此变异的位置也只能出现在这三个位置中, 在算法实现上, 会随机对这三个位置坐变异处理.
public void mutate(TimetablePlan timetablePlan, List<Room> rooms) {    for (Lesson lesson : lessons) {        // 在时间、位置三个基因中随机变异        int pos = RANDOM.nextInt(0, 3);        if (pos == 0) {            lesson.room = lesson.basedOnClassRoom ? lesson.course.clazz().room() : rooms.get(RANDOM.nextInt(rooms.size()));        } else if (pos == 1) {            lesson.dayIndex = RANDOM.nextInt(1, timetablePlan.getWeekDayCount() + 1);        } else if (pos == 2) {            lesson.sectionIndex = RANDOM.nextInt(1, timetablePlan.getDayLessonCount() + 1);        }    }
    fit();}


实例验证

算法运行结果如下:

第0代最优个体适应度：0.25，课程冲突数：4第1代最优个体适应度：0.25，课程冲突数：4第2代最优个体适应度：0.25，课程冲突数：4第3代最优个体适应度：0.25，课程冲突数：4第4代最优个体适应度：0.25，课程冲突数：4第5代最优个体适应度：0.25，课程冲突数：4第6代最优个体适应度：0.25，课程冲突数：4第7代最优个体适应度：0.25，课程冲突数：4第8代最优个体适应度：0.25，课程冲突数：4第9代最优个体适应度：0.25，课程冲突数：4第10代最优个体适应度：0.25，课程冲突数：4第11代最优个体适应度：0.25，课程冲突数：4第12代最优个体适应度：0.25，课程冲突数：4第13代最优个体适应度：0.25，课程冲突数：4第14代最优个体适应度：0.25，课程冲突数：4第15代最优个体适应度：0.25，课程冲突数：4第16代最优个体适应度：0.25，课程冲突数：4第17代最优个体适应度：0.25，课程冲突数：4第18代最优个体适应度：0.25，课程冲突数：4第19代最优个体适应度：0.25，课程冲突数：4第20代最优个体适应度：0.25，课程冲突数：4第21代最优个体适应度：0.25，课程冲突数：4第22代最优个体适应度：0.25，课程冲突数：4第23代最优个体适应度：0.25，课程冲突数：4第24代最优个体适应度：0.25，课程冲突数：4第25代最优个体适应度：0.25，课程冲突数：4第26代最优个体适应度：0.25，课程冲突数：4第27代最优个体适应度：0.25，课程冲突数：4第28代最优个体适应度：0.25，课程冲突数：4第29代最优个体适应度：0.25，课程冲突数：4第30代最优个体适应度：1.0，课程冲突数：0

可见, 在经过几轮迭代后, 最终得到冲突数量为0可做使用的排课计划.

精品文章8
精品文章 · 目录
上一篇流媒体-传输延时计算（SEI插帧）
继续滑动看下一个
好奇de悟空
向上滑动看下一个