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

Two efficient local search algorithms for solving RB model examples

作　　者：杨易 王晓峰[1,2] 唐傲 彭庆媛 杨澜 庞立超 Yang Yi;Wang Xiaofeng;Tang Ao;Peng Qingyuan;Yang Lan;Pang Lichao(School of Computer Science&Engineering,North Minzu University,Yinchuan 750021,China;Key Laboratory of Image&Graphics Intelligent Processing of State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,银川750021 [2]北方民族大学图形图像智能处理国家民委重点实验室,银川750021

出　　处：《计算机应用研究》2024年第5期1394-1401,共8页Application Research of Computers

基　　金：国家自然科学基金资助项目(62062001);宁夏青年拔尖人才资助项目(2021);北方民族大学研究生创新项目(YCX23145)。

摘　　要：RB(revised B)模型是一种在约束可满足问题中具备精确相变增长域的随机实例模型,提出两种高效的启发式局部搜索算法用于解决RB模型生成的大值域约束可满足问题。首先为基于权重指导搜索的W-MCH算法,该算法通过约束判断和违反约束数计分来进行搜索,并引入了基于约束违反概率的权重计算公式,根据其关联的约束权重进行修正,再对变量进行迭代调整。然后提出最小化值域的MDMCH算法,该算法通过记录违反约束和逐步消除已违反约束变量的启发式策略来减少搜索空间,并在最小化后的变量域内重新校准变量赋值,进而有效提高算法的收敛速度。此外,还提出了融入模拟退火策略的WSCH和MDSCH算法,这两种算法都能根据变量的表征特点对变量域进行针对性的搜索。实验结果表明,与多种启发式算法相比,这两种算法在精度与时间效率方面均呈现明显提升,在复杂难解的实例中能够提供高效的求解效率,验证了算法的有效性和优越性。The RB(revised B)model is a stochastic instance model with an accurate phase change growth domain in constraint-satisfiable problems.This paper proposed two efficient heuristic local search algorithms to solve the large-value domain constraints generated by the RB model.The first is the W-MCH algorithm based on weight-guided search.This algorithm searched through constraint judgment and constraint violation score,and introduced a weight calculation formula based on constraint violation probability,which was modified according to its associated constraint weight,and iteratively adjusted then variables.Then it proposed the MDMCH algorithm for minimizing the value range,this algorithm reduced the search space by recording the heuristic strategy of constraint violations and gradually eliminating the violated constraint variables,and recalibrated the variable assignments within the minimized variable domain,thereby effectively improving the algorithm’s convergence speed.In addition,it also proposed the WSCH and MDSCH algorithms that incorporate simulated annealing strategies.Both algorithms can perform targeted searches in the variable domain based on the characterization characteristics of the variables.Experimental results show that compared with various heuristic algorithms,these two algorithms have significantly improved accuracy and time efficiency,and can provide efficient solution efficiency in complex and difficult instances,verifying the effectiveness and superiority of the algorithms.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]