Binary Fruit Fly Swarm Algorithms for the Set Covering Problem

Broderick Crawford,Ricardo SotoHanns de la Fuente MellaClaudio ElorteguiWenceslao PalmaClaudio Torres-RojasClaudia Vasconcellos-Gaete,Marcelo BecerraJavier Pe?a and Sanjay Misra

1Pontificia Universidad Católica de Valparaíso,Valparaíso,2362807,Chile

2LERIA,Université d’Angers,Angers,49000,France

3Department of Computer Science and Communication,Ostfold University College,Halden,Norway

Abstract: Currently, the industry is experiencing an exponential increase in dealing with binary-based combinatorial problems.In this sense,metaheuristics have been a common trend in the field in order to design approaches to solve them successfully.Thus, a well-known strategy consists in the use of algorithms based on discrete swarms transformed to perform in binary environments.Following the No Free Lunch theorem, we are interested in testing the performance of the Fruit Fly Algorithm, this is a bio-inspired metaheuristic for deducing global optimization in continuous spaces, based on the foraging behavior of the fruit fly, which usually has much better sensory perception of smell and vision than any other species.On the other hand,the Set Coverage Problem is a well-known NP-hard problem with many practical applications,including production line balancing,utility installation,and crew scheduling in railroad and mass transit companies.In this paper,we propose different binarization methods for the Fruit Fly Algorithm,using Sshaped and V-shaped transfer functions and various discretization methods to make the algorithm work in a binary search space.We are motivated with this approach, because in this way we can deliver to future researchers interested in this area,a way to be able to work with continuous metaheuristics in binary domains.This new approach was tested on benchmark instances of the Set Coverage Problem and the computational results show that the proposed algorithm is robust enough to produce good results with low computational cost.

Keywords: Set covering problem; fruit fly swarm algorithm; metaheuristics;binarization methods;combinatorial optimization problem

1 Introduction

The Set Covering Problem (SCP) is a well-known NP-hard class covering problem, which consists of finding a subset of columns in a zero-one matrix such that it covers all rows of the matrix at minimum cost.It has important practical applications, such as: localization of emergency services[1],scheduling of crews in mass transit companies[2],routing of vehicles[3],reconstruction of sibling relationships[4].

Considering the complex nature of SCP,the huge size of the real data sets and the variety of methods designed to approach similar problems,SCP has been solved by exact methods,metaheuristics and other techniques,such as hyperheuristics[5]or with Machine Learning techniques[6–8].Solving by exact methods is mainly based on Branch-and-Bound,Branch-and-Cut and Lagrangean heuristics[9].

Resolution by metaheuristics includes Genetic Algorithms [10], Tabu Search [11], Ant Colony Optimization [12], Artificial Bee Colonies [13], Firefly Algorithms [14], Cat Swarm Optimization[15], Cuckoo Search [16], Teaching-learning Based Optimization [17] and Shuffled Frog Jumping Algorithm[18],Binary Black Hole Algorithms[19].Previous work[20]propose the use of binarization techniques in order to improve the solutions of combinatorial problems like the SCP, but they lack explanation on how the binarization affects the metaheuristics,also the previous work don’t propose a pre-processing phase to reduce the computational cost of the instances of the SCP.

In this paper,we present a new approach to solving the SCP based on Wen Tsao-Pan’s Fruit Fly Swarm Algorithm (FFSA) [21].This metaheuristic is based on the foraging behavior of fruit flies,which use the senses of smell and vision to find their food;in terms of the algorithm,these senses are represented by a combination of local (smell) and global (vision) searches to improve the quality of solutions.Since FFSA was developed for continuous spaces and SCP is a binary problem,our work contributes to propose several binarization methods for a continuous algorithm in order to promote a better distribution between exploration/exploitation.In order to achieve this balance, we present eight different transfer functions and five discretization methods,generating a total of 39 variations to the original BFFSA.The results of this work suggests that BFFSA(the binary version of FFSA)is a robust algorithm,capable to produce good results at a low computational cost.

This article is organized as follows: A brief description of the Set Coverage Problem in Section 2,the presentation of Pan’s Fruit Fly Algorithm in Section 3,an adaptation of Pan’s metaheuristic to work in a binary search space in Section 4.Our proposal with the description of the functions and methods used to allow the algorithm to run in discrete spaces in Section 5.Finally, we present our results,conclusions,and possible future lines of research in Sections 6 and 7.

2 Set Covering Problem

The SCP is a classical covering problem and is defined as a binary matrixAwhereai,j∈{0,1}is the value of each cell in the matrix andi,jare the size of m-rows and n-columns,respectively:

