Discrete Optimisation and the Plant Propagation Algorithm

Ms Selamoglu's research 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 combinatorial optimisation.

In order to show that our extension is viable and effective, we consider three types of representative problems 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 consider 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 centre 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 ones. The results will be discussed.