分类框架单解方法与种群方法按照“算法在任一时刻维护多少个候选解”这一维度元启发式算法可分为两大类对比维度单解方法轨迹方法种群方法候选解数量只维护 1 个“当前解”同时维护几十到几百个解搜索轨迹形态解空间中的一条路径一片不断移动的“点云”信息来源当前解 邻域结构记忆个体之间的信息交换跳出局部最优的手段概率接受劣解、禁忌约束交叉重组、变异、多样性维持单次迭代开销小只评估一个或少数候选大每代评估整个种群并行能力以串行为主天然适合并行代表算法模拟退火、禁忌搜索遗传算法、蚁群算法、粒子群优化算法形象比喻单解方法像一位独行登山者在浓雾中寻找谷底每一步只能根据脚下情况决定走不走种群方法像一支出发位置各异的探险队队员之间互相通报各自发现的好位置整体上覆盖更广但队形也可能集体涌向同一个山头早熟收敛。单解方法轨迹方法这一类的共性整个搜索过程是“当前解”被不断替换形成的一条轨迹。算法每步只需回答两个问题——“往哪里走”邻域与移动规则和“走不走”接受准则。内存占用小、实现轻量但探索覆盖面完全依赖接受准则的设计。模拟退火灵感来源金属退火的物理过程——高温时原子剧烈运动缓慢降温后系统逐渐趋于能量最低的有序状态。核心思想用一个温度参数控制“容忍劣解”的程度。温度高时敢于大幅退让大范围探索温度降低后越来越挑剔精细开发。关键机制——概率接受准则源自统计物理中的梅特罗波利斯准则新解不劣于当前解 →必然接受新解更差、目标值增加量为 ΔE → 以概率P exp(−ΔE / T)接受温度 T 越高接受劣解的概率越大温度趋近零时算法退化为纯贪心的爬山法。冷却进度表温度按固定比例下降例如每轮乘以 0.95~0.99或采用更缓慢的对数降温。算法流程随机产生初始解设置较高初始温度对当前解做邻域随机扰动得到新解按概率接受准则决定是否移动到新解在同一温度下重复若干次扰动降温回到第 2 步直至温度足够低理论性质已被证明当降温足够缓慢时算法以概率一收敛到全局最优解——这给了它坚实的理论地位但实际中满足该条件需要的迭代次数往往过大。优缺点实现简单、能跳出局部最优、理论完备但单点搜索效率偏低性能高度依赖降温策略与邻域设计。典型应用旅行商问题、超大规模集成电路布图规划、组合优化问题也常作为混合算法中的扰动算子。禁忌搜索灵感来源人类记忆——“好记性让人不重蹈覆辙”。核心思想每一步都在邻域中选择最优的移动即使会让解变差也照样执行保证持续前进的能力同时用一张禁忌表禁止近期已经做过的移动防止搜索绕圈。关键机制邻域与移动定义“一步”意味着什么例如交换两个元素、插入、翻转等——这直接决定搜索空间的结构禁忌表与禁忌长度记录最近 L 步做过的移动或访问过的解这些方向在近期内被禁止避免循环特赦准则若某个被禁忌的移动能把历史最优解显著改善则破例解禁允许执行算法流程产生初始解清空禁忌表生成当前解的邻域候选集合剔除禁忌中的移动除非满足特赦条件在剩余候选中选最优的一个执行移动即使目标值变差更新禁忌表和历史最优解重复直至满足终止条件优缺点局部开发能力极强、下降速度快但邻域设计高度依赖领域经验禁忌长度需要精细调节且需要维护记忆结构。典型应用车间调度问题、车辆路径问题、图着色问题等邻域结构清晰的组合优化问题。同属单解两者为何不同对比点模拟退火禁忌搜索移动决策方式概率性、随机扰动确定性、系统性扫描邻域跳出局部最优靠“概率退让”接受劣解靠“记忆避让”禁止回头、允许劣化移动记忆机制无显式记忆显式短期记忆禁忌表关键参数初始温度、降温速度禁忌长度、邻域结构两者高度互补模拟退火擅长大范围随机探索禁忌搜索擅长结构化的精细开发实践中常先退火后禁忌地串联使用。种群方法这一类的共性同时维护一组解靠个体之间的信息交换实现协同搜索每代计算量更大但覆盖面广、天然可并行。三个算法的差异主要在两点——个体是什么、个体之间怎么交流遗传算法个体是“染色体”交流靠两个父代两两交叉重组直接交换成分蚁群算法个体是构造解的“蚂蚁”交流靠信息素这一环境媒介间接通信后来者读取并修改环境粒子群优化算法个体是带速度的“粒子”交流靠广播全局最优位置直接获取共享信息遗传算法灵感来源达尔文进化论——“物竞天择适者生存”。核心思想把解编码为染色体维护一个种群通过选择、交叉、变异三类遗传算子模拟自然进化让种群整体适应性逐代提升。关键机制编码二进制串、实数向量或排列如旅行商问题直接用城市访问顺序选择适应度高者更易被选为父代常用轮盘赌选择或锦标赛选择交叉以交叉概率通常 0.6~0.9让两个父代交换基因片段产生后代这是种群间信息交换的核心变异以小概率通常 0.01~0.1随机改动基因维持多样性精英保留当代最优个体直接进入下一代防止最优解丢失算法流程随机初始化种群 → 评估适应度 → 选择 → 交叉 → 变异 → 精英保留 → 进入下一代循环直至收敛。理论基础模式定理——短的、低阶的、适应度高于平均的模式在遗传操作下数量呈指数增长这解释了算法为什么有效。优点全局探索能力强、通用性好缺点收敛慢、易早熟、参数较多。典型应用函数优化、调度问题、特征选择、神经网络结构搜索。蚁群算法灵感来源蚂蚁觅食——蚂蚁在路径上释放信息素短路径上蚂蚁往返快、信息素积累多最终整个蚁群涌现出最短路径。这是一种通过修改环境实现间接协作的现象共识主动性。核心思想多只人工蚂蚁独立构造完整解用信息素浓度作为共享的集体经验指导后续搜索形成正反馈放大同时用挥发机制防止过早锁定坏路径。关键机制以旅行商问题为例①转移概率规则——蚂蚁在城市 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映射的来历两个中段按位置一一对应形成“值对值”的映射关系中段位置567父代一的值318父代二的值265即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、87 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思想构造式算子。把两个父代中所有相邻元素对“边”汇成一张边表然后贪心建造子代每一步优先继承已共享的边其次选剩余边最少的邻居尽量不让子代出现父代没有的新边。第一步建边表两父代的相邻对合并去重元素25463187邻居5,8,62,4,6,35,6,7,14,3,2,56,1,53,8,41,7,28,4加粗的 1-8 是两父代共享的边——两边都出现最有价值优先继承第二步贪心构造从父代一首元素2出发当前元素候选邻居选择依据选定25, 8, 68的剩余边最少881, 7边8-1是两父代共享边优先113, 43的剩余边更少336, 5平局随机664, 55只剩1条边554唯一候选447唯一候选7子代 2 8 1 3 6 5 4 7效果检验子代的 7 条邻接边2-8、8-1、1-3、3-6、6-5、5-4、4-7全部来自父代——这是理想情况实际运行中绝大多数边被继承偶尔出现新边若走入死端候选邻居全部用完则随机跳到任一剩余元素。适用判断标准只有当目标函数主要由相邻元素对的代价决定时旅行商问题的距离、相邻工序的切换成本边重组交叉才显著优于前几类否则边信息无价值用它反而浪费。进阶算子一瞥边装配交叉1999年构造式思路的高性能延伸通过“边交换修复子回路”在旅行商问题上接近专用求解器的水平顺序构造交叉构造过程中用启发式如最近邻而非纯继承来选下一个元素这两个实现复杂度高除非做旅行商类问题的深度研究一般不必首选。全部算子横向对比算子主打保留产生方式实现难度经验适用场景部分匹配交叉绝对位置中段原位映射修复重组式双子代中位置有意义的一般调度循环交叉绝对位置逐位取值元素不换位重组式双子代中位置强烈敏感的问题基于位置的交叉绝对位置随机位点继承重组式双子代低同上工程简化版顺序交叉相对顺序外段循环保序重组式双子代低顺序敏感问题默认首选基于顺序的交叉相对顺序子集换序不换位重组式双子代低顺序敏感问题边重组交叉邻接关系构造式单子代较高旅行商等邻接代价主导的问题经验规律因问题而异仅供参考旅行商类邻接问题上邻接类占优、顺序交叉优于部分匹配交叉位置主导的调度问题上部分匹配交叉与循环交叉更好。
