Local Optima and Weight Distribution in the Number Partitioning Problem

Khulood Alyahya and Jonathan E. Rowe

Abstract. This paper investigates the relation between the distribution of the weights and the number of local optima in the Number Partitioning Problem (NPP). The number of local optima in the 1-bit flip landscape was found to be strongly and negatively correlated with the coefficient of variation (CV) of the weights. The average local search cost using the 1-bit flip operator was also found to be strongly and negatively correlated with the CV of the weights. A formula based on the CV of the weights for estimating the average number of local optima in the 1-bit flip landscape is proposed in the paper. The paper also shows that the CV of the weights has a potentially useful application in guiding the choice of heuristic search algorithm.

Keywords: Combinatorial optimisation, phase transition, partitioning problem, makespan scheduling, fitness landscape

LNCS 8672, p. 862 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer International Publishing Switzerland 2014