Stochastic Approximation Algorithms for Number Partitioning
Citation
Ruml, Wheeler. 1993. Stochastic Approximation Algorithms for Number Partitioning. Harvard Computer Science Group Technical Report TR-17-93.Abstract
This report summarizes research on algorithms for finding particularly good solutions to instances of the NP-complete number-partitioning problem. Our approach is based on stochastic search algorithms, which iteratively improve randomly chosen initial solutions. Instead of searching the space of all 2^(n-1), possible partitionings, however, we use these algorithms to manipulate indirect encodings of candidate solutions. An encoded solution is evaluated by a decoder, which interprets the encoding as instructions for constructing a partitioning of a given problem instance. We present several different solution encodings, including bit strings, permutations, and rule sets, and describe decoding algorithms for them. Our empirical results show that many of these encodings restrict and reshape the solution space in ways that allow relatively generic search methods, such as hill climbing, simulated annealing, and the genetic algorithm, to find solutions that are often as good as those produced by the best known constructive heuristic, and in many cases far superior. For the algorithms and representations we consider, the choice of solution representation plays an even greater role in determining performance than the choice of search algorithm.Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAACitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:25691715
Collections
- FAS Scholarly Articles [18292]
Contact administrator regarding this item (to report mistakes or request changes)