元启发式算法介绍，按解的数量分类

分类框架：单解方法与种群方法

按照“算法在任一时刻维护多少个候选解”这一维度，元启发式算法可分为两大类：

形象比喻：
单解方法像一位独行登山者在浓雾中寻找谷底，每一步只能根据脚下情况决定走不走；
种群方法像一支出发位置各异的探险队，队员之间互相通报各自发现的好位置，整体上覆盖更广，但队形也可能集体涌向同一个山头（早熟收敛）。

单解方法（轨迹方法）

这一类的共性：整个搜索过程是“当前解”被不断替换形成的一条轨迹。算法每步只需回答两个问题——“往哪里走”（邻域与移动规则）和“走不走”（接受准则）。内存占用小、实现轻量，但探索覆盖面完全依赖接受准则的设计。

模拟退火

灵感来源：金属退火的物理过程——高温时原子剧烈运动，缓慢降温后系统逐渐趋于能量最低的有序状态。
核心思想：用一个温度参数控制“容忍劣解”的程度。温度高时敢于大幅退让（大范围探索），温度降低后越来越挑剔（精细开发）。
关键机制——概率接受准则（源自统计物理中的梅特罗波利斯准则）：

• 新解不劣于当前解 →必然接受
• 新解更差、目标值增加量为 ΔE → 以概率P = exp(−ΔE / T)接受

温度 T 越高，接受劣解的概率越大；
温度趋近零时，算法退化为纯贪心的爬山法。
冷却进度表：温度按固定比例下降（例如每轮乘以 0.95~0.99），或采用更缓慢的对数降温。

算法流程：

1. 随机产生初始解，设置较高初始温度
2. 对当前解做邻域随机扰动，得到新解
3. 按概率接受准则决定是否移动到新解
4. 在同一温度下重复若干次扰动
5. 降温，回到第 2 步，直至温度足够低

理论性质：已被证明当降温足够缓慢时，算法以概率一收敛到全局最优解——这给了它坚实的理论地位，但实际中满足该条件需要的迭代次数往往过大。
优缺点：实现简单、能跳出局部最优、理论完备；但单点搜索效率偏低，性能高度依赖降温策略与邻域设计。
典型应用：旅行商问题、超大规模集成电路布图规划、组合优化问题；也常作为混合算法中的扰动算子。

禁忌搜索

灵感来源：人类记忆——“好记性让人不重蹈覆辙”。
核心思想：每一步都在邻域中选择最优的移动（即使会让解变差，也照样执行，保证持续前进的能力），同时用一张禁忌表禁止近期已经做过的移动，防止搜索绕圈。
关键机制：

1. 邻域与移动：定义“一步”意味着什么，例如交换两个元素、插入、翻转等——这直接决定搜索空间的结构
2. 禁忌表与禁忌长度：记录最近 L 步做过的移动或访问过的解，这些方向在近期内被禁止，避免循环
3. 特赦准则：若某个被禁忌的移动能把历史最优解显著改善，则破例解禁允许执行

算法流程：

1. 产生初始解，清空禁忌表
2. 生成当前解的邻域候选集合
3. 剔除禁忌中的移动（除非满足特赦条件）
4. 在剩余候选中选最优的一个执行移动，即使目标值变差
5. 更新禁忌表和历史最优解，重复直至满足终止条件

优缺点：局部开发能力极强、下降速度快；但邻域设计高度依赖领域经验，禁忌长度需要精细调节，且需要维护记忆结构。
典型应用：车间调度问题、车辆路径问题、图着色问题等邻域结构清晰的组合优化问题。

同属单解，两者为何不同

两者高度互补：模拟退火擅长大范围随机探索，禁忌搜索擅长结构化的精细开发，实践中常先退火后禁忌地串联使用。

种群方法

这一类的共性：同时维护一组解，靠个体之间的信息交换实现协同搜索；
每代计算量更大，但覆盖面广、天然可并行。
三个算法的差异主要在两点——个体是什么、个体之间怎么交流：

• 遗传算法：个体是“染色体”，交流靠两个父代两两交叉重组（直接交换成分）
• 蚁群算法：个体是构造解的“蚂蚁”，交流靠信息素这一环境媒介（间接通信，后来者读取并修改环境）
• 粒子群优化算法：个体是带速度的“粒子”，交流靠广播全局最优位置（直接获取共享信息）

遗传算法

灵感来源：达尔文进化论——“物竞天择，适者生存”。
核心思想：把解编码为染色体，维护一个种群，通过选择、交叉、变异三类遗传算子模拟自然进化，让种群整体适应性逐代提升。
关键机制：