Defining the columnjsatisfies a rowiifaijis equal to 1 and this will be the contrary case if this is 0.In addition, it has an associated costc∈C, whereC= {c1,c2,...,cn} together withi∈{1,2,...,m} andj∈{1,2,...,n} are the sets of rows and columns, respectively.The problem results in the following objective:to minimize the cost of the subsetS?J,with the constraint that all rowsi∈Iare covered by at least one columnj∈J.It is taken into consideration that when the columnjis in the subset of solutionS,this is equal to 1 and 0 otherwise.The SCP can be defined as the following:

Subject to Eqs.(3)and(4):

One of the many practical applications of this problem is the location of fire stations.Lets consider a city divided in a finite number of areas which need to locate and build fire stations.Each one of these areas need to be covered by at least one station,but a single fire station can only bring coverage to its own area and the adjacent ones;also,the problem requires that the number of stations to build needs to be the minimum.

Intentionally, we have selected an instance of SCP withm= 11 andn= 11 to represent it graphically in Fig.1 and by Eqs.(5)–(16).When a SCP formulation has a constant cost (a value of 1 in this case),we will refer to it as anUnicostSCP instance.

Figure 1:Solution to the practical example of SCP

Subject to:

As the SCP is a NP-hard class problem,one of the many difficulties that benchmarks arise is their size and the computational time associated.To solve this,many authors propose to do a pre-processing of the problem before apply any exact method or metaheuristic in order to obtain instances that are equivalent to original but smaller in terms of rows and columns.In the next section,we describe the methods used in this research.

2.1 Pre-Processing

To accelerate the problem solving,we introduce a preprocessing phase before run the metaheuristic to reduce the size of instances and improve the performance of the algorithm.In this article, we use two methods that have proven to be more effective: Column Domination [22] and Column Inclusion[23].

Column Domination:It consists into deleting the redundant columns without affecting the final solution.In other words,if the rows belonging to the columnjcan be covered by another column with a cost lower thancj,then the columnjisdominatedand it can be removed.This method is detailed in the Algorithm 1.

Algorithm 1:Column Domination 1:Order all columns by cost,ascending.2:if Two or more columns have the same cost then 3: Order those columns by the amount of rows Ij covered by column j,descending 4: Check if rows Ij can be covered by a set of other columns with a cost lower than c j(Continued)

Algorithm 1:Continued 5: if Cost is lower then 6: The column j is dominated and it can be removed.7: end if 8:end if

Column Inclusion:If a row is covered by only one column after the above domination,that column must be included in the optimal solution,and there is no need to evaluate its feasibility.

3 Fruit Fly Swarm Algorithm

The FFSA is a bio-inspired metaheuristic [21] based on the foraging behavior of fruit flies or vinegar flies for finding food, considering that their smell(osphresis)and vision senses are much better than in any other specie.The foraging behavior processes consider smell the food source,fly to it and then visualize the same food source to determine a better direction.

In Fig.2, there is a graphical representation of these foraging search processes.ConsiderS1,S2andS3as fruit flies from our population.During the smell-based search,the flies will randomly move across the search space,so their new positions will be(X1,Y1),(X2,Y2)and(X3,Y3)respectively;then,in the next phase, flies will be evaluated in their smell concentration (fitness function) to determine which one is the best in the group;for our example,we are using the reciprocal of distance to the origin(1/Disti)as fitness function.Finally,and knowing which one is the best fruit fly,the population will move into its direction to get closer to the food source.

Figure 2:Food searching of a group of fruit flies

The traditional FFSA consists of 4 phases.These are:initialization,smell-based search,population evaluation,and vision-based search.In the initialization phase,parameters are set and the fruit flies (solutions) are created randomly with a very sensitive osphresis and vision organs.During the smell-based search phase,flies use their senses to feel all kinds of smells in the air and fly towards the corresponding locations.Then,the flies are evaluated to find the best concentration of smell.When they are near to food, in the vision-based search phase, they fly toward the food source using their vision organ.The pseudocode of these phases is detailed in Algorithm 2.

Algorithm 2:Fruit Fly Swarm 1:Initialization 2:Initialize population size(N)3:Initialize generation max(gen)4:for i=1 to N do 5: Create randomly Fi,the i-th fruit fly 6:end for 7:for t=1 to gen do 8: Smell-based search 9: Emulate the smell sense by modifying population with random values 10: Fi=Fi+random_value 11: Population evaluation 12: Evaluate solutions fitness using the objective function.13: Vision-based search.14: BF=Best fruit fly 15: for i=1 to N do 16: Fi=(Fi+BF)/2 17: end for 18:end for

