知识卡片

普通读书笔记卡 · 1295.i.1.f.1

平均冲突数衡量排课间隔

理解等级:高级

“平均冲突数”按每名考生两门考试之间隔了几个时段来罚分,间隔越近罚得越重:

两门考试的间隔 相邻 隔 1 个时段 隔 2 个 隔 3 个 隔 4 个 隔 5 个及以上
罚分 W 16 8 4 2 1 0

式(1-4)把罚分汇总成平均值:f = Σ(W_s × N_s) / S。其中 W_s 是第 s 档罚分,N_s 是落在该档的考生人数,S 是考生总数;f 越小,考试分布越均匀。

示例(补充演算):3 名考生,甲两门考试相邻(16),乙隔 2 个时段(4),丙隔 6 个时段(0),则 f = (16 + 4 + 0) / 3 ≈ 6.7。

它改进的是式(1-1):式(1-1)只统计“连续参加两门考试”的人数,隔 1 个时段和隔 10 个时段在它看来没有区别;平均冲突数按间隔递减罚分,能区分这些可行时间表的松紧。

使用时要注意原书的不一致:式(1-2)把式(1-1)的相邻冲突数设为必须等于 0 的硬约束,而新目标又要求“依然满足式(1-2)”。照此理解,相邻那一档(W = 16)永远不会出现,式(1-1)作为目标也恒为 0。应按题设确认相邻考试是被禁止还是只被罚分,不宜把两式直接照抄为同一模型。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 1 . 3 . 1 基 于 遗 传 算 法 的 T T P 问 题 · 查看原书依据

      该方法作用于每个学生,其规则为,对每个需要参加考试的学生,若连续参加两门考试,则对他设定一个惩罚值,该值表示为W=16;若中间间隔一个时间段,则惩罚值为W=8;若中间间隔两个时间段,则惩罚值为W=4;若中间间隔3个时间段,则惩罚值为W=2;若中间间隔4个时间段,则惩罚值为W=1;其余的大于4个时间段间隔的惩罚值都为0。

    参考来源

    - 位置:《智能算法导论》第 1 章 1.3.1 节“数学模型”(`EPUB/xhtml/chapter1_0007.xhtml`);图式 `image_005.svg` 至 `image_008.svg`。 - 结论依据:原文给出 16、8、4、2、1 惩罚和平均冲突数式(1-4),同时式(1-2)把相邻冲突总数设为 0(已对照 `image_005.svg`、`image_006.svg`:两式的求和项相同)。3 名考生的演算为依据原书定义补充的教学示例,非书中数据。 - 原始内容:若连续参加两门考试,则对他设定一个惩罚值,该值表示为 W =16;若中间间隔一个时间段,则惩罚值为 W =8。