An Improved Version of a Many-objective Evolutionary Algorithm based on Non-dominated Decomposed Sets (MEANDS-II)

In the present paper, the application of ManyObjective Evolutionary Algorithms (many-MOEA) was evaluated in a widely-known discrete problem: the Multi-objective Knapsack Problem (MKP). A characteristic of most chosen instances is to define high cardinality search spaces, since they challenge a recently proposed many-MOEA in the literature called MEANDS. We propose two modifications in order to improve the performance offered by MEANDS and to increase its applicability. One refers to the use of the Pareto dominance relaxation transformation known as CDAS. Another modification refers to the multiple subpopulations of non-dominated solutions, which were not restricted in size in the original version. We used the widely-known crowding distance metric to keep the subpopulation size within a pre-set threshold. As a result we arrived at a new version of the model called MEANDS-II. Experiments reported herein with MKP under formulations of 4 to 6 objectives show that MEANDS-II exceeds its predecessor, improving its performance as the complexity of the instance increases, both in number of objectives and number of items. Additionally, we compared the MEANDS-II performance against two well-known methods (NSGA-III and MOEA/D), showing a very competitive method in both convergence and diversity.