最小冲突启发式辅助离散的海洋捕食者求解RB模型

打开文本图片集

关键词： RB 模型; 约束可满足问题; 海洋捕食者算法; 元启发式; 最小冲突启发式中图分类号： TP301 文献标志码： ADOI： 10.13705/j . issn. 1671-6841. 2023260

文章编号： 1671-6841（2025）04-0071-09

Abstract： The revised B （ RB） model was a stochastic instance model that possessed an exact phasechange growth domain in constraint-satisfiable problems. A solution algorithm was proposed for solving RB model instances， based on a combination of meta-heuristics and local search. Utilizing the marine predator algorithm， the initial solution space was discretized by real coding， and the three core phases of the marine predator algorithm were optimized. The current candidate solutions were targeted to guide the search towards the optimal solution. In the final stage， with the assistance of the local search method， the current optimal solution was passed to the minimum-conflict heuristic of the annealing strategy when the resulting optimal solution failed to satisfy the solution of the RB model instances， further enhancing the algorithm′s solving efficiency. Experimentally， the algorithm was shown to be significantly more accurate and time-efficient than many other heuristic algorithms. It demonstrated the potential of high probability solution even when it was close to the satisfiability phase transition point.

Key words： RB model; constraint satisfiability problem; marine predators algorithm; meta heuristic; minimum conflict heuristic

0 引言

约束 可 满 足 问 题 （ constraint satisfiability prob-lem， CSP）是人工智能科学领域中一个重要的研究方向，许多实际的优化问题都可以建模转化为 CSP，这使得 CSP 通过运用不同编码方式的可满足性判定问题（ satisfiability problem，SAT） 更加拟合现实问题中的约束关系。（剩余13778字）