Evolutionary Diversity Optimisation in Constructing Satisfying Assignments
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 satisfiability problem (SAT) in the context of EDO. SAT is of great importance in computer science and differs from the other problems studied in EDO literature, such as KP and TSP. SAT is heavily constrained, and the conventional evolutionary operators are inefficient 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 fix 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.
Code (0)
등록된 구현이 없습니다.
Tasks
DiversityEvolutionary AlgorithmsMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem
Recently different evolutionary computation approaches have been developed that generate sets of high quality diverse solutions for a given optimisation problem. Many studies have considered diversity 1) as a mean to exp…
DiversityComputing High-Quality Solutions for the Patient Admission Scheduling Problem using Evolutionary Diversity Optimisation
Diversification in a set of solutions has become a hot research topic in the evolutionary computation community. It has been proven beneficial for optimisation problems in several ways, such as computing a diverse set of…
DiversitySchedulingEvolutionary Diversity Optimisation for The Traveling Thief Problem
There has been a growing interest in the evolutionary computation community to compute a diverse set of high-quality solutions for a given optimisation problem. This can provide the practitioners with invaluable informat…
DiversityInvestigating the effects Diversity Mechanisms have on Evolutionary Algorithms in Dynamic Environments
Evolutionary algorithms have been successfully applied to a variety of optimisation problems in stationary environments. However, many real world optimisation problems are set in dynamic environments where the success cr…
DiversityEvolutionary AlgorithmsEntropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem
Computing diverse sets of high-quality solutions has gained increasing attention among the evolutionary computation community in recent years. It allows practitioners to choose from a set of high-quality alternatives. In…
Diversity