Non-dominated Sorting for Multi-Objective Optimization
Some of you know that I'm maintaining PGApack, a genetic algorithm package and a corresponding Python wrapper, PGApy. PGApack implements multi-objective optimization using NSGA-II [DPAM02] and NSGA-III [DJ14], [JD14].
Multi-objective optimization means that we have more than one objective (or fitness-) function. Since typically these functions can contradict each other – when a candidate solution becomes better in one objective it might become worse in another objective – we need to establish what better means in the context of multi-objective optimization. An individual \(A\) is strictly better than another individual \(B\) – we say individual \(A\) dominates individual \(B\) – when \(A\) is better or equal to \(B\) in all objectives and strictly better in at least one of them.
Since we do not have a single fitness for individuals, multi-objective algorithms typically establish a ranking of individuals by dominance. Individuals which are not dominated by any other individual get dominance rank 0. Then we remove all rank-0 individuals and all individuals that are then non-dominated get rank 1 etc. This procedure is typically called non-dominated ranking or non-dominated sorting. This rank is then one of the components of the new fitness function.
The NSGA-II paper [DPAM02] implements this by checking each individual in a population against every other individual to see if one dominates the other. Then it removes the current non-dominated individuals one-by-one and establishes ranks as outlined above. This algorithm has a run-time that grows quadratically with the number of individuals to sort. In computer science we write this in the big O notation as \(O(n^2)\) where \(n\) is the number of individuals.
In 2003 Jensen [Jen03] published an algorithm that can perform the dominance-ranking of all individuals with effort \(O\left(n\cdot(\log n)^{m-1}\right)\) where \(m\) is the number of objectives (and \(n\) is the population size as before). Jensen's algorithm was updated 10 years later because he had formulated his algorithm in a way that could not handle individuals with the same evaluation in one objective which he claimed was easy to remedy but was not so easy for others [FGP13]. A year later a slight modification was made to formally prove that the algorithm runtime complexity actually fits the formula above [BS14].
I've now implemented this algorithm and benchmarked the new against the old \(O(n^2)\) version. For the benchmark I'm using the DTLZ-1 algorithm [DTLZ05] as Jensen did in his original paper [Jen03]. Similar to Jensen I've measured times up to a population size of 2000 individuals. I'm also getting most of the speedup for low numbers of objectives. In the following graphics the Y-axis is in seconds of CPU-time while the X-axis is the population size. There are three graphics for 2, 10, and 20 objectives. The effort is increasing with each objectives, the other graphics are quite similar. Note that contrary to Jensen I'm using a linear, not a log-log plot. All measurements contain the full time the algorithm needs, not just the non-dominated sorting, the times also include, e.g., the time for computing the evaluation functions. I've not measured this time separately.
The following graphics displays the speedups I'm getting. Note that contrary to Jensen [Jen03] I'm not getting higher times for the new algorithm for large numbers of objectives and small number of individuals. This may be due to computers having become a little faster during the last 20 years. Interesting is that starting with 5 objectives, the speedup stays almost the same (this is relative to the \(O(n^2)\) algorithm). This is probably because both, my implementation of the old algorithm as well as the new one stop comparing objectives when they have established that individuals do not dominate each other: This is the case whenever in one individual an objective is larger while another objective is smaller. Since after some optimization steps, most of the individuals tend to be non-dominated, it seems that the non-dominance can be established quickly without looking at all objectives.
Maxim Buzdalov and Anatoly Shalyto. A provably asymptotically fast version of the generalized Jensen algorithm for non-dominated sorting. In Thomas Bartz-Beielstein, Jürgen Branke, Bogdan Filipič, and Jim Smith, editors, Parallel Problem Solving from Nature – PPSN XIII, volume 8672 of Lecture Notes in Computer Science, pages 528–537. Ljubljana, Slovenia, September 2014.
Kalyanmoy Deb and Himanshu Jain. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints. IEEE Transactions on Evolutionary Computation, 18(4):577–601, August 2014.
Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182–197, April 2002.
Kalyanmoy Deb, Lothar Thiele, Marco Laumanns, and Eckart Zitzler. Scalable test problems for evolutionary multiobjective optimization. In Ajith Abraham, Lakhmi Jain, and Robert Goldberg, editors, Evolutionary Multiobjective Optimization, Theoretical Advances and Applications, Advanced Information and Knowledge Processing, pages 105–145. Springer, 2005.
Félix-Antoine Fortin, Simon Grenier, and Marc Parizeau. Generalizing the improved run-time complexity algorithm for non-dominated sorting. In Christian Blum, editor, Genetic and Evolutionary Computation GECCO 2013, pages 615–622. Amsterdam, The Netherlands, July 2013.
Himanshu Jain and Kalyanmoy Deb. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part II: Handling constraints and extending to an adaptive approach. IEEE Transactions on Evolutionary Computation, 18(4):602–622, August 2014.