BSAS: Beetle Swarm Antennae Search Algorithm for Optimization Problems
Jiangyu Wang Huanxin Chen

























Shell et al.: Bare Demo of IEEEtran.cls
	for Journals BSAS:Beetle Swarm Antennae Search Algorithm for Optimization
Problems
    Jiangyu Wang, Huanxin Chen*
    Received July 26, 2018; accepted May 11, 2021
=====================================================================




Beetle antennae search (BAS) is an efficient meta-heuristic algorithm.
However, the convergent results of BAS rely heavily on the random beetle
direction in every iterations. More specifically, different random seeds
may cause different optimized results. Besides, the step-size update
algorithm of BAS cannot guarantee objective become smaller in iterative
process. In order to solve these problems, this paper proposes Beetle
Swarm Antennae Search Algorithm (BSAS) which combines swarm
intelligence algorithm with feedback-based step-size update
strategy. BSAS employs k beetles to find more optimal position
in each moving rather than one beetle. The step-size updates only when
k beetles return without better choices. Experiments are carried
out on building system identification. The results reveal the efficacy
of the BSAS algorithm to avoid influence of random direction of Beetle.
In addition, the estimation errors decrease as the beetles number goes
up.






§ INTRODUCTION

Meta-heuristics have enormous potential for solving complex optimization problems where analytical solutions are not available.
Jiang and Li<cit.> develop a algorithm called Beetle antennae search(BAS), which is taking inspiration from detecting and searching behavior of longhorn beetles. BAS shows good performance in the benchmark experiments which aims at searching global optimum value of two typical test functions, namely Michalwwicz and Goldstein-Price.

However, the results deviate greatly while we try to identify a high-dimensional system, for example, a lumped resistance-capacitance model with nine unknown parameters. There are two reasons why BAS performs not well when dealing with this optimization problem.

On the one hand, the convergence results of  BAS in <cit.> is highly depentdent on the beetle direction(random walking mechanism in <cit.>), which is randomly generated in each iteration, thus causing unstable results when faced with complex and high diamensional problems. On the other hand, the step size of each iteration will be attenuated. In other words, the step size is updated  regardless of the objective function value is better or not. In general, due to the random direction and the inefficient step size update strategy, the BAS may converge early and fall into the local optimal solution for high-dimensional problems. What's more, the results of multiple tests on the same objective function may vary greatly.

Aim at solving aforementioned problems, this paper proposes a modified BAS algorithm, namely Beetle swarm antennae search(BSAS), which takes swarm intelligence and feedback-based step update strategy into consideration.  In this paper, BSAS is applied to estimate parameters (including the initial temperature value) for a resistance-capacitance(RC) model, which is widely used in describing the thermal dynamics of the buildings . The main contributions of this paper are illuminated as below:

	
  * Feedback-based step update strategy is applied to make sense of every move of beetle. In other word,  the step-size updates only if the next hypothetical position of beetle cannot make the objective function value better.
	
  * Beetles swarm is employed to search possible positions which optimizes the objective function in each iteration, thus overcoming the blindness of random walking of one beetle in a certain degree.


The rest of the paper is organized as follows. In Section <ref>, BSAS is proposed. In Section <ref>, BSAS is applied to system identification of a RC model and the numerical results are presented and compared to the results of BAS. Section <ref> concludes the main works of this paper.






§ PROPOSED APPROACH

In this section, an improved BAS is proposed by  taking both of swarm intelligence algorithm with feedback-based step-size update
strategy into consideration. Besides,  two diagrams describing optimization process of BAS and BSAS respectively are given to illuminate the difference of two algorithms and make them easily understood.



 §.§ Original BAS

The original BAS includes two rules, namely seraching behavior and detecting behavior. In each timestep, beetle moves in a random direction. Therefore, a random unit vector b∈ℝ^N is used to describe the direction. The 
coordinate of  both right-hand and left-hand sides of the beetle's antennae are presented as (<ref>),

    x_r   =   x^t+d^tb, 
    x_l   =   x^t-d^tb,

where the subscript r,l represents the right-hand side and left-hand side respectively, the superscript t represent specific moment. d is behalf of  distance from the antenna to the centroid of the beetle. More specfically, d^t represents corresponding beetle's searching area at a certain moment, and the area will attenuate over time as described in (<ref>). d_0 guarantees that d^t will not reduce to zero. By the way, magnitude of d_0 depends on the scale of specific problem. The beetle's detecting behavior is described as (<ref>),

    x^t=x^t-1+δ^tbsign(f(x_r)-f(x_l)),

where δ^t represents the step size, which will reduce over time as demonstrated in (<ref>).
 The update rules of d and δ are presented in (<ref>) and (<ref>). 

    d^t   =   η_dd^t-1+d_0,
    δ^t   =   η_δδ^t-1 + δ_0.

where η_d and η_δ are attenuation coefficients of antennae length d and step size δ respectively.
 Jiang and Li <cit.> indicate that presetting of parameters such as d and δ influences performance of BAS seriously. In Section<ref>, we discuss about parameters initialization in brief for the concerned problem,namely RC model estimation, in this paper. 

The diagrammatic drawing of BAS algorithm is shown in Fig.<ref>. Beetle moves according to a random direction in every iteration. Meanwhile, the position updates as (<ref>). The grey dotted line with arrow  points out the direction. Evidently, the length of grey line, which represents the step-size, reduces over time as (<ref>). Note that Fig.<ref> doesn't show the process of δ updating to make the beetle big enough to observe.



