Design Of Perturbative Hyper-Heuristics For Combinatorial Optimisation

Combinatorial optimisation is an area which seeks to identify optimal solution(s) from a discrete solution search space. Approaches for solving combinatorial optimisation problems can be separated into two main sub-classes, i.e. exact and approximation algorithms. Exact algorithm is a sub-class of t...

Full description

Saved in:

Bibliographic Details
Main Author:	Choong, Shin Siang
Format:	Thesis
Language:	English
Published:	2019
Subjects:	QA75.5-76.95 Electronic computers Computer science
Online Access:	http://eprints.usm.my/46600/1/Choong_Shin_Siang_PhD_Thesis24.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-usm-ep.46600
record_format	uketd_dc
spelling	my-usm-ep.466002020-06-24T02:51:31Z Design Of Perturbative Hyper-Heuristics For Combinatorial Optimisation 2019-06 Choong, Shin Siang QA75.5-76.95 Electronic computers. Computer science Combinatorial optimisation is an area which seeks to identify optimal solution(s) from a discrete solution search space. Approaches for solving combinatorial optimisation problems can be separated into two main sub-classes, i.e. exact and approximation algorithms. Exact algorithm is a sub-class of techniques that is able to guarantee global optimality. However, exact algorithms are not feasible for solving complex problem due to its high computational overhead. Approximation algorithm is a sub-class of techniques which is able to provide sub-optimal solution(s) with reasonable computational cost. In order to explore the solution search space of a combinatorial optimisation problem, an approximation algorithm performs perturbations on the existing solutions by adopting a single or multiple perturbative Low-Level Heuristic(s) (LLHs). The use of a single LLH leads to poor performance when the particular heuristic is incompetent in solving the problem. Thus, the use of multiple LLHs is more desirable as the weaknesses of one heuristic can be compensated by the strengths of another. When there are multiple LLHs, a hyper-heuristic can be integrated to determine the choice of heuristics for a particular problem or situation. Hyper-heuristic automates the selection of LLHs through a high-level heuristic that consists of two key components, i.e. a heuristic selection method and a move acceptance method. The capability of a high-level heuristic is highly problem dependent as the landscape properties of a problem are unique among others. The high-level heuristics in the existing hyper-heuristics are designed by manually matching different combinations of high-level heuristic components. 2019-06 Thesis http://eprints.usm.my/46600/ http://eprints.usm.my/46600/1/Choong_Shin_Siang_PhD_Thesis24.pdf application/pdf en public phd doctoral Universiti Sains Malaysia Pusat Pengajian Sains Komputer
institution	Universiti Sains Malaysia
collection	USM Institutional Repository
language	English
topic	QA75.5-76.95 Electronic computers Computer science
spellingShingle	QA75.5-76.95 Electronic computers Computer science Choong, Shin Siang Design Of Perturbative Hyper-Heuristics For Combinatorial Optimisation
description	Combinatorial optimisation is an area which seeks to identify optimal solution(s) from a discrete solution search space. Approaches for solving combinatorial optimisation problems can be separated into two main sub-classes, i.e. exact and approximation algorithms. Exact algorithm is a sub-class of techniques that is able to guarantee global optimality. However, exact algorithms are not feasible for solving complex problem due to its high computational overhead. Approximation algorithm is a sub-class of techniques which is able to provide sub-optimal solution(s) with reasonable computational cost. In order to explore the solution search space of a combinatorial optimisation problem, an approximation algorithm performs perturbations on the existing solutions by adopting a single or multiple perturbative Low-Level Heuristic(s) (LLHs). The use of a single LLH leads to poor performance when the particular heuristic is incompetent in solving the problem. Thus, the use of multiple LLHs is more desirable as the weaknesses of one heuristic can be compensated by the strengths of another. When there are multiple LLHs, a hyper-heuristic can be integrated to determine the choice of heuristics for a particular problem or situation. Hyper-heuristic automates the selection of LLHs through a high-level heuristic that consists of two key components, i.e. a heuristic selection method and a move acceptance method. The capability of a high-level heuristic is highly problem dependent as the landscape properties of a problem are unique among others. The high-level heuristics in the existing hyper-heuristics are designed by manually matching different combinations of high-level heuristic components.
format	Thesis
qualification_name	Doctor of Philosophy (PhD.)
qualification_level	Doctorate
author	Choong, Shin Siang
author_facet	Choong, Shin Siang
author_sort	Choong, Shin Siang
title	Design Of Perturbative Hyper-Heuristics For Combinatorial Optimisation
title_short	Design Of Perturbative Hyper-Heuristics For Combinatorial Optimisation
title_full	Design Of Perturbative Hyper-Heuristics For Combinatorial Optimisation
title_fullStr	Design Of Perturbative Hyper-Heuristics For Combinatorial Optimisation
title_full_unstemmed	Design Of Perturbative Hyper-Heuristics For Combinatorial Optimisation
title_sort	design of perturbative hyper-heuristics for combinatorial optimisation
granting_institution	Universiti Sains Malaysia
granting_department	Pusat Pengajian Sains Komputer
publishDate	2019
url	http://eprints.usm.my/46600/1/Choong_Shin_Siang_PhD_Thesis24.pdf
_version_	1747821693786652672

Design Of Perturbative Hyper-Heuristics For Combinatorial Optimisation

Similar Items