Keywords

1 Introduction

The Set Covering Problem (SCP) is a class of representative combinatorial optimization problem that has been applied to many real world problems, such as crew scheduling in airlines [1], facility location problem [2], and production planning in industry [3]. The SCP is a well-known NP-hard in the strong sense [4]. Many algorithms have been developed to solve it has been reported to literature. Exact algorithms are mostly based on branch-and-bound and branch-and-cut [5, 6]. However, these algorithms are rather time consuming and can only solve instances of very limited size. For this reason, many research efforts have been focused on the development of heuristics to find good or near-optimal solutions within a reasonable period of time. Classical greedy algorithms are very simple, fast, and easy to code in practice, but they rarely produce high quality solutions for their myopic and deterministic nature [7]. An improved greedy algorithm by incorporating randomness and memory into it and obtained promising results [8]. Compared with classical greedy algorithms, heuristics based on Lagrangian relaxation with subgradient optimization are much more effective. The most efficient ones are those proposed in [9, 10]. As top-level general search strategies, metaheuristics were also applied to the SCP. An incomplete list of this kind of heuristics for the SCP includes genetic algorithm [11], simulated annealing algorithm [12], tabu search algorithm [13], evolutionary algorithms [14], ant colony optimization (ACO) [15], electromagnetism (unicost SCP) [16], gravitational emulation search [17] and cultural algorithms [18]. A deeper comprehension of most of the effective algorithms for the SCP can be found in [19].

In this paper, a new approach based on Binary Firefly Algorithm for the SCP is presented. Firefly Algorithm (FA) is a recently developed, population-based metaheuristic [20, 21]. So far, it has been shown that firefly algorithm is very efficient in dealing with multimodal, global optimization problems. For a deeper comprehension of review of firefly advances and applications please refer to [22, 23]. Researches on FA for SCP have not been seen to date.

This paper is organized as follows: In Sect. 2, we formally describe the SCP. The Sect. 3, we present the overview of FA. The description of the proposed approach is described in Sect. 3. In Sect. 5, we present experimental results obtained when applying the algorithm for solving the 65 instances different of SCP. Finally, in Sect. 6 we conclude the paper.

2 Problem Description

The Set Covering Problem (SCP) can be formally defined as follows. Let A = (a ij ) be an m-row, n-column, zero-one matrix. We say that a column j covers a row i if a ij  = 1. Each column j is associated with a nonnegative real cost c j . Let I = {1, …, m} and J = {1, …, n} be the row set and column set, respectively. The SCP calls for a minimum cost subset S ⊆ J, such that each row i ∊ I is covered by at least one column j ∊ S. A mathematical model for the SCP is

$$Minimize\;f(x) = \sum\limits_{j = 1}^{n} c_{j} x_{j}$$
(1)

subject to

$$\sum\limits_{j = 1}^{n} a_{ij} x_{j} \ge 1,\quad \forall i \in I$$
(2)
$$x_{j} \in \{ 0,1\} ,\quad \forall j \in J$$
(3)

The goal is to minimize the sum of the costs of the selected columns, where x j  = 1 if the column j is in the solution, 0 otherwise. The restrictions ensure that each row i is covered by at least one column.

3 Overview of Firefly Algorithm

Nature-inspired methodologies are among the most powerful algorithms for optimization problems. The Firefly Algorithm (FA) is a novel nature-inspired algorithm inspired by the social behavior of fireflies. By idealizing some of the flashing characteristics of fireflies, a firefly-inspired algorithm was presented in [20, 21]. The pseudo code of the firefly-inspired algorithm was developed using these three idealized rules:

  • All fireflies are unisex and are attracted to other fireflies regardless of their sex.

  • The degree of the attractiveness of a firefly is proportional to its brightness, and thus for any two flashing fireflies, the one that is less bright will move towards the brighter one. More brightness means less distance between two fireflies. However, if any two flashing fireflies have the same brightness, then they move randomly.

  • Finally, the brightness of a firefly is determined by the value of the objective function. For a maximization problem, the brightness of each firefly is proportional to the value of the objective function and vice versa.

As the attractiveness of a firefly is proportional to the light intensity seen by adjacent fireflies, we can now define the variation of attractiveness β with the distance r by

$$\beta = \beta_{0} e^{{ - \gamma r^{2} }}$$
(4)

where β 0 is the attractiveness at r = 0. The distance r ij between two fireflies is determined by

$$r_{ij} = \left\| {x^{i} - x^{j} } \right\| = \sqrt {\sum\limits_{k = 1}^{d} \left( {x_{k}^{i} - x_{k}^{j} } \right)^{2} }$$
(5)

where x i k is the kth component of the spatial coordinate of the ith firefly and d is the number of dimensions. The movement of a firefly i is attracted to another more attractive (brighter) firefly j is determined by

$$x_{i}^{t + 1} = x_{i}^{t} + \beta_{0} e^{{ - \gamma r_{ij}^{2} }} \left( {x_{j}^{t} - x_{i}^{t} } \right) + \alpha \left( {rand - \frac{1}{2}} \right)$$
(6)

