On the computational efficiency of multiple objective metaheuristics. The knapsack problem case study

The paper describes a computational experiment which goal is to evaluate computational efficiency of three multiple objective evolutionary metaheuristics on the multiple objective multiple constraints knapsack problem. The relative efficiency of the multiple objective algorithms is evaluated with respect to a single objective evolutionary algorithm (EA). We use a methodology that allows consistent evaluation of the quality of approximately Pareto-optimal solutions generated by both multiple and single objective metaheuristics. Then, we compare computational efforts needed to generate solutions of approximately the same quality by the two kinds of methods. The results indicate that computational efficiency of multiple objective EAs deteriorates with the growth of the number of objectives. Furthermore, significant differences in the performance of the three algorithms are observed. (C) 2003 Elsevier B.V. All rights reserved.