Escaping the Bounds of Generality---Unbounded Bi-Objective Optimisation


Abstract

The vast majority of contemporary evolutionary multiobjective optimisation research is grounded in the ideals of generality — that is, the capacity to perform well irrespective of the number of objectives that exist in a given task. Despite this resolute focus, the fact remains that a large portion of the reported real-world applications and existing algorithmic studies are exclusively two-dimensional. By remaining fixated on generality, research has failed to explore the unique properties of these bi-objective tasks and, in so doing, has sacrificed potential performance gains in lieu of an often-unnecessary level of flexibility. As a response, this work focuses on the bi-objective domain, endeavouring to elucidate and then harness the special characteristics of non-dominated bi-objective sets to produce powerful and efficient specialist techniques. Central to this work is the bi-objective specialisation of the powerful elite archiving mechanism. Where conventional modern systems limit the size of their archives to curb the inefficiencies of naive list constructs (despite the potential for degradation in both the quality of archival members and crowding estimates caused by such artificial thresholding), this thesis describes a new construct (the Mak_Tree) that releases artificial size bounds while maintaining high levels of efficiency. Indeed, both theoretical and empirical results illustrate that the Mak_Tree performs better than other generalist unbounded methodologies and is often more efficient than, or at least competitive with, tightly bound truncated techniques. Moreover, this thesis indicates that the use of unbounded archives imparts a real practical performance benefit to the optimisation of bi-objective problems. The extension of modern evolutionary optimisers to incorporate the efficient unbounded Mak_Tree construct — be it in a passive, active or hybridised manner — results in significant performance improvements across a host of disparate test functions. The creation of novel algorithms designed to capitalise on the properties of the Mak_Tree further emphasises the power of specialisation, with significant improvements again noted when results are compared against those produced by the contemporary bounded approaches. Outside of the improvement of optimiser efficacy, efficient access to unbounded elite sets also offers potential for the development of enhanced meta-processes. Specifically, this thesis proposes and then explores amongst the first fully-realised, intuitive, autonomous and reliable termination systems available to the field — a system that is simply infeasible with access only to bounded archival sets. Additionally, the work examines a new end-of-run presentation system that distills complete unbounded archives into well-distributed collections that are suitable for decision-maker analysis. Empirical results suggest that the proposed system produces significantly better distributions than pre-existing techniques and offers guarantees of solution quality that simply cannot be made when using bounded stores.