Evolutionary Diversity Optimisation in Constructing Satisfying Assignments
Date
2023
Authors
Nikfarjam, A.
Rothenberger, R.
Neumann, F.
Friedrich, T.
Editors
Paquete, L.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO, 2023), 2023 / Paquete, L. (ed./s), vol.abs/2305.11457, pp.938-945
Statement of Responsibility
Adel Nikfarjam, Ralf Rothenberger, Frank Neumann, Tobias Friedrich
Conference Name
Genetic and Evolutionary Computation Conference (GECCO) (15 Jul 2023 - 19 Jul 2023 : Lisbon, Portugal)
Abstract
Computing diverse solutions for a given problem, in particular
evolutionary diversity optimisation (EDO), is a hot research topic
in the evolutionary computation community. This paper studies the
Boolean satis!ability problem (SAT) in the context of EDO. SAT is
of great importance in computer science and di"ers from the other
problems studied in EDO literature, such as KP and TSP. SAT is
heavily constrained, and the conventional evolutionary operators
are ine#cient in generating SAT solutions. Our approach avails of
the following characteristics of SAT: 1) the possibility of adding
more constraints (clauses) to the problem to forbid solutions or to !x
variables, and 2) powerful solvers in the literature, such as minisat.
We utilise such a solver to construct a diverse set of solutions.
Moreover, maximising diversity provides us with invaluable
information about the solution space of a given SAT problem, such
as how large the feasible region is. In this study, we introduce
evolutionary algorithms (EAs) employing a well-known SAT solver
to maximise diversity among a set of SAT solutions explicitly. The
experimental investigations indicate the introduced algorithms’
capability to maximise diversity among the SAT solutions.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.