Asynchronous Evolutionary Algorithm for Finding Backdoors in Boolean Satisfiability
Artem Pavlenko, Чивилихин Даниил Сергеевич, Alexander Alexeevich Semenov · 2022 IEEE Congress on Evolutionary Computation (CEC) · 2022
In this work we propose an asynchronous parallel evolutionary algorithm that is efficient for a specific type of gray-box optimization problems, in which the calculation of the fitness function may be split into a set of several independent calculations. An example of such an optimization problem is the search for backdoors (hidden structures) in the Boolean satisfiability problem: subsets of variables that allow an efficient splitting of the problem into a set of independent subproblems. Our experiments show that the proposed asynchronous approach allows speeding up the algorithm considerably, while also effi-ciently utilizing comnuting cluster time.