Local optima and weight distribution in the number partitioning problem

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

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.

Details

Original languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XIII
Subtitle of host publication13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings
EditorsThomas Bartz-Beielstein, Jurgen Branke, Bogdan Filipic, Jim Smith
Publication statusPublished - 2014
Event13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) - - Ljublijana, Slovenia
Duration: 13 Sep 201417 Sep 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer-Verlag
Volume8672
ISSN (Print)0302-9743

Conference

Conference13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) -
CountrySlovenia
Period13/09/1417/09/14

Keywords

  • Combinatorial optimisation, Fitness landscape, Makespan scheduling, Partitioning problem, Phase transition