ND-Tree-based update: a Fast Algorithm for the Dynamic Non-Dominance Problem
Andrzej Jaszkiewicz, Poznan University of Technology, Faculty of Computing, Institute of Computing Science, ul. Piotrowo 2, 60-965 Poznan, Poland, e-mail: andrzej.jaszkiewicz at put.poznan.pl
Thibaut lust, Sorbonne University, Computer Science, 4, place Jussieu, 75005 Paris, thibaut.lust at lip6.fr
ND-Tree-based update (or shortly ND-Tree) is a new method for solving the dynamic non-dominance problem, i.e. the problem of online update of a Pareto archive composed of mutually non-dominated points. It uses a new ND-Tree data structure in which each node represents a subset of points contained in a hyperrectangle defined by its local approximate ideal and nadir points. Building subsets containing points located close in the objective space and 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 multiobjective evolutionary algorithms and other multiobjective metaheuristics to update an archive of potentially non-dominated points.
Code
C Code: NDTreeC.zip
Visual C++ 2015 version: ND_Tree.zip
Linux version: ND_Tree.zip
Data Sets
The Data sets used in the experiments are available below:
- Artificial sets with 2 to 6 objectives: DataArtSet2_6.zip
- Artificial sets with 7 to 10 objectives: DataArtSet7_10.zip
- Clustered artificial sets with 2 to 6 objectives: DataClustered.zip
- MOEAD sets with 2 to 6 objectives: DataMOEAD.zip
- PLS sets with 2 to 6 objectives: DataPLS.zip
- Non-dominated sorting test sets: DataNDS.zip
Complete Results:
Additional Results
Some additional results (representation of the instances, Exact nearest neighbors in M-Front, PLS, Algorithm of M-Front-II) can be found here: