On asynchronous non-dominated sorting for steady-state multiobjective evolutionary algorithms

In parallel and distributed environments, generational evolutionary algorithms often do not exploit the full potential of the computation system since they have to wait until the entire population is evaluated before starting selection procedures. Steady-state algorithms can perform fitness evaluations asynchronously however, if the algorithm updates its state in a complicated way - which is common in multiobjective evolutionary algorithms - the threads will eventually have to wait until this update finishes.

The most expensive part of the update procedure in NSGA-II is non-dominated sorting. We turned the existing incremental non-dominated sorting algorithm into an asynchronous one using several concurrency techniques: a single entry-level lock, finer-grained locks on non-domination levels, and a non-blocking approach using compare-and-set operations. Our experimental results reveal the trade-off between the work-efficiency of the algorithm and the achieved amount of parallelism.