Paper Info
Title
Achieving super-linear performance in parallel multi-objective evolutionary algorithms by means of cooperative coevolution
Abstract
This article introduces three new multi-objective cooperative coevolutionary variants of three state-of-the-art multi-objective evolutionary algorithms, namely, Non-dominated Sorting Genetic Algorithm II (NSGA-II), Strength Pareto Evolutionary Algorithm 2 (SPEA2) and Multi-objective Cellular Genetic Algorithm (MOCell). In such a coevolutionary architecture, the population is split into several subpopulations or islands, each of them being in charge of optimizing a subset of the global solution by using the original multi-objective algorithm. Evaluation of complete solutions is achieved through cooperation, i.e., all subpopulations share a subset of their current partial solutions. Our purpose is to study how the performance of the cooperative coevolutionary multi-objective approaches can be drastically increased with respect to their corresponding original versions. This is specially interesting for solving complex problems involving a large number of variables, since the problem decomposition performed by the model at the island level allows for much faster executions (the number of variables to handle in every island is divided by the number of islands). We conduct a study on a real-world problem related to grid computing, the bi-objective robust scheduling problem of independent tasks. The goal in this problem is to minimize makespan (i.e., the time when the latest machine finishes its assigned tasks) and to maximize the robustness of the schedule (i.e., its tolerance to unexpected changes on the estimated time to complete the tasks). We propose a parallel, multithreaded implementation of the coevolutionary algorithms and we have analyzed the results obtained in terms of both the quality of the Pareto front approximations yielded by the techniques as well as the resulting speedups when running them on a multicore machine.
Year
DOI
Venue
2013
10.1016/j.cor.2011.11.014
Computers & OR
Keywords
DocType
Volume
coevolutionary algorithm,super-linear performance,parallel multi-objective evolutionary algorithm,coevolutionary architecture,cooperative coevolutionary multi-objective approach,new multi-objective cooperative coevolutionary,bi-objective robust scheduling problem,problem decomposition,real-world problem,state-of-the-art multi-objective evolutionary algorithm,original multi-objective algorithm,complex problem
Journal
40
Issue
ISSN
Citations 
6
0305-0548
17
PageRank 
References 
Authors
0.62
18
4
Name
Order
Citations
PageRank
Bernabé Dorronsoro157540.72
Grégoire Danoy223933.33
Antonio J. Nebro3111854.62
Pascal Bouvry449356.10