1. 编码：二进制串、实数向量或排列（如旅行商问题直接用城市访问顺序）
2. 选择：适应度高者更易被选为父代，常用轮盘赌选择或锦标赛选择
3. 交叉：以交叉概率（通常 0.6~0.9）让两个父代交换基因片段产生后代，这是种群间信息交换的核心
4. 变异：以小概率（通常 0.01~0.1）随机改动基因，维持多样性
5. 精英保留：当代最优个体直接进入下一代，防止最优解丢失

算法流程：随机初始化种群 → 评估适应度 → 选择 → 交叉 → 变异 → 精英保留 → 进入下一代，循环直至收敛。
理论基础：模式定理——短的、低阶的、适应度高于平均的模式，在遗传操作下数量呈指数增长，这解释了算法为什么有效。
优点：全局探索能力强、通用性好；
缺点：收敛慢、易早熟、参数较多。
典型应用：函数优化、调度问题、特征选择、神经网络结构搜索。

蚁群算法

灵感来源：蚂蚁觅食——蚂蚁在路径上释放信息素，短路径上蚂蚁往返快、信息素积累多，最终整个蚁群涌现出最短路径。这是一种通过修改环境实现间接协作的现象（共识主动性）。
核心思想：多只人工蚂蚁独立构造完整解，用信息素浓度作为共享的集体经验指导后续搜索，形成正反馈放大；同时用挥发机制防止过早锁定坏路径。
关键机制（以旅行商问题为例）：
①转移概率规则——蚂蚁在城市 i 选择下一个城市 j 的倾向正比于：

信息素浓度(i, j) 的 α 次方 × 启发式信息(i, j) 的 β 次方
其中启发式信息通常取两城距离的倒数（近的更有吸引力），α 与 β 控制经验与贪心的相对权重。

②信息素挥发与强化——每轮迭代结束后：

每条边上的信息素 ← (1 − 挥发系数) × 原信息素 + 各蚂蚁按其路径质量追加的量

两个平衡机制是算法的灵魂：

• 正反馈（强化）：好路径吸引更多蚂蚁、沉积更多信息素 → 加速开发
• 挥发（遗忘）：防止信息素无限累积、避免错误路径被过早固化 → 保持探索

值得注意：蚂蚁本身没有记忆，记忆被外化存储在信息素场（环境）中。
优点：分布式、鲁棒、特别适合离散组合问题；
缺点：收敛慢，大规模问题的信息素更新开销大。
典型应用：旅行商问题、车辆路径问题、网络路由、任务分配。著名变体包括蚁群系统、最大最小蚁群算法。

粒子群优化算法

灵感来源：鸟群觅食的社会行为——个体同时参考自己的经验和群体共享的信息来调整飞行方向。
核心思想：每个粒子有位置和速度，受自身历史最优（认知学习）和群体历史最优（社会学习）的双重牵引飞向有前途的区域。
更新公式（用文字表述）：

新速度 = 惯性权重 × 当前速度 ＋ 第一学习因子 × 随机数 × （个体历史最优位置 − 当前位置） ＋ 第二学习因子 × 随机数 × （群体历史最优位置 − 当前位置）

新位置 = 当前位置 + 新速度

三项分量的作用：

第一、第二学习因子通常取 2 左右，随机数在 0 到 1 之间，它们带来随机扰动、避免所有粒子走完全相同的路线。
优点：在元启发式算法中实现最简单、参数最少、连续问题收敛快；
缺点：全体粒子趋向同一个全局最优位置，容易早熟收敛，高维多峰问题性能下降。
典型应用：连续函数优化、控制器与神经网络参数整定、多目标优化的粒子群扩展版本。

三个种群算法的深层差异：记忆存在哪里

5种算法总览对比

选型建议

离散组合问题（旅行商问题、调度、车辆路径问题）→ 优先考虑蚁群算法、禁忌搜索、排列编码的遗传算法
连续参数优化→ 优先考虑粒子群优化算法、实数编码的遗传算法
计算预算紧张、追求轻量实现→ 模拟退火（单解方法每步开销最小）
需要并行或分布式部署→ 种群方法天然占优
邻域结构清晰、有领域知识可用的工程问题→ 禁忌搜索

发展趋势：两类方法的融合

