eTheses Repository

Fitness landscape analysis of a class of np-hard problems

Alyahya, Khulood (2017)
Ph.D. thesis, University of Birmingham.

PDF (10Mb)Accepted Version

Restricted to Repository staff only until 01 January 2019.


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.

Type of Work:Ph.D. thesis.
Supervisor(s):Rowe, Jon
School/Faculty:Colleges (2008 onwards) > College of Engineering & Physical Sciences
Department:School of Computer Science
Subjects:TK Electrical engineering. Electronics Nuclear engineering
Institution:University of Birmingham
ID Code:7271
This unpublished thesis/dissertation is copyright of the author and/or third parties. The intellectual property rights of the author or third parties in respect of this work are as defined by The Copyright Designs and Patents Act 1988 or as modified by any successor legislation. Any use made of information contained in this thesis/dissertation must be in accordance with that legislation and must be properly acknowledged. Further distribution or reproduction in any format is prohibited without the permission of the copyright holder.
Export Reference As : ASCII + BibTeX + Dublin Core + EndNote + HTML + METS + MODS + OpenURL Object + Reference Manager + Refer + RefWorks
Share this item :
QR Code for this page

Repository Staff Only: item control page