The FFSA has been successfully used to solve continuous problems such as: the financial distress [21], web auction logistics service [24], power load forecasting [25], design of key control characteristics for automobile parts[26]and distribution of pollution particles[27].

4 Binary-Fruit Fly Swarm Algorithm

In contrast with traditional FFSA, the BFFSA [28] uses a discrete binary string (Fig.3) to represent a solution and a probability vector to generates the population(Fig.4);then,the value of each bit of the fruit flies goes from zero to one(and vice versa)to exploit the neighborhood in the smellbased search process and perform a global vision-based search to improve the exploration ability.This new algorithm,detailed later in pseudocode(Algorithm 3),preserves the four phases but adds three search methods:Smell-based,Local-Vision-based and Global-Vision-based.Also,these methods will add new parameters to perform searches;all of them are detailed in Tab.1.

Figure 3:Representation of a fruit fly(solution)in BFFSA

Figure 4:Representation of the probability vector in BFFSA

Algorithm 3:Binary Fruit Fly Swarm Algorithms 1:Initialization Phase 2:Initialize parameter values of N,gen,S,L and b 3:Initialize probability vector p(t=0)(Continued)

Algorithm 3:Continued 4:for i=1 to N do 5: for d=1 to n do 6: Create randomly the Fd bit 7: end for 8:end for 9:for t=1 to gen do 10: Smell-based Search 11: for i=1 to N do 12: for s=1 to S do 13: Create the Fi,s neighbor,flipping L bits around Fi 14: end for 15: end for 16: Apply the repair operator 17: Population Evaluation Phase 18: Evaluate solution fitness using the objective function 19: Local-Vision-based Search 20: for i=1 to N do 21: Find the best neighbor Fi,best for Fi 22: Make the neighborhood fly towards Fi,best 23: end for 24: Global-Vision-based Search 25: Find the best fruit fly in the population,Fbest 26: Select randomly two flies F1 and F2 27: Update probability vector p(t)28: for i=1 to N do 29: Create Fi according to p(t)30: end for 31:end for

Table 1: BFFSA parameters

This article proposes and evaluates new instances for BFFSA,created from the combination of the original binary algorithm,eight transfer functions and two discrete methods,in order to improve solutions.

4.1 Initialization

In the BFFSA, each fruit fly is a solution represented by a n-bit binary vector, where n is the number of columns in the instance to solve.Thus, in a fruit flyFi, the valueFdrepresents thedthbinary decision bit,d∈[1,n].All fruit flies are generated by an n-dimensional probability vectorp(t),wheretrepresents generation(or iteration)witht∈[1,gen].Then,theis the probability in thedthdimension of the fruit flyFito be 1 during generationt.The pseudocode for this phase is detailed in Algorithm 4.

Algorithm 4:Initial population in BFFSA 1:for i=1 to N do 2: for d=1 to n do 3: if rand()＜pd(0)then 4: Fd=1 5: else 6: Fd=0 7: end if 8: end for 9:end for

To generate a uniformly distributed population in the search space, the probability vector must bep(0)=[0.5,0.5,...,0.5],so all columns have fifty percent probability of being selected.In the next generation,a new population with N fruit flies will be generated using this probability vector.

4.2 Smell-Based Search

In this phase, we createSneighbors randomly around each fruit flyFiusing the smell-based search.Each one of these neighbors are generated using the following method:first,we select randomly L-bits,and then we flip theseLcolumns values to the opposite binary value.For example,if we have a 9-bit fruit fly andL= 3,the smell-based search may produce a neighbor like the one represented in Fig.5.

At this point,a population with(N·S)-fruit flies is evaluated using the objective function.In case to get unfeasible solutions, we apply a repair operator.This additional phase will be explained later(SubSection 4.5).

4.3 Local-Vision-Based Search

Once all solutions in the neighborhood are feasible, the fruit flies are evaluated with the vision sense(the objective function)to find the best local neighbor and fly towards it.If a better neighbor is found,then the whole neighborhood will fly towards it and this recently discovered“l(fā)ocal best”fruit fly will replace the previous solution;otherwise,solution will remain the same.

4.4 Global-Vision-Based Search

This search works on the exploration ability(Eqs.(17)and(18)),considering that previous phases are more focused into the exploitation ability.To update the next fruit flies generation, this phase updates the probability vector with the differential information between the best fruit flyFbestand two random fruit flies(F1 and F2)to set a coefficient for the vision sensitivity b to enhance the exploration.

