Paper Info
Title
Local Optima And Weight Distribution In The Number Partitioning Problem
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.
Year
DOI
Venue
2014
10.1007/978-3-319-10762-2_85
PARALLEL PROBLEM SOLVING FROM NATURE - PPSN XIII
Keywords
Field
DocType
Combinatorial optimisation, phase transition, partitioning problem, makespan scheduling, fitness landscape
Coefficient of variation,Mathematical optimization,Fitness landscape,Local optimum,Computer science,Heuristic search algorithm,Operator (computer programming),Local search (optimization),Weight distribution
Conference
Volume
ISSN
Citations 
8672
0302-9743
1
PageRank 
References 
Authors
0.41
7
2
Name
Order
Citations
PageRank
Khulood AlYahya1195.17
Jonathan E. Rowe245856.35