A Binary Firefly Algorithm For Knapsack Problems

3y ago
42 Views
2 Downloads
1.50 MB
5 Pages
Last View : 15d ago
Last Download : 2m ago
Upload by : Elise Ammons
Transcription

A Binary Firefly Algorithm for Knapsack ProblemsKaushik Kumar Bhattacharjee , S.P. Sarmah†Department of Industrial & Systems Engineering,Indian Institute of Technology Kharagpur,Kharagpur 721302, West Bengal, India. Email: kkb@iem.iitkgp.ernet.in, † spsarmah@iem.iitkgp.ernet.intance move and a greedy repair operator. Also we usethe opposition-based learning technique to implement theproposed algorithm. The efficiency of the modified BFAis established by applying it to 01 KP.Abstract—Knapsack problems are one of the classicalNP-hard problem and it offers many practical applicationsin vast field of different areas. Several traditional as wellas population based metaheuristic algorithms are appliedto solve this problem. In this paper, we introduce thebinary version of firefly algorithm (FA) for solving knapsackproblems, specially 01 knapsack problem. The modifiedalgorithm utilizes the advantages of the variable distancemove along with the opposition-based learning mechanism tosolve knapsack problems efficiently. So far FA is generallyapplied to continuous optimization problems. In order toinvestigate the performance of FA on combinatorial optimization problem, an attempt is made in this paper. Todemonstrate the efficiency of the proposed algorithm anextensive computational study is provided with standardbench mark problem instances and comparison with particleswarm optimization is also carried out.The work is organized as follows: first we will give abrief description of FA. Next we will discuss the detailsof proposed BFA. Section IV presents experimental resultsof BFA and finally the conclusions, based on the results,are discussed in the last section.II.FA is one of the recently developed swarm intelligencebased metehuristic. It is proposed by Yang in 2008 [5]and is inspired from the flashing lights of fireflies innature. It is a kind of stochastic meta-heuristic algorithmthat can be applied for solving the complex optimizationproblems, as well as NP-hard problems such as graphscheduling problem [6], quadratic assignment problem[7], job shop scheduling problem [8], traveling salesmanproblem [9]. A comprehensive survey of Firefly Algorithmwas presented in [10]. In a typical FA, the brightness ofa firefly means how well the objective of a solution isand brighter firefly (solution) attracts other fireflies. Asthe distance between fireflies increases, the attractivenessdecreases exponentially because of the light absorption ofmedium. There are three basic assumption of FA [11]:Keywords—Metaheuristic algorithms, binary firefly algorithm, knapsack problems, variable distance move, oppositionbased learning.I.I NTRODUCTIONThe knapsack problems are well known strongly NPhard problem. Research has shown myriad applicationswhich can be formulated as knapsack problems, suchas project selection, resource distribution, investment decision making, capital budgeting, cargo loading, cuttingstocks etc. The most common formulation of 01 knapsackproblem (KP) isMaximize f (⃗x) Sub ject to g(⃗x) 1)n c jx j2)j 1n a j x j b,(1)j 1x j {0, 1}, j 1, 2, ., n,c j 0, a j 0, 0 b 3)n a j.All firefly are unisex. One firefly will attract otherfireflies regardless of their sex.The attractiveness of a firefly depends upon thebrightness of the firefly. The brightness will beinversely proportional to the distance. If there isno brighter one than a particular firefly, it willmove randomly.The landscape of the objective function determines the brightness of the firefly.The distance between any two fireflies (i and j) atxi and x j , respectively, can simply be evaluated by theEuclidean distance given by Equation 2.j 1The binary decision variables x j indicate whether item jis included in the knapsack or not. It may be assumedthat the all profits and weights are positive, and that allweights are smaller than the capacity b. D (xik x jk )2 .ri j x j x j (2)k 1A vast collection of exact as well as heuristic techniques are available to solve knapsack problems. Heuristicalgorithms include simulated annealing [1], genetic algorithm [2], ant colony optimization [3], particle swarmoptimization [4], etc.Where D is the dimension. As the distance increasesthe attractiveness of a firefly decreases exponentially. Theattractiveness of a firefly at a distance r is given by theEquation 3.In this paper a new Binary Firefly Algorithm (BFA)is proposed. The algorithm is based on a variable dis-978-1-4673-8066-9/15/ 31.00 2015 IEEEF IREFLY A LGORITHMβ (r) β0 e γ r ,m73m 1.(3)

