Towards Parallel NSGA-II: An Island-Based Approach Using Fitness Redistribution Strategy

Non-dominated sorting genetic algorithm II (NSGA-II) is introduced as a powerful variant of genetic algorithm because it alleviates computational complexity and removes sharing parameter in comparing to other multiobjective evolutionary algorithms (MOEAs). Master-slave, island model and diffusion model are three approaches to parallel MOEAs. However, in those approaches, to ensure that the crossover operator is performing efficiently across sub-populations on multiple threads remains a challenging issue. In this paper, we propose an approach based on island model with a new strategy that properly divides the population into islands, each of which runs in an individual thread, but still exchanges their chromosomes with good fitness to each other reasonably and effectively. We regard our strategy as fitness redistribution, which maximizes the chance of good fitness produced once paralleled. We show that the approach maintains optimized results, improves speed in comparing to the original NSGA-II and overcomes the disadvantages of previous island model-based algorithms.