Landscape Analysis of a Class of NP-Hard Binary Packing Problems

Khulood Alyahya, Jonathan Rowe

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)
298 Downloads (Pure)

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 ofb 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.
Original languageEnglish
Number of pages27
JournalEvolutionary Computation
Early online date26 Oct 2018
DOIs
Publication statusE-pub ahead of print - 26 Oct 2018

Keywords

  • Local search
  • Random Restarts
  • Landscape Analysis
  • Binary Knapsack Problem
  • Number Partitioning
  • Quadratic Knapsack
  • Combinatorial Optimisation Problems
  • Operator Selection
  • Plateau
  • Local Optima
  • Basin of Attraction
  • Phase transition
  • Constraint Optimisation
  • Penalty Functions
  • Feasibility Problem

Fingerprint

Dive into the research topics of 'Landscape Analysis of a Class of NP-Hard Binary Packing Problems'. Together they form a unique fingerprint.

Cite this