MIC 2009: The VIII Metaheuristics International Conference , 2009-07-13

Title : ( A metaheuristic approach for the unicost set covering problem )

Authors: Zahra Naji Azimi , Paolo Toth , Laura Galli ,

Access to full-text not allowed by authors

Citation: BibTeX | EndNote

Abstract

In this paper we propose a new heuristic algorithm to solve the unicost version of the well-known set covering problem. The method is based on the electromagnetism metaheuristic approach which, after generating a pool of solutions to create the initial population, applies a fixed number of local search and movement iterations based on the ‘‘electromagnetism” theory. In addition to some random aspects, used in the construction and local search phases, we also apply mutation in order to further escape from local optima. The proposed algorithm has been tested over 80 instances of the literature. On the classical benchmark instances, where the number of columns is larger than the number of rows, the algorithm, by using a fixed set of parameters, always found the best known solution, and for 12 instances it was able to improve the current best solution. By using different parameter settings the algorithm improved 4 additional best known solutions. Moreover, we proved the effectiveness of the electromagnetism metaheuristic approach for the unicost set covering problem by embedding the procedures of the proposed algorithm in a genetic algorithm scheme. The worse results obtained by the genetic algorithm show the impact of the electromagnetism metaheuristic approach in conducting the search of the solution space by applying the movements based on the electromagnetism theory. Finally, we report the results obtained by modifying the proposed electromagnetism metaheuristic algorithm for solving the non-unicost set covering problem.

Keywords

, Heuristic Procedures, Set Covering Problem
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

@inproceedings{paperid:1024981,
author = {Naji Azimi, Zahra and Paolo Toth and Laura Galli},
title = {A metaheuristic approach for the unicost set covering problem},
booktitle = {MIC 2009: The VIII Metaheuristics International Conference},
year = {2009},
location = {Hamburg, GERMANY},
keywords = {Heuristic Procedures; Set Covering Problem},
}

[Download]

%0 Conference Proceedings
%T A metaheuristic approach for the unicost set covering problem
%A Naji Azimi, Zahra
%A Paolo Toth
%A Laura Galli
%J MIC 2009: The VIII Metaheuristics International Conference
%D 2009

[Download]