知识卡片
平均冲突数衡量排课间隔
“平均冲突数”按每名考生两门考试之间隔了几个时段来罚分,间隔越近罚得越重:
| 两门考试的间隔 | 相邻 | 隔 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 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 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。