As we can see in the Eq.(17),the algorithm have a high probability of exploration in the first steps of the search,because the two random fruit flies tend to be far away one of the other,but always with the guide of the best fruit flyFbest.Once the flies are stuck on close positions, they tend to perform more exploitation with the smell-based search and the local-vision-based search.

4.5 Repair Operator

A common issue with metaheuristics is the generation of unfeasible solutions during an iteration.For the SCP,this means that some individuals will not cover all rows and a subset of constraints may be violated.To solve this issue, the algorithm implements a repair operator to make all individuals feasible and eliminate redundancy.The method described in[29]calculates a ratio between the cost of an uncovered column(cj)and the number of uncovered rows covered by that column;once all rows are covered and the solution is feasible, the operator includes an optimization step to eliminate any redundant column(Algorithm 5).

Algorithm 5:Repair Operator 1:I =The set of all rows;2:J =The set of all columns;3:αi =The set of columns that cover row i,i ∈I;4:βj =The set of rows covered by column j, j ∈J;5:K =The set of columns in a solution;6:wi =The number of columns that cover row i, i ∈I.For this,wi =|S ∩αi|,?i ∈I;7:U =The set of uncovered rows.For this,U ={i|wi =0,?i ∈I};8:for row i ∈U (in increasing order of i)do 9: Find the first column j in increasing order of j ∈αi that minimizes cj|U∩bj|;10: Add j to K and set wi =wi+1,?i ∈bj;11: Set U =U -bj;12:end for 13:for column j ∈K (in decreasing order of j)do 14: if wi ≥2 then 15: K =K j;16: wi =wi-1, ?i ∈βj;17: end if 18:end for(Continued)

Algorithm 5:Continued 19:K is now a feasible solution for the SCP that contains no redundant columns;18:end for 19:K is now a feasible solution for the SCP that contains no redundant columns;

5 Proposed Binarization Methods for the BFFSA

In this article,we propose to modify the original BFFSA with a two-step binarization technique(Fig.6),which will transform the solution from ? to an“InterSpace”(in Z)and then to the binary space.Following a procedure similar to the one proposed in[30,31],we will replace the equation for global searching (Eq.(18)) with one of the eight transfer functions (Eqs.(19)–(26)) showed in the Tab.2.Specifically,our idea is to replace the calculation for the differential information-0.5),with one of these eight transfer functions in order to define the probability to move an element of the solution from 1 to 0(or vice versa),forcing the fruit flies to be in the interval[0,1].With this change,we force to have a controlled balance between exploration and exploitation in all the search steps of the algorithm.Thus,we promote the search of new areas meanwhile we search better solution in known promising areas.

Figure 6:Classic binarization scheme

Table 2: First step-transfer functions

Table 2:Continued

It is important to note that of theS-shaped(left-hand in Fig.7) andV-shaped(right-hand in Fig.7)functions presented here,the original BFFSA uses the transfer functionPS2with a standard discretization method.In this paper,we test a universe of 40 different instances of the algorithm,where 39 of the 40 are new variations realized by our research.

Figure 7:(a)S and(b)V transfer functions

After updating the probability vector with one of these S-shaped or V-shaped transfer functions,an element of a fruit fly will be updated using one of the following discretization methods:Standard,Complement,Static Probability,ElitistandElitist Roulette,detailed in Tab.3 with the Eqs.(27)–(31),respectively.In all of them,Fdrepresents thedthposition of the fruit flyFi,Fbestis the best fruit fly in the current generation andαis the static probability.

6 Experiment Results

The modified BFFSA with the transfer functions proposed has been implemented in Java in a Common KVM processor of 2.66 GHz with 4 GB RAM computer, running Microsoft Windows 7.The parameter tuning for the algorithm is detailed in Tab.4.

Table 3: Second step-techniques of binarization

Table 4: Parameter tuning for BFFSA experiments

All the datasets tested are from Beasley’s OR Library 3.In total,we solved 65 data files;instances 4,5,6 are from[36],instances A,B,C,D are from[22]and instances NRE,NRF,NRG,NRH are the unknown-solution problem set from[37].Details of datasets are described in Tab.5.

For each instance,we report the average values obtained after run 30 times each algorithm.

Table 5: Set covering instances

6.1 Comparison of Proposed BFFSA with Other Metaheuristics

