A package containing various specialised multiobjective data structures in Java. If you use this package in your work please cite
J. E. Fieldsend
Data structures for non-dominated sets: implementations and empirical assessment of two decades of advances
Proceedings of the 2020 Genetic and Evolutionary Computation Conference
pages 489-497
2020
and additionally the source of the base data structure employed (see reference list in the citation above for the various data structures, and/or API documentation generated from the codebase using the javadoc tool).
The packages are detailed below at a high level -- package documentation gives further details.
contains the various interfaces, abstract types and Exceptions core to the package. Primarily the ParetoSetManager interface which all of the data structures implement, and define their core functionality.
Currently contains the implementations of eight data structures from the liteature to store, query and update non-dominated sets of solutions (Pareto set approximations). Factory methods are provided in each of the implementations, which return an instance of the type declared as the common ParetoSetManager supertype interface.
- Linear List:
multiobjective_data_structures.implementations.LinearListManager.managerFactory(seed, numberOfObjectives) - Balanced Binary Tree (for bi-objective problems only):
multiobjective_data_structures.implementations.BiObjectiveSetManager.managerFactory(seed) - Quad Tree variants 1, 2, and 3:
multiobjective_data_structures.implementations.MTQuadTree1.managerFactory(numberOfObjectives)multiobjective_data_structures.implementations.MTQuadTree2.managerFactory(numberOfObjectives)multiobjective_data_structures.implementations.MTQuadTree3.managerFactory(numberOfObjectives)
- Dominance Decision Tree:
multiobjective_data_structures.implementations.DominanceDecisionTreeManager.managerFactory(numberOfObjectives) - BSP Tree:
multiobjective_data_structures.implementations.BSPTreeArchiveManager.managerFactory(numberOfObjectives) - ND Tree:
multiobjective_data_structures.implementations.NDTree.managerFactory(numberOfObjectives)
Contains the unit tests and supporting test classes for the package.
The Experiments class contains methods to rerun the experiments from the GECCO 2020 paper.
Experiments.dtlzExperiments()
Will run each data structure in the package 30 times on each of DTLZ1 and DTLZ2 using a (1+1)--ES for 200,000 generations, for 2, 3, 5 and 10 objective dimensions, and write out timings results to file for each combination. Note the performance of some data structures seriously degrades as the archive size and/or number of objectives increases, so unless you have cycles to burn you might not want to run all combinations(!).
Experiments.simulationExperiments()
Will run each data structure in the package on each the file generated from the analytical generator. Note that you will want therefore to generate these files first -- matlab files containing functions for this are alos provided in the repository. Files generated should be named
GECCO2020_analytical_fold_" + fold + "_objectives_" + numberOfObjectives + "_c_" + c + "_d_" + d + "_Nd_"+ nd +".txt"
Where fold, c, d and nd are as defined in the paper, in order for Experiments.simulationExperiments() to process them.
In an unorthadox approach the unit tests are in the package multiobjective_data_structures.implementations.tests rather than in a parallel structure. This is deliberate -- many of the tests are written to the core interface provided (e.g. ParetoSetManager), so should be useful for testing any data structure that you might want to develop in the framework, and are therefore distrubuted directly with the package.
Most classes have JavaDoc for the methods -- I'll be tidying these up a bit post-GECCO, but often the internal variables are named according to the convention of the source paper (unless I made a decision that the original name was too opaque).
For computational efficiency the QuadTree approaches precompute an array of arrays of child indices, rather than reclaculating them on the fly each time. This saves wasted computation, however due to the power term (it is 2^numberOfObjectives by 2^numberOfObjectives) for a high numberOfObjectives this is likely to hit memory bounds. Other data structures don't have this issue, and I'll likely develop an 'on the fly' version in the next substantial release for the QuadTree.