Bio-Inspired Computing for Chance-Constrained Combinatorial Optimisation Problems

Abstract

Bio-inspired methods have been widely used to solve stochastic optimisation problems, and they can find high-quality solutions. Motivated by real-world applications such as mining engineering problems where constraint violations have distributive effects, we discuss using chance-constrained optimisation to solve optimisation problems under various uncertainties. This thesis contributes to the theoretical analysis and application of evolutionary algorithms on chance-constrained combinatorial optimisation problems. We address complex problems under stochastic settings and are subject to chance constraints. We start our investigations in two significant areas: chance-constrained knapsack problem (CCKP) and a real-world application problem. The CCKP is a stochastic version of the classical knapsack problem, which aims to maximise the profit of selected items under a constraint that the knapsack capacity bound is violated with a small probability. We first show how to use well-known deviation inequalities as surrogate functions when tacking the chance constraint. Then, we investigate the performance of some classical approaches for solving knapsack problems and the simplest single- and multi-objective evolutionary algorithms on solving the CCKP instances. Our experimental results show that evolutionary algorithms perform better than those classical approaches in computation time and quality of solutions. Afterwards, to improve the performance of the evolutionary algorithms on solving the chance-constrained knapsack problems, we examine the use of two problem-specific operators and present a new multi-objective model of the problem. Our experimental results show that this leads to significant performance improvements when using the proposed operators in multi-objective evolutionary algorithms. Then, we perform a runtime analysis of a randomised search algorithm and a basic evolutionary algorithm for the chance-constrained knapsack problem with correlated uniform weights. Furthermore, we investigate a real-world problem in this thesis, the stockpile blending problem, which aims to blend material from stockpiles to construct concentrate parcels containing optimal metal grades. For this problem, we first present the model of the problem without chance constraints and name it the "deterministic model" and then show that the results obtained by a differential evolution approach are better than the actual results for all instances. We then consider the problem with uncertain source supply, named the stockpile blending problem with chance constraints. We introduce chance-constrained optimisation to guarantee the constraints are violated with a small probability to tackle the stochastic material grades and evaluate the performance of the differential evolution algorithm.