1. 项目概述：当课程表遇上伊辛机
每到选课季，看着教务系统里密密麻麻的课程列表，你是不是也感到头疼？必修、选修、专业限选，每个类别都有学分要求；课程时间不能冲突，还得兼顾老师的口碑和课程的“性价比”；最好能把课都集中在几天，留出完整的空闲时间来做项目、实习或者干脆“躺平”。这看似简单的个人选择，其实是一个典型的组合优化问题：从成百上千门课程中，挑出一个子集，既要满足硬性的学分约束，又要让时间安排和课程质量达到某种意义上的“最优”。手动排列组合？随着课程数量增加，可能的方案数量会爆炸式增长，这早已超出了人脑甚至普通计算机能轻松处理的范围。
传统的解决方法，比如用整数规划软件或者自己写个启发式搜索算法（例如模拟退火），在面对大规模选课数据时，往往力不从心，要么算得慢，要么找不到好解。近年来，一种名为伊辛机的专用计算硬件进入了人们的视野。它不像我们熟悉的CPU那样一条条执行指令，而是将优化问题映射成一个物理模型——伊辛模型，然后让这个物理系统自然演化到能量最低的“基态”，这个状态对应的就是问题的最优或近似最优解。听起来很物理对不对？但它的应用却非常“接地气”。本文将带你深入拆解一项前沿研究：如何利用伊辛机和其对应的QUBO模型，来高效解决这个让无数大学生“头秃”的个性化课程选择问题。
2. 核心原理：从磁铁相变到组合优化
2.1 伊辛模型：物理世界的优化大师
伊辛模型最初是物理学家为理解铁磁体相变而提出的一个简化模型。想象一个二维的棋盘格子，每个格点上有一个可以朝上或朝下的小磁针（称为“自旋”）。相邻磁针之间倾向于方向一致（以降低相互作用能），同时外部磁场会试图让所有磁针朝向某个特定方向。整个系统的总能量，就由每个磁针自身的取向以及它们之间的相互作用共同决定。系统会自发地趋向于能量最低的状态，也就是基态。
这个模型的数学形式非常简洁。对于一个由N个自旋构成的系统，其能量函数（哈密顿量）可以写作：H = -Σ J_ij * s_i * s_j - Σ h_i * s_i其中，s_i代表第i个自旋的状态，取值为+1或-1（上或下）。J_ij表示自旋i和j之间的耦合强度（相互作用），h_i表示作用在第i个自旋上的外部磁场。我们的目标就是找到一组{s_i}的取值，使得总能量H最小。
这个寻找基态的过程，本质上就是一个组合优化：每个自旋有两种状态，整个系统有2^N种可能配置，要从中找出能量最低的那一个。许多复杂的组合优化问题，比如旅行商问题、图着色问题、物流调度问题，都可以巧妙地映射成这种形式的伊辛模型。伊辛机，就是专门为了快速找到这个模型的基态而设计的计算机。
2.2 QUBO：通往伊辛机的“桥梁语言”
虽然伊辛模型很强大，但它的变量是±1的自旋，在计算机和优化领域，我们更习惯使用0/1二进制变量。这就引出了二次无约束二进制优化模型。QUBO模型的目标是找到一组二进制变量x_i ∈ {0, 1}，使得以下二次型目标函数最小化：H = Σ a_i * x_i + Σ b_ij * x_i * x_j其中，a_i是线性项系数，b_ij是二次项系数。
QUBO与伊辛模型是等价的，它们之间可以通过一个简单的线性变换相互转换：s_i = 2*x_i - 1。这意味着，任何能写成QUBO形式的问题，都可以交给伊辛机去求解。QUBO因此成为了伊辛机（包括量子退火机）的标准输入“语言”。
注意：QUBO模型本身是“无约束”的，但实际问题往往带有各种约束（比如“必须修满6个专业学分”）。处理这些约束的技巧是，将约束条件转化为惩罚项，加到目标函数H中。如果约束被违反，惩罚项就会使目标函数值变大，从而引导求解器去寻找满足约束的解。如何设置惩罚项的权重，是应用中的一大关键。
2.3 量子退火与数字退火：伊辛机的两种实现
目前主流的伊辛机主要有两类实现路径：
量子退火：以D-Wave公司的机器为代表。它利用量子力学中的“绝热演化”原理。简单来说，先将量子系统初始化到一个简单的、已知基态的问题上，然后非常缓慢地将其哈密顿量演化到代表我们想解决的复杂问题的哈密顿量。如果演化足够慢，系统将始终保持在瞬时基态，最终就能得到目标问题的基态。量子退火的一个潜在优势是量子隧穿效应，它允许系统穿越某些经典算法难以逾越的势垒，从而可能更有效地跳出局部最优解，找到全局最优解。
数字退火/模拟退火硬件：以富士通、日立等公司的产品为代表。这类机器使用传统的数字电路（如FPGA）或高度优化的经典算法来模拟伊辛模型的演化过程，例如进行并行的、硬件加速的模拟退火。它不依赖量子效应，但通过专用硬件架构，在求解特定形式的QUBO问题时，速度比通用CPU快几个数量级。
无论是量子还是经典实现，伊辛机的核心价值在于它为NP难组合优化问题提供了一种专用的、可能带来指数级加速的计算范式。本文实验部分使用的Fixstars Amplify AE，就是一种基于GPU加速的高性能模拟退火求解器，属于数字退火机的范畴。
3. 问题定义：个性化课程选择问题的精确建模
要把选课问题塞进伊辛机，首先得把它严格地定义成一个数学优化问题。我们称之为个性化课程选择问题。
3.1 问题输入与要素
假设一个学期内，大学提供了N门候选课程。每门课程i都有以下属性：
- 时间安排
T_i: 一组具体的上课时间段（如“周一第1节”、“周三第3-4节”）。 - 学分
w_i: 该课程对应的学分值（正整数）。 - 学分类别
d_i: 该课程所属的类别（如“专业必修”、“通识选修”、“专业限选”等）。假设共有M个不同的类别。 - 评分
r_i: 一个1到5的整数，代表学生对这门课的偏好或评价（5分最高）。这个评分可以来自历史评价、个人兴趣或课程难度预估。
同时，学生有自己的需求，即每个学分类别k需要修满的最低学分W_min_k。
3.2 硬约束：必须满足的条件
任何可行的课表都必须满足以下两个硬约束：
- 时间冲突约束：不能在同一时间段选择两门或以上的课程。这是最基础的排他性约束。
- 学分约束：对于每一个学分类别k，所选课程的总学分必须至少达到要求的最低学分
W_min_k。
3.3 优化目标：什么是“好”课表？
满足了硬约束的课表有很多，我们需要一个标准来评判哪个“更好”。PCSP综合了以下四个优化目标，希望同时实现：
- 最大化平均课程评分：尽量选择评分高的课程，提升学习体验和预期收获。
- 最小化每周上课天数：把课尽量集中到少数几天，获得更多完整的、不受打扰的自由日。
- 最小化空闲时段：在同一天内，如果两门课之间隔了没课的时间段（空堂），我们希望这种空堂越少越好。连续上课的效率通常更高。
- 最小化总课时：在满足学分要求的前提下，不要选过多的课，减轻学业负担。
显然，这些目标之间可能存在冲突。比如，评分最高的课可能分散在一周五天，而集中上课可能不得不选一些评分稍低的课。因此，我们需要一个综合的成本函数来量化一个课表的“好坏”。
4. QUBO建模详解：将选课问题“翻译”给伊辛机
这是整个项目的核心技术环节。我们需要为PCSP设计一个QUBO模型，其目标函数H的最小值对应着最优课表。
4.1 定义决策变量
首先，为每一门候选课程i引入一个二进制决策变量x_i：x_i = 1表示选择这门课，x_i = 0表示不选。 我们的任务就是找到一组{x_i}的最优赋值。
4.2 设计目标函数H_obj
目标函数H_obj需要反映之前提到的四个优化目标。研究者通过调查问卷，将学生的偏好转化为了具体的成本数值。H_obj由两部分构成：
单课程成本p_i：选择一门课i所带来的基础成本。
- 它首先包含基于评分
r_i的成本P_r(r_i)。评分越高（5分），成本越低（0）；评分越低（1分），成本越高（例如600）。这直接鼓励选择高评分课程。 - 如果一门课占据多个连续时段（比如一次上两节课），那么这些时段之间的“距离”也会产生成本。连续时段的成本为0，有时段间隔则成本增加。这鼓励选择连贯的课程，减少单门课内部的时间碎片。
双课程成本p_{i,j}：当同时选择两门课i和j时，由于它们的时间安排关系而产生的额外成本。
- 核心是计算两门课所有可能上课时段对之间的成本
P_t(t1, t2)。 - 如果两门课在同一天，但时段不连续，则根据间隔时段数增加成本（间隔越大，成本越高）。这惩罚了同一天内的“空堂”。
- 关键设计：如果两门课在不同天，则施加一个较大的固定惩罚（例如250）。这是实现“最小化上课天数”目标的核心机制。选择分散在不同天的课程会显著增加总成本，从而促使求解器将课程压缩到更少的天数内。
最终，目标函数定义为所有被选课程的单课程成本之和，加上所有被选课程对的双课程成本之和：H_obj = Σ p_i * x_i + Σ p_{i,j} * x_i * x_j其中第二项求和只针对那些时间不冲突的课程对（时间冲突的课程对由后面的约束处理）。
通过精心设计的P_r和P_t成本表，最小化H_obj的行为就等价于同时追求：选高评分课（P_r项）、课程安排紧凑减少空堂（P_t中间隔惩罚）、以及将课程集中在少数几天（P_t中不同天惩罚）。而“最小化总课时”则通过p_i和p_{i,j}均为非负值来自然实现：多选一门课永远不会降低总成本，因此求解器在满足学分要求后没有动机去选额外的课。
4.3 编码硬约束为惩罚项
QUBO本身无约束，所以我们必须把硬约束转化为目标函数中的惩罚项。
1. 时间冲突约束惩罚H_cst1： 对于所有时间冲突的课程对(i, j)，我们添加惩罚项x_i * x_j。因为x_i和x_j都是0或1，只有当两门冲突的课都被选中（x_i = x_j = 1）时，这一项才为1（产生惩罚）。如果都没选或只选一门，此项为0（无惩罚）。H_cst1 = Σ_{冲突对(i,j)} x_i * x_j这个函数的最小值是0，当且仅当没有任何时间冲突被违反时取得。
2. 学分约束惩罚H_cst2： 对于每个学分类别k，我们需要确保Σ_{i属于类别k} w_i * x_i >= W_min_k。在QUBO中处理“大于等于”不等式比较棘手。一个巧妙的技巧是引入辅助二进制变量。 我们不是要求“至少达到W_min_k”，而是要求“达到某个介于W_min_k 和 W_min_k + w_max_k - 1 之间的值”，其中w_max_k是类别k中单门课的最高学分。这个范围足以覆盖所有可能刚好满足或略超过学分要求的情况。 通过引入一组辅助变量y_{k,1}, y_{k,2}, ...，我们可以构造一个平方惩罚项：H_cst2 = Σ_{k} [ ( Σ_{i∈C_k} w_i*x_i - W_min_k - Σ_j y_{k,j} )^2 ]当括号内的式子等于0时，惩罚为0。通过调整辅助变量的值（0或1），可以让中间那个求和式匹配上实际获得的总学分，从而在总学分落在允许范围内时使惩罚归零。如果总学分不足，这个平方项就会是正数，产生惩罚。
4.4 完整的QUBO模型
将目标函数和约束惩罚项结合起来，就得到了完整的QUBO能量函数：H = H_obj + α * (H_cst1 + H_cst2)其中α是一个很大的正数，称为惩罚权重。
实操心得：惩罚权重α的调参艺术这里的α设置至关重要。如果α太小，求解器可能会“无视”约束，输出一个成本
H_obj很低但违反约束（时间冲突或学分不足）的无效解。如果α太大，虽然能保证找到可行解，但可能会掩盖目标函数H_obj的细节差异，导致找到的解虽然可行，但质量（课程评分、时间紧凑度）不高。在实际操作中，α需要根据问题规模通过实验来调整。本文实验中手动设置为2500，但在更复杂的应用中，可能需要使用网格搜索或贝叶斯优化等自动调参方法。
最终，伊辛机的任务就是找到一组{x_i}和{y_{k,j}}的赋值，使得这个总能量H最小化。这个最小化过程，就是在所有满足硬约束的课表中，寻找那个综合评分最高、上课最集中、空堂最少、总课时最少的“帕累托最优”解。
5. 实验验证与结果分析
理论模型是否有效，需要用实验说话。研究者设计了一系列实验，将基于伊辛机的方法与两种经典方法进行对比。
5.1 对比方法与实验设置
- 本文方法：使用Fixstars Amplify AE伊辛机（基于GPU的模拟退火求解器）求解上述QUBO模型。
- 基线方法1：QUBO-SA：使用传统的模拟退火算法在CPU上求解同一个QUBO模型。这用于对比硬件加速的效果。
- 基线方法2：课程交换法：一种针对选课问题设计的专用模拟退火算法。它从一个满足学分约束的初始课表出发，通过随机“交换”课程（例如，退选一门课，再从同类别中另选一门填补学分）来生成新解，并按照模拟退火的准则接受或拒绝新解。
实验使用了四组不同规模的现实选课数据实例，从小型（ins-c545）到大型（ins-c4625），课程数从545门到4625门，变量规模也随之增长。对于伊辛机，设置了不同的计算时间上限（500ms到10000ms）。评价指标包括：平均总成本（H_obj，越低越好）、计算时间、以及可行解概率（找到的课表满足所有硬约束的比例）。
5.2 结果解读：效率与质量的碾压
实验结果表格清晰地展示了伊辛机的优势：
| 实例 | 方法 | 平均总成本 | 计算时间 | 可行解概率 |
|---|---|---|---|---|
| ins-c4625-d3-r26-p | 伊辛机 (10000ms) | 12250 | ~10000 ms | 100% |
| 课程交换法 (SA) | 12350 | ~200000 ms | 100% | |
| QUBO-SA | 19650 | ~180000 ms | 100% |
- 解的质量：在所有测试实例上，给定足够计算时间，伊辛机方法总能找到总成本最低（即课表综合质量最好）的解。在最大的实例中，其解的质量显著优于QUBO-SA，也比专用的课程交换法略好。QUBO-SA的解质量最差，说明传统的模拟退火算法在求解如此大规模的QUBO问题时，容易陷入局部最优。
- 计算速度：这是伊辛机最���出的优势。在最大的实例上，伊辛机仅用约10秒就找到了与课程交换法质量相当的解，而课程交换法则需要约200秒，速度提升了20倍。相比于同样求解QUBO模型的CPU模拟退火（QUBO-SA），伊辛机的速度优势更是达到了两个数量级。这完美体现了专用硬件对于特定计算任务的巨大加速潜力。
- 可行性：通过设置合适的惩罚权重α，伊辛机方法在所有实验中都实现了100%的可行解概率，即每次都能找到满足所有约束的合法课表。
5.3 生成的课表示例分析
以最大实例的一个解为例，可以直观感受优化效果：
- 伊辛机生成的课表：总成本12250。课程集中在3天（周一、二、五），没有空堂，总课时11节，平均课程评分4.18。
- 课程交换法课表：总成本12350。同样集中3天，无空堂，总课时11节，但平均评分略低（4.09）。
- QUBO-SA课表：总成本19650。课程分散在5天，有2个空堂，总课时13节，平均评分仅3.46。
显然，伊辛机得到的课表更符合“好课表”的直觉：课程集中、连贯、评分高、负担轻。对学生的调研也证实，伊辛机生成的课表是最受青睐的。
6. 深入探讨：优势、局限与未来展望
6.1 伊辛机求解PCSP的核心优势
- 硬件加速，速度飞跃：这是最直接的收益。将问题映射到QUBO后，伊辛机能够利用其并行处理单元（无论是量子比特还是数字电路）同时探索海量解空间，对于大规模组合优化问题，相比传统CPU串行算法有数量级的速度提升。
- 通用建模框架：QUBO是一个极其灵活的建模框架。一旦掌握了将各种约束（时间、学分、甚至更复杂的如先修课程、教室容量）转化为惩罚项的技巧，同一个伊辛机平台可以解决千变万化的调度、分配、选择问题，无需为每个问题开发特定算法。
- 处理复杂多目标的能力：本研究成功地将多个有时相互冲突的优化目标（评分、天数、空堂、课时）融合进了一个单一的成本函数中。通过调整成本函数中各项的权重，可以轻松地体现不同用户的偏好（例如，有人更看重评分，有人更看重集中度）。
6.2 当前面临的挑战与局限性
- 问题映射与变量膨胀：将实际问题编码成QUBO是一门艺术，尤其是处理复杂约束时。引入辅助变量会导致总变量数增加，可能超出当前伊辛机的硬件规模（量子比特数或模拟比特数）。如何设计更紧凑的编码方式是一个研究热点。
- 参数调优的复杂性：惩罚权重α、成本函数中的具体数值（如不同天惩罚设为250）都需要精心调整。这些参数没有普适的最优值，严重依赖于具体问题和数据分布。不当的参数会导致无解或解质量低下。
- 与现有系统的集成：学术研究验证了可行性，但要投入实际应用，需要与大学的教务系统深度集成，实时获取课程数据、学生已修学分等信息，并处理动态变化（如课程取消、人数已满）。
- 量子优势的验证：本研究使用的是数字退火机。对于真正的量子退火机，其相对于经典算法的“量子优势”在多大程度上能转化为此类实际问题的求解优势，仍需更多大规模、真实世界的案例来验证。
6.3 未来可能的拓展方向
- 多学期长期规划：当前的PCSP只考虑单个学期。更实用的系统应该支持多学期甚至整个学年的课程规划，并纳入课程之间的先修关系约束，这会使QUBO模型更加复杂，但价值也更大。
- 个性化偏好学习：成本函数中的评分
r_i和各项权重（如对空堂的厌恶程度）可以不是固定的，而是通过机器学习从学生的历史选课数据、点击行为、甚至问卷调查中动态学习，实现真正的“个性化”。 - 混合求解策略：结合伊辛机与传统优化算法。例如，用伊辛机快速得到一个优质初始解，再用局部搜索算法进行微调；或者将大规模问题分解，部分用伊辛机求解，部分用经典算法。
- 探索其他新兴硬件：除了伊辛机，还有基于光学的相干伊辛机、FPGA加速器等。比较不同硬件平台在同一批教育优化问题上的表现，也是一个有趣的方向。
从手动排课到遗传算法，再到今天的伊辛机，我们解决复杂排课问题的工具在不断进化。这项研究为我们展示了一条清晰的技术路径：将一个繁琐的现实世界决策问题，通过严谨的数学建模，转化为一个适合专用计算硬件求解的QUBO模型，从而在速度和质量上获得突破。虽然目前还存在参数调优、系统集成等工程挑战，但伊辛机在组合优化领域的潜力已经毋庸置疑。或许在不久的将来，当你点击“一键智能排课”按钮时，背后为你高效工作的，就是这样一个基于量子或经典物理原理的“优化大师”。
