1. UKM Learning and Research Repository
2. PHD Thesis / Tesis PHD
3. Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Title:	Bird mating optimizer for combinatorial optimization problems
Authors:	Anas W.A. Arram (P73048)
Supervisor:	Masri Ayob, Prof. Dr.
Keywords:	Algorithms Combinatorial optimization
Issue Date:	10-Jul-2017
Description:	Berth Allocation Problem (BAP) and Travelling Salesman problems (TSP) are classified as non-deterministic polynomial-time hard (NP-hard) problems, which are difficult to solve for optimality in reasonable amount of time. Many metaheuristic methods have been developed to solve NP-hard problems, however, most of these algorithms have some drawbacks such as, weak ability to explore the search space and facing difficulties to operate on different datasets. The need to either enhance the existing algorithms or utilize a new algorithm is still necessary. Recently, Bird Mating Optimizer algorithm (BMO) have been proposed to solve several optimization problems with strong exploration ability. The BMO algorithm was successfully applied to many continuous optimization problems. However, as far as we are concerned, its application on combinatorial optimization problems are very limited and never been applied to solve the BAP or TSP. BMO is an intelligent technique that can explore the search space in order to find a good quality solution by employing three types of operators: two parents mating, multi parents mating and mutation. However, despite the good performance of BMO, there are still a lot of rooms for improvements. The most important challenges include: (i) finding an appropriate application of BMO to solve combinatorial problems as it was originally proposed to solve continuous problems, (ii) using an effective multi-parent crossover as a multi-parent mating operator that can produce solutions with reasonable computational time, (iii) improve the exploitation ability of the algorithm to improve the solution quality by hybridizing it with single-based methods, (iv) automatically adjust the parameters and components of the hybrid BMO. Therefore, this research aims to investigate the effectiveness of BMO in solving two combinatorial optimization problems: BAP and TSP by introducing the following objectives: firstly, we investigate the suitable representation for applying the BMO for solving BAP and TSP. Secondly, a new multi-parent crossover is proposed in order to reduce the computational time of the BMO and produce better quality solutions over both tested domains. In order to improve the exploitation mechanism of BMO, we then hybridize BMO (that responsible for exploration) with five single-based meta-heuristics (SBHs) (i.e Hill-Climbing, Late Acceptance Hill Climbing, Simulated Annealing, Iterated Greedy Algorithm and Variable Iterated Greedy Algorithm). Finally, a meta-BMO is proposed to automatically select SBHs and BMO parameters for each problem domain/instance during the search process without external interference. Results tested on BAP and TSP demonstrated that the proposed BMOs had obtained competitive results in most instances for both problems domains when compared to the best known method in the literature. This demonstrates that combining BMO with SBHs along with the use of meta optimization technique to automatically tune the BMO components during the search process, produces an effective BMO technique that can improve the basic BMO and work well across both BAP and TSP problems.,Certification of Master's/Doctoral Thesis" is not available
Pages:	215
Call Number:	QA402.5.A737 2017 3 tesis
Publisher:	UKM, Bangi
Appears in Collections:	Faculty of Information Science and Technology / Fakulti Teknologi dan Sains Maklumat

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.