Bat Algorithm

Chapter 8 Bat Algorithm 8.1 Introduction Bat algorithm is an innovative or population-based technique which belongs to the swarm intelligence. It is also referred to as a metaheuristic algorithm developed by Yang [1]. The bat algorithm as a unique algorithm provides a suitable solution tech- nique than numerous and prevalent classical and heuristic algorithms. The algorithm is used for quick decision making and for solving complex problems in diverse fields of operations ranging from engineering, business, transportation, and other fields of human endeavor. It is important to understand the communication and naviga- tional pattern of bats while defining the algorithm since the algorithm is based on the micro-bats echolocation (EL) [1]. EL is an enchanting and captivating sonar propen- sity produced bats. The appealing wave of sound made by the bats is a great strength they often exhibit while searching for prey. The wave of sound is a formula they adopt not only in food search but serves other purposes [2]. For instance, while searching for food in a completely dark environment, there might be obstacles or dangers on their way to the food source. This can easily be detected in some magical manner as they can sense and discern possible danger on their way to the food source as shown in Fig. 8.1 [3]. The structure and flying position of a bat is shown in Fig. 8.1. BA is therefore a very powerful algorithm as it uses the frequency-tuning methodology for range intensification of the solutions in the population. At the same time, the BA system implements the instinctive skyrocketing or zooming procedure to maintain stability during the food search or exploration process. In developing the BA, the pattern of direction finding, manipulation, and exploration during prey hunting is taken into consideration by mimicking the disparities in terms of emission rates of pulse and intensity of sound released by the bats while hunting or searching for prey. The algorithm demonstrates a high level of efficiency with a distinctive swift start process (Fig. 8.2). © The Author(s), under exclusive license to Springer Nature Switzerland AG 2021 71 M. O. Okwu and L. K. Tartibu, Metaheuristic Optimization: Nature-Inspired Algorithms Swarm and Computational Intelligence, Theory and Applications, Studies in Computational Intelligence 927, https://doi.org/10.1007/978-3-030-61111-8_8 72 8 Bat Algorithm Fig. 8.1 Structure and flying position of a bat Fig. 8.2 Behavior and navigation pattern of bat 8.2 Idealized Rules of the Bat Algorithm 73 8.2 Idealized Rules of the Bat Algorithm It is very important to note the rules associated with bats. Since bats emit loud ultrasonic sound waves and listen to the echo that reflects from the surrounding objects, the bat algorithm uses some idealized rules for uncomplicatedness. The following section points out some common rules of bat algorithm [1]: • All bats employ the echolocation pattern to perceive sense or discern prey, barrier, distance, predator, or any form of obstacle during direction-finding, routing, or path navigation. This navigation pattern is performed in a very magical way, strange to man. • Bats, in the course of direction-finding or path navigation fly haphazardly with a supposed velocity, vi while maintaining position, xi . They maintain a fixed frequency ‘f’ with varying wavelengths and loudness, Ai to reach their prey. They can adjust the frequency of pulse emission, ri . • As they get close to the prey, pulse increases, and loudness decreases. The flow diagram describing the bat algorithm is shown in Fig. 8.3. 8.3 Example of Implementation of BAT Algorithm Let’s consider 3 bats, the Bat population = 3 (i = 1, 2.3), x1 , x2 and x3 represent respectively the position of the three bats. Steps of the BAT algorithm implementation. • Initialization of the frequency (fi ), the bat population (xi ), the loudness (Ai ), the Pulse (ri ) and the velocity (vi ) with (i = 1, 2, 3, . . . n). Initially (t = 0), we will assign random values to the frequency (fi ), position (xi ), loudness (Ai ), Pulse (ri ) and velocity (vi ) as follows (Table 8.1): • While t < Max number of iterations (t = 1, 2, 3, 4, 5, …), new solutions will be generated by adjusting frequencies, velocities, and locations. BAT 1: Suppose that we consider 20 iterations for this example. Hence for the first iteration (t = 1), the condition is true. Therefore, new solutions will be generated by adjusting the frequency and updating velocity and position. The following equation will be used to adjust the frequency (NOTE: BAT can automatically adjust frequency). fi = fmin + β(fmax − fmin ) (8.1) with the domain size of the problem [fmin , fmax ] = [0, 10] and β ∈ [0, 1]   vit = vit−1 + xit − xgbest t fi (8.2) t where xgbest is the current best (nearest) position. 74 8 Bat Algorithm Fig. 8.3 Flow diagram of bat algorithm [1] Table 8.1 Initial BAT BAT 1 BAT 2 BAT 3 parameters f0 = 2 f0 = 6 f0 = 3 x0 = 4 x0 = 8 x0 = 5 v0 = 3 v0 = 7 v0 = 4 A0 = 1 A0 = 0.8 A0 = 0.9 r0 = 0 r0 = 0.2 r0 = 0.1 xit = xit−1 + vit (8.3) • If the random value rand > ri , selection of a solution among the best solutions can be done. Local solution around the best solution can be generated. 8.3 Example of Implementation of BAT Algorithm 75 Table 8.2 Updated BAT BAT 1 BAT2 BAT3 parameters f1 = f2 = f3 = 1+(5−1) = 5 2 + 1(8 − 2) = 8 3 + 1(7 − 3) = 7 x1 = 4 + 35 = 39 x2 = 8 + 63 = 71 x3 = 5 + 29 = 34 v1 = v2 = v3 = 3 + (4 − 0)8 = 35 7 + (8 − 0)7 = 63 4 + (5 − 0)5 = 29 A1 = 1 A2 = 0.8 A3 = 0.9 r1 = 0 r2 = 0.2 r3 = 0.1 For the three bats, r1 , r2 and r3 are respectively equal to 0, 0.2 and 0.1. We will choose the random value between [0, 1], let’s say 0.5. For BAT 1, 0.5 > 0: TRUE, for BAT 2, 0.5 > 0.2: TRUE and for BAT 3, 0.5 > 0.1: TRUE. If the condition is true, we will select a solution among the best solution. How to select the best solution? According to the frequency: Best solution = if the prey is in the scope of frequency increase. The frequency of the waves increases if the BAT finds the prey (i.e. best solution). Referring to Table 8.2, the highest frequency corresponds to BAT 1, which is the best solution in this case. We can generate a local solution around the best solution. We will update the position of the first BAT using the following equation: xnew = xold + εAt (8.4) with ε ∈ [−1, 1] xnew = 35 + 1.1 = 36 • If rand < Ai and f(xi ) < f(x∗ ) accept the solution and increase ri and reduce Ai (as the BAT moves closer to the prey, the loudness decreases and pulse rate increases). f(xi ) and f(x∗ ) depend on the new BAT location and the best solution depending on the function. If the solution is TRUE, we will increase ri and reduce Ai using the following equations:   rit+1 = ri0 1 − eγ t (8.5) Ait+1 =∝ Ait (8.6) where the two constant ∝ and γ are in the range [0, 1]. Let’s assume ∝ = γ = 0.9, the updated values are: 76 8 Bat Algorithm BAT 1 BAT2 BAT3 f1 = 8 f2 = 7 f3 = 5 x1 = 36 x2 = 71 x3 = 34 v1 = 39 v2 = 63 v3 = 29 A1 = 1 A2 = 0.8 A3 = 0.9 r1 = 0.4 r2 = 0.2 r3 = 0.1 • We can now rank the BAT and find the current best. We will check the loudness first and the frequency. Based on that, the first BAT has the highest loudness and frequency. It is the current best solution. 8.4 Application of BAT Optimization Algorithm with a Numerical Example A MATLAB code has been provided in the Appendix to illustrate the implementation of the BAT algorithm for a typical optimization problem considering a numerical equation F(x) = (x1 6 + x2 4 − 17)2 + (2x1 + x2 − 4)2 describing the Wayburen function. The model considers 10 bats and the maximum number of iterations was 1000. The best solution obtained by BAT is: [1.3138 1.8528 0.261 0.83905 0.34859 1.1436 0.73859 1.7623 0.16537 0.28717]. The best optimal value of the objective function found by BAT is: 0.23604. The parameter space and objective space are shown respectively in Figs. 8.4 and 8.5. The MATLAB code is provided in Appendix F. A detailed description of the CODE is provided in Ref. [1]. Fig. 8.4 Parameter space 8.5 Application of BAT Optimization Algorithm … 77 Fig. 8.5 Objective space 8.5 Application of BAT Optimization Algorithm for Traffic Congestion Problem Case Scenario A number of problems can be caused by congested traffic. Congestion is mainly caused by intensive use of vehicles. Traffic congestion in Delta State is a big challenge especially in the morning and night hours. Individuals who navigate to workplace in the morning hours (8 a.m.) encounter this recurring traffic congestion, leading to delay, high fuel consumption, environmental pollution and other operating costs. Also, returning home after work (4 p.m.) could be challenging too. This issue is common at certain locations in the state (PP junction in DSC and Mofor junction). Another location spotted with a high level of traffic congestion is the Udu road to Enerhen junction. From observation, the roads are very narrow to allow uninterrupted traffic flow. Observation It was observed that the transportation system in the state was poorly planned, as alternative routes were not mapped out for easy access, and to further congest the road, marketers and roadside sellers occupy the vast extension of the road. All these led to traffic congestion in a section of the state under un-signalized circumstances. Network Architecture To address the problem, road network can be taken as a directed graph G = (N, a), where ‘N’ is the set of nodes; i.e., the road junctions ‘a’ is the links connecting the junctions as shown in Fig. 8.6. For each pair of origin (O) and destination (D), (O-D) signify a nonnegative travel demand, drs . The road network can represent a highly connected graph, where each node “i” is accessible by another node “j” following the directed path of the network 78 8 Bat Algorithm Fig. 8.6 An intersection of the network showing an O-D pair connected by a 3-way and a 4-way junction O i j D ‘N’. It is assumed that the links connecting the nodes have a travel time function ta , for the assigned rate of flow xa . This study aims to mimic the bat algorithm for solving traffic congestions issues in the state. The major objectives include to: (i) choose possible shortest route to travel from source to destination while maintaining uninterrupted traffic flow; (ii) reduce the traffic delay at each junction under un-signalized circumstances. The continuous network design model is chosen with budget constraints for the link capacity expansion. The objectives are interdependent and can be formulated as a bi-level problem. The upper level is responsible for reducing the travel time of the assigned road users or travellers. The lower level is the traffic assignment model which estimates the travelers flow. The model is presented clearly in Fig. 8.7. This model can be formulated mathematically as shown below for both the layers. Upper-Level Function   minT(y) = xa ta (xa ) + da ya (8.7) a∈A a∈A(y)  Such that, ca ya ≤ B where A is the set of all links ‘a’ in the network ‘N’. Link Travel Time Function Traffic Assignment Function Wait time at signal Traffic flow estimation Users’ travel time Fig. 8.7 Bi-level model for traffic network determination problem 8.5 Application of BAT Optimization Algorithm … 79 X(a) gives the user equilibrium flow, which is estimated from the lower level of the model for the assigned value of link capacity ‘y’. ca is construction cost for link ‘a’ and B is the budget. Lower Level Function  xa min ∫ ta (u)du (8.8) 0 a∈A  Such that, fk = dij fk ≥ 0  fk δij = xa ∀δij = {1; 2; ifa ∈ k rs where f is the flow on path k and r-s are the nodes on the path connecting O-D pair. The flowchart for the traffic signal optimization from a BA perspective is shown in Fig. 8.8. Solution Procedure Using Delta State, Udu road as a case study from the Enerhen Junction to Orhuwhorun Junction. The nodes and links are presented in Fig. 8.9. Model Notation and Formulations • No of links, a = 2 • No of nodes/junctions, N = 3 • The possible number of networks in this case is given as 2n 23 = 8 possible number of networks • Budget constraint, B = 500,000 NGN • Upper-level function is considered • First, according to the flow chart, the necessary parameters are considered • Distance by car is 22 km • Time taken is to navigate—33 min • Assuming the following: – Xa = 0.67 km/min – Ta = 33 min – Ya (link capacity) = 50 – da (demand) = 300 – ca = 50,000 NGN per link Notice that:  ca ya ≤ B 80 8 Bat Algorithm Fig. 8.8 Flow chart for the traffic signal optimization problem using bat algorithm 8.5 Application of BAT Optimization Algorithm … 81 Fig. 8.9 Road network for three nodes and two links Since the above condition is satisfied, we proceed;   minT(y) = xa ta (xa ) + da ya a∈A a∈A(y)   0.67 × 33 × 0.67 + (300 × 50) a∈A a∈A(y) This gives min T(y) = 15,014.8137. Bat algorithm is applied at the upper-level function. Defining objective function f(x) and assigning the parameters. • Bat population (demand), xi = 300 82 8 Bat Algorithm • Velocity, vi = 0.67 km/min • Loudness, ai = 50,000 (cost of link construction) • Pulse rate, ri = 50 (link capacity) • Frequency, fi = 0.030. Solution Method • Let the bats stationed for direction-finding represent the available vehicles in search space or road network. The map reading or course-plotting is made easy. • Since the number of vehicles passing the road has been estimated to be roughly 300 periodically and the link capacity is 50 per link, then the total capacity for both links is 50 × 2 = 100. • The roads mapped for the study is such that 100 vehicles can be allowed for easy navigation. • 300 vehicles use the road frequently, a random value is assigned to the pulse rate or link capacity. • For the first iteration, it is assumed that the link capacity or pulse rate is 70 per link. This makes a total of 140 vehicles for both links. • According to the initially defined condition, Rand > ri ; 70 > 50 satisfies the condition. • It is important to generate a new solution around the defined condition. • To achieve this, assume the link capacity (pulse rate) to be 75, making the demand for both links equal to 150 vehicles. • Since the link capacity has been increased, the time rate of flow will reduce. So that ta equal 31 min; fi equal 0.032 and velocity, vi equal 0.71 km/min. The cost of construction (loudness) increases to 90,000 NGN. • For the second iteration, assume the link capacity is 100, therefore, demand for both links equal 200 vehicles. • Recall the established condition, Rand > ri ; 100 > 50 satisfies the condition, it is important to store and generate a new solution around the stated condition. • Assume the link capacity to be 105, making the demand for both links equal to 210. • Again, the time rate of flow will automatically increase as the link capacity has reduced. • So, ta equals 29 min; fi equals 0.034 and vi equals 0.76 km/min. • The cost of construction (loudness) increases to 100,000 NGN. • For the third iteration, let Rand equal 140, making the demand for both links equal to 280 vehicles. • Following the established condition, Rand > ri ; 140 > 50 satisfies the stated condition. It is important to store and generate a new solution around the stated condition. • Considering the link capacity of 145. The demand for both links becomes 290. With increase in the link capacity, the time rate of flow will increase to ta = 27 min; fi = 0.037 and vi = 0.81 km/min. The construction cost (loudness) equals to 150,000 NGN. 8.5 Application of BAT Optimization Algorithm … 83 • Finally, for the last iteration, Rand equals 155, and the demand for both links equals 310. Since Rand > ri ; 155 > 50. Since the condition is satisfied, a new solution is generated. • With a pulse rate of 160, the demand for both links becomes 320 vehicles. The time flow rate increases to 25 min, at fi of 0.040, and vi equal 0.88 km/min. The construction cost (loudness) increases to 200,000 NGN. Calculating the fitness of generated population, the table is presented thus: Population/demand Capacity links 100 50 150 75 210 105 290 145 320 155 Comparing obtained information using the condition established thus: • Rand < ai and f(xi ) < f(x) • ai = 50,000 and f(xi ) = 0.030. For the first iteration, the random loudness was ₦90,000 which does not satisfy the condition since it is greater ₦50,000. But, f(xi ), 0.030 is less than f(x) which are, 0.032, 0.034, 0.037 and 0.040, so the results are shown and ranked in the following table. Population/demand Capacity per link Velocity (vi ) Time (ta ) (min) Frequency (fi ) (km/min) 100 50 0.67 33 0.030 150 75 0.71 31 0.032 210 105 0.76 29 0.034 290 145 0.81 27 0.037 320 155 0.88 25 0.040 At this stage, the termination criteria is reached. Optimal result is generated by creating a road with the link capacity of 155 vehicles so that a total of 320 vehicles can freely navigate through, from the origin to destination at a faster rate, 0.88 km/min and for a lesser time, 25 min. The construction of this road will only cost 200,000 NGN per link summing up to a total amount of ₦400,000 which is clearly within the assigned budget. So having solved the problem of time, the lower-level function can be obtained by using optimized results  Xa ta (u)du a∈A 0 84 8 Bat Algorithm where, ta = 25 min, xa = 0.88 km/min. Substituting in the above equation,  0.88 25u · du 0 This results in total value of 9.68 which represent the traveller’s flow. The result cannot be optimized further so that the construction budget is not exceeded. By mimicking the bat algorithm and following the echolocation pattern of bats for easy location of prey and avoiding obstacles, a transportation network problem has been solved in Delta State, Udu road. The following parameters have been consid- ered: population of bat (of the vehicles that passes the roads), velocity, loudness (construction cost for link), and pulse rate (link capacity), corresponding to the bat behavior. The problem of travel time has been optimized to allow uninterrupted traffic flow under un-signalized situation at Udu road. After four iterations, best solution was obtained with maximum link capacity of 160 to accommodate vehicles travelling that route on a daily basis. References 1. Yang, X.S. 2010. A new metaheuristic bat-inspired algorithm. In Nature Inspired Cooperative Strategies for Optimization (NICSO 2010), 65–74. Berlin, Heidelberg: Springer. 2. Yang, X.S. 2011. Bat algorithm for multi-objective optimisation. International Journal of Bio- Inspired Computation 3 (5): 267–274. 3. Rizk-Allah, R.M., and A.E. Hassanien. 2018. New binary bat algorithm for solving 0–1 knapsack problem. Complex and Intelligent Systems 4 (1): 31–53.