概念

元启发式

遗传算法模拟自然进化、模拟退火借鉴物理退火、禁忌搜索利用记忆机制，在解空间中智能搜索，适合大规模难解问题。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

元启发式运筹学

本主题暂无后续概念

01定义

元启发式是问题无关的搜索框架：遗传算法模拟进化、模拟退火借鉴物理降温、禁忌搜索利用记忆——以「可接受的质量 + 可控的时间」换取大规模 NP 难问题的可行解，是无最优保证但极其实用的工具箱。

模拟退火：受控的随机跳跃逃离局部最优

遗传算法：选择-交叉-变异迭代种群；模拟退火：以 $e^{-\Delta/T}$ 概率接受劣解、按退火计划降温；禁忌搜索：近期访问解入禁忌表避免循环——探索与开发的平衡是共同主题。

退火在无穷慢降温下概率 1 收敛到全局最优（Geman 等），实用中只能有限步；参数（种群大小、降温率、禁忌长度）常用自动调参（irace、贝叶斯优化）确定。

元启发式 + 局部搜索 = 膜算法/混合遗传；与精确法混合（大邻域搜索：破坏-修复 + LP）在车辆路径等领域常胜纯精确法——「框架套框架」是实践常态。

P(\text{接受劣解})=e^{-\Delta f/T_k},\quad T_{k+1}=\alpha T_k\ (\alpha<1)

柯克帕特里克等 1983 年提出模拟退火；霍兰德 1975 年发展遗传算法；格洛弗 1986 年提出禁忌搜索；三者共同构成 1980 年代元启发式浪潮。

车辆路径与排班（实际规模常超精确法能力）、芯片布局布线、蛋白质结构预测、超参数搜索与调度竞赛冠军方案。

模拟退火：高温大跳、低温收敛温度高时接受差解的意愿强，降温后逐渐锁定全局最优

T 温度1.00