7 - 智能优化方法 - Gavin0576's Blog

想象你在夜里寻找山谷：只能测量脚下高度，看不见全部地形，某些区域禁止进入，有些决策甚至不是连续的。这时随机搜索与群体方法确实有价值，但“智能”两个字也最容易掩盖不严谨。

本文讨论遗传算法、差分进化、粒子群和模拟退火。每个更新式都会明确写出，编码和约束与目标函数同等重要。真实案例是 2024 国赛一篇采用差分遗传算法优化种植策略的优秀论文。我们重点追问：怎样确认启发式算法搜索的是原本想表达的模型？

启发式算法契约

必须说明编码、初始化、变异与交叉、约束处理、停止条件、随机种子和比较基线。一条平滑的收敛曲线不能证明全局最优。

1. 什么时候才需要元启发式

若 LP、凸优化、动态规划或 MILP 能合理求解，应优先使用，因为它们能给出最优性条件或上下界。非凸、离散、仿真驱动、混合变量或规模过大时，元启发式才更有吸引力。

选择前先问：能否重新表达成 LP/QP/SOCP/MILP？缩小实例能否精确求解？目标评估是否含噪声？可行性是否容易保持？需要一个最优方案还是一组多样方案？若适应度函数奖励错了，再强的搜索也只会找到一个非常好的错误答案。

2. 编码先于进化

编码把算法状态映射到真实决策。路线适合排列编码，特征选择适合比特串，种植规划则包含面积、作物与季节。表示方式应让合法方案容易表达，让非法方案难以产生。

若把作物编号随意排成向量，交叉后几乎必然违反地块兼容与轮作。问题相关的编码可以只生成允许的作物，并按时间顺序修复轮作。每次设计交叉，都应手工拿两个合法父代试一次；若修复步骤需要改掉大多数基因，说明算子正在与编码对抗。

3. 遗传算法的每一步

第代种群为。锦标赛选择从个候选中留下最好者。若优质个体比例为，锦标赛中至少出现一个的概率是

越大，选择压力越强，也越容易提前失去多样性。实数编码的算术交叉为

高斯变异为。排列问题必须使用顺序交叉、交换或逆序变异，不能直接平均两个路线。

每代包括评估、精英保留、选择、交叉、变异、修复和替换。记录最好值还不够，还应记录中位数、四分位距、可行率和多样性。最好值不再改善可能表示收敛，也可能表示种群已经塌缩。

4. 差分进化

DE/rand/1 从三个不同个体构造

二项交叉得到

$或否则$

强制坐标保证试验个体至少有一维来自变异。若不差于就保留。差分向量让步长随种群尺度自适应：初期走得大，后期局部细化。太小会停滞，太大则频繁越界；best/1 收敛快，却更容易围绕坏盆地塌缩。

边界截断会把大量个体堆在边界，反射或重新采样通常更自然。等式约束最好通过参数化直接满足，而不是设置巨大罚项。

5. 粒子群优化

粒子位置、速度、个人最优和全局最优的更新是

保留惯性，是个人记忆，是社会吸引。参数太大时粒子震荡甚至发散；社会项过强会早熟。环形邻域传播较慢，往往比全局拓扑保留更多多样性。

离散问题必须重新定义“速度”，例如比特取 1 的概率或交换序列。简单把连续位置四舍五入会引入偏差并破坏可行性。

6. 模拟退火与接受概率

若新邻居的目标变化，总是接受；更差的移动以

$接受$

的概率接受。高温允许越过局部山脊，降温后逐渐挑剔。若初始典型上坡幅度为，希望接受率为，可取

几何降温为。理论上的对数降温可能保证全局收敛，但实践中极慢，因此竞赛论文应如实报告使用的经验日程。邻域决定哪些状态可达；如果移动无法连通可行解空间，再慢的降温也无济于事。

7. 约束与罚函数

常见罚函数是

罚系数太小会奖励非法方案，太大又会让边界极端陡峭。更稳健的方法包括可行编码、修复、重采样、投影和 Deb 规则：可行优先；都可行时比目标；都不可行时比总违规量。

一定要报告可行率。若 99.9% 候选都非法且被大幅修复，名义种群规模并不代表有效搜索规模。多目标场景可用 NSGA-II 的非支配排序和拥挤距离，同时评估前沿逼近与分布多样性。

8. 获奖案例：2024 国赛种植规划 DEGA

公开优秀论文《基于差分遗传算法的农作物种植策略优化》处理 2024–2030 年、不同土地类型、季节、轮作、豆类要求、需求和不确定性，并把 DE 差分变异与 GA 选择交叉结合。

令为种植面积，为是否使用。解码器必须保证

同时满足作物兼容、最小管理面积、禁止连续重茬和三年滚动窗口中的豆类要求。收入必须把原价销量限制在需求以内。

合理流程是：只初始化兼容组合；把面积归一到地块容量；对面积做 DE 变异；对作物日程做问题相关交叉；按时间修复轮作与豆类；先按可行性再按利润比较；保留精英和多样性。

用两年小实例建立 MILP 精确基准，再验证 DEGA。完整实例还应比较 2023 可行方案、带修复的贪心、连续松弛等基线。至少运行 30 个随机种子，报告最好、中位、最差与离散度。收敛曲线平滑，只说明这一次运行不再改善，不说明全局最优。

9. 公平实验与复现

不同算法必须获得相同的目标评估次数、停止预算和硬件。1000 次 GA 与 10 万次 PSO 不能构成公平比较。随机结果应报告中位数和四分位距，多实例可用性能分布。

超参数应在训练实例上调，在留出实例上评估。保存配置、随机种子、数据校验值、代码提交、运行时间、评估次数和可行残差。混合算法要做消融：DEGA 对比 DE、GA，以及去掉修复或精英后的版本。

10. 论文可以声称什么

可以说“30 次运行中找到的最好可行解”“在相同评估预算下中位目标比贪心改善 8.4%”“在缩小实例中匹配已证明最优值”。不能因为曲线变平，就写“得到了全局最优解”。

最后留一道隐藏题：把 PSO 的随机数都替换成期望，并令，写出距离的线性递推。群体隐喻消失后，你会发现底层其实是一个动力系统——它会在后面的微分方程博客里再次出现。

知识检查

下面 10 道单选与多选题从表示方法和基本更新规则开始，逐步进入 GA、DE、PSO、SA 的数值计算、约束处理、过早收敛、公平实验，以及混合种植优化器需要什么证据。题目会按难度记录 EXP；登录后可以保存首次作答结果。

Gavin0576's Blog

7 - 智能优化方法