Proceedings of the 2015 IEEE IEEMHere γ is the light absorption coefficient; β0 is the attractiveness at distance r 0, usually accepted as one;and m defines the sharpness of the exponential curve,usually we use m 2. For a given length scale Γ in anoptimization problem, Γ m is used as the initial value forγ . The movement of a firefly i is attracted to another moreattractive (brighter) firefly j is defined by Equation 4.xi xi β (ri j )(x j xi ) α (ε 0.5).an infeasible solution; so the fitness function of individualfirefly for 01 KP is defined as earlier, given byf (⃗x) ⃗c ⃗x (ρ (⃗a ⃗x b))2 ,where ρ (5)considering a j 0.In order to achieve sufficient diversification, the initialpopulation is generated randomly from entire dimension.And we define the stopping criteria based on four basiccriteria : reach the optimal solution, maximum run time,maximum number of iterations, predefined number of nonimprovement iterations. If any of this criteria meets, thealgorithm will stop.(4)Here ε is a random number drawing from standard uniform distribution (i.e. ε U(0, 1)); and α [0, 1] is thescaling factor of the randomness. Pseudocode for FA isgiven in Algorithm 1.B. Distance of two firefliesThe distance between any two fireflies i and j isdefined by the Hamming distance, i.e., the number ofdifferent elements between their permutations. Because thedifference between the objective function values directlyproportional to Hamming distance.Algorithm 1: Pseudocode for FA Proceduresetting the parameters of FA;generate the initial population of fireflies;evaluate the initial population;initialize the light intensity li ;while g MaxGen dofor i 1 : n (all n fireflies) dofor j 1 : n (all n fireflies) doif l j li thenmove firefly i towards firefly j;endattractiveness varies with the distance;evaluate new solution;update the light intensity li ;endendrank the fireflies and find out the current best;update the global best if required;if termination criteria fulfill thenstop the evaluation process;endendreturn the global best solution;III.cmax j 1,2,.,n a jj1) Attractiveness of fireflies: A firefly i attracted toanother firefly j, if the objective function value of iis smaller than the objective function value of j. Theattractiveness of firefly i with respect to firefly j is givenby2β (ri j ) β0 e γ ri j ,(6)where ri j is the Hamming’s distance between fireflies i andj. Theoretical value of the light absorption coefficient γ isγ [0, ], we are considering γ in range of [0.01, 0.20].C. Movement of firefliesIn continuous problem the movement is defined by theEquation 4, which can be represented by Equation 7, like[7],xi (1 β (ri j ))xi β (ri j )x j ,xi xi α (ε 0.5).B INARY F IREFLY A LGORITHMThere are several studies available in literature of Firefly Algorithm for continuous optimization problems. Onlyfew studies available for integer programming problem.In recent studies, Palit et al. [12] use a binary FireflyAlgorithm to deduce the meaning of an encrypted messagefor cryptanalysis. Falcon et al. [13] used a binary adaptiveFirefly Algorithm for fault identification in parallel anddistributed system. Chandrasekaran and Simon [14] usedbinary real coded Firefly Algorithm for solving networkand reliability constrained unit commitment problem. Inall these works they use sigmoid function for transformingcontinuous variables to binary variables, and use euclideandistance to perform light intensity measuring. Here we usea different approach to solve knapsack problems similarto the approach used by Rahmaniani and Ghaderi [15] forsolving facility location problem.(7a)(7b)So any firefly moves in solution space in two steps : inthe first step β (ri j ) determines the movement of firefly itowards firefly j given by Equation 7a; then in the nextstep α determines the random movement of firefly i givenby Equation 7b. It is to be noted that these two steps arenot interchangeable.The first step is known as β -step, from the equation itis clear that xi will be equal to x j with a probability givenby β (ri j ); and xi will be unchanged with a probabilitygiven by (1 β (ri j )). The β -step procedure is shown inAlgorithm 2.For the next step, we choose α value in the rangeof [0, 1] and randomize the movement of the firefly forcontinuous optimization problems. If the α value is highthen xi will take large step and solution will be farawayfrom the current solution. Similarly for low α value newsolution will be within the small neighborhood of thecurrent solution. So α value determines the conditionfor global and local search, an appropriate value of αdetermines the balance between global search and localsearch procedure. However obtaining the appropriate levelA. Construction of individual fireflyThe individual firefly (solution) is represented by a nbit binary string, where n is the number of variables inknapsack problem. A bit string ⃗x {0, 1}n , may represent74

