Local optima and weight distribution in the number partitioning problem
Research output: Chapter in Book/Report/Conference proceeding › Conference 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 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 |
| Publication status | Published - 2014 |
| Event | 13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) - - Ljublijana, Slovenia Duration: 13 Sep 2014 → 17 Sep 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 | Slovenia |
| Period | 13/09/14 → 17/09/14 |
Keywords
- Combinatorial optimisation, Fitness landscape, Makespan scheduling, Partitioning problem, Phase transition