Back to search

University of Birmingham

Fitness landscape analysis of a class of np-hard problems

Abstract

dc:description.abstract

A number of fitness landscape properties of randomly generated instances of a class of NP-hard combinatorial optimisation problems are empirically studied in this research. 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. The properties include: types of search position, number of local and global optima and plateaux, quality of optima and plateaux, basin size and its correlation with fitness, time to local optima, cost of finding the global solution, and the quality of optima obtained with a fixed budget search. Our work focuses on studying how these properties vary with different values of problem parameters. We also compare these properties across different landscapes that were induced by different neighbourhood operators or different penalty functions of the following problems: the number partitioning problem, the binary knapsack problem, and the quadratic binary knapsack problem. Unlike existing studies of these problems, we study instances generated at random from various distributions. We found a general trend where in all the three problems, some of their landscape features 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 local search heuristics.

Degree

thesis:*
Name dc:type.qualificationname
d_ph
Level dc:type.qualificationlevel
d_ph
Grantor dc:publisher.institution
University of Birmingham
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Alyahya, Khulood

Subjects

dc:subject × 1

Rights

Language dc:language.dcterms_iso639_2
eng

Chain of custody

source
Harvested from
University of Birmingham
Base URL
etheses.bham.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Alyahya, Khulood. Fitness landscape analysis of a class of np-hard problems. d_ph thesis, University of Birmingham, 2017.