Stochastic Approximation Algorithms for Number Partitioning

DSpace/Manakin Repository

Stochastic Approximation Algorithms for Number Partitioning

Citable link to this page


Title: Stochastic Approximation Algorithms for Number Partitioning
Author: Ruml, Wheeler
Citation: Ruml, Wheeler. 1993. Stochastic Approximation Algorithms for Number Partitioning. Harvard Computer Science Group Technical Report TR-17-93.
Full Text & Related Files:
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
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search