In this thesis, we present a new algorithm, ARRNO, for computing the distance to the nondominated area. The distance between a dominated point and the nondominated region is a metric used for ranking dominated solutions in the well-known bi-objective optimization algorithm COMO-CMA-ES. The novelty of ARRNO is that it enables the computation of this distance for points in three or more dimensions, whereas the existing algorithm is limited to sets of two-dimensional points.
The algorithm is implemented in Python, and its correctness and computational complexity are experimentally evaluated on various sets of nondominated points. For three-dimensional point sets of size n, ARRNO achieves a time complexity of O(nlogn). For constant dimension D >= 4, the time complexity is O(n^(D-1)).
An implementation of the algorithm for three and four-dimensional point sets is also included in the open-source moarchiving library, which provides efficient storage of nondominated solution sets and computation of indicators in multiobjective optimization. ARRNO thus enables the extension of COMO-CMA-ES to optimization problems with more than two objectives.
|
