如何基于OptaPlanner创建含局部搜索元启发式的求解器配置及算法选择？

一、核心配置思路：从简到繁，先跑通再优化 #

1. 锚定问题类型：先明确你要解决的是排班、装箱、路径规划还是资源分配？不同问题的解空间特性差异大，适配算法也不同——比如排班适合延迟接受，装箱用贪心+局部搜索效率更高。
2. 搭建基线配置：别一开始就搞复杂组合，先用OptaPlanner默认的构造启发式（如First Fit Decreasing）+默认局部搜索（Tabu Search）跑通，拿到基准解后再迭代优化。
3. 拆分求解阶段：构造启发式负责快速生成可行解（不用追求最优，快就行），局部搜索负责精细化调优（这一步再抠解质量）。
4. 调参优先于换算法：很多时候不是算法不行，是参数没调对——比如Tabu的禁忌列表长度、延迟接受的历史解数量，这些参数对结果影响极大。

二、算法/元启发式选择指南 #

构造启发式选法 #

• First Fit/First Fit Decreasing：适合装箱、资源分配类问题，实现简单速度快，能快速凑出可行解，作为基线非常合适。
• Delay Acceptance（延迟接受）：适合排班、调度类问题，比普通贪心更能避开局部最优坑，生成的初始解质量更高。
• Cheapest Insertion：适配路径规划（VRP）类问题，逐步插入节点时优先选成本最低的，兼顾初始解的合理性。
• 硬约束优先的问题，直接选Constraint Match Aware的构造启发式——它会优先处理违反硬约束的情况，避免后期花大量时间修正。

局部搜索元启发式选法 #

• Tabu Search（禁忌搜索）：通用性极强，几乎适配所有离散优化问题，通过禁忌列表避免反复绕圈，适合需要跳出局部最优的场景。
• Late Acceptance（延迟接受）：比模拟退火简单，计算开销小，适合实时性要求高的场景（如动态调度），探索解空间的速度快。
• Simulated Annealing（模拟退火）：适合解空间崎岖、局部最优扎堆的问题，通过“降温”过程接受较差解，探索能力强，但收敛速度慢，适合对解质量要求极高、时间充裕的场景。
• 遗传算法：适合大规模、解空间极复杂的问题，通过交叉变异探索解空间，但计算成本高，需要调种群大小、交叉概率等参数，一般是其他算法都搞不定时才用。

组合策略建议 #

• 构造启发式+局部搜索是标准搭配，先把这个组合玩明白，别搞花里胡哨的。
• 局部搜索内部可采用阶段式组合：比如先跑Late Acceptance快速拓宽解空间，再切到Tabu Search精细化优化——这种组合适合先“撒网”找好的解区域，再“深耕”挖最优解。
• 别同时堆多个高开销的元启发式（如遗传+模拟退火），算力开销翻倍，解质量提升却有限，性价比极低。

三、如何判断算法组合的效果优劣 #

别凭感觉，用数据说话：

1. 解质量：计算目标函数值（如总成本、延迟时间），直接对比不同组合的最终结果，值越优（如成本越低）越好。
2. 收敛速度：记录不同时间点（1s、10s、60s）的解质量，看哪个组合能更快逼近最优解——对实时场景来说，这比最终解质量还重要。
3. 可行性：统计硬约束违反次数，确保所有组合都能生成可行解（如果硬约束是必须满足的红线）。
4. 稳定性：同一配置跑5-10次，看解质量的波动范围，波动小的组合更可靠，不会偶尔出好解偶尔拉胯。
5. 计算开销：对比CPU使用率、内存占用，选在你能接受的资源范围内达到最优解的组合。

比如你问的“先延迟接受再禁忌搜索”，直接对比三种情况：

• 单独跑延迟接受的最终解质量+收敛速度
• 单独跑禁忌搜索的最终解质量+收敛速度
• 组合后的解质量+收敛速度
  如果组合后能在更短时间内拿到比单独用更好的解，那这个组合就是有效的。

四、XML配置示例（构造启发式+阶段式局部搜索） #

拿排班问题举个实际例子，直接修改类名就能用：

<?xml version="1.0" encoding="UTF-8"?>
<solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
  <!-- 替换成你的问题模型类 -->
  <solutionClass>com.example.ShiftScheduleSolution</solutionClass>
  <entityClass>com.example.ShiftAssignment</entityClass>

  <!-- 终止条件：60秒内跑完，或者拿到完美硬约束解就停 -->
  <termination>
    <secondsSpentLimit>60</secondsSpentLimit>
    <bestScoreLimit>0hard/0soft</bestScoreLimit>
  </termination>

  <!-- 构造启发式：延迟接受，快速生成高质量初始解 -->
  <constructionHeuristic>
    <constructionHeuristicType>DELAYED_ACCEPTANCE</constructionHeuristicType>
    <delayedAcceptanceSize>100</delayedAcceptanceSize> <!-- 历史解数量，先从100试 -->
  </constructionHeuristic>

  <!-- 局部搜索分阶段：先探索再优化 -->
  <localSearch>
    <phaseList>
      <!-- 第一阶段：延迟接受跑20秒，快速探索解空间 -->
      <localSearchPhase>
        <localSearchType>LATE_ACCEPTANCE</localSearchType>
        <lateAcceptanceSize>500</lateAcceptanceSize>
        <termination>
          <secondsSpentLimit>20</secondsSpentLimit>
        </termination>
      </localSearchPhase>
      <!-- 第二阶段：禁忌搜索精细化优化剩余时间 -->
      <localSearchPhase>
        <localSearchType>TABU_SEARCH</localSearchType>
        <tabuSize>7</tabuSize> <!-- 禁忌列表长度，按问题规模1%-5%调整 -->
        <acceptor>
          <entityTabu/> <!-- 基于实体的禁忌策略，避免重复调整同一实体 -->
        </acceptor>
      </localSearchPhase>
    </phaseList>
  </localSearch>
</solver>

五、实用调参小技巧 #

• 先固定终止条件（比如60秒），再调算法参数，不然变量太多没法对比。
• Tabu Search的tabuSize一般设为问题规模的1%-5%（比如100个实体，设5-10就行）。
• 延迟接受的size越大，探索能力越强，但计算开销也会涨，先从100-500开始试。
• 如果解质量一直卡瓶颈，试试换移动选择器（比如从CHANGE_MOVE换成SWAP_MOVE）——有时候不是算法不行，是移动方式没选对，没法触达更好的解。

内容的提问来源于stack exchange，提问作者Vinayak Tiwari AI and Data Sci