Application of the firefly algorithm to the uncapacitated facility location problem

2.1 Firefly algorithm

The firefly algorithm is a swarm intelligence algorithm inspired by bioluminescence of tropical fireflies. It was proposed by Xin-She Yang [20, 21]. Almost all tropical fireflies produce luminescence by physiological processes and give short and rhythmic flashes with unique pattern depending on the particular species. This bioluminescence has objectives to attract mating partners and potential preys. The flashing behavior of tropical fireflies is explained in [15]. FA is constructed under threeassumptions.

All fireflies are unisex so that each firefly is attracted to other fireflies regardless of theirsex.

2.2 Applying to UFLP

Each fireflyk is given an open facility vectorY _k  (= [y_k1, y_k2, y_k3, …, y _kn ]) representing a potential solution of opening facilities, where n is the number of facilities. If the i-th facility is open, y _ki  = 1.For the open facility vector Y _k of a firefly k, X (k) is defined to be the set of facilities i in F such that y _ki  = 1, that is, X (k) is the set of the facilities that are opened.

For the open facility vector Y _k , assignment function σ : C → X (k) from C to X (k) is defined by the transport costs c _ij as follows. For each j in C, σ (j) is defined to be i ∈ X (k) such that c _ij is the smallest among {c _hj  | h ∈ X (k)}. If there are several candidates h, one of them is selected randomly.

The total costT (Y _k ) for each firefly k is computed as the sum of the cost of opening facilities determined by the open facility vector Y _k and the transport cost determined by the assignment function σ : C → X (k) for Y _k . The cost T (Y _k ) for the open facility vector Y _k is defined by the formula (1) and is given as follows. T ( Y k ) = ∑ i ∈ X ( k ) f i + ∑ j ∈ C c σ ( j ) j(2)

The notations used in this paper are summarized in Table 1.

An example of a problem instance of UFLP is given in Table 2. Suppose that A, B, C, D, E are facilities, a, b, c, d are customers, and [1, 0, 1, 0, 1] is the open facility vector Y _k given to a firefly k. Note that f_A = 3, f_B = 4, f_C = 6, f_D = 7, and f_E = 2 and σ (a) = A, σ (b) = B (it may be E as well), σ (c) = C, and σ (d) = D for this open facility vector Y _k . Then the total cost T (Y _k ) for the open facility vector Y _k is computed following the Equation (2). T ( Y k ) = Opening costs + Transport cost = ( 3 + 6 + 2 ) + min ( 1 , 2 , 9 ) + min ( 8 , 5 , 2 ) + min ( 4 , 3 , 6 ) + min ( 9 , 4 , 3 ) = 20 .

Attractiveness of a firefly is represented by the light intensity. From the assumption 3, the light intensity of the firefly is given by the objective function, that is, the total cost T (Y _k ).

Light intensityI (Y _k ) of a firefly k is represented by the Equation (3). I ( Y k ) = 1 T ( Y k ) .(3)

Note that I (Y _k ) gets larger as T (Y _k ) gets smaller. It can be determined whether the firefly has a good solution by comparing I (Y _k ).

Distance between any two fireflies is represented by the Hamming distance of their open facility vectors. Suppose that the firefly s and the firefly t have open the facility vectors below. Then the Hamming distance r _st between s and t is 3. Y s = [ 1 , 1 , 0 , 0 , 0 , 0 ] Y t = [ 0 , 1 , 0 , 1 , 1 , 0 ]

If I (Y _s ) > I (Y _t ) holds for two fireflies s and t, then t moves towards s.

Movement of the firefly t toward the firefly s is the conversion of the open facility vector of t. Common components of Y _s and Y _t are carried over to the new open facility vector Y _t . Y t = [ 0 , 1 , 0 , 1 , 1 , 0 ] Y s = [ 1 , 1 , 0 , 0 , 0 , 0 ] new Y t = [ ? , 1 , 0 , ? , ? , 0 ]

Each component of Y _t different from Y _s is replaced with a probability β. The probability β is given by the following formula (4). β = β 0 1 + γ r st 2(4) where β₀ is the probability at r _st  = 0 and β₀ is set 1, and γ is the light absorption coefficient. In this paper, suitable values of γ are explored.

