Regresar

Attempt to reduce the computational complexity in multi-objective differential evolution algorithms

Abstract:

Nondominated sorting and diversity estimation procedures are an essential part of many multiobjective optimization algorithms. In many cases these procedures are the computational bottleneck of the entire algorithm. We present the methods to decrease the cost of these procedures for multiobjective differential evolution (DE) algorithms. Our approach is to compute domination ranks and crowding distances for the population at the beginning of the algorithm and use a combination of well known data structures to efficiently update these attributes. Experiments show that the cost of improved nondominated sorting is sub-quadratic in the number of individuals. In practice using our methods the overall DE algorithm can run 2 to 100 times faster. Copyright © 2013 ACM.