# Binary Bat Algorithm: On The Efficiency of Mapping Functions When Handling Binary Problems Using Continuous-variable-based Metaheuristics

Zakaria Dahi, Chaker Mezioud, Amer Draa

► To cite this version:

Zakaria Dahi, Chaker Mezioud, Amer Draa. Binary Bat Algorithm: On The Efficiency of Mapping Functions When Handling Binary Problems Using Continuous-variable-based Metaheuristics. 5th International Conference on Computer Science and Its Applications (CIIA), May 2015, Saida, Algeria. pp.3-14, 10.1007/978-3-319-19578-0_1 . hal-01789955

HAL Id: hal-01789955

https://inria.hal.science/hal-01789955

Submitted on 11 May 2018

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Binary Bat Algorithm:
On The Efficiency of Mapping Functions When Handling
Binary Problems Using Continuous-variable-based
Metaheuristics

Zakaria Abd El Moiz Dahi, Chaker Mezioud, and Amer Draa

Modeling and Implementation of Complex Systems laboratory
Dept. of New Technologies of Information and Communication
Constantine 2 university
Constantine City, Algeria

{zakaria.dahi,chaker.mezioud}@univ-constantine2.dz

{draa_amer@yahoo.fr}

**Abstract.** Global optimisation plays a critical role in today's scientific and industrial fields. Optimisation problems are either continuous or combinatorial depending on the nature of the parameters to optimise. In the class of combinatorial problems, we find a sub-category which is the binary optimisation problems. Due to the complex nature of optimisation problems, exhaustive search-based methods are no longer a good choice. So, metaheuristics are more and more being opted in order to solve such problems. Some of them were designed originally to handle binary problems, whereas others need an adaptation to acquire this capacity. One of the principal adaptation schema is the use of a mapping function to decode real-valued solutions into binary-valued ones. The Antenna Positioning Problem (APP) is an NP-hard binary optimisation problem in cellular phone networks (2G, EDGE, GPRS, 3G, 3G+, LTE, 4G). In this paper, the efficiency of the principal mapping functions existing in the literature is investigated through the proposition of five binary variants of one of the most recent metaheuristic called the Bat Algorithm (BA). The proposed binary variants are evaluated on the APP, and have been tested on a set of well-known benchmarks and given promising results.

# 1 Introduction

Combinatorial problems are problems whose parameters belong to a finit set of integers ($x_i \in \mathbb{N}$). The latter includes a more specific type called *binary optimisation problems*: problems whose parameters can take values from a bi-valued search space called *genotype space* ($x_i \in \{1, 0\}$).

The design of cellular phone networks (2G, EDGE, GPRS, 3G, 3G+, LTE, 4G) is one of the most critical tasks during the network implantation. Any design process that can not deal with this phase may alter the service quality
of the network itself. The *Antenna Positioning Problem (APP)* is one of the
most challenging optimisation issues in the design phase of cellular networks.
The APP is formulated as a binary optimisation problem and was proven to be
NP-hard.

Metaheuristics are efficient tools to use when tackling such optimisation prob-
lems. Regardless to the source of their inspiration, metaheuristics can be divided
into algorithms who are originally designed to tackle continuous problems, and
those who are designed to tackle combinatorial ones.

The *Bat Algorithm (BA)*, is one of the recently proposed metaheuristics [14].
It was inspired by the natural phenomenon of echolocation used by bats. The
BA was originally designed to tackle optimisation problems within continuous
search space and it has shown encouraging performances.

Generally, when adapting a *continuous-variable-based metaheuristic* (i.e. a *metaheuristic that was designed originally to operate on variables within continuous search space*) to tackle binary problems, many schemas of adaptation exist. One of the most opted one, is the use of a mapping function to map the real-valued solutions into binary ones. Several sub-schemas of mapping exist as well in this last one : *one-to-one*, *many-to-one*, *one-to-many*.

Many questions still surround this schema of adaptation, such as the fact
that the efficiency of these mapping functions is still fuzzy and unexplored. In
addition, no clear statement exist on whether using *binary-variable-based metaheuristics* (i.e. *metaheuristics that were designed originally to operate on variables within binary-valued search space*) or continuous ones to tackle binary optimisation problems. Does the efficiency of these mapping functions depends on
the algorithm used or the problem solved. Finally, no affined study shows if it is
worth using this mapping functions and ultimately which kind of metaheuristics
is more efficient when solving binary problems.

Through analysing the literature, the five principal mapping functions exist-
ing are used to propose new binary variants of the *Bat Algorithm*. The mapping
functions used in this work were selected to illustrate different schemas of map-
ping. These functions are : The *Nearest Integer method (NI)*, the *normalisation
technique*, the *Angle Modulation method (AM)*, the *Great Value Priority method
(GVP)* and finally, the *Sigmoid Function (SF)*. The proposed binary variants
of the BA were tested on the APP using well-known benchmark instances, with
different sizes and complexity as well. In addition, the last ones were compared
to one of the most used binary-variable based algorithm : the *Genetic Algorithm*.