The FA program generates fireflies and sets the parameters. Fireflies compare the each other’s intensity and then change their positions, that is, the open facility vectors according to their distance. Repeating this process, the FA program updates fireflies’ intensity and their open facility vectors, and then it outputs a solution. A pseudocode of the FA program is illustrated below.

begin

 Objective function minT (Y),

 Initialize positions of fireflies

 Y _k  (k = 1, 2, …, K)

 I (Y _k ) is defined by the reciprocal of T (Y _k ),

 Define parameter γ and β

 while (r < Repeat count)

   fort = 1 to K

  fors = 1 to K

  ifI (Y _s ) > I (Y _t )

  Move firefly t towards firefly s;

  else

  Move firefly t randomly;

  end if

  Update of intensity and total cost;

   end fors

    end fort

 Rank the fireflies and find the current best.

 Local Search.

 r++;

  end while

  Post-process results and visualization

end

2.4 Local search

Local search is an algorithm to improve computational performance by changing a solution to another solution in the space of all the solutions by locally replacing solutions until a solution gets closer to optimal [16]. It randomly selects a neighbor solution and substitutes it if it is good. It repeats this procedure a certain number of times. We also implemented the FA program employing local search. The pseudocode of the FA program equipped with local search is illustrated below.

begin

 loop ← 0,

 s₀← The best solution currently Y₀,

 s ← s₀ Invert two randomly selected components of s₀,

 while (loop < Number of facilities)

   s₁← Invert a randomly selected component of s,

   if (I (s₁) > I (s))

  s ← s₁;

   loop++;

 end while

 if (I (s) > I (s₀))

   Y₀ ← s;

end

3.1 Objectives

We implemented FA to solve UFLP carried out experiments. Suitable values of the light absorption coefficient parameter γ are explored to accomplish better performance. Effect of local search over FA is also examined. FA is compared with FA with local search (FA _LS for short) and ABC algorithm.

The program is implemented in C# language using Visual Studio and run on an Intel Core i5 2.67 GHz Desktop with 4.0 GB memory.

Several test data sets of benchmark problems are borrowed from the OR-Library [4], which is a collection of test data sets for numerous operations research problems and originally described in [2]. UFLP is called the uncapacitated warehouse location problem in the OR-Library.

There are 15 data files provided; the test data sets VII, X, XIII and A to C from [3]. The test data sets VII (cap 71, 72, 73, 74), X (cap 101, 102, 103, 104) and XIII (cap 131, 132, 133, 134) are employed for experiments. These test data sets are summarized in Table 3, in which m stands for the number of customers and n stands for the number of facilities. The optimal solutions for these test data sets are taken from the OR-Library.

3.2 Light absorption coefficient γ

Experiments to explore a suitable value of the light absorption coefficientγ are conducted. Note that γ is a non-negative real number. When γ is close to 0, the light intensity does not decrease in the solution space. In this paper, γ is set to be one of the values 0.001, 0.005, 0.01, 0.05 or 0.1.

The result of the experiment for the value of β given in the Equation (4), in the case of (m, n) = (50, 50) is shown in Fig. 1. The x-axis represents the Hamming distance, and the y-axis represents the probability β.

The probability β refers to the probability that the open facility vector Y _k of firefly k is changed. For example, take fireflies s and t such that I (Y _s ) > I (Y _t ) and the Hamming distance r _st is 10. If γ is 0.001, some components of Y _t change in approximately 90% of the cases. If γ is 0.01, the probability β is 0.5. As the Hamming distance increases, the probability β decreases, because the attractiveness decreases as distance increases.

The number of fireflies is set to be 20, the repeat count 50, and γ is one of the values 0.001, 0.005, 0.01, 0.05 or 0.1 in the experiments.

The results for cap 74 and cap 134 are shown in Figs. 2 and 3, respectively. The x-axis represents the repeat count, and the y-axis represents the total cost T (Y).

In the case of cap 74, total cost T (Y) does not depend on the value of γ, and T (Y) for each γ are almost same after the repeat count 10.

