ParLS-PBO：一种针对伪布尔优化的并行局部搜索求解器
内容提要
本文探讨了提高局部搜索算法效率的方法，提出了新的局部搜索算法SPB-MaxSAT和加权布尔优化框架，实验结果表明其性能优于现有算法。此外，介绍了多目标PBO框架及其在个性化设计任务中的应用，验证了其有效性和收敛性。
延伸解读
并行局部搜索的机制创新
文章通过单位传播等机制将伪布尔优化问题广义化，并利用措辞作为桥梁增强理解，从而提升局部搜索算法效率。实验表明，这种广义化方法使算法性能优于现有算法。这提示读者，在解决PBO问题时，对问题结构的重新表述和机制引入可能比单纯优化搜索策略更有效。
SPB-MaxSAT与加权布尔优化的进展
研究提出了新的局部搜索算法SPB-MaxSAT，为MaxSAT局部搜索的子句权重方法提供了新视角和优秀性能。同时，加权布尔优化的新统一框架及基于不可满足性的算法，比现有专用算法更有效，并能处理非常规伪布尔约束。这些进展表明，统一框架和不可满足性驱动的方法在复杂约束优化中具有潜力。
多目标PBO框架与DSTS的应用
文章提出了第一个多目标PBO框架，并介绍了dueling scalarized Thompson sampling（DSTS）。在多个测试函数和模拟的个性化外骨骼及驾驶政策设计任务中，DSTS优于其他基准算法，并具有渐进一致性，提供了首个收敛保证。这说明多目标PBO在个性化设计任务中具有实际应用价值，且DSTS的收敛性为其可靠性提供了理论支持。
元求解器与多项式模型优化的表现
针对NP-Hard的伪布尔优化问题，构建的任意时刻元求解器明显提高了性能，并改进了Gurobi在组合求解器组合中的成功率。此外，基于多项式模型的优化方法（PMBO）在低维优化问题中表现出色，与经典贝叶斯优化和进化算法相比，具有更好的鲁棒性和解释性。这些成果提示，元求解器和多项式模型在特定场景下能有效提升优化效果。
Q&A
什么是伪布尔优化问题？
伪布尔优化问题（PBO）是一类优化问题，涉及布尔变量的组合，通常用于决策和设计任务中。
SPB-MaxSAT算法的优势是什么？
SPB-MaxSAT算法在MaxSAT局部搜索中表现优越，提供了新的视角和更好的性能。
加权布尔优化的新框架有什么创新之处？
新框架通过基于不可满足性的算法提供解决方案，显著提高了加权布尔优化的效率。
多目标PBO框架的应用场景有哪些？
多目标PBO框架可用于个性化设计任务，如外骨骼和驾驶政策设计，表现优越。
PLAyBOOK方法如何提高超参数调优效率？
PLAyBOOK通过异步并行计算，显著提高了超参数调优的效率，减少了时间和函数评估次数。
本文提出的优化方法在低维问题中表现如何？
采用多项式模型优化方法在低维优化问题中表现出色，具有更好的鲁棒性和解释性。
