Research Repository

The Plant Propagation Algorithm for Discrete Optimisation

Selamoglu, Birsen Irem (2017) The Plant Propagation Algorithm for Discrete Optimisation. PhD thesis, University of Essex.

[img] Text
SelamogluBirsenIrem-thesisAug2017.pdf
Restricted to Repository staff only until 14 August 2020.

Download (4MB) | Request a copy

Abstract

The thesis is concerned with novel Nature-Inspired heuristics for the so called NP-hard problems of optimisation. A particular algorithm which has been recently introduced and shown to be effective in continuous optimisation is the Plant Propagation Algorithm or PPA. Here, we intend to extend it to cope with combinatorial optimisation. In order to show that our extension is viable and effective, we consider three types of problems which are good representatives of the whole topic. These are the Travelling Salesman Problem or TSP, the Knapsack Problem or KP and the scheduling problem of Berth Allocation as arises in container ports or BAP. Because PPA is a population-based search heuristic, we devote a chapter to the important issue of generating good and yet computationally relatively light initial populations of solutions to kick start the search process. In the case of the TSP we revisit and extend the Strip Algorithm (SA). We introduce the 2-Part SA and show that it is better than the classical SA. We also introduce new variants such as the Adaptive SA and the Spiral SA which cope with clustered cities and instances with cities concentrated around the center of the unit square, respectively. In the case of KP we adapt the Roulette Wheel selection approach to generate solutions to start with PPA. And in the case of BAP, we introduce a number of simple heuristics which consider a schedule as a flat box with one side being the processing time and the other the position of vessels on the wharf. The heuristics try to generate schedules by avoiding overlap as much as possible. All approaches and algorithms are implemented and tested against well established algorithms. The results are recorded and discussed extensively. The thesis ends with a conclusion and ideas for further research.

Item Type: Thesis (PhD)
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science and Health > Mathematical Sciences, Department of
Depositing User: Birsen Selamoglu
Date Deposited: 22 Aug 2017 08:07
Last Modified: 22 Aug 2017 08:07
URI: http://repository.essex.ac.uk/id/eprint/20198

Actions (login required)

View Item View Item