  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 are often seen as a
solution to this problem, since fitness evaluation can be done by multiple
threads in an asynchronous way. However, if the algorithm updates its state in
a complicated way, the threads will eventually have to wait until this update
finishes. State update procedures that are computationally expensive are common
in multiobjective evolutionary algorithms.
  We have implemented an asynchronous steady-state version of the NSGA-II
algorithm. Its most expensive part, non-dominated sorting, determines the time
needed to update the state. 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 working with
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.
