dc.contributor.author | Alyahya, KYO | |
dc.contributor.author | Rowe, J | |
dc.date.accessioned | 2018-09-21T08:39:17Z | |
dc.date.issued | 2019-03-04 | |
dc.description.abstract | This paper presents an exploratory landscape analysis of three NP-hard combinatorial optimisation problems: the number partitioning problem, the binary knapsack problem, and the quadratic binary knapsack problem. In the paper, we examine empirically a number of fitness landscape properties of randomly generated instances of these problems. We believe that the studied properties give insight into the structure of the problem landscape and can be representative of the problem difficulty, in particular with respect to local search algorithms. Our work focuses on studying how these properties vary with different values of problem parameters. We also compare these properties across various landscapes that were induced by different penalty functions and different neighbourhood operators. Unlike existing studies of these problems, we study instances generated at random from various distributions. We found a general trend where some of the landscape features in all of the three problems were found to vary between the different distributions. We captured this variation by a single, easy to calculate, parameter and we showed that it has a potentially useful application in guiding the choice of the neighbourhood operator of some local search heuristics. | en_GB |
dc.description.sponsorship | This work was supported by King Saud University, Riyadh, Saudi Arabia and partially
supported by the Engineering and Physical Sciences Research Council [grant number
EP/N017846/1]. | en_GB |
dc.identifier.citation | Vol. 27 (1), pp. 47-73 | en_GB |
dc.identifier.doi | 10.1162/evco_a_00237 | |
dc.identifier.uri | http://hdl.handle.net/10871/34049 | |
dc.language.iso | en | en_GB |
dc.publisher | Massachusetts Institute of Technology Press (MIT Press) | en_GB |
dc.rights | © 2018 Massachusetts Institute of Technology. | |
dc.subject | Local Search | en_GB |
dc.subject | Random Restarts | en_GB |
dc.subject | Landscape Analysis | en_GB |
dc.subject | Binary Knapsack Problem | en_GB |
dc.subject | Number Partitioning | en_GB |
dc.subject | Quadratic Knapsack | en_GB |
dc.subject | Combinatorial Optimisation Problems | en_GB |
dc.subject | Operator Selection | en_GB |
dc.subject | Plateau | en_GB |
dc.subject | Local Optima | en_GB |
dc.subject | Basin of Attraction | en_GB |
dc.subject | Phase transition | en_GB |
dc.subject | Constraint Optimisation | en_GB |
dc.subject | Penalty Functions | en_GB |
dc.subject | Feasibility Problem | en_GB |
dc.title | Landscape Analysis of a Class of NP-Hard Binary Packing Problems | en_GB |
dc.type | Article | en_GB |
dc.identifier.issn | 1063-6560 | |
dc.description | This is the author accepted manuscript. The final version is available from MIT Press via the DOI in this record. | en_GB |
dc.identifier.journal | Evolutionary Computation | en_GB |
dcterms.dateAccepted | 2018-06-11 | |
rioxxterms.version | AM | |
refterms.dateFCD | 2018-09-21T08:39:17Z | |
refterms.versionFCD | AM | |