Proceedings of the 2015 IEEE IEEMTABLE I.Algorithm 2: Pseudocode for β StepProblemevaluate the objective function values of firefly xi and x j , f (xi )and f (x j ) respectively;if f (xi ) f (x j ) thencalculate the Hamming’s distance ri j d(xi , x j );calculate the attractiveness using Equation 6;for k 1 : length(xi ) doif xik x jk thenx(new)ik x jk ;elsegenerate a random number r U(0, 1);if r β (ri j ) thenx(new)ik x jk ;elsex(new)ik xik ;endendendendreturn x(new)i 3940099For 01KP, variables are sorted and renumbered according to the decreasing order of their profit to weight ratios.The greedy algorithm is utilized for selection procedurewhich always chooses the last item for deletion.IV.E XPERIMENTS AND C OMPUTATIONAL R ESULTSIn this section we implement the Binary Firefly Algorithm and performance of this algorithm is investigatedwith standard 01KP instances. All computational experiTM 2Rments are conducted with python 2.7.6 in Intel⃝CoreDuo CPU E8400 @ 3.00GHz with 2GB of RAM in Unixenvironment.Two sets of knapsack problems are considered hereto test the efficiency of BCSA. First set of KP instanceswhich contains 10 instances is taken from various literature, details can be found in [20]. Items in this setranging from 4 to 23. Second set contains 25 instances istaken from http://www.math.mtu.edu/ kreher/cages/Data.html, used in [21], [22]. Number of items in this instanceranging between 8 and 24. Details of these test problemsalong with the best solution found are given in Table I.D. Generating new fireflyIn the original FA if there is no better solution thana particular one, then we generate a solution randomly.Here we use opposition-based learning (OBL) introducedby Tizhoosh [16] to generate the new solution. It isproved that an opposite solution has a higher chance tobe closer to the global optimal than a random solution[17]. Opposite point is defined as(8)A. Effect of population size (n)where X (x1 , x2 , ., xn ) be a point in n-dimensional spaceand x j [a j , b j ], j 1, 2, ., n [18]. The generalized OBL(GOBL) is defined asx́ k(a b) a24b24c24d24emake infeasible solutions to feasible one. This proceduredepends upon the problem type and the constraint.of α is not an easy task. For binary variables this α -steponly represents the change in bit values for a particularfirefly. There are two ways by which we may change inbit values for binary variables : flip and swap procedure.We may use any of these two procedures as the α step for solving knapsack problem. And α represents theprobability that a particular bit will change or not. Thenumber of bits (nB) for which there is a change in bit valuewill depend on Hamming distance (i.e., ri j ). Because hereour aim is to minimize the distance between firefly i and j,as firefly x j is brighter than firefly xi ; so xi attracts towardsx j . So nB α ri j and α should be small; otherwise theHamming distance will increase between xi and x j ratherthan decreasing. This is similar to variable distance move(k-distance or k-exchange); here we choose k 1.x j a j b j x j ,S TANDARD TEST PROBLEMS OF 01 K NAPSACK .CapacityopProblem Set 7801308791025Problem Set or the experimental study we choose population size,n {30, 40, 50, 60, 70, 80, 90, 100} and light absorption coefficient γ 0.1. Here we consider total 50 independentruns for each case and the relation between number ofiterations and population size is shown in Figure 1 for KPinstance f8 . Anova table of Kruskal-Wallis test is givenin Table II and p value is 2.91E 12. So we can rejectthe null hypothesis and conclude that at least one samplemedian is significantly different from the others. Figure2 shows the result of multiple comparison mean ranks.Two groups G1 {n n 30, 40} and G2 {n n 60, 70,80, 90, 100} are significantly different from each other. Asthe computational complexity increases with the increasein population size, so we choose population size n 60for solving knapsack problem instances.(9)where k is a real number [19]. Here we consider kis a random variable generated from standard uniformdistribution U(0, 1). This will transform the solution toa new search space, and by that provide more chance tofind better solutions.E. Constraint handlingWhen the binary string violates the constraint of thegiven problem, then repair algorithm is employed to75