where x ij is the firefly position of the next generation. \(x_{i}^{t}\) and \(x_{j}^{t}\) are the current position of the fireflies and \(x_{i}^{t + 1}\) is the ith firefly position of the next generation. The second term is due to attraction. The third term introduces randomization, with α being the randomization parameter and “rand” is a random number generated uniformly but distributed between 0 and 1. The value of γ determines the variation of attractiveness, which corresponds to the variation of distance from the communicated firefly. When γ = 0, there is no variation or the fireflies have constant attractiveness. When γ = 1, it results in attractiveness being close to zero, which again is equivalent to the complete random search. In general, the value of γ [20, 21] is in between [0, 10].

4 Description of the Proposed Approach

In this section, the FA is proposed to solve the SCP using binary representation.

  1. Step 1

    Initialize the firefly parameters (γ, β 0, size for the firefly population and the maximum number of generation, for the termination process).

  2. Step 2

    Initialization of firefly position. Initialize randomly M = [X 1; X 2; …; X m ] of m solutions or firefly positions in the multi-dimensional search space, where m represents the size of the firefly population. Each solution of X is represented by the d-dimensional binary vector.

  3. Step 3

    Evaluation of fitness of the population. For this case the function of fitness is equal to the objective function SCP (Eq. 1).

  4. Step 4

    Modification of firefly position. A firefly produces a modification in the position based on the brightness between the fireflies. The new position is determined by modifying the value (old firefly position) using Eq. 6 for each dimension of a firefly. The result of the new component of the firefly, is probable to be a real number, to fix this, apply a threshold of 0 and 1. If \(x_{p}^{\prime}\) is greater than the threshold, it is very likely to choose 1, otherwise 0. The threshold level can be made to range from 0 to 1, and in order to achieve this a tanh function is used as given in [24].

$${ \tanh }\left(\left| {x_{p}^{\prime} } \right|\right) = \frac{{{ \exp }(2*|x_{p}^{\prime} |) - 1}}{{{ \exp }(2*|x_{p}^{\prime} |) + 1}}$$
(7)
  1. Step 5

    The new solution is subjected to an evaluation, if is not a feasible solution generated then is repaired. To make feasible solution is to determine which rows have not yet been covered and choose the columns needed for coverage. The search for these columns is based in: cost of a column/number of rows not covered that cover the column j. Once the solution has become feasible applies optimization step to eliminate those redundant columns. A redundant column is that if removed, the solution remains feasible.

  2. Step 6

    Memorize the best solution achieved so far. Increment the generation count.

  3. Step 7

    Stop the process and display the result if the termination criteria are satisfied. Termination criteria used in this work are the specified maximum number of generations. Otherwise, go to step 3.

5 Experiments and Results

The performance of Binary Firefly Algorithm was evaluated experimentally using 65 SCP test instances from OR-Library of Beasley [25]. These instances are divided into 11 groups and each group contains 5 or 10 instances. Table 1 shows their detailed information where “Density” is the percentage of non-zero entries in the SCP matrix. The algorithm was coded in C in the development environment NetBeans 7.3 with support for C/C++ and run on a PC with a 1.8 GHz Intel Core 2 Duo T5670 CPU and 3.0 GB RAM, under Windows 8 system.

Table 1 Details of the test instances
Full size table

In all experiments, the Binary Firefly Algorithm is executed 50 generations, and 30 times each instance. This number was determined by the rapid convergence to a local optimal closest to global optimum. We used a population of 25 fireflies. The parameters γ, β 0 are initialized to 1. These parameters were selected empirically after a large number of tests and showed good results but may not be optimal for all instances.

Table 2 shows the results obtained of the 65 instances. Column “Optimum” reports the optimal or the best known solution value of each instance. Columns “Min. value found”, “Max. value found” and “Average” reports the minimum, maximum, and average of the best solutions obtained in the 30 executions.

Table 2 Computational results on 65 instances of SCP
Full size table

In the Fig. 1 shows the evolution of mean best values for the instances 4.1, 4.2 and 4.3, which shows the rapid convergence of cost minimization.

Fig. 1
figure 1

Evolution of mean best values for SCP4.1, SCP4.2 and SCP4.3

Full size image

6 Conclusions

As can be seen from the results obtained, the metaheuristic behaves of good way in almost all instances, with the first set columns instances between 1,000 and 2,000, there is a mean cost difference of 54 between the global optimum with the best optimum obtained, and starts to decrease. With a set of columns in 5,000, Firefly behaves very well coming to have a difference of 2 with respect to the best known solution value (NRF.2). This paper has demonstrated the Binary Firefly Algorithm is a valid alternative to solve the SCP, being that its main use is for continuous domains.

An interesting research direction to pursue in future work about the integration of autonomous search in the solving process, which in many cases has demonstrated excellent results [26–29].