On the other hand, in the case of cap 134, when γ is one of 0.001, 0.005, or 0.01, T (Y) converges to the optimal solution much faster than for other values of γ, that is, 0.05 or 0.1. Therefore, the value of γ should be adjusted depending on the size of the testdata.

3.3 Comparison

The effectiveness of the ABC algorithm to solve UFLP is discussed and the validity of the fitness function of ABC algorithm is examined in [18]. In the ABC algorithm the fitness value fitness (x _k ) of the potential solution of the employed bee k is calculated from its total cost x _k by the formula (5) which is given in [9]. fitness ( x k ) = { 1 1 + x k if x k ≥ 0 1 + abs ( x k ) if x k < 0(5) where abs (x) represents the absolute valueof x.

It is shown that the conventional fitness function (5) is not more efficient than the fitness function with a constant value for the benchmark problems in OR-Library.

A new candidate for a fitness function is introduced in [18] and is given by the formula (6). fitness ( x k ) = 1 Q + ( x k - x * )(6) where Q is an arbitrary constant. It is shown in [18] that the formula (6) works better than the original function (5) for UFLP.

FA is compared with the ABC algorithm with the formula (6) based on the results in [18] with respect to the average relative percent error (ARPE for short) and the hit to optimum rate (HR for short). ARPE is the average of the difference from the optimum expressed in percentages. If ARPE is lower, then we have a better chance to obtain better solutions. ARPE is given by the formula (7). ARPE = ∑ i = 1 R ( H i - U U ) × 100 R(7) where H _i denotes the i-th replication solution value, R is the number of replications, and U is the optimal value provided by [4].

HR represents the number of times that the algorithm finds the optimal solutions over all repetitions. If HR is higher, then the probability to obtain a better solution is higher.

Experimental results are summarized in Table 4. The results on the ABC algorithm with the formula (6) are taken from Table 4 in [18] where Q is 10000, the number of employed bees is 50, the number of the onlooker bees is 200, the cut limit is 20 and the number of repetitions is 100. Parameters for FA are set as follows: the number of fireflies to 20, repeat count 100, and γ = 0.01.

Note that both FA _LS and ABC perform better than FA with respect to either of ARPE and HR, and that FA _LS performs better than FA in all test data sets. Therefore, the combination of the firefly algorithm and the local search algorithm is an effective method to improve performance. The experimental results show that improvement depends on the size of the test data while no superiority of FA over ABC can be recognized or vice versa.

Effect of repeat counts over ARPE and HR is considered for FA and FA _LS , respectively, in this section.

Experimental results of ARPE of FA and FA _LS for cap 71, cap 101, and cap 131 are shown in Figs. 4, 5, and 6, respectively, where the x-axis represents repeat count. As the test data increases in size, FA _LS performs better than FA.

Experimental results of HR of FA and FA _LS for cap 71, cap 101, and cap 131 are shown in Figs. 7, 8, and 9, respectively, where the x-axis represents repeat count. Tables 5 and 6 show values of ARPE and HR of FA and FA _LS .

It is recognized that FA _LS performs better than FA for all of cap 71, cap 101, and cap 131. In particular, if the test data gets larger, local search makes HR much higher. If the size of the problem is large, the difference of ARPE is large. Observe the ARPE and HR of cap 101. Note that the difference in ARPE is small, on the other hand, the difference in HR is large. FA _LS has a high probability to output the optimal solution with less repeat count than FA. When the repeat count is 25, ARPE of FA is 2.9%. ARPE of FA _LS is 0.4%.

Further, when the repeat count is 50, HR of FA is 36%. In contrast, HR of FA _LS is 90%. Next, consider the figure of cap 131. When the repeat count is 25, ARPE of FA is 21.5%. ARPE of FA _LS is 4.9%. Further, when the repeat count is 50, FA is not able to output the optimum solution even once. In contrast, HR of FA _LS is 34%.

Therefore, the probability of outputting the optimum solution gets bigger if we employ a local search with FA. We conclude that a local search is an effective method to improve the performanceof FA.