Scale Adaptive Reproduction Operator for Decomposition based Estimation of Distribution Algorithm

Abstract

Multi-objective evolutionary algorithm based on decomposition (MOEA/D) uses crossover operator which often either breaks the building blocks or mix them ineffectively. Multi-objective estimation of distribution algorithm based on decomposition (MEDA/D) evolves a probability vector for each sub-problem to guide the search instead of using crossover operator.However, since the number of the weight vectors in the neighborhood of each weight vector is relatively small and MEDA/D does not provide a way to maintain diversity, the performance of MEDA/D is limited. To overcome the drawbacks of MEDA/D, we proposed a new reproduction operator. This operator could promote diversity. We introduced it into MOEA/D framework and the new algorithm is called s-MEDA/D. We also prove that the parameter newly introduced has physical significance and the reproduction operator is not susceptible to the scale of the problem. The s-MEDA/D was tested on nine instances of the 0/1 multi-objective knapsack problem. Empirical evaluation suggests that the proposed algorithm is effective and efficient.