Solving satisfiability in fuzzy logics with evolution strategies

Tim Brys, Yann-Michaël De Hauwere, Martine De Cock, Ann Nowé2012 · DOI

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 trapezoid function used to map fuzzy truth values to a fitness score.

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:

  1. Benchmark [11]: 200 instances with "coarse" bounds (multiples of 0.25).
  2. 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.

Comparison of instances solved by Minion and CMA-ES across coarse and fine-grained benchmarks.

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

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.
BibTeX
@misc{brys2012solving,
  author = {Tim Brys and Yann-Michaël De Hauwere and Martine De Cock and Ann Nowé},
  title = {{Solving satisfiability in fuzzy logics with evolution strategies}},
  year = {2012},
  doi = {10.1109/nafips.2012.6290998},
}
Figure