We can see that only one position in the random direction is explored in one iteration. In addition,  beetle position and the step size updates regardless of the objective function value obtained in last iteration is smaller or larger. A possible scenario is shown in Fig.<ref>, in which the step size reduces too fast and the directions seem not good in some iterations. As a result of this scene, the beetle fall into local optimum position shown in wathet blue and cannot jump out of the local area. 



 §.§ Proposed BSAS algorithms


In general, there are two drawbacks for BAS algorithm. First,  beetle moves in onerandom direction for each iteration. It cannot guarantee that the move of beetle will  make the objective function value better. Correspondingly,  we can improve the searching behavior of BAS algotithm by employing k beetles to move in k directions, thus enhancing the possibility for finding better position of beetle. Second, every movement of the beetle will cause an update of the position and step size. In fact, if the objective function is better, the position of beetle should be updated while the step size not. Vice versa. Therefore, we can design a feedback-based position and step-size update strategy as shown in algorithm <ref>.

In addition, a probability constant p_δ is introduced to measure the impact of random directions. In other word, we think there is a small probability p_δ that k beetles will miss the better position (parameters set) for objective function at the current step size. Therefore, we generate a random number which belongs to [0,1] and compare it to p_δ. As a result, in most of the time, if k beetles cannot find smaller objective function value, BSAS algorithm thinks there are no better positions at current step size and it needs to be updated. In a few cases, the algorithm thinks there are still some positions to satisify beetle's need to minimize the objective, but these beetles cannot find it because of limited beetles number k. Therefore, step-size δ and sensing lenght d will remain the same if the random number is less than p_δ. However, the beetle position updates only if bettles swarm find better positions to optimize objective function as shown in Fig.<ref>.










§ VALIDATION

In order to verify the efficacy of the proposed BSAS algorithm for high-dimensional and complex system, RC model is applied to validate the improved algorithm. In this section, we use both of BAS and BSAS algorithm to estimate the parameters of RC model. Then the numerical results are compared.


 §.§ A. Test model

RC model is a typical grey-box model and it is widely used in wide range of data-driven modeling applications, for example, describing the thermal dynamics of buildings<cit.>. As shown in Fig.<ref>, an building with only one zone in cooling season can be abstracted to three parts consisting of thermal resistances and capacitances. The envelop part is composed of two resistances and one capacitance. More specifically, we only take the wall's thermal dynamic into consideration. As for windows, it can be treated as a resistance. The indoor part represents the property of indoor air, of which the resistance can be ignored. Furthermore, cooling power Q_c, windows transmitted beam solar radiation rate Q_solar and all heat gains throughout the zone Q_in also have great influence on the indoor temperature. The last part is internal mass, which is on behalf of construction/material parameters within the space. It can be viewed as a resistance and a capacitance.



As shown in (<ref>), we can abstract the ordinary differential equations (ODEs) for the thermal characteristics of the RC model based on the  Kirchhoff's law. 

    C_1 dT_e/ dt   =   T_out-T_e/R_1
    
    C_in dT_in/ dt   =   T_e-T_in/R_2-T_in-Tm/R_3
           + Q_in + Q_c + Q_solar
    
    C_m dT_m/ dt   =   T_in-T_m/R_3


Given a parameters set , we can solve ODEs (<ref>rc_equation) by using the numerical method, for example, fourth-order Runge-Kutta method. Then, we design an objective function in a mean absolute error (MAE) form as shown in (<ref>),

    f(x_pars) =| T_in,sim(x_pars) - T_in,obs|/N_obs

where x_pars is parameters set [T_e0, T_in0, T_m0, C_1, C_in,C_m,
R_1, R_2, R_3]  to be estimated, and T_e0, T_in0, T_m0 are the initial values of T_e, T_in, T_m. T_in,sim(x_pars) represents the numerical results of (<ref>) and T_in,obs is the real observation of indoor temperature. N_obs is the number of T_in,obs.



 §.§ B. Results

50 experiments are carried out on both of BAS and BSAS algorithm. In addition, we set a range of k from 1 to 5. The results of experiments are shown in Fig.<ref>.


The x axis represents convergent results of ibjective function (<ref>) for each experiments. The y axis represents the counts of numerical results within the same intervals. Evidently, BAS performs worst because of the largest mean MAE index. With the k increases, the more compact distribution are obtained and the mean MAE becomes smaller.  BSAS shows better performance than BAS regardless of the k value. It is interesting to note that BSAS with k = 1 also performs better than BAS. This phenomenon reveals the efficacy of the feedback-based step-size update strategy.




§ CONCLUSION


This work presents an extended BAS algorithm to raise BAS's ability and efficency for dealing with high-dimensional problems. Swarm intelligence method and feedback-based step-size update strategy are introduced to modify the original BAS algorithm. System identification for RC model is employed to test the performances of  BSAS in terms of local minimum avoidance. The results reveal the efficacy of proposed algorithm. 



§ ACKNOWLEDGMENT


Gratitude is extended to Dr. Li for his suggestions in algorithm improvement.



§ APPENDIX


A implementation of BAS and BSAS algorithm in form of R package could be found at <https://github.com/jywang2016/rBAS>.



99
	ref.BAS
	X. Y. Jiang, and S. Li, “BAS: beetle antennae search algorithm for optimization
	problems,” arXiv:1710.10724v1.
	ref.BAS-WPT
	X. Y. Jiang, and S. Li, “Beetle Antennae Search without Parameter Tuning
	(BAS-WPT) for Multi-objective Optimization,” arXiv:1711.02395v1.
	ref.ggplot2
	H. Wickham. ggplot2: Elegant Graphics for Data Analysis. Springer-Verlag New York,
	2009.
	ref.RCpaper
	Bacher, Peder, and H. Madsen. "Identifying suitable models for the heat dynamics of buildings." Energy & Buildings 43.7(2011):1511-1522.


