Do multiple-objective metaheuristics deliver on their promises? A computational experiment on the set-covering problem

In this paper, we compare the computational efficiency of three state-of-the-art multiple-objective metaheuristics (MOMHs) and their single-objective counterparts on the multipleobjective set-covering problem (MOSCP). We use a methodology that allows consistent evaluation of the quality of approximately Pareto-optimal solutions generated by of both MOMHs and single-objective metaheuristics (SOMHs). Specifically, we use the average value of the scalarizing functions over a representative sample of weight vectors. Then, we compare computational efforts needed to generate solutions of approximately the same quality by the two kinds of methods. In the computational experiment, we use two SORMs-the evolutionary algorithm (EA) and the memetic algorithm (MA), and three MOMHs-controlled elitist nondominated sorting genetic algorithm, the strength Pareto EA, and the Pareto MA. The methods are compared on instances of the MOSCP with 2,3, and 4 objectives, 20,40,80 and 200 rows, and 200,400,800 and 1000 columns. The results of the experiment indicate good computational efficiency of the multiple-objective metaheuristics in comparison to their single-objective counterparts.