实践中单一算法正让位于混合元启发式算法，恰好体现两大类方法的优势互补：
模因算法：遗传算法提供种群级全局探索，局部搜索（禁忌搜索等）负责个体级精修
退火式接受准则嵌入粒子群优化算法：缓解向全局最优聚集导致的早熟
自适应参数控制：让交叉概率、惯性权重、禁忌长度等随搜索状态动态调整

排列专用交叉算子详解

问题回顾：为什么必须专用

普通交叉对排列编码必然产生非法解。以 8 个波束排时隙为例，在第 4 位之后做单点交叉：

父代一： 2 5 4 6 | 3 1 8 7 父代二： 7 4 1 8 | 2 6 5 3 拼合结果：2 5 4 6 | 2 6 5 3 ← 波束2、6重复，1、7缺失，非法

排列约束是“每个元素恰好出现一次”。所有排列专用算子的共同目标：保证子代天然合法（不需要修复或惩罚），同时把父代中“有价值的结构”传给子代。各算子的区别，只在于它们认为什么结构有价值。

总框架：排列中的三种“遗传信息”

一条排列里能被继承的信息只有三种，这决定了算子的三大门派：

另一个二级分类维度：

• 重组式：直接从父代复制片段，冲突时修复——部分匹配、顺序、循环交叉属于此类，通常一次产生两个互补子代
• 构造式：把父代当“材料库”，按规则从零逐位建造子代——边重组交叉属于此类，通常一次产生一个子代

统一示例约定：下文所有算子共用同一对父代（切割点随机，各算子示例的切割点可以不同）：

父代一： 2 5 4 6 3 1 8 7 （时隙1放2号波束，时隙2放5号波束……） 父代二： 7 4 1 8 2 6 5 3

位置类算子：认为“元素在哪个槽位”最值钱

部分匹配交叉（Partially Mapped Crossover）

思想：中段原位继承，外段从另一方照抄，用中段定义的位置映射修复冲突。
切割点取在第 4、7 位之后：

父代一： 2 5 4 6 | 3 1 8 | 7 父代二： 7 4 1 8 | 2 6 5 | 3

构造子代一：

第1步 原位继承父代一中段： _ _ _ _ | 3 1 8 | _ 第2步 空位照抄父代二对应位： 7 4 1 8 | 3 1 8 | 3 ← 1、8、3与中段重复 第3步 映射修复： 7 4 6 5 | 3 1 8 | 2

映射的来历：两个中段按位置一一对应，形成“值对值”的映射关系：

即3↔2、1↔6、8↔5。修复时把冲突值换成其映射伙伴：位置3的1换成6，位置4的8换成5，位置8的3换成2。
子代二对称构造（继承父代二中段 2 6 5，外面抄父代一并同样修复）：

子代一： 7 4 6 5 3 1 8 2 子代二： 3 8 4 1 2 6 5 7

保留的信息：中段的“值+位置”原样传递；外段尽量维持来自另一父代的原位值，映射本身也是位置对应关系。整体偏重绝对位置。
实现陷阱：若两个中段含有相同元素（本例刻意避开了），修复时替换值可能再次冲突，需沿映射链追溯多步——这是该算子最常见的实现出错点。

循环交叉（Cycle Crossover）

思想：先找出两个父代之间的“循环”（值的位置互换圈），同一循环内的位置，无论取哪个父代的值都合法，于是按循环分组抄值，元素绝不搬家。
找循环：从位置1出发，做“父代一的值 → 去父代二里找同值的位置”的跳转：

• 位置1：父代一放2，父代二的2在位置5 → 跳到位置5
• 位置5：父代一放3，父代二的3在位置8 → 跳到位置8
• 位置8：父代一放7，父代二的7在位置1 → 回到起点，循环一闭合 = {1, 5, 8}

从剩余的位置2出发，同样跳转得循环二 = {2, 3, 4, 6, 7}。
合法性来源（关键洞察）：同一循环内的位置，两个父代放的恰好是同一组值（循环一：父代一放{2,3,7}，父代二放{7,2,3}）。所以循环内各位置随便取哪个父代的值都不会重复。
构造子代：循环一的位置取父代一的值，其余取父代二的值（子代二取反）：

位置： 1 2 3 4 5 6 7 8 [循环一]-----取父代一-----┐ 父代一： 2 5 4 6 3 1 8 7 父代二： 7 4 1 8 2 6 5 3 子代一： 2 4 1 8 3 6 5 7 （位置1,5,8来自父代一，其余来自父代二） 子代二： 7 5 4 6 2 1 8 3

