Abstract
Satisfiability in propositional logic is well researched and many approaches to checking and solving exist. In infinite-valued or fuzzy logics, however, there have only recently been attempts at developing methods for solving satisfiability. In this paper, we propose a new incomplete solver, based on a class of continuous optimization algorithms called evolution strategies. We show experimentally that our method is an important contribution to the state of the art in incomplete fuzzy-SAT solvers.
Introduction
In classical logic, statements are binary: true or false. Fuzzy logic extends this by allowing truth values to exist on a continuous spectrum within the interval $[0, 1]$. Finding variable assignments that satisfy a set of fuzzy formulas, known as the $SAT_\infty$ problem, is critical for fields such as the Semantic Web and non-monotonic reasoning.
Traditional approaches to $SAT_\infty$ typically rely on Mixed Integer Programming (MIP) or discretization. MIP often struggles with scalability, while discretization—converting the continuous interval into finite steps—faces a "granularity gap." If a problem requires high precision (e.g., a truth value of 0.99), discretization-based solvers must use extremely fine steps, leading to an exponential increase in search space complexity.
Methodology
This research proposes treating $SAT_\infty$ as a continuous optimization problem rather than a discrete search.
The Objective Function
Logical formulas are transformed into a continuous "fitness landscape." For a formula $\alpha_i$ with a required truth range $[l_i, u_i]$, a trapezoid function $f_i(\alpha_i)$ is defined. The function returns 1 if the truth value is within the bounds and decreases linearly to 0 outside them.
The objective is to find an interpretation that maximizes the average score across all formulas to 1.
The Solver: CMA-ES
To navigate this landscape, the authors employ the Covariance Matrix Adaptation Evolution Strategy (CMA-ES). CMA-ES is a derivative-free optimization algorithm that adapts a covariance matrix to learn the topography of the objective function, making it highly effective at finding global maxima in complex, multi-modal continuous spaces.
Experimental Evaluation
The solver was tested against "Minion," a state-of-the-art constraint satisfaction solver using discretization, across two datasets in Łukasiewicz logic:
- Benchmark [11]: 200 instances with "coarse" bounds (multiples of 0.25).
- New Benchmark: A "fine-grained" dataset with bounds drawn from 100 discrete steps (multiples of 0.01) to test the limits of discretization.
Results and Discussion
The experiments revealed a significant performance shift based on problem granularity.
On the coarse benchmark, both solvers performed comparably in terms of total instances solved, though Minion was faster on the problems it could handle. However, on the fine-grained benchmark, Minion's performance plummeted, solving only 42 instances. In contrast, CMA-ES remained robust, solving 118 instances. This demonstrates that CMA-ES is far less sensitive to the precision of constants within the formulas.
Conclusion
By reframing fuzzy satisfiability as a continuous optimization task, this paper provides a robust alternative to discretization-based methods. While traditional solvers excel at low-granularity problems, evolution strategies like CMA-ES offer superior reliability for high-precision fuzzy logic applications. Future work will explore restart strategies and discrete recombination to further improve solver efficiency and escape local optima.
Summary updated