Comparison Study of Particle Swarm Optimization and Differential Evolution Methods for Solving SAT Problem Using nVidia CUDA Framework

Abstract

The satisfiability problem (SAT) is a constitutive decision problem for mathematical logic, VLSI engineering and computational theory. Uniform random 3 Boolean satisfiability problem is a type of SAT problem which consists of randomly generated clauses with 3 literals. In this study, two population based metaheuristic algorithms, particle swarm optimization (PSO), differential evolution (DE) were implemented to solve uniform random 3 Boolean satisfiability problem on both CPU and GPU through nVidia CUDA framework. Moreover the performance comparison of both algorithms was done in terms of solution quality, running time and speedup performance between CPU and GPU. The novel contribution of the study into the literature is comparison of PSO and DE algorithms in GPU to solve uniform random 3 Boolean satisfiability problem. As the results of the study; PSO find the best optimal solution for the problem rather than DE algorithm. In addition to this, solving this problem on GPU results nearly 11.95-30.4 times for PSO and 7.21-18.04 times for DE faster than CPU implementation.