保留的信息：子代每一个位置的值都来自某个父代的同一位置——位置信息百分之百保留。这是最接近经典遗传算法“等位基因交叉”观念的排列版本，适合“槽位本身意义强烈”（如第一个时隙至关重要）的问题。

基于位置的交叉（Position-based Crossover）

思想：循环交叉的随机化替代——不做循环分析，直接随机选几个位置从父代一原位继承，其余空位按父代二的出现顺序填入。
随机选位置 {2, 4, 7}：

第1步 位置2、4、7继承父代一： _ 5 _ 6 _ _ 8 _ 第2步 其余位按父代二顺序填（跳过5、6、8）：7 5 4 6 1 2 8 3

实现比循环交叉简单，效果相近，是位置类问题的常用工程选择。

顺序类算子：认为“先后次序”最值钱

顺序交叉（Order Crossover）

思想：中段原样继承，其余空位填入另一父代的值时，保持它们在另一父代中的相对先后次序（从切割点起循环读取）。
切割点取在第 3、6 位之后：

父代一： 2 5 4 | 6 3 1 | 8 7 父代二： 7 4 1 | 8 2 6 | 5 3

构造子代一：

第1步 原位继承父代一中段： _ _ _ 6 3 1 _ _ 第2步 从父代二第7位起循环读取： 5 3 7 4 1 8 2 6 第3步 剔除已有的6、3、1，剩下： 5 7 4 8 2 第4步 从第7位起循环填入空位： 位置7←5 位置8←7 位置1←4 位置2←8 位置3←2

子代一： 4 8 2 6 3 1 5 7

构造子代二（继承父代二中段 8 2 6，从父代一第7位起循环读取，剔除8、2、6后得 7 5 4 3 1，填入空位）：

子代二： 4 3 1 8 2 6 7 5

保留的信息：中段的“值+位置”，以及外段值的循环相对顺序（子代一中 5→7→4→8→2 的先后关系与父代二一致）。适合“先后次序决定优劣”的问题（作业加工顺序、服务次序），是文献和实践中的默认首选之一。
实现提示：另有“空位从左到右直接顺序填”的简化变体，效果相近；实现时固定一种即可，不要混用。

基于顺序的交叉（Order-based Crossover）

思想：随机选一组位置，读出父代二在这些位置的值；这组值保持它们在父代一中的位置，但相互间的顺序改为父代二的顺序。
随机选父代二的位置 {2, 4, 6}，对应值为 4、8、6：

第1步 以父代一为底板： 2 5 4 6 3 1 8 7 第2步 4、8、6在父代一的位置： 位置3、位置4、位置7 第3步 按(父代二的)顺序放回： 位置3←4 位置4←8 位置7←6 子代： 2 5 4 8 3 1 6 7

与基于位置的交叉是一对孪生算子（一个保位置、一个保顺序），注意两者在文献中命名时有互换，看机制不要看名字。

邻接类算子：认为“谁挨着谁”最值钱

边重组交叉（Edge Recombination Crossover）

思想：构造式算子。把两个父代中所有相邻元素对（“边”）汇成一张边表，然后贪心建造子代：每一步优先继承已共享的边，其次选剩余边最少的邻居，尽量不让子代出现父代没有的新边。
第一步：建边表（两父代的相邻对合并去重）：

（加粗的 1-8 是两父代共享的边——两边都出现，最有价值，优先继承）
第二步：贪心构造（从父代一首元素2出发）：

子代： 2 8 1 3 6 5 4 7

效果检验：子代的 7 条邻接边（2-8、8-1、1-3、3-6、6-5、5-4、4-7）全部来自父代——这是理想情况；实际运行中绝大多数边被继承，偶尔出现新边，若走入死端（候选邻居全部用完）则随机跳到任一剩余元素。
适用判断标准：只有当目标函数主要由相邻元素对的代价决定时（旅行商问题的距离、相邻工序的切换成本），边重组交叉才显著优于前几类；否则边信息无价值，用它反而浪费。

进阶算子一瞥

• 边装配交叉（1999年）：构造式思路的高性能延伸，通过“边交换修复子回路”，在旅行商问题上接近专用求解器的水平
• 顺序构造交叉：构造过程中用启发式（如最近邻）而非纯继承来选下一个元素
  这两个实现复杂度高，除非做旅行商类问题的深度研究，一般不必首选。

全部算子横向对比

经验规律（因问题而异，仅供参考）：
旅行商类邻接问题上邻接类占优、顺序交叉优于部分匹配交叉；
位置主导的调度问题上部分匹配交叉与循环交叉更好。