Application of Bio-inspired Algorithms to Selected Real-World Problems

Abstract

Real-world combinatorial optimisation problems often include uncertain parameters, dynamic constraints, mixed solution representations, and precedence constraints that make finding high-quality feasible solutions difficult. Randomised methods such as bio-inspired algorithms can solve intractable combinatorial problems in a reasonable timeframe. Bio-inspired algorithms can solve a variety of problems by using operators inspired by nature. The thesis focuses on the practical application of bio-inspired methods to different combinatorial problems of varying attributes. We investigate four combinatorial problems, starting with the knapsack problem with dynamic inequality capacity constraint, which changes over time and random weights of items from a probability distribution. We use two inequality tail bounds, namely Chebyshev’s inequality and Chernoff bound to derive helper objective functions to quantify the uncertainty for a candidate solution to the knapsack problem. We address the problem as a bi-objective problem to handle uncertainties, and we modify a baseline multi-objective optimisation algorithm to tackle the dynamic constraint to maintain separate partitions of infeasible and feasible solutions at each time frame ready to adapt to the capacity constraint change. Our experimental results show that adding a second objective to this complex problem results in better solutions than using a single-objective approach, and further improvements can be achieved using more sophisticated approaches such as NSGA-II. The second problem is a famous structural engineering problem whose ultimate solution as a structural design combines combinatorial and continuous components. We focus on the combinatorial aspects of the problem at the upper level of a bi-level problem setting, whereas at the lower level, we use a state-of-the-art optimiser to determine optimal components. We develop an enumeration method and a novelty-based approach to deal with small and large-scale problems. Using the proposed methods, we are able to obtain high-quality designs with similar objective functions and different features. The last two problems are concerned with solving a stockpile management problem in the mining industry, where a low-quality solution can result in the mining operator paying huge financial penalties to the client. Based on the data provided by our industry partner, we model this issue as a permutation problem. We use greedy algorithms and ant colony optimization to solve and understand it. Using a lexicographic objective function, we demonstrate how effectively these algorithms prioritise penalty fees over speedy delivery. We expand the previous problem to consider more realistic settings to schedule multiple machines, consider their safety constraints, and take material from stockpiles in a cooperative manner and demonstrate their efficiency.