The Tabs.6–13 show the detailed results obtained by different instances of our modified BFFSA.In all of them, the results are presented along with the transfer function (TF) and discretization method(DM)used in each case,and compared with other metaheuristics in terms of minimum and maximum number of optimal founded (ZMIN,ZMAX) and the relative percentage deviation (RPD),which represents the deviation of the objective value Z(fitness)fromZOPT(Eq.(32)).

Table 6: Computational results for instance set 4

Table 6:Continued

Table 7: Computational results for instance set 5

Table 7:Continued

Table 8: Computational results for instance set 6 and A

Table 8:Continued

Table 9: Computational results for instance set B and C

Table 9:Continued

Table 10: Computational results for instance set D

Table 10:Continued

Table 11: Computational results for instance set NRE and NRF

Table 11:Continued

Table 12: Computational results for instance set NRG

For comparison purposes,we consider the values reported in[16]for Binary Cuckoo Search(BCS)and Binary Black Hole(BBH);also,we have taken results for Binary Cat Swarm Optimization(BCSO)[15], Binary Firefly Optimization (BFO) [13], Binary Shuffled Frog Leap Algorithm (BSFLA) [18],Binary Electromagnetism-like Algorithm(BELA)[38]and Binary Artificial Bee Colony(BABC)[39].

Table 13: Computational results for instance set NRH

Tab.6 presents the results obtained from instance set 4.in this case our algorithm was better to all others in comparison,as it reached optimal values in all instances;BCSO,BSFLA,BELA and BABC are unable to achieve optimal values and BFO reached only two.The closest methods in comparison were BCS with eight optimal and BBH with five.

Tab.7 describes the results from instance set 5.Once again, our algorithm got the best results along with BCS and BBH.Algorithms BCSO and BELA are unable to solve optimally any instance,BABC found only two optimal values,BFO reached three and BSFLA got four.

Tab.8 illustrates the results from instance sets 6 and A.Our algorithm performed well,reaching eight optimal values(the whole set 6 and 3 from set A).BBH was slightly better than BCS this time,BCSO and BELA are unable to optimally solve any instance,BABC is capable to find only two optimal values(one in each set),BFO reached three and BSFLA got four.

Tab.9 shows the results from instance set B and C.In case of set B,our algorithm had a very good performance,reaching all the optimal values,just like BCS and BBH.For instance set C,situation is similar,as BFFSA reached four out of five optimal values,outperforming all other methods.

Tab.10 shows the results from instance set D.Here,the BFFSA and BBH(3 optimal values each one)could not reach results of BCS.However,we can still say this is an acceptable result,considering that all other approaches got less than 30%of optimal values.

For the NRE and NRF sets described in Tab.11, only two RPD=0 per set are reached by the BFFSA algorithm.Other approaches fail in general to find optimum values as the instance set becomes harder.Only BCS and BBH are closer to our results.BSFLA and BABC achieve one optimum for the instances belonging to set NRF,while BBH and BCS reach three.

Finally, for the hardest instance sets NRG and NRH(see Tabs.12 and 13),we observe that the RPD obtained by the proposed BBFOA is good enough to compete with the approaches like BCS and BBH,as in the three cases,they could only reached one optimal value.

7 Conclusion

This article proposes several variations to BFFSA (39 to be precise), created by adding to the original BFFSA different transfer functions and discrete methods in order to improve the solutions obtained.All of these BBFOA-variations were tested into 65 SCP instances and the values reported correspond to the algorithm with the best performance.From our results,we conclude that variations presented are robust enough to compete with other algorithms as we were able to find many optimal solutions with a little parameter tuning.

We observed that best combinations of transfer functions and discretization methods depend on the instance size.For small instances (4, 5, 6, A, B, C, D) best results were achieved with transfer functions pS3 and pS4 plus the Standard discretization,whereas for huge instances(NRE,NRF,NRG,NRH)the best combinations are the same transfer functions pS3 and pS4,but with the Elitist method.A point to remark is that the use of the Elitist discretization is not exclusive for this algorithm and problem;other articles like[40]report good results with it.

In the future,we are interested in the hybridization of BFFSA with other meta-heuristics or apply an hyper-heuristics version.In the short term,we expect to test our algorithms on other SCP libraries,such like the Unicost (available at OR-Library website) or Italian railways [41] benchmarks.Due to the good results and the simplicity of this algorithm, it could be used to solve other combinatorial problems.

Acknowledgement:Marcelo Becerra-Rozas and Javier Pe?a are supported by Grant DI Interdisciplinary Undergraduate Research/VRIEA/PUCV/039.421/2021.

Funding Statement:The authors received no specific funding for this study.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.