An Approach for Non-domination Level Update Problem in Steady-State Evolutionary Algorithms With Parallelism
Sumit Mishra, Carlos A. Coello Coello · 2019
One of the bottlenecks in steady-state multiobjective evolutionary algorithms (MOEAs) is non-dominated sorting because it is performed every time whenever a new offspring is generated. The recent literature shows that there is no requirement to perform the complete non-dominated sorting procedure because the entire structure of non-domination level (NDL) does not change. Some approaches have been recently proposed based on this idea. In this paper, we update our previous work where an offspring is inserted into the set of fronts, to further reduce the number of dominance comparisons. Additionally, we also explore parallelism in the updated approach in two different manners considering the PRAM CREW model. Finally, the time and space complexities of two parallel versions is theoretically analyzed.