两种高效局部搜索算法求解RB模型实例

作者：杨易; 王晓峰^*; 唐傲; 彭庆媛; 杨澜; 庞立超

来源：计算机应用研究, 2023, 1-10.

DOI：10.19734/j.issn.1001-3695.2023.09.0415

• RB模型
• 约束满足问题
• 局部搜索算法
• 模拟退火
• 最小冲突启发式

RB (revised B)模型是一种在约束可满足问题中具备精确相变增长域的随机实例模型，提出两种高效的启发式局部搜索算法用于解决RB模型生成的大值域约束可满足问题。首先为基于权重指导搜索的W-MCH算法，该算法通过约束判断和违反约束数计分来进行搜索，并引入了基于约束违反概率的权重计算公式，根据其关联的约束权重进行修正，再对变量进行迭代调整。然后提出最小化值域的MDMCH算法，该算法通过记录违反约束和逐步消除已违反约束变量的启发式策略来减少搜索空间，并在最小化后的变量域内重新校准变量赋值，进而有效提高算法的收敛速度。此外，还提出了融入模拟退火策略的WSCH和MDSCH算法，这两种算法都能根据变量的表征特点对变量域进行针对性的搜索。实验结果表明，与多种启发式算法相比，这两种算法在精度与时间效率方面均呈现明显提升，在复杂难解的实例中能够提供高效的求解效率，验证了算法的有效性和优越性。

• 单位
  北方民族大学