Combining solutions of the optimum satisfiability problem using evolutionary tunneling
Peer reviewed, Journal article
Published version
View/ Open
Date
2020Metadata
Show full item recordCollections
- Artikler [415]
- Publikasjoner fra Cristin [432]
Original version
The MENDEL Soft Computing Journal : International Conference on Soft Computing MENDEL. 2020, 26 (1), 23-29. 10.13164/mendel.2020.1.023Abstract
The optimum satisfiability problem involves determining values for Boolean vari- ables to satisfy a Boolean expression, while maximizing the sum of coefficients associated with the variables chosen to be true. Existing literature has identified a tabu search heuristic as the best method to deal with hard instances of the prob- lem. This paper combines the tabu search with a simple evolutionary heuristic based on the idea of tunneling between local optima. When combining a set of solutions, variables with common values in all solutions are identified and fixed. The remaining free variables in the problem may be decomposed into several in- dependent subproblems, so that parts of the solutions combined can be extracted and combined in an improved solution. This solution can be further improved by applying the tabu search in an improvement stage. The value of the new heuristic is demonstrated in extensive computational experiments on both existing and new test instances. Keywords: zero-one integer programming, boolean optimization, metaheuristic, tabu search, adaptive memory programming, recombination operator.
Keywords: zero-one integer programming, boolean optimization, metaheuristic, tabu search, adaptive memory programming, recombination operator