The remainder of this paper is structured as follows. In Section 2, we intro-
duce basic concepts related to the antenna positioning problem, the bat algo-
rithm, and the mapping functions used in this work. In Section 3, we introduce
the proposed binary variants of the bat algorithm. Section 4 is dedicated to ex-
perimental results, their interpretation and discussion. Finally, we present the
conclusion of our work in Section 5.
# 2 Basic Concepts

In this Section, we introduce basic concepts related to the antenna positioning problem, the bat algorithm, and the used mapping functions.

## 2.1 Antenna Positioning Problem

In this section, we present a widely used formulation of the APP, that was given by Guidec et. al. [3]. This modeling of the antenna positioning problem consider two objectives : maximizing the covered area while minimizing the number of base station used.

The antenna positioning problem recalls NP-hard problems in graph theory such as the Minimum Dominating Set (MDS), the Maximum Independent Set (MIS), or the Unicast Set Covering Problem (USCP), see Sub-figures (a), (b), (c) of Figure 2.

Let $L$ be the set of all potentially covered areas and $M$ the set of all potential locations of base stations. Suppose $G$ is a graph where $E$ is the set of edges in the graph verifying that each transmitter is linked to the area that it covers. One seeks for the minimum subset of transmitters that covers the maximum surface of a given area. In other words, the objective is to find a subset $M'$ such that $|M'|$ is minimised and $|Neighbours(M', E)|$ is maximised [4]; where Neighbours represents the set of the covered area, and $M'$ represents the set of transmitters used to cover this area.

$$|Neighbours(M', E)| = \{u \in L | \exists v \in M', (u, v) \in E\} \quad (1)$$

$$M' = \{t \in B | x_t = 1\} \quad (2)$$

A Base Tranceiver Station (BTS) is a radio transmitting device with a specific type of coverage (See Figure 1). In this work, we used three types of coverage introduced in [1]. A cell is a part of a geographical area that is covered by a base station.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Antenna Coverage Models</figcaption></figure>
The working area is discretized in a rectangular grid with $Dim_x$ and $Dim_y$ dimensions. Having $Sites = \{site_1, site_2, site_3, ..., site_N\}$ is the set of potentially preselected sites, where the antennas can be placed. Each potential site location is identified by Cartesian coordinates $\{site_1 = (x_1, y_1), site_2 = (x_2, y_2), site_3 = (x_3, y_3), ..., site_N = (x_N, y_N)\}$, see Sub-figures (d), (e), (f) of Figure 2.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Representation of The Discretized Area</figcaption></figure>

A potential solution of the APP can be a binary vector described as follows. Each vector $\vec{X}$ represents a potential configuration of the mobile network. The number of elements of each vector represents the number of potential candidate sites. The rank of each dimension represents the rank of the corresponding base station $i = 1, 2, ..., Dimension_{\vec{X}}$. Each dimension of the vector is strictly binary valued: $x_i \in \vec{X} / x_i = 1 \lor x_i = 0$. If $x_i = 1$, the $i^{th}$ base station is selected, otherwise it is discarded. The objective function to optimize is defined by the formula 3.

$$ \text{Maximize: } f(x) = \frac{\text{Cover ratio}^{\alpha}}{\text{Number of used base station}} \qquad (3) $$

with:

$$ \text{Number of used base station} = \sum_{i=1}^{\text{Dimension}_{\vec{X}}} x_i, \qquad (4) $$

with:

$$ \text{cover ratio} = \left( \frac{\text{Covered area}}{\text{Total area}} \right) * 100 \qquad (5) $$

And:

$$ \text{Covered area} = \sum_{i=1}^{\text{Dim}_x} \sum_{j=1}^{\text{Dim}_y} \text{cover}(i, j), \qquad (6) $$

And:

$$ \text{Total area} = \text{Dim}_x * \text{Dim}_y. \qquad (7) $$

It is worth to mention that other mathematical models of the antenna positioning problem exist like the one proposed in [12]. Generally, these models differ by their mathematical formulations or modeling.
## 2.2 Bat Algorithm

The Bat Algorithm has been recently proposed. It is a swarm-based metaheuris-
tic [14]. This algorithm is inspired by the natural echolocation behaviour of bats.
Microbats use a type of sonar, called echolocation, to detect their preys, avoid
obstacles, and locate their roosting crevices in the dark. These bats emit a very
loud sound pulse and listen for the echo that bounces back from the surrounding
objects. Their pulses vary in properties and can be correlated with their hunting
strategies, depending on the species. The bats then adjust the pulse and rate
of the sound as they get closer to the obstacles or the prey. This phenomenon
has been translated into the newly proposed bat algorithm. The pseudo-code of
Algorithm 1 describes the general framework of the bat algorithm.

**Algorithm 1. The Bat Algorithm**

1: Objective function $f(x), x = (x_1, ..., x_d)^T$
2: Initialize the bat population $X_i$ ($i = 1, 2, ..., n$) and $V_i$
3: Define the pulse rate $r_i$ and the loudness $A_i$
4: **Input**: Initial bat population
5: **while** ($t < \text{Max number of iterations}$) **do**
6: &nbsp;&nbsp;&nbsp;&nbsp;Generate new solutions by adjusting frequency, and updating velocities and locations/solutions (Equations 8 to 10)
7: &nbsp;&nbsp;&nbsp;&nbsp;**if** ($rand > r_i$) **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Select a solution among the best solutions
9: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
10: **end if**
11: Generate a new solution by flying randomly
12: **if** ($rand < A_i$ & $f(X_i) < f(X_*)$) **then**
13: &nbsp;&nbsp;&nbsp;&nbsp;Accept the new solutions
14: &nbsp;&nbsp;&nbsp;&nbsp;Increase $r_i$ and reduce $A_i$
15: **end if**
16: Rank the bats and find the current best $X_*$
17: **end while**
18: **Output**: Best bat found (i.e. best solution)

Equations 8, 9 and 10 define how the position $X_i$ and velocity $V_i$ in a $d$-dimensional search space are updated. The new solution $X_i^t$ and velocity $V_i^t$ at a time step $t$ are given by :

$$f_i = f_{min} + (f_{max} - f_{min})\beta \quad (8)$$

$$V_i^t = V_i^{t-1} + (X_i^t - X_*)f_i \quad (9)$$

$$X_i^t = X_i^{t-1} + V_i^t \quad (10)$$
Initially, each bat is randomly assigned a frequency which is drawn randomly from [f<sub>min</sub>, f<sub>max</sub>]. βε [0, 1] is a random vector drawn from a uniform distribution. X<sub>*</sub> is the current global best location (solution) which is located after comparing all the solutions.

When a local search is performed a solution is selected among the current best solutions. A new solution for each bat is generated using a random walk as described in Equation 11; Where ε is a random number from [-1, 1], and A<sup>t</sup> = <A<sup>t</sup><sub>i</sub> > is the average loudness of all bats at this time step.

$$
X_{new} = X_{old} + \epsilon A^{t} \qquad (11)
$$

Likewise, the loudness A<sub>i</sub> and the rate r<sub>i</sub> of pulse are updated once the new solution is accepted. This is done using Formulas 12 and 13, where α and γ are constants. Initially, each bat is randomly assigned a loudness and a rate drawn respectively from the intervals [A<sub>min</sub>, A<sub>max</sub>] and [r<sub>min</sub>, r<sub>max</sub>].

$$
A_{i}^{t+1} = \alpha A_{i}t \qquad (12)
$$

$$
r_i^{t+1} = r_i^0 [1 - \exp(-\gamma t)] \quad (13)
$$

2.3 From Phenotype to Genotype Space

Several approaches exist for adapting a continuous-variable-based metaheuristic to work also in binary search space. The first schema of adaptation consists in replacing arithmetic operators of the metaheuristic by logical ones to operate directly on the binary solutions. The second aims to find the corresponding operators of the algorithms in the geometric space (*Hamming space*). Finally, the third approach consists in conserving the original operators, architecture and solution representation of the algorithm, and adding a complementary module that maps real-valued solutions into binary ones. The techniques used in this third category are generally known also as *mapping functions*. Several schemas of mapping exist. The principal ones are : *one-to-one*, *many-to-one*, and *one-to-many*.

The mapping functions used in this work have been chosen to illustrate sev-
eral mapping schemas and several mathematical properties. In the following, the
mapping functions used in this study are introduced.

**Nearest Integer (NI):** This technique consists of assigning a real number to the nearest integer by rounding or truncating it up or down [2, 6].

**Normalisation :** This approach was proposed in [9, 10]. It consists of the normalisation of the solution by linearly scaling it using the Formula_14. Then the condition 15 is applied to get the corresponding binary solution.
$$x'_{ij} = \frac{(x_{ij} + x_i^{min})}{(|x_i^{min}| + x_i^{max})} \qquad (14)$$

$$x_{ij} = \begin{cases} 1, & \text{If } x'_{ij} \ge 0.5 \\ 0, & \text{Otherwise} \end{cases} \qquad (15)$$

Assuming that $i = 1 \cdots N$ and $j = 1 \cdots D$. Where : $N$ is the population size, $D$ is the size of the solution vector. $x_i^{min}$ and $x_i^{max}$ are respectively the minimum and the maximum values in the $i^{th}$ vector at the iteration $t$.

**Angle Modulation (AM) :** The idea is to use a trigonometric function to map real-valued solutions into binary ones. The generator function is used for signal processing in telecommunications and defined as follows [11, 13].

$$g(x_{ij}) = \sin(2\Pi(x_{ij} - a) * b * \cos(2\Pi(x_{ij} - a) * c)) + d \qquad (16)$$

Where $i = 1 \cdots N$ and $j = 1 \cdots D$. $N$ is the population size, $D$ is the size of the solution vector. $g(x)$ is the generator function, and $x_{ij}$ is a single element from a potential solution vector. Instead of optimizing a $D$-dimensional binary string solution, the search space is reduced to a 4-dimensional search space. Each vector of solution $\vec{G}$ represents potential values of the coefficients $(a, b, c, d)$ in the generator function. At each iteration, every solution vector is applied to a sample vector $\vec{X}$ with the original $D$-dimensions of the problem. The sample vector is drawn from a uniform distribution and has equally spaced intervals between each dimension and another. Finally, one has to apply the following formula on the resulting vector :

$$x_{ij} = \begin{cases} 1, & \text{If } g(x_{ij}) \ge 0 \\ 0, & \text{Otherwise} \end{cases} \qquad (17)$$

**Sigmoid Function (SF) :** In this technique, each real valued dimension of the solution vector is mapped into a strictly binary valued one [7,8]. The probability of each dimension to flip to one state or another is computed according to the real value of the dimension itself by applying Formula 18.

$$x_{ij} = \begin{cases} 1, & \text{If } \text{Rand}[0, 1] \le \frac{1}{1 + e^{-x_{ij}}} \\ 0, & \text{Otherwise} \end{cases} \qquad (18)$$

Where $i = 1 \cdots N$ and $j = 1 \cdots D$. $N$ is the population size, $D$ is the size of the solution vector, and $\text{Rand}[0, 1]$ is a randomly generated positive number, drawn from a uniform distribution in the interval $[0, 1]$.
**Great Value Priority (GVP)**: Recently, authors in [5] have introduced this technique. Starting from a given real valued solution vector $\vec{X}$, a permutation vector $\vec{P}$ is created. The first element of the permutation vector $p_1$ will contain the position of the largest element in the original vector, the second element of the permutation vector $p_2$ will receive the position of the second largest element of the real valued vector, and so on. The procedure will be repeated until all the elements of the original vector are browsed. Finally, having the permutation vector $\vec{P}$, the following formula will be applied to recover back a binary valued vector.

$$x_{ij} = \begin{cases} 1, & \text{If } p_j > p_{j+1} \\ 0, & \text{Otherwise} \end{cases} \qquad (19)$$

## 3 The proposed Binary Bat Algorithm

The inclusion of the discretisation step using one of the mapping functions after line code 10 in pseudo-code of Algorithm 1 results in giving birth to new variants of the bat algorithm. The first variant, using the nearest ineteger method as a discretising technique is called NI-BBA (for Nearest Integer based Binary Bat Algorithm). The second variant is called N-BBA (for Normalisation based Binary Bat Algorithm) is based on the normalisation method. The third variant uses the sigmoid function and is called SF-BBA (for Sigmoid Function based Binary Bat Algorithm). The fourth variant is the AM-BBA (for Angle Modulation based Binary Bat Algorithm) is based on the angle modulation method. Finally, GVP-BBA (for Great Value Priority based Binary Bat Algorithm) uses the great value priority technique.

## 4 Experimental Results and Discussion

The experiments where carried using an Intel I3 core with 2 GB Ram and a Windows 7 OS. The implementation was done using Matlab 7.12.0 (R2011a).

Two scenarios were randomly generated. Both are representing a working area of 20.25 Km². The first instance contains 549 available locations, whereas the second instance contains 749 available locations. Other instances of 149 and 349 preselected positions, are used here. They were provided by the university of Malaga, Spain. We used three types of coverage : squared, omnidirectional and directive [1]. It is worth to mention that directive antennas cover one sixth of the area of omnidirectional antennas having the same radius. Table 1 shows all the features of the used instances.

The proposed binary variants of the bat algorithm were also compared to one of the most used binary-variable-based metaheuristic and whose the efficiency is well established : the canonical Genetic Algorithm (GA). The GA uses a wheel selection and a two-point crossover with a probability equal to 0.7 and a bit-flip
<table><caption>**Table 1.** Instances : Size and Coverage</caption><thead><tr><th>Instance Type</th><th>Grid Dimension</th><th>Instance</th><th>Coverage</th><th>Radius</th></tr></thead><tbody><tr><td rowspan="6">Synthetic</td><td rowspan="6">287 x 287</td><td rowspan="3">149</td><td>Omnidirectional</td><td>22</td></tr><tr><td>Squared</td><td>20</td></tr><tr><td>Directive</td><td>22</td></tr><tr><td rowspan="3">349</td><td>Omnidirectional</td><td>22</td></tr><tr><td>Squared</td><td>20</td></tr><tr><td>Directive</td><td>22</td></tr><tr><td rowspan="6">Random</td><td rowspan="6">300 x 300</td><td rowspan="3">549</td><td>Omnidirectional</td><td>26</td></tr><tr><td>Squared</td><td>24</td></tr><tr><td>Directive</td><td>26</td></tr><tr><td rowspan="3">749</td><td>Omnidirectional</td><td>26</td></tr><tr><td>Squared</td><td>24</td></tr><tr><td>Directive</td><td>26</td></tr></tbody></table>

mutation with a probability of 0.05. The percentage of chromosomes used to create the matting pool is 50 %. The parameters of the bat algorithm used in this experiment are shown in Table 2.

<table><caption>**Table 2.** Bat Algorithm Parameters</caption><thead><tr><th>Prameter</th><th>Value</th></tr></thead><tbody><tr><td>f<sub>max</sub></td><td>10</td></tr><tr><td>f<sub>min</sub></td><td>-10</td></tr><tr><td>A<sub>max</sub></td><td>2</td></tr><tr><td>A<sub>min</sub></td><td>1</td></tr><tr><td>r<sub>max</sub></td><td>1</td></tr><tr><td>r<sub>min</sub></td><td>0</td></tr><tr><td>α</td><td>0.9</td></tr><tr><td>γ</td><td>0.9</td></tr></tbody></table>

The experiments were performed till reaching 20.000 evaluations, and each one is repeated for 20 runs. Several results are reported such as : the *best* and the *worst* fitness, and also the *mean* and *standard deviation* of fitness value over 20 runs.

Tables 3, 4, 5 and 6 show the results obtained when evaluating the five binary variants of the bat algorithm using the instances 149, 349, 549, 749 and this for each type of coverage : squared, omnidirectional and directive.

Based on the results shown in Tables 3, 4, 5 and 6 many observations can be made. The performances of the variants for small instances (149, 349) are close, but one can note that as the instance size increases (549, 749), the difference in the efficiency of the variants is more obvious. So, for some variants like the AM-BBA, N-BBA, GVP-BBA their efficiency depends highly on the size of the problem treated. Whereas for other variants such as the NI-BBA and the SF-BBA the efficiency is maintained even if the size of problem increases.

In general, NI-BBA and SF-BBA variants has shown better results than the other variants when solving the APP, especially the NI-BBA. The scalability of both variants is similar since both succeeded to solve the different sizes of
<table><caption>**Table 3.** Results of the Bat Algorithm Variants For Instance 149</caption><thead><tr><th>Instance</th><th>Coverage</th><th>Algorithm</th><th>Best</th><th>Worst</th><th>Mean</th><th>Std</th></tr></thead><tbody><tr><td rowspan="14">149</td><td rowspan="6">Squared</td><td>NI-BBA</td><td>120.582</td><td>120.582</td><td><b>120.582</b></td><td>1.458E-14</td></tr><tr><td>N-BBA</td><td>106.361</td><td>95.006</td><td>100.501</td><td>2.70580121</td></tr><tr><td>AM-BBA</td><td>111.120</td><td>97.564</td><td>104.250</td><td>4.63919122</td></tr><tr><td>SF-BBA</td><td>103.012</td><td>102.112</td><td>102.157</td><td>0.20130794</td></tr><tr><td>GVP-BBA</td><td>113.548</td><td>113.400</td><td>113.489</td><td>0.0745577</td></tr><tr><td>GA</td><td>110.495</td><td>99.044</td><td>104.332</td><td>3.60183932</td></tr><tr><td rowspan="6">Circle</td><td>NI-BBA</td><td>97.701</td><td>97.701</td><td>97.701</td><td>2.916E-14</td></tr><tr><td>N-BBA</td><td>94.310</td><td>87.932</td><td>90.455</td><td>1.7646704</td></tr><tr><td>AM-BBA</td><td>99.283</td><td>85.004</td><td>90.940</td><td>3.79249425</td></tr><tr><td>SF-BBA</td><td>100.366</td><td>100.366</td><td><b>100.366</b></td><td>2.916E-14</td></tr><tr><td>GVP-BBA</td><td>98.747</td><td>98.747</td><td>98.747</td><td>2.916E-14</td></tr><tr><td>GA</td><td>97.282</td><td>85.472</td><td>90.832</td><td>2.99547967</td></tr><tr><td rowspan="6">Directive</td><td>NI-BBA</td><td>41.473</td><td>41.473</td><td>41.473</td><td>1.458E-14</td></tr><tr><td>N-BBA</td><td>40.354</td><td>37.315</td><td>38.905</td><td>0.81358109</td></tr><tr><td>AM-BBA</td><td>42.560</td><td>40.963</td><td>41.594</td><td>0.44465264</td></tr><tr><td>SF-BBA</td><td>42.388</td><td>41.859</td><td><b>42.362</b></td><td>0.11845141</td></tr><tr><td>GVP-BBA</td><td>40.639</td><td>40.639</td><td>40.639</td><td>0</td></tr><tr><td>GA</td><td>41.543</td><td>36.904</td><td>38.924</td><td>1.10100813</td></tr></tbody></table>

<table><caption>**Table 4.** Results of the Bat Algorithm Variants For Instance 349</caption><thead><tr><th>Instance</th><th>Coverage</th><th>Algorithm</th><th>Best</th><th>Worst</th><th>Mean</th><th>Std</th></tr></thead><tbody><tr><td rowspan="14">349</td><td rowspan="6">Squared</td><td>NI-BBA</td><td>95.371</td><td>95.371</td><td>95.371</td><td>2.916E-14</td></tr><tr><td>N-BBA</td><td>61.664</td><td>58.335</td><td>59.981</td><td>1.03311284</td></tr><tr><td>AM-BBA</td><td>188.758</td><td>89.671</td><td><b>135.391</b></td><td>30.2152069</td></tr><tr><td>SF-BBA</td><td>102.880</td><td>98.142</td><td>102.643</td><td>1.05964286</td></tr><tr><td>GVP-BBA</td><td>63.551</td><td>62.123</td><td>63.479</td><td>0.319142</td></tr><tr><td>GA</td><td>63.643</td><td>57.858</td><td>61.196</td><td>1.60235842</td></tr><tr><td rowspan="6">Circle</td><td>NI-BBA</td><td>95.081</td><td>95.081</td><td><b>95.081</b></td><td>2.916E-14</td></tr><tr><td>N-BBA</td><td>60.350</td><td>56.624</td><td>58.753</td><td>0.98804881</td></tr><tr><td>AM-BBA</td><td>127.577</td><td>75.920</td><td>88.332</td><td>13.1198896</td></tr><tr><td>SF-BBA</td><td>90.144</td><td>88.803</td><td>88.911</td><td>0.3445047</td></tr><tr><td>GVP-BBA</td><td>61.270</td><td>60.903</td><td>61.251</td><td>0.08199193</td></tr><tr><td>GA</td><td>62.199</td><td>57.224</td><td>59.614</td><td>1.48976652</td></tr><tr><td rowspan="6">Directive</td><td>NI-BBA</td><td>41.464</td><td>41.464</td><td><b>41.464</b></td><td>7.29E-15</td></tr><tr><td>N-BBA</td><td>39.659</td><td>37.102</td><td>38.221</td><td>0.54525135</td></tr><tr><td>AM-BBA</td><td>42.283</td><td>38.420</td><td>39.408</td><td>0.91636124</td></tr><tr><td>SF-BBA</td><td>39.899</td><td>39.899</td><td>39.899</td><td>7.29E-15</td></tr><tr><td>GVP-BBA</td><td>39.723</td><td>39.723</td><td>39.723</td><td>7.29E-15</td></tr><tr><td>GA</td><td>39.450</td><td>37.199</td><td>38.304</td><td>0.66880293</td></tr></tbody></table>

the problem. No clear conclusion can be made about how the proposed variants behave when dealing with a specific type of coverage (squared, omnidirectional, directive), or a specific type of data (random, synthetic). One can note also that all the binary variants of the BA were able to outperform the results obtained by the canonical GA for all the instances and for all the sizes of the instances. But one can note also that the difference between the GA and the other variants decreases as the size of the instance decreases.

The conclusion that can be made concerning the impact of the mapping functions on the efficiency of an algorithm, is that the adequate use of a mapping function depends in some cases on the size of the problem engaged and in other cases on the type of the problem. Furthermore, one can note that in reality the bat algorithm do not need complex mapping functions since the basic *rounding function* has shown better results than the other complex mapping functions.
<table><caption>Table 5. Results of the Bat Algorithm Variants For Instance 549</caption><thead><tr><th>Instance</th><th>Coverage</th><th>Algorithm</th><th>Best</th><th>Worst</th><th>Mean</th><th>Std</th></tr></thead><tbody><tr><td rowspan="10">549</td><td rowspan="5">Squared</td><td>NI-BBA</td><td>139.973</td><td>139.973</td><td>139.973</td><td>2.916E-14</td></tr><tr><td>N-BBA</td><td>40.668</td><td>38.939</td><td>40.063</td><td>0.46911297</td></tr><tr><td>AM-BBA</td><td>134.322</td><td>96.348</td><td>112.442</td><td>8.45490438</td></tr><tr><td>SF-BBA</td><td>147.445</td><td>147.445</td><td><strong>147.445</strong></td><td>2.916E-14</td></tr><tr><td>GVP-BBA</td><td>40.529</td><td>40.365</td><td>40.521</td><td>0.03669093</td></tr><tr><td>GA</td><td>42.777</td><td>38.927</td><td>41.070</td><td>1.19535659</td></tr><tr><td rowspan="5">Circle</td><td>NI-BBA</td><td>127.289</td><td>126.025</td><td><strong>126.910</strong></td><td>0.59402311</td></tr><tr><td>N-BBA</td><td>41.311</td><td>38.693</td><td>39.740</td><td>0.77547919</td></tr><tr><td>AM-BBA</td><td>116.780</td><td>89.794</td><td>102.404</td><td>6.32663866</td></tr><tr><td>SF-BBA</td><td>117.067</td><td>116.067</td><td>117.017</td><td>0.223514</td></tr><tr><td>GVP-BBA</td><td>41.411</td><td>41.411</td><td>41.411</td><td>7.29E-15</td></tr><tr><td rowspan="5">Directive</td><td>GA</td><td>42.640</td><td>39.027</td><td>40.620</td><td>1.06845162</td></tr><tr><td>NI-BBA</td><td>49.046</td><td>49.046</td><td><strong>49.046</strong></td><td>1.458E-14</td></tr><tr><td>N-BBA</td><td>36.371</td><td>34.536</td><td>35.468</td><td>0.4751343</td></tr><tr><td>AM-BBA</td><td>52.156</td><td>45.135</td><td>48.721</td><td>1.83706437</td></tr><tr><td>SF-BBA</td><td>51.874</td><td>51.808</td><td>51.870</td><td>0.01464278</td></tr><tr><td rowspan="2">749</td><td rowspan="5">Circle</td><td>GVP-BBA</td><td>35.853</td><td>35.814</td><td>35.852</td><td>0.00873771</td></tr><tr><td>GA</td><td>37.913</td><td>34.444</td><td>35.851</td><td>0.89470107</td></tr><tr><td>NI-BBA</td><td>101.870</td><td>101.870</td><td>101.870</td><td>1.46E-14</td></tr><tr><td>N-BBA</td><td>29.917</td><td>28.275</td><td>29.018</td><td>0.45477513</td></tr><tr><td>AM-BBA</td><td>110.941</td><td>87.658</td><td>97.607</td><td>6.66552368</td></tr><tr><td rowspan="5">Directive</td><td>NI-BBA</td><td>114.077</td><td>114.077</td><td><strong>114.077</strong></td><td>0</td></tr><tr><td>SF-BBA</td><td>29.367</td><td>29.142</td><td>29.356</td><td>0.05020659</td></tr><tr><td>GVP-BBA</td><td>30.579</td><td>27.929</td><td>29.198</td><td>0.82131334</td></tr><tr><td>GA</td><td>50.405</td><td>50.024</td><td>50.386</td><td>0.08519864</td></tr><tr><td>N-BBA</td><td>28.674</td><td>27.113</td><td>27.730</td><td>0.4651209</td></tr><tr><td rowspan="5">Directive</td><td>AM-BBA</td><td>50.920</td><td>45.767</td><td>48.605</td><td>1.36744246</td></tr><tr><td>SF-BBA</td><td>51.189</td><td>49.877</td><td><strong>51.123</strong></td><td>0.29334724</td></tr><tr><td>GVP-BBA</td><td>27.578</td><td>27.415</td><td>27.503</td><td>0.02651541</td></tr><tr><td>GA</td><td>29.608</td><td>26.802</td><td>27.785</td><td>0.66481778</td></tr></tbody></table>

<table><caption>Table 6. Results of the Bat Algorithm Variants For Instance 749</caption><thead><tr><th>Instance</th><th>Coverage</th><th>Algorithm</th><th>Best</th><th>Worst</th><th>Mean</th><th>Std</th></tr></thead><tbody><tr><td rowspan="10">749</td><td rowspan="5">Squared</td><td>NI-BBA</td><td>135.888</td><td>135.888</td><td><strong>135.888</strong></td><td>2.92E-14</td></tr><tr><td>N-BBA</td><td>29.847</td><td>28.486</td><td>29.175</td><td>0.40036354</td></tr><tr><td>AM-BBA</td><td>126.827</td><td>90.586</td><td>109.403</td><td>11.4041269</td></tr><tr><td>SF-BBA</td><td>130.915</td><td>130.915</td><td>130.915</td><td>0</td></tr><tr><td>GVP-BBA</td><td>29.586</td><td>29.586</td><td>29.586</td><td>3.65E-15</td></tr><tr><td>GA</td><td>30.788</td><td>28.477</td><td>29.437</td><td>0.52843974</td></tr><tr><td>NI-BBA</td><td>101.870</td><td>101.870</td><td>101.870</td><td>1.46E-14</td></tr><tr><td>N-BBA</td><td>29.917</td><td>28.275</td><td>29.018</td><td>0.45477513</td></tr><tr><td>AM-BBA</td><td>110.941</td><td>87.658</td><td>97.607</td><td>6.66552368</td></tr><tr><td rowspan="5">Circle</td><td>NI-BBA</td><td>114.077</td><td>114.077</td><td><strong>114.077</strong></td><td>0</td></tr><tr><td>SF-BBA</td><td>29.367</td><td>29.142</td><td>29.356</td><td>0.05020659</td></tr><tr><td>GVP-BBA</td><td>30.579</td><td>27.929</td><td>29.198</td><td>0.82131334</td></tr><tr><td>GA</td><td>50.405</td><td>50.024</td><td>50.386</td><td>0.08519864</td></tr><tr><td>N-BBA</td><td>28.674</td><td>27.113</td><td>27.730</td><td>0.4651209</td></tr><tr><td rowspan="5">Directive</td><td>AM-BBA</td><td>50.920</td><td>45.767</td><td>48.605</td><td>1.36744246</td></tr><tr><td>SF-BBA</td><td>51.189</td><td>49.877</td><td><strong>51.123</strong></td><td>0.29334724</td></tr><tr><td>GVP-BBA</td><td>27.578</td><td>27.415</td><td>27.503</td><td>0.02651541</td></tr><tr><td>GA</td><td>29.608</td><td>26.802</td><td>27.785</td><td>0.66481778</td></tr></tbody></table>

## 5 Conclusion

In this paper we conducted a comparative study on the impact of mapping functions on the efficiency of the continuous-variable-based metaheuristic. This was done by proposing five new variants of a recent metaheuristic which is the Bat Algorithm (BA). The proposed binary variants, were tested on an NP-hard optimisation problem in cellular phone networks which is the Antenna Positioning Problem (APP). The results showed that the impact of such mapping functions on the efficiency of an algorithm depends on two factors: the size of the problem, or the complexity of the problem. The best mapping functions found for the bat algorithm are the nearest integer and sigmoid function techniques.

This work illustrates a simple comparative study, and no deep and general conclusion can be made about the efficiency of the mapping functions, the con-
trolling factor of these last ones or the usefulness of these mapping functions when solving binary problems. So, we seek to conduct a more deep statistical comparative study using several continuous-variable-based metaheuristics and compare them with more powerful binary-variable-based metaheuristics.

## References

1. Alba, E., Molina, G., Chicano, F.: Optimal placement of antennae using metaheuristics. In: Proceedings of the 6th International Conference on Numerical Methods and Applications, (NMA). pp. 214–222 (2006)

2. Burnwal, S., Deb, S.: Scheduling optimization of flexible manufacturing system using cuckoo search-based approach. The International Journal of Advanced Manufacturing Technology 64(5-8), 951–959 (2013)

3. Calegari, P., Guidec, F., Kuonen, P.: A parallel genetic approach to transceiver placement optimisation. In: Proceedings of the SIPAR Workshop : Parallel and Distributed Systems. pp. 21–24 (1996)

4. Calegari, P., Guidec, F., Kuonen, P., Kobler, D.: Parallel island-based genetic algorithm for radio network design. J. Parallel Distrib. Comput. 47(1), 86–90 (1997)

5. Congying, L., Huanping, Z., Xinfeng, Y.: Particle swarm optimization algorithm for quadratic assignment problem. In: Proceedings of the International Conference on Computer Science and Network Technology, (ICCSNT). vol. 3, pp. 1728–1731 (2011)

6. Costa, M., Rocha, A.A.M., Francisco, B.R., Fernandes, M.E.: Heuristic-based firefly algorithm for bound constrained nonlinear binary optimization. Advances in Operations Research 1(215182), 12 (2014)

7. Liu, Q., Lu, W., Xu, W.: Spectrum allocation optimization for cognitive radio networks using binary firefly algorithm. In: Proceedings of the International Conference on Innovative Design and Manufacturing, (ICIDM). pp. 257 – 262 (2014)

8. Palit, S., Sinha, S., Molla, M., Khanra, A.: A cryptanalytic attack on the knapsack cryptosystem using binary firefly algorithm. In: Proceedings of the 2nd International Conference on Computer and Communication Technology, (ICCCT). pp. 428 – 432 (2011)

9. Pampara, G., Engelbrecht, A.: Binary artificial bee colony optimization. In: Proceedings of the IEEE Symposium on Swarm Intelligence, (SIS). pp. 1 – 8 (11-15 April 2011)

10. Pampara, G., Engelbrecht, A., Franken, N.: Binary differential evolution. In: Proceedings of the IEEE Congress on Evolutionary Computation, (CEC'06). pp. 1873–1879 (2006)

11. Pampara, G., Franken, N., Engelbrecht, A.: Combining particle swarm optimization with angle modulation to solve binary problems. In: Proceedings of the Congress on Evolutionary Computation, (CEC'05). pp. 89–96 (2005)

12. Segura, C., Segredo, E., González, Y., León, C.: Multiobjectivisation of the antenna positioning problem. In: International Symposium on Distributed Computing and Artificial Intelligence, (DCAI). pp. 319–327 (2011)

13. Swagatam, D., Rohan, M., Rupam, K., Thanos, V.: Multi-user detection in multi-carrier CDMA wireless broadband system using a binary adaptive differential evolution algorithm. In: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, (GECCO '13). pp. 1245–1252 (2013)

14. Yang, X.S.: A new metaheuristic bat-inspired algorithm. In: Nature Inspired Cooperative Strategies for Optimization, (NICSO), vol. 284, pp. 65–74. springer (2010)