一个 500 维排列编码的调度问题，当前遗传算法 100 个体、2000 代，单次 40 分钟，最好解波动 8%；业务要求 10 分钟内完成且波动小于 1%，还要求可复现、可解释。团队想继续调交叉变异概率。作为技术负责人，你怎么诊断和改造？会保留 GA 还是换算法？给出编码、算子、并行、早停和验收方案。
面试官在考什么
判断能否把随机启发式产品化，处理波动、时延、可复现和混合算法选型。
回答框架 · 前两步
- 先量化：评估函数耗时、种群多样性、选择压力、早熟/漂移、结果分位数；40 分钟可能主要耗在评估。
- 编码与算子：排列编码用顺序交叉、部分匹配交叉等合法交叉，变异用交换、插入、逆序；约束要修复或惩罚。
还有 3 条答案要点、 3 层追问、 5 个常见坑， 以及针对你简历的追问路径，在定制报告里。
同一能力域的其他题
- 你说做过排产调度，用了遗传算法/模拟退火。请说明你的编码方式（染色体/状态表示）是什么？适应度函数里有没有加惩罚项？为什么？
- 你要实现一个最小化 0-1 整数规划的分支定界求解器。某实例根节点 LP 松弛下界 = 100，已知最优整数解 = 118。跑完 10 万个节点后 incumbent 仍是 118，open list 里还有 5 万个节点，其中最好的下界是 104。请回答：(a) 你用什么指标判断瓶颈在“下界太松”还是在“分支/节点选择策略差”？(b) 如果不改模型语义，只改界的紧度，列出两种手段并说明各自代价；(c) 当前 incumbent = 118，某子节点 LP 下界恰好等于 118 且解是分数，你是否剪枝，为什么？
- 一个 0-1 整数规划模型：200 个 0-1 变量、500 条约束，用求解器跑 1 小时，MIP gap 仍有 28%。日志显示 root LP relaxation 的目标值只比初始可行解好 5%，搜索树在第 3 层就展开出上万个节点。你会优先动哪几个地方？先动哪个、为什么？
- 你负责一个生产排程的混合整数规划求解服务：约 10 万变量，约束以背包和先后关系为主，16 核机器，当前分支定界跑 20 小时仍有 5% gap，LP 重求解占 80% 时间。业务要求 2 小时内给出可执行方案。团队提出三条路线：A 自研强分支+并行 B&B；B 增加问题特定割平面；C 改用约束规划/商用求解器或启发式先给可行解。作为技术负责人，你如何诊断瓶颈、排序路线、做 build/buy 取舍，并给出 90 天落地计划与验收指标？
- 整数规划：max z = 5x1 + 4x2，约束 2x1 + 3x2 ≤ 12，2x1 + x2 ≤ 7，x1, x2 ≥ 0 且取整。它的 LP 松弛最优解是 (x1, x2) = (2.25, 2.5)，z = 21.25。请回答：(1) 你会对哪个变量分支，两个子问题分别是什么，各自 LP 上界大概是多少；(2) 如果某个子问题的 LP 松弛最优解恰好是整数解，是不是就可以直接把它从待探索列表里删掉，为什么；(3) 搜索过程中的“当前下界”是怎么来的、什么时候更新它。
- 你用列生成求解一个集合覆盖型主问题（最小化总成本）。当前 RMP 的对偶解为 π = (3, 2, 5)（对应 3 个需求）。子问题返回一条覆盖需求 2 和 3、成本为 6 的列。请回答：(a) 这条列的 reduced cost 是多少？该不该加入 RMP？(b) 列生成收敛后 RMP 的 LP 最优值是 100，四舍五入得到的整数可行解是 115，这个 gap 你打算怎么处理？(c) 如果子问题改用启发式搜索而不是精确最短路，对 (b) 中的下界和剪枝会有什么影响？