Alex S. Fukunaga
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Latest Publications
- 5 November 2009
- Published by Springer Nature in Annals of Operations Research
- Vol. 184 (1) , 97-119
A branch-and-bound algorithm for hard multiple knapsack problems
- 5 November 2009
- Published by Springer Nature in Annals of Operations Research
- Vol. 184 (1) , 97-119
A branch-and-bound algorithm for hard multiple knapsack problems
- 1 March 2008
- Published by MIT Press in Evolutionary Computation
- Vol. 16 (1) , 31-61
Automated Discovery of Local Search Heuristics for Satisfiability Testing
The development of successful metaheuristic algorithms such as local search for a difficult problem such as satisfiability testing (SAT) is a challenging task. We investigate an evolutionary approach to automating the discovery of new local search heuristics for SAT. We show that several well-known SAT local search algorithms such as Walksat and Novelty are composite heuristics that are derived from novel combinations of a set of building blocks. Based on this observation, we developed CLASS, a genetic programming system that uses a simple composition operator to automatically discover SAT local search heuristics. New heuristics discovered by CLASS are shown to be competitive with the best Walksat variants, including Novelty+. Evolutionary algorithms have previously been applied to directly evolve a solution for a particular SAT instance. We show that the heuristics discovered by CLASS are also competitive with these previous, direct evolutionary approaches for SAT. We also analyze the local search behavior of the learned heuristics using the depth, mobility, and coverage metrics proposed by Schuurmans and Southey.
- 1 March 2008
- Published by MIT Press in Evolutionary Computation
- Vol. 16 (1) , 31-61
Automated Discovery of Local Search Heuristics for Satisfiability Testing
The development of successful metaheuristic algorithms such as local search for a difficult problem such as satisfiability testing (SAT) is a challenging task. We investigate an evolutionary approach to automating the discovery of new local search heuristics for SAT. We show that several well-known SAT local search algorithms such as Walksat and Novelty are composite heuristics that are derived from novel combinations of a set of building blocks. Based on this observation, we developed CLASS, a genetic programming system that uses a simple composition operator to automatically discover SAT local search heuristics. New heuristics discovered by CLASS are shown to be competitive with the best Walksat variants, including Novelty+. Evolutionary algorithms have previously been applied to directly evolve a solution for a particular SAT instance. We show that the heuristics discovered by CLASS are also competitive with these previous, direct evolutionary approaches for SAT. We also analyze the local search behavior of the learned heuristics using the depth, mobility, and coverage metrics proposed by Schuurmans and Southey.