Comparative analysis of multiobjective evolutionary algorithms for random and correlated instances of multiobjective d-dimensional knapsack problems

作者：Shah Ruchit; Reed Patrick^*

来源：European Journal of Operational Research, 2011, 211(3): 466-479.

DOI：10.1016/j.ejor.2011.01.030

• Combinatorial optimization
• Multiobjective optimization
• Knapsack problem
• Probabilistic model building evolutionary algorithms
• Hierarchical Bayesian networks

This study analyzes multiobjective d-dimensional knapsack problems (MOd-KP) within a comparative analysis of three multiobjective evolutionary algorithms (MOEAs): the epsilon-nondominated sorted genetic algorithm II (epsilon-NSGAII), the strength Pareto evolutionary algorithm 2 (SPEA2) and the e-nondominated hierarchical Bayesian optimization algorithm (epsilon-hBOA). This study contributes new insights into the challenges posed by correlated instances of the MOd-KP that better capture the decision interdependencies often present in real world applications. A statistical performance analysis of the algorithms uses the unary epsilon-indicator, the hypervolume indicator and success rate plots to demonstrate their relative effectiveness, efficiency, and reliability for the MOd-KP instances analyzed. Our results indicate that the epsilon-hBOA achieves superior performance relative to epsilon-NSGAII and SPEA2 with increasing number of objectives, number of decisions, and correlative linkages between the two. Performance of the epsilon-hBOA suggests that probabilistic model building evolutionary algorithms have significant promise for expanding the size and scope of challenging multiobjective problems that can be explored.

• 出版日期2011-6-16