Research Article

A self-adaptive biogeography-based algorithm to solve the set covering problem

¹ Pontificia Universidad Católica de Valparaíso, Valparaíso, Chile
² Universidad de Valparaíso, Valparaíso, Chile
³ Universidad de Playa Ancha, Valparaíso, Chile
⁴ Universidad Técnica Federico Santa María, Valparaíso, Chile
⁵ Universidad Diego Portales, Santiago, Chile

^* Corresponding author: ricardo.soto@pucv.cl

Received: 29 April 2017
Accepted: 29 March 2019

Abstract

Using the approximate algorithms, we are faced with the problem of determining the appropriate values of their input parameters, which is always a complex task and is considered an optimization problem. In this context, incorporating online control parameters is a very interesting issue. The aim is to vary the parameters during the run so that the studied algorithm can provide the best convergence rate and, thus, achieve the best performance. In this paper, we compare the performance of a self-adaptive approach for the biogeography-based optimization algorithm using the mutation rate parameter with respect to its original version and other heuristics. This work proposes altering some parameters of the metaheuristic according to its exhibited efficiency. To test this approach, we solve the set covering problem, which is a classical optimization benchmark with many industrial applications such as line balancing production, crew scheduling, service installation, databases, among several others. We illustrate encouraging experimental results, where the proposed approach is capable of reaching various global optimums for a well-known instance set taken from the Beasleys OR-Library, and sometimes, it improves the results obtained by the original version of the algorithm.