BandMaxSAT: 多臂Bandit局部搜索MaxSAT求解器优于SATLike3.0和TT-Open-WBO-Inc

+v：mala2277获取更多论文BandMaxSAT：一个多臂Bandit局部搜索MaxSAT求解器郑炯智1，2，何坤<$1，周建荣1，严进1，李楚民3，Felip Manya41华中科技大学计算机科学与技术学院2华中科技大学人工智能研究所3法国皮卡第儒勒·凡尔纳大学MIS4西班牙巴塞罗那IIIA-CSIC人工智能研究所jzzheng@hust.edu.cn，brooklet60@hust.edu.cn[2]通讯作者。摘要我们解决部分MaxSAT（PMS）和加权PMS（WPMS），MaxSAT问题的两个实际推广，并 提 出 了 一 个 本 地 搜 索 算 法 称 为BandMaxSAT，适用于多臂强盗引导搜索方向，为这些问题。在我们的方法中的bandit与输入（W）PMS实例中的所有软子句相关联。每个分支对应一个软从句。Bandit模型通过选择当前步骤需要满足的软子句，即选择需要拉动的手臂，帮助BandMaxSAT选择一个好的方向，从而跳出局部最优。我们进一步提出了一个初始化方法（W）PMS优先单位和二元条款时产生的初始解决方案。大量的实验表明，BandMaxSAT显着优于最先进的（W）PMS本地 搜 索 算 法 SATLike3.0 。 具 体 而 言 ，BandMaxSAT 获 得 更 好 结 果 的 实 例 数 约 为SATLike3.0获得的实例数的两倍。我们进一步将 BandMaxSAT 与 完 整 的 求 解 器 TT-Open-WBO-Inc.由此产生的求解器BandMaxSAT-c也优于一些最好的最先进的完整（W）PMS求解器 ， 包 括 SATLike-c ， Loandra 和 TT- Open-WBO-Inc。1介绍最大布尔可满足性（MaxSAT）问题是著名的布尔可满足性（SAT）判定问题的一个优化推广，其目标是寻找一个布尔变量的完全分配，使给定的命题公式在共轭范式 （ CNF ） 中 满 足 尽 可 能 多 的 子 句 . 部 分 MaxSAT（PMS）是MaxSAT的一个变体，其中子句分为硬和软。PMS的目标是在满足所有硬子句的约束下，最大化满足的软子句的数量加权PMS（weight PMS）的目标是在PMS的约束条件下最大化满足的软子句的总权重，即所有硬子句都必须满足。PMS和WPMS（表示为（W）PMS）都有许多实际应用，例如规划[Bonetet et al. ，2019]，routing [Liet al. ，2020] ， 组 测 试 [Ciampiconiet al. ， 2020] 和 可 拆 卸[Demirovic和Musliu，2017]等。在本文中，我们专注于本地搜索方法，这是一个研究得很好的类别的不完整算法的（W）PMS和表现出良好的性能随机和精心制作的（W）PMS实例。 最近表现良好 的（W ）PMS 局 部搜 索算 法， 如Dist [Caiet al. ，2014] ， CCEHC [Luoet al. ， 2017] ， SATLike [Lei 和Cai，2018]和SATLike3.0 [Cai和Lei，2020]，都是从初始的完全赋值开始，然后每步翻转选定变量的布尔值以找到更好的解决方案。这些局部搜索算法遵循类似的过程来逃离局部最优。请注意，局部最优值表明翻转任何单个变量都不能改善当前解。当落入不可行的局部最优时（即，存在伪造的硬子句），这些算法首先随机选择伪造的硬子句，然后通过翻转其变量之一来满足它。由于所有的硬子句都应该满足，所以选择伪造硬子句的随机策略是合理的。然而，当落入可行的局部最优（即，不存在伪造的硬子句），但是这些算法仍然使用随机策略来确定在当前步骤中要满足的软子句，这可能不是好的策略，原因如下：1）与硬子句不同，不是所有的软子句都应该被满足。2）高度的随机性可能导致这些算法找到好的搜索方向的概率很小（满足伪造的软子句对应于搜索方向）。为了解决上述问题，我们提出了一个多臂的禁令（MAB）的本地搜索算法，称为BandMaxSAT，（W）PMS。 MAB是钢筋混凝土结构领域的一个基本模型[Slivkin s，2019;La tti more and d Sze pe sva′ r i，2020]。在MAB强化学习模型中，智能体需要选择拉动手臂（即，执行动作）在每个决策步骤（即，#21453;，这就带来了一些奖励。智能体使用奖励来评估拉动每个手臂的收益，并使用评估值来决定在每一步中要拉动的手臂。总之，MAB可用于帮助程序学习从多个候选项中选择适当的项。因此，我们提出应用MAB来帮助（W）PMS局部搜索算法学习选择适当的软子句（即，高质量的搜索方向）是满意的-arXiv：2201.05544v1 [cs.AI] 2022年1月+v：mala2277获取更多论文fied ， 每 当 搜 索 落 入 可 行 的 局 部 最 优 。 具 体 地 ，BandMaxSAT的bandit中的每个臂对应于输入（W）PMS实例中的软子句拉动臂意味着选择要在当前步骤中满足的相应子句有一些相关的研究将MAB应用于MaxSAT。例如，Goffinet和Ramanujan [2016]提出了一种基于蒙特卡洛树搜索的MaxSAT算法，其中双臂强盗与每个变量（搜索树中的节点）相关联以决定分支方向，即，将哪个布尔值赋给变量。他们的方法需要一个局部搜索求解器来评估分支节点的质量，因此性能依赖于局部搜索求解器。Lassouaoui等人。[2019]建议使用MAB在MaxSAT的超启发式框架中选择低级算法在他们的模型中拉动手臂意味着选择相应的低级启发式来优化当前的解决方案。它们没有与最先进的完整MaxSAT算法进行比较，而只是与其他超启发式方法进行比较。这项工作提出了一种新的MAB模型的（W）PMS和显着改善（W）PMS国家的最先进的本地搜索方法。据我们所知，这是第一次将MAB与（W）PMS局部搜索求解器中的子句相关联。此外，受SAT和MaxSAT研究的启发，SAT和MaxSAT优先考虑单位和二元子句（即， 分别具有恰好一个和两个 字面量 的子句 ）超过 其他子 句[Liet al. ， 2006;Kaufmann and Kottler，2011; Abrame 'and Habet，2014;Gonget al. ，2019]，我们提出了一种新的抽取方法，更倾向于满足单位和二进制条款，表示为混合抽取（Hy-Deci），用于生成BandMaxSAT中的初始分配。抽取方法是一类不完全方法，其通过顺序地分配一些（通常是一个）变量的布尔值来进行，并相应地简化公式[Caietal. ， 2017] 。 针 对 单 位 子 句 的 抽 取 方 法 已 用 于MaxSAT[Caiet al. ，2017; Caiand Lei，2020]. 然而，这是第一次，据我们所知，抽取方法集中在单位和二进制条款中使用的MaxSAT。实验结果表明，同时考虑单位分句和二元分句比只考虑单位分句要好。为了评估所提出的Band-MaxSAT算法的性能，我们将BandMaxSAT与最先进的（W）PMS局部搜索算法SAT-Like 3.0 进 行 了 比 较 [Cai 和 Lei ， 2020]。 实 验 表 明 ，BandMaxSAT 在 PMS 和 WPMS 上 的 性 能 都 明 显 优 于SATLike3.0此外，作为最先进的（W）PMS解算器之一，SATLike-c1将SATLike3.0与有效的完整解算器TT-Open-WBO-Inc2相结合，并在最新的MaxSAT评估（MSE2021）中赢得了四个不完整轨道（PMS和WPMS类别，每个类别与两个时间限制相关）中的三个类别。1https://maxsat-evaluations.github.io/2021/mse21-solver-src/i ncomplete/satlike-c.zip2https://maxsat-evaluations.github.io/2021/mse21-solver-src/i ncomplete/TT-Open-WBO-Inc-21.zip通过将BandMaxSAT与TT-Open-WBO-Inc相结合，所得求 解 器 BandMaxSAT-c 的 性 能 也 优 于 一 些 最 先 进 的（ W ） PMS 完 整 求 解 器 ， 包 括 SATLike-c 、 Loandra[Berget al. ，2019]和TT-Open- WBO-Inc.本工作的主要贡献如下：• 我们提出了一个多臂强盗（MAB）模型，适合与MaxSAT局部搜索算法，和一个有效的局部搜索求解器（W）PMS，称为Band-MaxSAT，应用所提出的强盗模型来指导搜索方向。• 我们表明，有一个很大的潜力，用于解决MaxSAT的MAB模型，我们提出的MAB模型是通用的，可以应用于改善其他MaxSAT局部搜索算法。• 我们提出了一种新的抽取方法（W）PMS，命名为HyDeci，更倾向于满足单位和二进制条款。HyDeci算法可以为BandMaxSAT算法提供高质量的初始分配，并可用于改进其他MaxSAT局部搜索算法。• 大量的实验表明，BandMaxSAT显着优于最先进的（W）PMS局部搜索算法，SATLike3.0。此外，通过将BandMaxSAT与完整求解器TT-Open-WBO-Inc组合，所得求解器BandMaxSAT-c的性能也优于最先进的（W）PMS完整求解器。2预赛给定一组布尔变量{x1，...， xn}，文字是变量本身xi或它的否定形式xi;子句是变量的否定形式，即， cj=lj1.其中nj是子句c j中的文字的数量。合取范式（CNF）公式F是子句的合取，即，F=c1... 布拉克山一个完整的赋值A表示一个映射，它将每个变量映射到一个值1（true）或0（false）。A literalxi（resp.如果当前分配将xi映射到1（相应地，0）。一个条款是由电流满足如果子句中至少有一个真文字，则使用租金赋值如果F中的所有子句都满足，则当前赋值满足CNF公式F给定CNF公式F，SAT是一个决策问题，的目的是确定是否存在满足F的赋值，并且MaxSAT是SAT的优化扩展，其目的是找到满足F中尽可能多的子句的赋值给定CNF公式F，其子句分为硬子句和软子句，PMS是MaxSAT的变体，其旨在找到满足所有硬子句的分配，并最大化F中满足的软子句的数量，并且WPMS是PMS的推广，其中每个软条款都是与非负权重相关。WPMS的目标是找到一个分配，满足所有的硬条款，并最大化满足条款的总重量在F。在（Max）SAT的局部搜索算法中，变量的翻转运算符是改变其布尔值的运算符给定一个（W）PMS实例F，一个完全指派A是可行的，如果它满足F中的所有硬子句。为方便起见，将A的成本（表示为cost（A））设置为+∞，如果A+v：mala2277获取更多论文是不可行的。否则，成本（A）等于PMS的伪造软条款的数量，并且等于WPMS的伪造软条款的总权重此外，有效子句加权技术广泛用于最近性能良好的（W）PMS局部搜索算法[Caiet al. ，2014; Luo等人，2017; Lei and Cai，2018; Cai and Lei，2020]。使用这种技术的算法将动态权重（独立于WPMS实例中的原始软子句权重）与子句相关联，并使用动态权重来指导搜索方向。我们的BandMaxSAT算法还应用了子句加权技术，并通过SATLike3.0中使用的子句加权策略来保持硬子句和软子句的动态权重[Cai和Lei，2020]。给定（W）PMS实例F、当前赋值A和动态子句权重，变量x的常用评分函数（表示为score（x））被定义为由翻转A中的x引起的满足子句。此外，（W）PMS的局部最优性表明不存在得分为正的变量。如果不存在伪造的硬子句，则局部最优解是可行的，否则是不可行的。3方法建议的多臂强盗本地搜索算法BandMaxSAT由建议的混合抽取（HyDeci）的初始化过程和搜索过程。在局部搜索过程中，我们使用与软子句相关联的多臂强盗来帮助BandMaxSAT学习选择好的方向以逃离可行的局部最优。本部分首先介绍了BandMaxSAT的HyDeci方法和Band-dit模型，然后介绍了BandMaxSAT的主要过程。3.1混合抽取HyDeci是一种有效的抽取方法，它更倾向于满足单位子句和二进制子句。由于长度较短的子句更容易被证伪，因此优先满足较短的子句可以减少证伪子句的数量，从而产生高质量的初始赋值。过程HyDeci在算法1中示出。我们使用SIMPLIFY来表示在为变量赋值后简化公式的过程HyDeci算法迭代地生成初始完全分配。在每次迭代中，HyDeci只分配一个变量的值。当有单元子句时，HyDeci先随机抽取一个单元子句（硬子句优先），然后满足它;当没有单元子句但有二元子句时，HyDeci先随机抽取一个二元子句c（硬子句优先），然后从c中两个未赋值的文字中选择一个，按照贪婪策略满足它，即，倾向于满足其满足导致更满意的软子句（或导致更大的满足软子句的总权重）的文字。当没有单位和二元子句时，Hy- Deci随机选择一个未赋值的变量，并随机为其赋值一个布尔值。算法1：HyDeci（F）输入：A（W）PMS实例F输出：F中变量的完整赋值A1 而未赋值的变量2如果使用硬单位子句，则3c：=随机硬单位子句;4满足c和SIMPLIFY;5. elseif不支持软单位子句，则6c：=随机软单位子句;7满足c和SIMPLIFY;8. else if不确定二元子句，则9c：=随机硬二元子句;10l：=c中一个greatest选择的未赋值的文字;11满足l和SIMPLIFY;12else if软二进制子句，则13c：=随机软二元子句;14l：=c中一个greatest选择的未赋值的文字;15满足l和SIMPLIFY;其他16个17v：=一个随机的未赋值变量;18给v分配一个随机值并SIMPLIFY;19返回结果的完整赋值A;Cai和Lei，2020]的一个重要特征是HyDeci不仅关注单位子句，而且关注二元子句。 实验结果表明，同时考虑单位子句和二元子句比只考虑单位子句更能生成高质量的初始赋值.3.2（W）PMS的多臂Bandit模型我们提出了一个多臂强盗模型（W）PMS，以帮助BandMaxSAT学习选择适当的软条款时，落入一个可行的局部最优值。强盗模型的每个分支对应于一个软子句。拉动臂意味着选择要在当前步骤中满足的相应软子句。强盗模型为每个臂保持估计值V（i）和选择的时间t（i(i.e.、软条款）i. 我们初始化V（i）=1和t（i）=0对于每个臂I.手臂的估计值越大拉动臂的益处越多，即，满足对应于ARM的软子句可以产生更好的解决方案。本小节的其余部分首先介绍选择要拉动的手臂的方法，然后介绍更新估计值的方法手臂选择策略BandMaxSAT使用置信上限结合法[Huet al. ，2019]在勘探和开采之间进行权衡，并选择要拉动的臂。具体地，利用以下公式计算臂i的估计值Vi的置信上限Ui.所提出的HyDeci算法相对于先前抽取方法的主要改进[Caiet al. ，2017年;Ui=Vi +λ·ln（N），（1）t（i）+1+v：mala2277获取更多论文∗∗∗∗′∗算法2：PickArm（Armstrong，N，λ）输入：采样臂数Armstrong、落入局部最优值的次数N、探测偏差参数λ输出：选择要拉动的臂c1 初始化U ：=−∞;2fori：= 1toArmando3j：=随机伪造的软子句;算法3：BandMaxSAT输入：A（W）PMS实例F、截止时间截止、BMS参数k、奖励延迟步长d、奖励折扣因子γ、采样武器装备，勘探偏差参数λ输出：F的可行分配A，或未找到可行分配1A：=HyDeci（F）;4个计算器U根据Eq.1个;5ifUj>UthenU：=Uj，c：=j;2 A：=A，成本（A′）：= +∞，N：= 0;3 当运行时间截止<时，∗6t（c）：=t（c）+1;7 returnc;如果A是可行成本（A）<，则&5A ：=A;6ifD：={x|score（x）>0}{\displaystyle {\frac {x}7其中N表示落入可行8局部最优，λ是勘探偏差参数。9选择臂的过程如Algo-10Rithm2. 因为我们的强盗有大量的武器11（等于软条款的数量），选择最佳的12个所有的武器都是低效的。 BandMaxSAT13首先应用（第3行）采样策略来随机地采样，14 选择手臂（默认为20）候选手臂，然后se-15选择具有最高置信上限的手臂，16候选人（第4-5行）。 类似的抽样策略有被用于多武装土匪问题[Ouet al. ，2019年]17v：=BMS（k）选取的D中的变量其他return（）;如果你伪造了硬性条款，c：=随机伪造的硬子句;其他更新估计值（A，A′，Aβ，d，γ）;N：=N+1，A′：=A;c：=PickArm（Arm，N，λ）v：=c中得分最高的变量;A：=v翻转后的A和一些组合优化问题[Cai，2015;Lei和Cai，2018]。注意，bandit旨在选择要在当前步骤中满足的软子句。因此，对应于当前赋值所满足的软子句的臂将不被视为候选。实验结果表明，我们的强盗模型中的采样策略可以显着提高算法的性能。估计值更新策略由于BandMaxSAT在落入可行局部最优时拉动强盗的手臂，因此我们应用拉动手臂之前和之后的可行局部最优解的成本值来计算动作的奖励（即，拉手臂）。设A′和A是最后一个和当前可行局部18 如果 是可行的，则返回A;19else返回未找到;这不仅是由于最后一次行动，也是由于先前的行动。为了 处 理 这 个 问 题 ， 我 们 应 用 延 迟 奖 励 方 法 [Arya 和Yang，2020]来更新获得奖励后最后d（默认为20）拉臂的估计具体地说，假设A′和A是最后一个，当前可行局部最优解，A是到目前为止找到的最佳解决方案，以及{a1，...，ad}是最近d个拉动的臂的集合（ad是最近的一个）。 然后d类武器的估计值更新如下：最优解，并且c是最后拉动的手臂，拉动c的简单奖励可以设置为r=cost（A′）-VAI=Vai +γd−i·r（A，A′，A），i ∈ {1，.，d}，⑶成本（A）。 但是，将成本值从20减少到10，比从1000人减少到1000人更难更有意义到990。因此，这两种情况的奖励不应该是相同的。为了解决这个问题，我们将奖励定义如下：′成本（A′）−成本（A）r（A，A，A）=，（2）cost（A）-cost（A）+1其中A是迄今为止找到的最佳解。如果你假设cost（A′）-cost（A）在方程中是常数。2，则成本（A′）和成本（A）越接近，拉动最后一只手臂的动作所能产生的奖励越多，这是合理的和直观的。是的。此外，由于武器（即，软条款）由变量连接，我们假设我们的强盗模型中的臂不是彼此独立的。我们还认为，A对A′的改善（或恶化）可能其中γ是奖励折扣因子。3.3BandMaxSAT的主要流程最后介绍了BandMaxSAT算法的主要过程，如算法3所示。BandMaxSAT首先使用所提出的HyDeci算法来生成初始分配（第1行），然后重复选择一个变量并翻转它，直到达到截止时间（第3-17行）。当未达到局部最优值时，BandMaxSAT使用多选择最佳（BMS）策略选择要翻转的变量[Cai，2015]。 BMS选择 k个随机变量（带替换），并返回得分最高的一个（第6-7行）。当落入局部最优时，BandMaxSAT首先根据SAT中的子句加权方案更新动态子句权重（通过第9行中的update clause weight（）函数）+v：mala2277获取更多论文C+1Like3.0[Cai和Lei，2020]，然后选择要在当前步骤中满足的子句如果局部最优不可行，BandMaxSAT随机选择一个伪造的硬子句作为当前步骤中要满足的子句（第10-11行 ） 。 如 果 局 部 最 优 值 是 可 行 的 （ 第 12-15 行 ） ，BandMaxSAT首先根据等式（1）更新最近d个被3，然后使用PickArm（）函数（算法2）来选择要在当前步骤中满足在确定基准#inst.BandMS SATLike3.0#赢时间#赢 时间WPMS 2018172118114.7605173.677WPMS 2019297210108.46710375.496WPMS 2020253170137.4468881.809WPMS 202115189145.8685589.704PMS 201815311099.1485480.390PMS 201929920467.93314353.662PMS 202026217473.90911963.181PMS 202115511268.6636051.769表1：BandMS和SATLike3.0的比较要满足子句c，BandMaxSAT翻转变量在当前步骤中具有C中的最高分数（第16行）。4实验结果我们与最先进的（W）PMS局部搜索算法SATLike3.0[Cai和Lei，2020]以及一些最先进的完整求解器SATLike-c，Loandra [Berget al. ，2019]和TT-Open-WBO-Inc. 实验结果表明，我们提出的BandMaxSAT算法的优良性能，显着提高最佳（W）PMS局部搜索求解器。仿真结果还表明了BandMaxSAT中各个组成部分的有效性，包括HyDeci初始化方法、采样策略和延迟奖励方法。4.1实验装置BandMaxSAT是用C++实现的，用g++编译。我们的实验在使用In-tel ® Xeon® E5-2650 v3 2.30 GHz 10核CPU和256 GB RAM、运行Ubuntu 16.04 Linux操作系统的服务器上进行。我们在来自最后四次MaxSAT评估（MSE）的不完整跟踪的所有（W）PMS实例上测试了算法，即，MSE2018-MSE2021。请注意 ，我们将包含 MSE2021未完成跟踪中所有PMS/WPMS实例的基准标记表示为PMS 2021/WPMS 2021，依此类推。每个实例由每个算法计算一次，时间限制为300秒，这与MSE中的设置一致表中的最佳结果以粗体显示此外，我们在表中使用BandMS作为BandMaxSAT的简称BandMaxSAT中的参数包括BMS参数k、奖励延迟步长d、奖励折扣因子γ、采样臂数Armstrong和探索偏差参 数 λ 。 我 们 使 用 来 自 MSE2017 不 完 整 跟 踪 的 所 有（W）PMS实例作为训练集来调整这些参数。这些参数的参数域如下：对于k，[10，50]，对于d，[1，50]，[0.5，1]对于γ，[10，50]对于Armstrong，以及[0. 1，10]对于λ。最后，默认设置-这些参数的取值如下：k=15，d=20，基准BandMS-cSATLike-c 洛 安德拉TT-OWIWPMS 20180.90410.89010.88200.9026WPMS 20190.89740.88190.84740.9022WPMS 20200.87070.86130.80430.8655WPMS 20210.78440.78090.78330.7729PMS 20180.85370.84400.78110.8412PMS 20190.87930.87450.78180.8713PMS 20200.86190.85110.82160.8586PMS 20210.85920.85380.77140.8436表2：BandMS-c和最先进的（W）PMS完整解算器的结果由MSE 2021中使用的评分函数表示。列时间表示产生列的平均运行时间。#赢实例.如表1中的结果所示，BandMaxSAT（BandMS）对于PMS和WPMS都显著优于SATLike3.0。特别是#赢了。Band-MaxSAT的实例比WPMS的SATLike3.0的实例大62-131%，并且比PMS的SATLike3.0的实例大43-103%，表明显著的改进。4.3与完全解算器的比较然后，我们将我们的BandMaxSAT局部搜索算法与完整的 求 解 器 TT-Open-WBO-Inc （ TT-OWI ） 组 合 ， 如SATLike-c所做的（其将SATLike3.0与TT-OWI组合），并将所得的求解器表示为BandMaxSAT- c（BandMS-c）。我们进一步将BandMaxSAT-c与一些最先进的完整（W）PMS求解器进行了比较，这些求解器在最近的MSE中表现出出色的性能，包括SATLike-c，Loandra和TT-OWI。我们应用MSE20213中使用的评分函数来评估这四个求解器的性能，因为评分函数适合于评估和比较多个求解器。评分函数实际上表示解与最佳已知解的接近程度具体来说，假设CBKS是记录在MSEs，Ci是在我们的实验中由第i个求解器（i∈ {1，2，3，4}）找到的解决方案的成本，γ= 0。9，Armstrong= 20，λ= 1。此实例为min（CBKS，C1，C2，C3，C4）+1我[0，1]（resp. 0个）4.2 BandMaxSAT和SATLike3.0我们首先比较BandMaxSAT与最先进的（W）PMS本地搜索算法，SAT- Like3.0[Cai和Lei，2020]，在所有测试实例上。 结果示于表1中。列#inst.表示每个基准中的实例数 列#win。如果由求解器i找到的解是可行的（相应地，不可行）。最后，求解器对基准的得分是基准中所有实例得分的平均值。这四个求解器的比较结果如表2所示。BandMaxSAT-c在除WPMS 2019之外的所有基准测试中得分最高，证明了我们所提出的方法的出色性能。指示算法在在表中的所有算法中产生最佳解3https://maxsat-evaluations.github.io/2021/rules.html+v：mala2277获取更多论文基准#inst.BandMSBandMS样品-1BandMSsample-all#赢时间#赢 时间#赢时间WPMS 2018172100102.0366266.4676574.153WPMS 2019297188100.34811773.20511878.906WPMS 2020253160127.4289681.85810094.542WPMS 202115180134.93853114.8904690.905PMS 201815310287.7467459.4486765.777PMS 201929919165.34516453.26213059.263PMS 202026216867.37813954.28311166.207PMS 202115510965.6138336.2447249.407表3：BandMS及其变体、BandMS样品-1、BandMS样品-全部的比较。基准#inst.#赢BandMS时间乐队#赢了。MS无延迟时间WPMS 2018172117108.9598564.596WPMS 2019297187106.77616587.298WPMS 2020253161130.91213391.498WPMS 202115189140.16464112.615PMS 201815311391.9929757.003PMS 201929920266.13619158.396PMS 202026218171.78115843.552PMS 202115510860.9809748.911表4：BandMS及其变体BandMS无延迟的比较。4.4消融研究最后，我们进行消融研究， 效果分析 BandMaxSAT中的每个组件。我们首先将BandMaxSAT与其两个变体进行比较，以评估采样战略在的强盗模型的第一一个是BandMaxSAT sample-1，它是BandMaxSAT的一个变体，它将参数Armstrong设置为1，它实际上用Dist中使用的简单随机策略替换了BandMaxSAT中的整个 强 盗 模 型 [Caiet al. ， 2014] ， CCEHC [Luoet al. ，2017]，SATLike [Lei和Cai，2018]和SATLike3.0 [Cai和Lei ， 2020] 。 第 二 个 是 BandMaxSATsample-all ， 这 是BandMaxSAT的一个变体，它重新移动了Bandit模型中的采样策略，即，通过遍历所有可用的臂来选择要被拉动的臂。结果示于表3中。表3中的结果表明，我们的bandit模型明显优于最近（W）PMS局部搜索算法中广泛使用的随机策略，可以大大提高性能。此外，我们的强盗模型中使用的抽样策略是有效的和必要的。然 后 ， 我 们 将 BandMaxSAT 与 其 另 一 个 变 体BandMaxSAT无延迟进行比较，将参数d设置为1，以评估延迟奖励方法。结果示于表4中。结果表明，延迟奖励法能较好地解决武器装备质量评估中存在的问题，能帮助Band-MaxSAT系统更好地评估武器装备质量。我们进一步做了两组实验来评估所提出的HyDeci初始化方法。第一组将BandMaxSAT与其变体BandMaxSAT非二进制进行比较，其不优先化HyDeci中的二进制子句（即，重 新 移 动 算 法 1 中 的 第 8-15 行 ） 。 第 二 组 比 较 了BandMaxSAT的两种变体。它们是，BandMaxSATfast，BandMaxSAT的一个变体，输出它找到的第一个可行解（在300秒的时间限制内），和BandMaxSATno-binary-fast，BandMaxSATno-binary的一个变体，输出它找到的第一个可行 解 。 我 们 实 际 上 使 用 BandMaxSATfast 和BandMaxSATno-binary-fast来粗略评估初始分配的质量。的结果基准#inst.BandMSBandMS非二进制#赢时间#赢 时间WPMS 2018172105110.1138694.172WPMS 2019297190104.24216593.956WPMS 2020253161129.541135103.390WPMS 202115189146.35976119.976PMS 2018153100107.7999879.069PMS 201929920376.27520163.905PMS 202026217880.20217663.129PMS 202115510272.0009242.792表5：BandMS及其变体BandMS非二进制的比较。基准#inst.BA#赢ndMS快速时间BandMS#win。非二进制快速时间WPMS 2018172919.695893.148WPMS 2019297 16210.8021657.308WPMS 202025315013.18313611.356WPMS 20211519018.4936915.617PMS 2018153946.146904.635PMS 20192991885.0581684.722PMS 20202621664.6161473.746PMS 2021155897.165795.126表6：BandMS的两种变体、BandMS快速、BandMS非二进制快速的比较。这两组分别示于表5和表6从表5和表6中的结果，我们可以看出：(1) BandMaxSAT fast在除了WPMS 2019之外的所有基准测试中都优于BandMaxSAT no-binary-fast，这表明我们优先考虑单元和二进制子句的方法可以比只优先考虑单元子句的方法产生更好的初始赋值。(2) BandMaxSAT优于BandMaxSAT非二进制的WPMS，表明我们的HyDeci方法是有效的，可以提高BandMaxSAT的WPMS。对于PMS，这两种算法具有接近的性能，表明BandMaxSAT中的局部搜索过程对于PMS是鲁棒的，因为BandMaxSAT非二进制可以获得与BandMaxSAT相似质量的PMS解，而初始分配更差5结论本 文 提 出 了 一 种 多 臂 强 盗 局 部 搜 索 求 解 器 ， 称 为BandMaxSAT 部 分 最 大 SAT （ PMS ） 和 加 权 PMS（WPMS）。当算法陷入可行局部最优时，所提出的Bandit模型可以帮助局部搜索学习选择一个合适的软我们进一步应用抽样策略和延迟奖励方法改进了我们的强盗模型。因此，强盗模型与（W）PMS非常吻合。此外，我们提出了一个有效的初始化方法称为HyDeci，优先单位和二元子句时，产生初始分配。Hy-Deci算法可以提供高质量的初始分配，从而提高BandMaxSAT算法的性能，并对其他MaxSAT局部搜索算法的改进有一定的借鉴意义。对来自最后四个MSE的不完整轨迹的所有（W）PMS实例的广泛实验表明，BandMaxSAT显著优于最先进的（W）PMS局部搜索算法SATLike3.0。此外 ， 通 过 将 BandMaxSAT 与 完 整 的 求 解 器 TT-Open-WBO-Inc相结合，得到的求解器BandMaxSAT-c的性能优 于 完 整 的 求 解 器 SATLike- c 、 Loandra 和 TT-Open-WBOInc。+v：mala2277获取更多论文设计局部搜索算法的关键问题是如何跳出局部最优，找到新的高质量的搜索方向。在未来的工作中，我们计划推广我们的band-dit模型，以改善其他局部搜索算法的各种NP难问题，需要选择多个候选人之一，以摆脱局部最优。引用[Abrame 'and Habet ， 2014] Andre' Abrame 'and DjamalHa- bet.Ahmaxsat：描述和评估分支和边界Max-SAT求解器。Journal on Satisfiability，Boolean Modelingand Computation，9（1）：89[Arya and Yang，2020] Sakshi Arya and Yuhong Yang.具有延迟报酬的上下文多武器土匪的非参数估计的随机分配统计概率快报，164：108818，2020。[Berg et al. JeremyBerg，Emir Demirovic，and Pe- ter J.Stuckey.不完全MaxSAT的核心提升线性搜索。在约束编程，人工智能和运筹学的集成-第16届国际会议，CPAIOR 2019，第11494卷，第39-56页[Bonetal. ，2019]BlaiBonett，GuillemFranc`s，anddHec-tor Geffner.学习计算广义计划的特征和抽象动作。在第三十三届AAAI人工智能会议，AAAI 2019，第2703-2710页[蔡和雷，2020]蔡少伟和雷振东。新方法中的旧技术：子句加权、单元传播和杂交以实现最大可满足性。商业情报，287：103354，2020。[Cai et al. 2014] Shaowei Cai ， Chuan Luo ， JohnThornton，and Kaile Su.为局部MaxSAT定制本地搜索。在The Twenty-Eighth AAAI Conference on ArtificialInteligence，AAAI 2014，第2623-2629页[Cai et al. ， 2017] Shaowei Cai ， Chuan Luo ， andHaochen Zhang.从抽取到局部搜索再返回：MaxSAT的新方法。在第二十六届国际人工智能联合会议上，IJCAI 2017，第571-577页[Cai，2015] Shaowei Cai.复杂性与质量的平衡：大规模图中最小顶点覆盖的局部搜索在第二十四届国际人工智能联合会议，IJCAI 2015，第747[Ciampiconi et al. Lorenzo Ciampiconi ， Bishwamit-traGhosh