On the Active Use of an ND-Tree-Based Archive for Multi-Objective Optimisation

Abstract

A number of data structures have been proposed for the storage and efficient update of unbounded sets of mutually non-dominating solutions. The recent ND-Tree has proved an effective data structure across a range of update environments, and may reasonably be considered the state-of-the-art. However, although it is efficient as a passive store of non-dominated solutions — which may be extracted at the end of an optimisation — its design is ill-suited to being an active source of parent solutions to directly exploit during a optimisation run. We introduce a number of modifications to the construction and maintenance of the ND-Tree to facilitate its use as an active archive (source of parents) during optimisation, and compare and contrast the run-time performance changes these cause (and discuss their drivers). Illustrations are provided with data sequences from a tunable generator and also a simple evolution strategy — but we emphasise such data structures are optimisation algorithm agnostic, and may be effectively integrated across the range of evolutionary (and non-evolutionary) optimisers