ND-Tree: a Fast Online Algorithm for Updating a Pareto Archive and its Application in Many-objective Pareto Local Search
Andrzej Jaszkiewicz, Thibaut Lust · arXiv (Cornell University) · 2016
In this paper we propose a new method called ND-Tree for fast online update of a Pareto archive composed of mutually non-dominated solutions. ND-Tree uses a tree structure in which each node represents a subset of solutions contained in a hypercube defined by its local approximate ideal and nadir points. A leaf is a subset of solutions organized as a simple list, and an internal node is subset of solutions composed of the union of all its sub-nodes. Using heuristic rules we build subsets, either leafs or internal nodes, containing solutions located close in the objective space. Using basic properties of local ideal and nadir points we can efficiently avoid searching many branches in the tree. ND-Tree may be used in any multiobjective metaheuristics e.g. in an multiobjective evolutionary algorithm to update the external archive of potentially efficient solutions. We experimentally compare ND-Tree to simple list, quad-Tree, and M-Front methods using artificial and realistic benchmarks. Finally we apply ND-Tree within two-phase Pareto Local Search for traveling salesperson problems instances with up to 6 objectives. We show that with this new method substantial reduction of the computational time can be obtained.