Proceedings of the 2015 IEEE IEEMLight absorption co-efficient (γ) as Group350Number of Population size (n)1001502002503003509 groups have mean ranks significantly different from Group 1The effect of population size n for knapsack instance f8 .Fig. 4. Multiple comparison of mean ranks of light absorption coefficient γ for knapsack problem instance f8 .TABLE III.1Population size (n) as Group2100Fig. 1.1SourceGroupsErrorTotal234K RUSKAL -WALLIS ANOVA .9519977.21χ229.92p χ24.53E-0456C. Results of second set of problem instances78100150200250300Results of the second set of problem instances aregiven in Table IV. Here we consider population sizen 60, γ 0.02 and maximum number of iterationsiMax 20 n. Total 50 independent trails are conductedfor each problem instance. Best and worst results foundout between these runs are reported along with average,median and standard deviation among best solution foundin each trial. Also average total time and average numberof iterations are also reported. The average profit over 100runs (AVPFT) for Binary Particle Swarm Optimization(BPSO) [23], Genotype-Phenotype Modified Binary Particle Swarm Optimization (GPMBPSO) [24], and ModifiedBinary Particle Swarm Optimization (MBPSO) [21] arealso provided in Table IV.3502 groups have mean ranks significantly different from Group 4Fig. 2. Multiple comparison of mean ranks of population size (n) forknapsack problem instance f8 .K RUSKAL -WALLIS ANOVA TABLETABLE 546df7392399MS130835.2311264.54χ268.54p χ22.91E-12B. Effect of light absorption coefficient (γ )Here we consider population size n 60 and light absorption co-efficient γ {0.02, 0.04, 0.06, 0.08, 0.09, 0.10,0.12, 0.14, 0.16, 0.18, 0.20}. Total 50 independent runs foreach case and the relation between number of iterationsand light absorption co-efficient is shown in Figure 3 forKP instance f8 . Anova table of Kruskal-Wallis test is givenin Table III and result of multiple comparison mean ranksis shown in Figure 4. From the results it is clear thatwe must select light absorption co-efficient γ 0.02 forsolving KP instances.BFA easily find out the best solutions for all probleminstances. Also the average values is much more betterthan the results found out by BPSO and GPMBPSOalgorithms; and except from only one case (Problem Number 24b), BFA outperforms MBPSO for all other cases(total 19 cases). The average total time taking to solve aparticular instance and average number of iterations forsolving these problems are also very low.V.C ONCLUSION250In this work the performance of the Binary FireflyAlgorithm has been extensively investigated on standardbenchmark instances of knapsack problems. Proposed algorithm is also compared with recently developed differentversions of particle swarm optimization algorithms. BFAoutperforms most of cases. From the results it is clearthat BFA is a powerful metaheuristic for solving knapsackproblems. Also it produce much more better results compared to other standard algorithms presented in literaturewithin very small time limit. BFA may be further modifiedand applied to other combinatorial problems for gettingbetter performance, which is scheduled as future work.Number of 160.180.2Light absorption co-efficient (γ)Fig. 3. The effect of light absorption co-efficient γ for knapsack instancef8 .76

