Local optima and weight distribution in the number partitioning problem

Khulood Alyahya; Jonathan E. Rowe

doi:10.1007/978-3-319-10762-2

Local optima and weight distribution in the number partitioning problem

Khulood Alyahya, Jonathan E. Rowe

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Parallel Problem Solving from Nature – PPSN XIII
Subtitle of host publication	13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings
Editors	Thomas Bartz-Beielstein, Jurgen Branke, Bogdan Filipic, Jim Smith
Publisher	Springer
Pages	862-871
Number of pages	10
Volume	8672
ISBN (Electronic)	9783319107622
ISBN (Print)	9783319107615
DOIs	https://doi.org/10.1007/978-3-319-10762-2
Publication status	Published - 2014
Event	13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) - - Ljublijana, Slovenia Duration: 13 Sept 2014 → 17 Sept 2014

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer-Verlag
Volume	8672
ISSN (Print)	0302-9743

Conference

Conference	13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) -
Country/Territory	Slovenia
Period	13/09/14 → 17/09/14

Keywords

Combinatorial optimisation
Fitness landscape
Makespan scheduling
Partitioning problem
Phase transition

ASJC Scopus subject areas

Computer Science(all)
Theoretical Computer Science

Access to Document

10.1007/978-3-319-10762-2

Cite this

Alyahya, K., & Rowe, J. E. (2014). Local optima and weight distribution in the number partitioning problem. In T. Bartz-Beielstein, J. Branke, B. Filipic, & J. Smith (Eds.), Parallel Problem Solving from Nature – PPSN XIII : 13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings (Vol. 8672, pp. 862-871). (Lecture Notes in Computer Science ; Vol. 8672). Springer. https://doi.org/10.1007/978-3-319-10762-2

Alyahya, Khulood ; Rowe, Jonathan E. / Local optima and weight distribution in the number partitioning problem. Parallel Problem Solving from Nature – PPSN XIII : 13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings. editor / Thomas Bartz-Beielstein ; Jurgen Branke ; Bogdan Filipic ; Jim Smith. Vol. 8672 Springer, 2014. pp. 862-871 (Lecture Notes in Computer Science ).

@inproceedings{a88af16ceae84b47ba6dba72884da5c8,

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.",

keywords = "Combinatorial optimisation, Fitness landscape, Makespan scheduling, Partitioning problem, Phase transition",

author = "Khulood Alyahya and Rowe, {Jonathan E.}",

year = "2014",

doi = "10.1007/978-3-319-10762-2",

language = "English",

isbn = "9783319107615 ",

volume = "8672",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "862--871",

editor = "Thomas Bartz-Beielstein and Jurgen Branke and Bogdan Filipic and Jim Smith",

booktitle = "Parallel Problem Solving from Nature – PPSN XIII",

note = "13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) - ; Conference date: 13-09-2014 Through 17-09-2014",

}

Alyahya, K & Rowe, JE 2014, Local optima and weight distribution in the number partitioning problem. in T Bartz-Beielstein, J Branke, B Filipic & J Smith (eds), Parallel Problem Solving from Nature – PPSN XIII : 13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings. vol. 8672, Lecture Notes in Computer Science , vol. 8672, Springer, pp. 862-871, 13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) - , Slovenia, 13/09/14. https://doi.org/10.1007/978-3-319-10762-2

Local optima and weight distribution in the number partitioning problem. / Alyahya, Khulood; Rowe, Jonathan E.
Parallel Problem Solving from Nature – PPSN XIII : 13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings. ed. / Thomas Bartz-Beielstein; Jurgen Branke; Bogdan Filipic; Jim Smith. Vol. 8672 Springer, 2014. p. 862-871 (Lecture Notes in Computer Science ; Vol. 8672).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Local optima and weight distribution in the number partitioning problem

AU - Alyahya, Khulood

AU - Rowe, Jonathan E.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Combinatorial optimisation

KW - Fitness landscape

KW - Makespan scheduling

KW - Partitioning problem

KW - Phase transition

UR - http://www.scopus.com/inward/record.url?scp=84921825923&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-10762-2

DO - 10.1007/978-3-319-10762-2

M3 - Conference contribution

AN - SCOPUS:84921825923

SN - 9783319107615

VL - 8672

T3 - Lecture Notes in Computer Science

SP - 862

EP - 871

BT - Parallel Problem Solving from Nature – PPSN XIII

A2 - Bartz-Beielstein, Thomas

A2 - Branke, Jurgen

A2 - Filipic, Bogdan

A2 - Smith, Jim

PB - Springer

T2 - 13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) -

Y2 - 13 September 2014 through 17 September 2014

ER -

Alyahya K, Rowe JE. Local optima and weight distribution in the number partitioning problem. In Bartz-Beielstein T, Branke J, Filipic B, Smith J, editors, Parallel Problem Solving from Nature – PPSN XIII : 13th International Conference, Ljubljana, Slovenia, September 13-17, 2014. Proceedings. Vol. 8672. Springer. 2014. p. 862-871. (Lecture Notes in Computer Science ). doi: 10.1007/978-3-319-10762-2

Local optima and weight distribution in the number partitioning problem

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this