MAX-SAT problem using evolutionary algorithms
Hafiz Munsub Ali, David G. M. Mitchell, Daniel C. Lee · IEEE Symposium on Swarm Intelligence (SIS) · 2014
MAX-SAT is a classic NP-hard optimization problem. Many real problems can be easily represented in, or reduced to MAX-SAT, and thus it has many applications. Finding optimum solutions of NP-hard optimization problems using limited computational resources seems infeasible in general. In particular, all known exact algorithms for MAX-SAT require worst-case exponential time, so evolutionary algorithms can be useful for finding good quality solutions in moderate time. We present the results of an experimental comparison of the performance of a number of recently proposed evolutionary algorithms for MAX-SAT. The algorithms include the Artificial Bee Colony (ABC) algorithm, Quantum Inspired Evolutionary Algorithm (QEA), Immune Quantum Evolutionary Algorithm (IQEA), Estimation of Distribution Algorithm (EDA), and randomized Monte Carlo (MC). Our experiments demonstrate that the ABC algorithm has better performance than the others. For problems with Boolean domain, such as MAX-SAT, the ABC algorithm requires specification of a suitable similarity measure. We experimentally evaluate the performance of the ABC algorithm with five different similarity measures to indicate the better choice for MAX-SAT problems.
Cited by 6 works. doi:10.1109/sis.2014.7011783
Authors
References
- A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm
- The wisdom of the hive: the social physiology of honey bee colonies
- The Wisdom of the Hive—the Social Physiology of Honey Bee Colonies
- Boolean satisfiability from theoretical hardness to practical success
- DisABC: A new artificial bee colony algorithm for binary optimization
- Evolving radial basis function networks via GP for estimating fitness values using surrogate models
- Wireless Mesh Network Planning Using Quantum Inspired Evolutionary Algorithm
- Inference Rules in Local Search for Max-SAT
- Binary Artificial Bee Colony for cooperative relay communication in cognitive radio systems
- pEvoSAT