Proceedings of the 2015 IEEE IEEMTABLE 9691354909412207241124487801181005113930566R ESULTS OF PROBLEM SET 54804907.1414702.448R EFERENCES[1] A. Liu, J. Wang, G. Han, S. Wang, and J. Wen, “Improvedsimulated annealing algorithm solving for 0/1 knapsack problem,”in Sixth International Conference on Intelligence System Designand Applications (ISDA 2006), vol. 02. IEEE Computer Society,2006.[14][15][2] J. Thiel and S. Voss, “Some experiences on solving multiconstraintzeo-one knapsack problems with genetic algorithm,” INFOR,vol. 32, pp. 226–242, 1994.[16][3] P. Zhao, P. Zhao, and X. Zhang, “A new ant colony optimization for knapsack problem,” in Seventh International Conferenceon Computer-Aided Industrial Design and Conceptual Design,November 17-19 2006, pp. 1–3.[17][4] B. Ye, J. Sun, and W.-B. Xu, “Solving the hard knapsack problemswith a binary particle swarm approach,” ICIC 2006, vol. LNBI4115, pp. 155–163, 2006.[18][5] X. Yang, “Firefly algorithm,” Nature-Inspired Metaheuristic Algorithms, vol. 20, pp. 79–90, 2008.[19][6] U. Honig, “A firefly algorithm-based approach for scheduling taskgraphs in homogeneous systems,” in Informatics. ACTA Press,2010, pp. 24–33.[7] K. Durkota, “Implementation of a discrete firefly al

algorithms include simulated annealing [1], genetic al-gorithm [2], ant colony optimization [3], particle swarm . step for solving knapsack problem. And α represents the

Related Documents:

Binary prices Binary prices rautmann (2013 Binary no price Epstein (2002 Binary prices al. (2014 Binary maximis- seek- er- t al. (2010 Binary individ- price al. 2014 Binary prices Binary sset prices Halevy (2019 Auction y Binary diffi- sig- nals Liang (2019 sm y Binary erreac- news al. (2012 Auction y Binary under- signals et y Gaussian erreac .

FIRE TOPPER Fire Bowl User Manual Home » FIRE TOPPER » FIRE TOPPER Fire Bowl User Manual Contents [ hide 1 FIRE TOPPER Fire Bowl 2 Setting Up Your Fire Topper Fire Bowl 2.1 Set-Up 3 Placement and Location 3.1 Liquid Propane Tank 4 Using your Fire Topper Fire Bowl - For your safety, read before lighting. 5 Cleaning, Maintenance, Storage 6 .

Binary compounds are those that are composed of only two elements. There are three types of binary compounds: binary covalent compounds, binary ionic compounds and binary acids. Examples of binary covalent compounds include water (H 2O), carbon monoxide (CO), and carbon dioxide CO 2. The naming convention for bina

And there are also only two options of the outcome that is: right or wrong. Hence, Binary Options are also known as Binary Bets or Binary Transactions. This simplicity, the simple two-way choice, is one of the main reasons why Binary Options have been so successful since their beginning. Binary Options exist since 2008 and in 2012 it became .

Lecture #1: Bits, Bytes, and Binary CS106E Spring 2018, Young The binary number system underlies all modern computers. In this lecture we'll take a look at the binary number system and some of the implications of using binary numbers. Having a solid grounding in binary will set us up to explore digital images and digital music in the next two .

social or cultural context (livelihoods, festivals, traditional, conflict) and perhaps regulatory framework (permit fires, illegal fires). The terms include fires, wildfires, wildland fire, forest fire, grass fire, scrub fire, brush fire, bush fire, veldt fire, rural fire, vegetation fire and so on (IUFRO 2018). The European Forest Fire

Fire Exit Legend Basement N Blood Fitness & Dance Center Fire Safety Plans 7.18.13 Annunciator Panel Sprinkler Room AP SR FIRE FIRE SR ELEV. Evacuation Route Stair Evacuation Route Fire Extinguisher Fire Alarm FIRE Pull Station Emergency Fire Exit Legend Level 1 N Blood Fitness & Dance Center Fire Safety Pl

Squirrel threw the fire to Chipmunk. The Fire Beings ran after the fire. One Fire Being grabbed Chipmunk’s back. The Fire Being’s hot hand put three stripes on Chipmunk’s back. Chipmunk threw the fire to Frog. The Fire Beings ran after the fire. One Fire Being grabbed Frog’s tail. Frog jumped, and