A Systematic Investigation of Multi-Objective Evolutionary Algorithms Applied to the Water Distribution System Problem

Abstract

Water distribution systems (WDSs) are one of society’s most important infrastructure assets. They consist of a great number of pumps, valves, junctions and a tremendous number of pipes that connect these nodes within the system, all of which induce a significant capital cost at the time of construction. However, there is no singular option for designing a WDS, and each potential design affects the cost and performance of the system differently (i.e., the pressure at each node and flow rates for each pipe). To identify solutions with a better trade-off between the cost and performance, multi-objective evolutionary algorithms (MOEAs) provide a robust optimisation tool to solve this type of problem. This PhD thesis focuses on improving and developing a more effective MOEA for WDS problems, and optimisation problems in general. The first stage of the research is to study the impact of select critical processes in MOEAs on algorithm performance and understand the reasons behind the performance observations. There are two chapters related to the first stage. The second stage is to develop a proposed General Multi-Objective Evolutionary Algorithm (GMOEA) and compare this with existing MOEAs for WDS problems. This is associated with the third content chapter. In the first paper, the impact of the operators on an algorithm’s performance has been studied. The operators are the key component for exchange of information between solutions in populations to produce offspring solutions, thereby exploring alternative regions of the search space. These have a significant impact on an algorithm’s search behaviour. However, the composition and number of operators that should be included in an MOEA is generally fixed, based on choices made by the developers of these algorithms. To explore this issue, an assessment was conducted via comprehensive numerical experiments that isolate the influence of the size of the operator set, as well as its composition. In addition, the relative influence of other search processes affecting search behaviour (e.g., the selection strategy and hyperheuristic) have been studied. It has been found that operator set size is a dominant factor affecting algorithm performance, having a greater influence than operator set composition and other search processes affecting algorithm search behaviour. Moreover, it was also found that an existing MOEAs’ performance can be improved by simply increasing the number of operators used within the algorithm. This finding can be applied to justify the usage of operators for designing a new MOEA in the future. In the second paper, a new convex hull contribution selection strategy for population-based MOEAs (termed CHCGen) has been proposed and compared with existing MOEAs in order to study the impact of the selection strategy on MOEA performance. It has been found that the CHCGen selection strategy is able to emphasise selection of the population of solutions on the convex hull of the non-dominated set of solutions. The CHCGen selection strategy has demonstrated that it can also improve an existing MOEAs’ performance. The finding suggests different selection strategies have an impact on MOEA performance. In addition, CHCGen can be used for developing a new MOEA in the future. In the third paper, a new multi-objective evolutionary algorithm, called GMOEA(CHCGen,12,T,A)1 has been proposed by conducting comprehensive numerical experiments to determine the optimised component configuration for each MOEA process. The components considered within the algorithm construction include: the selection strategy, hyperheuristic, and operator set size. The numerical experiments not only explore the impact of each process’s component on algorithm performance comprehensively, but also investigate the correlation of each pairwise combination of the process’s components. In addition, the optimal form of the algorithm GMOEA(CHCGen,12,T,A) was compared with seven other existing MOEAs with an extended computational budget for a range of WDS problems. From the results, GMOEA(CHCGen,12,T,A) was shown not only to have outperformed all other MOEAs considered, but also to find a greater number of new Pareto front solutions for intermediate and large scale problems.