Local optima and weight distribution in the number partitioning problem

Khulood Alyahya, Jonathan E. Rowe

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

1 Citation (Scopus)

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.

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
PublisherSpringer
Pages862-871
Number of pages10
Volume8672
ISBN (Electronic)9783319107622
ISBN (Print)9783319107615
DOIs
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) -
Country/TerritorySlovenia
Period13/09/1417/09/14

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Local optima and weight distribution in the number partitioning problem'. Together they form a unique fingerprint.

Cite this