{'fraction_non_alphanumeric': 0.021299915969456726, 'fraction_numerical': 0.006649373424427314, 'mean_word_length': 4.963939426952827, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Beamformer Design Based on Fibonacci Branch Search

An approach towards beamforming for a uniform linear array (ULA) based on a novel optimization algorithm, designated as Fibonacci branch search (FBS) is presented in this paper. The proposed FBS search strategy was inspired from Fibonacci sequence principle and uses a fundamental branch structure and interactive searching rules to obtain the global optimal solution in the search space. The structure of FBS is established by two types of multidimensional points on the basis of shortening fraction formed by the Fibonacci sequence, and in this mode, interactive global searching and local optimization rules are implemented alternately to reach global optima, avoiding stagnating in local optimum. At the same time, the rigorous mathematical proof for the accessibility and convergence of FBS towards the global optimum is presented to further verify the validity of our theory and support our claim. Taking advantage of the global search ability and high convergence rate of this technique, a robust adaptive beamformer technique is also constructed here by FBS as a real time implementation to improve the beamforming performance by preventing the loss of optimal trajectory. The performance of the FBS is compared with five typical heuristic optimization algorithms, and the reported simulation results demonstrate the superiority of the proposed FBS algorithm in locating the optimal solution with higher precision and reveal the further improvement in adaptive beamforming performance.


INTRODUCTION
Since the conception of the adaptive arrays came into usage in aerospace and military applications via the employment of electronically steered beamformer, the ultilized technique adaptive beamforming (ABF) has drawn significant attention in various fields [1][2][3][4]. ABF possesses the potential ability to optimize the radiation pattern in real time, which obtains a larger output signal to interference-plusnoise ratio (SINR) by steering the main lobe of radiation toward a desired signal while placing respective nulls toward several interference signals [5].
Classical adaptive beamforming methods used to extract the excitation weights are based on two main criterions: maximum signal-to-noise ratio (MSINR) and minimum mean square error (MMSE) [6]. Minimum variance distortionless response (MVDR) is one of the typical adaptive beamforming approaches on the basis of MSINR criterion. The design of this beamformer involves minimizing the output power subject to the unit gain constraint to desired signal [7][8][9]. Although the MVDR beamformer is capable of suppressing the interference and improving system reliability, the weights computed by MVDR are not able to form deep nulls towards the interference source in various interference scenarios on account of the characteristics of this technique. Closed-form (CF) design or the classic algorithm exists to easily find the optimal solution for a actually convex problem, such as the algorithm known as the sample matrix inversion (SMI) technique; however, the weight calculation of this solving process takes into account the interference correlation matrix which makes this beamforming process very difficult, time consuming, and sometimes, in ABF application, is unmanageable. Besides, the closed-form design for the convex ABF model problem always needs to compute the matrix inverse process which introduces high computational complexity especially for large number of array elements and not suitable for certain real-time beamforming situations [10][11][12]. In addition, the classic closedform design algorithms have hardware component device limitations. It is not possible to change the hardware of the filter for signal processing or to change the design of the antenna based on the increased number of components, but this is necessary. Another criterion for computing the array weights is to minimize the MMSE. One of the most widely used MMSE-based adaptive algorithm is the least mean square (LMS) approach, and this method needs a training sequence of signal of interest (SOI) to adaptively adjust the complex weights and minimize the difference between the array output and the desired signal for forming the optimum array pattern. Consequently, the inherent shortcomings of above mentioned derivative-based and gradient-based ABF methods have compelled many researchers to explore meta-heuristics (MH) methods for overcoming these difficulties.
The main advantage of the evolutionary heuristics algorithms over the classical derived approaches in antenna systems is that they have no requirements for extra iterative derivations or computationally extensive routines in objective functions of ABF model, and some of the evolutionary algorithms have been dedicated to beamformer implementations for their ability to search the global optimum. Approaches such as genetic algorithms (GA), particle swarm optimization (PSO), and other modified techniques are a set of optimization algorithms that have been suggested in the past decades to solve a variety of ABF problems [13,14]. Many researches have shown that the excitation weights extracted by these optimization techniques defined by specific criteria can be used to place a maximum beam and null in an array pattern in specified locations, and they also require relatively lower mathematical complexity than derivative-based or iterative-based ABF methods. However, there still exist weaknesses and limitations in the application of ABF with these techniques. Most iterative evolutionary methods are highly dependent on starting points in the case of large number of solution variables [15]. Yet the weights of ABF are regularly associated with a large number of array elements, and the excitation of array elements is complex, i.e., having both amplitude and phase, hence the size of the ABF solution space cannot be very small, and in case, these evolutionary algorithms are not really applicable to beamforming. Besides, the classic optimization methods are prone to get trapped in local minima and not reach the global optimum when solving complex multimodal optimization problems of array weight extraction, resulting in a suboptimum beamforming performance [16,17]. In addition, most of MH algorithms are population-based optimization techniques which require long execution times to converge, specifically when solving large scale complex ABF engineering problems, and the complexity required for implementing the algorithms would also result in huge cost and consumption of hardware resources.
In consideration of the above-mentioned studies, we propose a novel interactive-based random iterative search strategy, called FBS in this paper to deal with complicated optimization problems of ABF. The motivation for considering the FBS with application to such a robust adaptive beamformer is that we expect to be able to form deep nulls towards the interference source in various interference scenarios without the requirement of apriori information such as the training sequence of signal of interest and avoid complex mathematical processing such as the inverse calculation of the interference correlation matrix compared to the derivative-based approaches, and with respect to a traditional meta-heuristic algorithms applied to beamformer, it is anticipated that the FBS based on beamformer could obtain the near optimal nulling level performance featuring a high global optimization resolution capability and prevents the loss of optimal search trajectory low computational load possesssing to improve the convergence performance with the design flexibility of the algorithm in the framework of ABF.
The concept of the proposed FBS is defined from two aspects: The first one is the generation principle of the Fibonacci branch architecture. The basis for building a branch structure in FBS is to establish search points and the shortening fraction based on the Fibonacci sequence to generate a set of optimization elements composed of two types of search points. The optimization endpoints search for the optimal solution according to the branch's growth path pattern. The second view of the FBS concept is that the construction of interactive iteration applies rules to the calculation of optimization elements. The iterative rules are composed of global searching and local optimization, which are the two phases necessary to update the optimization elements. Global tentative points and local searching points are formulated in the phase of two interaction processes, and the points with the best fitness converge towards the global optimum in searching space. At the same time, computer memory can be fully used to record the optimizing process during the interaction optimization course. Global randomness is one of the important characteristics of FBS, and this mechanism is implemented on those points that are not easy to fall into the local optimum and not able to find a better solution. The novelty of this paper lies in the fact that we design the Fibonacci branch optimization structure and propose the novel global searching and local optimizing interaction iterative technique. In addition, the Fibonacci branch search algorithm proposed here has been applied to antenna array beamforming in several cases and in comparison with other evolutionary optimization-based techniques on several test functions and the robust ABF.
The reminder of this paper is organized as follows. Adaptive beamforming model incorporation with metaheuristic algorithm is described in Section 2. Section 3 presents the proposed FBS optimization algorithm and the accessibility convergence proof of FBS. The validation of the proposed FBS via benchmark functions and the simulation results are reported in Section 4. Section 5 gives the conclusion.

ADAPTIVE BEAMFORMING MODEL INCORPORATION WITH METAHEURISTIC ALGORITHM
Consider a uniform linear antenna array of M omnidirectional array elements employed in adaptive beamforming receiver, one desired signal and Q uncorrelated interferences which impinge on the array at the kth snapshot can be expressed by [18] x where s(k) and i i (k) are the desired global navigation satellite systems (GNSS) signal and the ith interference, and n(k) denotes the complex vector of sensor noise. a(θ d ) and a(θ i ) represent M × 1 steering vectors of s(k) and i i (k) as given by where θ d and θ i denote the direction of the desired signal and the ith interference; d c = λ 2 is the inter-element spacing; λ is the wavelength of GNSS carrier; T is the transpose operation.
The array beamformer output can be written as where w is the complex beamforming weight vector of the antenna array, and H stands for the Hermitian transpose.
The schematic structure of a linear adaptive antenna array processor on the front end of the receiver is shown in Figure 1. Solid incident arrow represents the GNSS signal, and dotted arrow represents the interference.
In the above model, the adaptive beamformer studied in this paper aims to calculate a complex weight vector that satisfies the requirement of achieving a deep nulling level for interference to maximize the output SINR, and is usually a low nulling level for multiple interference sources. The non-global optimal weight vector is one of the main disadvantages of MVDR beamforming technology. Therefore, in this section, the proposed FBS algorithm incorporated into the beamforming model will extract the optimal array excitation weights to achieve the improved performance of the technique.
Altering the radiation pattern of an antenna array by adjusting the weights is an inherently multiobjective problem, since multiple sets of agent weight vectors w with amplitude and phase to make deep nulls toward the interference place and steer the radiation beam toward the desired user to achieve the maximum SINR must be satisfied. The optimization method to the designed ABF aims at finding the near-global minimum of a fit mathematical function called fitness function; therefore, the best weight vector is determined according to the fitness value obtained from the object function defined based on the SINR. Therefore, a typical fitness function constructed from the perspective of SINR for calculating complex excitation weights using FBS can be appropriately expressed in the following form: where are, respectively, the power of the desired signal and the power corresponding to the ith interference, and P N is the noise power. x d and x i denote the desired signal and interference component of the received signal in Equation (1), and E is the expectation operator. Then, the design objective function can be properly stated in the following form where R i and R d are the covariance matrix of the ith interference and the desired one. The noise variance is calculated from the value of signal-to-noise ratio (SNR) in dB as follows: By maximizing Eq. (7), the optimal excitation weight corresponding to the minimum level of the interference sources but with the desired user gain of the beamformer can be achieved by the proposed FBS algorithm, and the optimum performance of the weight corresponding to the maximum SINR can be evaluated based on the best fitness account. Next section of the paper provides a brief description of the implementation steps for extracting the weight using Fibonacci branch search method.

PROPOSED FBS ALGORITHM
Since the inception of Fibonacci optimization strategy, the effectiveness of the algorithm for solving a set of nonlinear benchmark functions has been proven in one dimension space; however, this algorithm is seldom applied to the search optimization problem of multidimensional space for the properties and structure of itself, and very few of its variants have been implemented for the beamforming applications in open reported literatures. In this section, the conventional Fibonacci sequence method will be briefly introduced, and the inspired FBS will be explained in principle and provide an in-depth insight into this technique.

The Standard Principle of Fibonacci Sequence Method
The famous Fibonacci sequence was proposed initially by Etminaniesfahani et al. [19], and the recurrence formula of the general sequence term is given by [20] where F j represents the jth general term of Fibonacci sequence. Fibonacci sequence optimization method makes the tentative optimization points in the defined interval converge to the optimal solution by compressing the search interval proportionally based on Fibonacci sequence term, and it has been perceived as one of the most effective strategies to solve one-dimension unimodal problem [21]. Let us investigate below how the optimization method using the Fibonacci sequence works for a unimodal continuous function in an interval for a minimization problem.
Supposing a unimodal f (x) function which is defined on the intervals [A, B]. Initially, the technique starts a choice for two feasible points x 1 and x 1 , x 1 < x 1 in the given range for the first iteration. Then, it is necessary to reduce the initial box of range to a sufficiently small box region including the minimum solution of f (x) (through an iteration process) for the interval that can be narrowed down provided that the function values are known at two different points in the range. The implementation of the classical Fibonacci serial optimization algorithm can be found in [22], and we will not go into further details here. Let x p and x p denote the different random selected new points over the range of [A p , B p ] to be chosen for shortening the length of the interval at the pth iteration involving optimal point, x p < x p . Hence for each p = 1, 2, ..., N , N represents the maximum number of iterations, and Fibonacci algorithm can be executed as following proceedings.

Fibonacci Branch Structure and FBS Optimization Algorithm
The standard Fibonacci strategy cannot efficiently solve multi-variate problems and reliably perform the optimum fitness evaluation of multimodal functions [23]. While this is in contradiction to the classic heuristic optimization algorithms, the FBS algorithm, proposed in this paper, is used to overcome these defects while avoiding a loss of the optimal search trajectories by using the searching elements with a dendritic branch structure and interactive searching optimization rules.
The basic structure of FBS expanded to the multi-dimensional space D can be illustrated in Figure 2, where X A , X B , and X C are the vectors in D dimensional Euclidean space. X A and X B represent the endpoints of the search element satisfying the optimization rule, and X C denotes the segmentation points which can be determined from the searching rule. A certain proportion of the vectors can be constructed as follows where F p is the pth Fibonacci number.
Considering that the multimodal function with multiple variables f (X) is to be minimized in search space, the fitness function value calculated by the endpoints in the structure should be evaluated as f (X A ) < f (X B ) (11) Then, the coordinate computing formula of segmentation point X C can be written as The FBS optimization algorithm introduced in this section is based on a framework that is built around the concept of endpoints and segmentation points in basic structure. Although a similar relevant algorithm theory has been studied in [24], it did not elaborate on the steps and principles of the algorithm. In this section, the principle part of FBS is well explained, and the details of the implementation content are fully described including the implantation procedure being regularized, and it is successfully applied to the adaptive beamforming field.
Combining with the basic structure, the process of searching for global optimum solution which can also be regarded as establishing a search element in FBS is divided into two stages, the local optimization process and the global searching process, which are the corresponding two interactive rules. Let G denote the point sets of the object function searching for in current processing phase, and set |G| num = F p , p = 1, 2, · · · , N. | · | num represents the total number of points in a set, and N is the depth of the Fibonacci branch. The fitness value of the endpoints X A and X B are initialized using the two corresponding interactive optimization rules, then the segmentation points X C can be obtained from Equation (12). By comparison of the fitness values of all the points in the structure, we can get the results that the best fitness value accordingly corresponds to the closest optimal solution. To the next optimization phase, the optimal point with the best fitness value is provided in the forefront position of the set, and the points corresponding to the suboptimal fitness are arranged below the optimal point in accordance with the order from the best to worst. Throughout the operations above, the points set G can be updated in every optimizing phase to attain the aim of growing the Fibonacci branch and global optimization in search space simultaneously.
The two interactive searching rules of FBS in the optimization stage are summarized as follows: Rule One: Let us consider the endpoints X A and X B in the structure, which are defined by where G p is the search points space set in the pth iteration; X q are the points in set G p , and this search point was randomly selected in the whole search space with random search mechanism. q is the sequence number lying on the interval between 1 and the pth Fibonacci number, and it represents the Fibonacci layer used for searching the global optima. X A take all the points from G p of the pth iteration. The other endpoints X B take random points in search space, and the number of X B is equal to F P . D is the dimension of the points, and X f ub are the upper and lower bounds of the search points. Given that ∀X ∈ {X B }, component x of vector X is a random variable that satisfies a uniform distribution over the interval [X lb , X ub ] U , where the usual character U stands for the uniform distribution of the variable, and the probability distribution of the component can be written as Using the given endpoints X A and X B , we can determine the segmentation points X S1 in the first global search stage by Equation (12).

Rule Two:
Suppose that X best is the optimal solution corresponding to the best fitness value of the search space in the current iteration containing the endpoints and the segmentation points generated from rule one, as given by where BEST (·) means the best solution of the set at the pth iteration. Then, we set the endpoints X A = X best and have that: Using the calculation formula of the segmentation point, the segmentation point X S2 of the second local optimization stage can be determined according to the endpoints defined in Eqs. (17) and (18), and the segment search point is computed by Equation (12).
From the two interactive searching rules mentioned above, new points including endpoints X A , X B and segmentation points X S1 , X S2 are generated in the two optimization stages, and the total number of points is 3F P . Evaluating the cost functions in new points determines their fitness, and all these points are sorted from the best to the worst based on their fitness values. The population size of the search points is chosen as the Fibonacci series, thus, the top best F P +1 sets of these points are saved, and the remaining 3F P − F P +1 points need to be dropped. After this procedure, the sets of the search space in the current pth iteration are renewed from the saved points, e.g., the saved points form a new set G P +1 in search space for the next iteration.
The two stages of building Fibonacci branch for the global optimization in space is shown in Figure 3.
As can be seen from Figure 3, the depth of the Fibonacci branch layer illustrated in the figure is initialized as expected, and the number of points in every branch layer remains in the sequence of Fibonacci number. The white dashed circle in the figure represents the search points set of the previous iteration, and the black solid circles denote the endpoints X A in the current iteration. The global random endpoints X B are represented in grey solid circles. Figure 3(a) shows the first global searching stage of the global optimization process, and the segmentation points X S1 which are represented by solid white line circles are constructed on the basis of global random points and X A . As shown in Figure 3(b), the second local optimization stage combines the remaining end points of the best adaptation points X A and X B in the search space of the current iteration, and a new segmentation point X S2 can be obtained through iteration rules. The fitness values of X A , X B , X S1 , and X S2 are evaluated, and the best found F P +1 solutions with optimum object function evaluations need to be saved. Figure 4 shows the flowchart of the general procedures for the specific implementation of FBS.

Implementation Flowchart of Fibonacci Branch Search to Adaptive Beamforming
In this subsection, in light of the results described in detail previously, an optimization scheme of ABF problem combining with the novel FBS is presented to enhance the maximum power for target signal and generate deep nulls for interferences. The basic idea of the design of such an adaptive beamformer is to utilize the global searching and local convergence capability of the novel efficient search algorithm to reduce the local minimum problem of the solution to weight vector for getting the maximum SINR. The general procedures for the implementation of Fibonacci branch search method with application to adaptive beamforming are presented in Figure 5, in which the key steps are briefly described below.
(a) Choose the depth R of Fibonacci branch to determine the population F R of the top branch layer, and set the maximum number of iterations of the optimization process.
(b) Initialize the population of the first branch layer F j , and determine the dimension of the weight vectors acting as search points in space according to the element number of ULA. Also, define the amplitude search space of the weight within [0, 1], and limit the range of weight phase to [−π, π].
(c) Assign the values to the amplitude and phase of the weight elements inside the search space for constructing the initial population of the weight vector set G w , and the weight element in the vector sets G w constructed by the amplitude and phase can be expressed as follows: where the generated weight w jd represents the dth dimension of the jth individual in the population,  (e) Set the vector elements of G w and w B as the endpoints in Equation (12), and compute the first set of weights w S1 according to the iterative rule one.
(f) Calculate the fitness in the object function of Eq. (18) using G w , w B , and w S1 , then give the evaluation to the values to find the best weight vector w best with maximum fitness value among all the vectors in space.
(g) Generate the second set of weight vectors based on the best weight vector w best and the other weights from the weight space set using Equation (12) in iterative rule two.
(h) Select the top F j+1 best weight vectors depending on the maximum fitness value in the optimization process, and these best weights are selected to compose the new population of the set G w .
(i) Check the termination criteria G w = F R . If the termination criteria are not satisfied, then increment j, and go to step (d). Otherwise, stop.
(j) If the maximum number of iterations is not reached, repeat the algorithm from step (d), or else report the output results and terminate.

Accessibility and Convergence Proof of FBS towards the Global Optimum for Multimodal Functions
In this section, accessibility and convergence proof of Fibonacci tree optimization algorithm are analyzed and investigated based on global randomness of Fibonacci branch structure. Additional rigorous mathematical proofs were implemented to prove and clarify that the proposed FBS algorithm can achieve global optimality and ensure that FBS converges towards global optimality.

Accessibility Investigation of FBS Algorithm
Mathematical proof one: The solution set in the domain of objective function can be reached via the accessible set in search space by FBS.
According to the principle of interactive searching rules in Fibonacci branch search algorithm, after enough long iterations n < +∞, the endpoints X B are generated by rule one in the basic structure of Fibonacci branch obeying the uniform distribution between the space defined by the upper and lower bounds, i.e., ∀X ∈ X B , X = (X d ) D×1 where D is the dimension of the vector, and its probability distribution is P (X d ) = U (X min , X max ); therefore, X d satisfies the following relation in the domain of the target function From the above proof process, ∀X ∈ X B obey X ∈ B, namely, the optimization set B is the accessible set of X B by FBS algorithm. Mathematical proof two: The global optima of objective function in search space are accessible for FBS algorithm.
Suppose that the global optima X * in search space are in the definition domain B of objective function, then, it can be known that according to the mathematical proof one, the solution X * is within the accessible set of B. Then, consider that the probability of the uniformly distributed in search space for random search points is P , and make a hypothesis that the local optimal solution obtained by FBS is X L . Therefore, after long enough iterations n < +∞, the probability of falling into a local optimal solution for FBS is P * ≤ n i=1 (1 − P ) on the basis of proof one, then we can obtain that From this point of view, the global optima of objective function in search space are accessible for FBS algorithm.
Consequently, it can be demonstrated from the above two mathematical proofs that the global optima in the domain of objective function are reachable for the accessible solution of FBS in search space.

Convergence Analysis of FBS Algorithm
Suppose that long enough iterations n < +∞ are implemented by FBS to search for the global optima of objective function, and the current search element set G of the basic structure obtained by FBS can form the increasingly optimized search point sequences {x T } = {x t |x best ∈ S t }, t = 1, 2, · · · , n. x best is the optimal solution in the current set of iterations. Then, we establish a probability P (t) = P (|X * − x t | ≥ ς), the chance that FBS algorithm converges to the global optimal solution, and ς represents a fixed variable with a small value. According to the generation rules of Fibonacci branch P (t) = P X (t)+P ς (t). P X (t) is the probability of generating uniformly distributed random points in the definition domain of Rule one, and P ς (t) is the probability of generating uniformly distributed random search points in a region defined by the radius parameter ς based on Rule two. Therefore, after t iterations by FBS, the probability of the search points not falling into the region of ς spacing distance around the global optima X * is P (t) = P (|X * − x t | ≥ ς), then we have lim t→+∞ P (t) = 0, hence, the following results can be obtained Let t → +∞, and we can get P (n < +∞) = 1 So FBS converging to the global optimal solution with probability 100% can be demonstrated and proven.
From the above proof of Section 3.5.1 and Section 3.5.2, we can make a comprehensive conclusion that the proposed FBS algorithm is effective, convergent, and accessible for the global optimal solution of the objective function.

Verification of the Proposed FBS
In order to validate and analyze the efficiency and effectiveness of the proposed FBS, the algorithm is verified from the following aspects in simulation experiments: (1) The accessibility to the global optimum of the proposed search algorithm for multimodal function with numerous local optima is revealed by the location history of the search points towards the optimal point.
(2) The convergence of the FBS is proved and discussed by the presented gradient of the iteration curves which manifest the convergence rate speed and the average fitness of the chosen benchmark function.
(3) The optimization precision of the solution and other relevant optimization assessment aspects of the proposed algorithm are tested on eight representative standard benchmark functions, and the results are compared with typical heuristic algorithms.
The details of the parameter settings for every heuristic algorithm used in the experiments are given in Table 1. All the experimental tests are implemented on Intel (R) Core (TM) i7-7700 HQ Core Processor @2.8 GHz and 2.8 GB RAM, and all the meta-heuristics algorithms are coded and carried out in Matlab 2017b version under the Windows10 Professional.

The Location History of the Search Points in FBS for Langermann Function
In this section, the global optimization ability of the proposed FBS is demonstrated by employing the location history of the search points during optimization process for locating the global optimum solution rather than trapping into local optimization of the benchmark example, with results compared against metaheuristic PSO algorithm. The benchmark function chosen in this section is the Langermann function with several known local optimal points and one global optimum solution point which is taken from [25,26] and is summarized in Table 2. As can be found in Table 2, two typical extreme points exist in the function. The extreme point 1 shown in the table is the global optimum solution, and the extreme point 2 is the local suboptimal solution. The three-dimensional Langermann function and contour plots are illustrated in Figure 5.  [25] global optimum solution local suboptimal solution Langermann function f L (2.003, 1.006) = −5.1612 f L (7, 9) = −3 The performance of the proposed FBS in terms of the movement trajectory of the search points scattering around the best solutions and converge towards the optimal point in the search space for Langermann are illustrated in Figure 6  and provide the results in Figure 6(a). The initial positions of the search points in both FBS and PSO are set at the extreme point 2.
As the results exhibited in Figure 6, the search points tend to explore the promising regions of the search space and cluster around the global optima eventually in multimodal Langermann pattern. From the results depicted in Figure 6(a), we can know that as the number of iterations increases, the points of PSO algorithm gradually cluster around the extreme point 2 and proceed toward local optima, and almost no particles enter the region near the global optimum extreme point 1, providing the further evidence that PSO inherently suffers from local optima entrapment and stagnation in the search space. Under the same conditions, it can be seen from the trajectories and 3D version of the search points as shown in Figure 6(b) that although the Langermann function is non-symmetric and multimodal with different levels of peaks, finding its global optimum is challenging due to many local minima in the search space. Remarkably, FBS is extricated from the initial local optimum at extreme point 2 and jumps out of the trapped solution in a local optimum point assisted by global random searching. It is evident from the location history of the search points during the process of converging toward the global optima that the points grow towards the optimal point from the area of initialization, tending to scatter around extreme points gradually and moving towards the best solutions in the search space in both 2D and 3D spaces over the course of iteration. More than half of the agents have already approached the global optimum valley after the first 50 iterations and begin converging on the optimum. As iteration increases, more agents aggregate at the extreme points and scatter around the extreme point, especially attracted intensively at the global optimum target region. Eventually, the search points find the global optimum and converge toward the global optima. This can be discussed and reasoned according to the global randomness concepts introduced by the endpoints X B which is generated in rule one of FBS. Furthermore, the convergence of FBS is guaranteed by the local exploitation optimization ability emphasized in the other endpoints X A of the proposed algorithm. Since the global random points tend to move from a less fit universe to a more fit universe by global searching in space, the best universe is saved and moved to the next iteration. Consequently, these behaviors and abilities will assist the FBS not to become trapped in local optima and converge towards the target point quickly in the iterations of optimization.
The above simulations and discussions demonstrate the effectiveness of the FBS algorithm in finding the global optimum in the search space, and the convergence performance and the rate of obtaining the global optima of the proposed algorithm by employing a set of mathematical functions will be investigated in the next sections.

Convergence Performance of the Multimodal Function
To confirm the convergence behaviour of the proposed algorithm, in this subsection, we provide the convergence curves that exhibit the objective fitness value of the typical benchmark functions obtained by the best solutions so far in each iteration. A large set of complex mathematical benchmark functions to be tested are listed in Table 3. These functions have many local optima which make them highly suitable for benchmarking the performance of the metaheuristic algorithms in terms of optimization and convergence exploration. The illustrated results are compared against those of PSO, GA, CLPSO, DE, and ABC metaheuristic algorithms on the same set of multi-dimensional numerical benmark functions. The properties and formulas of these functions are presented below. Table 3. The details of multimodal benchmark functions (D: dimensions).  Figure 7 presents the convergence characteristics in terms of the best fitness value of the median run of each algorithm for the test functions. Comparing the results and the convergence graphs, among these six algorithms, we observe that the proposed algorithm has a good global search ability and converges fast. FBS achieves better results on all multimodal groups than the compared algorithms, and it surpasses all other algorithms apparently on functions 1, 2, 5, and 6, and especially significantly improves the results on functions 1 and 2. The other algorithms show poor performance on the complex problems since they miss the global optimum basin to approach the optimal fitness. The Schwefel's function is a good example, as it traps all other algorithms in local optima, while the FBS successfully avoids falling into the deep local optimum which is far from the global optimum. On the complex multimodal functions with randomly distributed local and global optima, FBS performs the best. It should also be noted that the FBS algorithm in the graphs exhibits superiority regarding the convergence speed over the other five algorithms, and it converge to a global optimum solution with less fitness evaluations and terminates after no more than 5000 iterations on functions 1, 3, and 4, and always converges faster than others on the remaining function problems. These figures also prove that FBS not only improves the accuracy of the approximated optimum initial, but also desirably enhances the convergence speed over the course of iterations that make it converge faster than the other algorithms. Global random property and space region shortening fraction guarantees a satisfactory convergence speed. Other algorithms could not converge as fast as the FBS, since they have a large potential search space. The proposed FBS combines a global searching method and local optimization strategy together to yield a balanced performance that achieves better fitness and faster convergence. Besides, the convergence speed is a crucial parameter of real time applications like adaptive beamforming system, thus, the FBS is highly suitable and affordable for ABF.

Minimization Result of the Tested Benchmark Functions
In this subsection, experiments are conducted on a suite of multimodal functions illustrated in Table 3 to evaluate six optimization algorithms including the proposed FBS. All the test functions are minimized, and the relevant information can be found in [26,27] for the standard benchmark functions, respectively. The number of iterations for conducting the experiments is 400. For the selected benchmarking problems F1-F8, the dimension of these functions is set to 10. Every algorithm runs 1000 times independently to reduce the statistical error and achieve reliable results [28].
The statistical results considering the average value and the standard deviation function fitness value as well as the success rate (SR) needed to reach the acceptable solution are summarized in Table 4. For the results shown in Table 4, the smaller the mean value is, the better the performance of The lower the standard deviation value is, the stronger the stability of algorithm is. As seen, for most benchmark data sets, the average value and standard deviation calculated by the FBS are both smaller than those other algorithms, and the proposed algorithm surpasses all other algorithms on functions 1, 2, 3, 5, 6, and 7, and especially significantly improves the results on functions 1 and 3. When the other algorithms find their own best fitness of these functions, the proposed FBS could still search better fitness closest to the optimal value. The CLPSO achieves similar results to the FBS on function 7, and they both are much better than the other variants on this problem. The DE also performs well on multimodal problems. The DE performs similarly to the FBS on functions 1, 3, 5, and 7. However, the FBS performs better on much more complex problems when the other algorithms miss the global optimum basin. As a result, in terms of performance in the global search ability and the optimization stability for benchmarking function, the proposed FBS outperforms all other heuristics algorithms on the tested functions. In addition, this table illustrates that FBS in comparison with others displays higher percentage and accuracy reaching the acceptable solutions on these test functions. For the mean reliability of test functions F1, F3, F5, F7, FBS exhibits the highest reliability with a 100% success rate and smallest average errors. This performance superior property is due to the FBS's interactive updating rule. With the new updating rule and global randomness, different dimensions may learn from different examples based on the historically optimal search experience, and the FBS explores a larger search space than the others. Because of this, the FBS performs comparably to or better than many meta-heuristic algorithms on most of the multimodal problems experimented in this section.

The Performance of the FBS Optimization Result in Adaptive Beamforming
To demonstrate the benefits of the FBS optimization with application to adaptive beamforming, in this part of the section, several groups of simulation experiments are conducted using Matlab R2017b. The desired GNSS signal is in the form of QPSK modulation mode with 0 • for incident azimuth angle, and the power of GNSS signal is extremely weak on the ground and far less than noise; therefore, the selected SNR should not be too large in our simulation scenes. All the impinged signals are arranged coming from zeniths 45 • . Simulation environment is additive white Gaussian noise channel (AWGN). We have taken the structure size of the search element in weight vector to be five and the number of search points per element in the first set 10 layers for Fibonacci branch increases according to the corresponding Fibonacci sequence, and the sum of the element nodes in all the layer of search element is 19. The maximum number of iterations in FBS is 400. The performance of the FBS-based ABF is evaluated from the following two simulation metric aspects: the beampattern performance of the adaptive antenna array and the steady state output signal-to-interference-plus-noise ratio (SINR) of beamformer system. The performance criteria of the given beampattern in Section 5.2 are the nulling level of interference, and the given criterion that we will use to compare the numerical results and make the comparison of SINR is the numerical value.
Four groups of simulation cases corresponding to the defined measure metrics aspects conducted in terms of various experimental critera are considered in this study. The effectiveness of the proposed FBS based beamformer is investigated by the power patterns formed by extracted weights in terms of different input SNRs in the first case. The second case considers the different numbers of array elements for system output SINR using FBS by the suitable weight vectors. The performance measurement on the number of interference sources of output SINR is studied in the third case. The rest case concerns the impact of different INRs of input interference on output SINR in front of a ULA system.
The proposed FBS-based beamforming method is compared with the following five conventional heuristics-based beamforming algorithms: 1) the differential evolution (DE) based beamforming method of [29], 2) the particle swarm optimization (PSO) based beamforming method of [30], 3) the comprehensive learning particle swarm optimization (CLPSO) based beamforming method of [31], 4) the artificial bees colony (ABC) based beamforming method of [32], 5) Genetic Algorithm (GA) based beamforming method of [33]. Besides, in order to fully evaluate FBS-based beamformer comprehensively and accurately from all aspects, the performance of the classic closed-form method [12] for ABF has been presented and compared with the other algorithms specially and separately in corresponding tables. A total of 300 repetitions (independent trials) are implemented and then averaged to obtain each figure of the results.

Input SNR Evaluation of the Beampattern
We first examine the beampattern performance synthesized by the FBS and compared it to the others given in terms of input SNR in this case. A uniform linear array with 6 omnidirectional antenna elements is considered in the simulation. For investigating the effect of the input SNR with different levels, we consider three sets of input SNRs with SNR = −30 dB, SNR = −10, and SNR = 10 to demonstrate the validity of our approach. Figure 8 shows the behavior of the beampatterns synthesized by the weight vectors determined by the optimization algorithms under different SNRs. It can be seen from the figures that the weight vectors found by FBS could synthesize an inerratic beampattern with deeper nulling (with nulling level exceeding −70 dB) towards the interference compared to the other algorithms. The proposed FBS-based adaptive beamformer has suppressed the jammers in all cases while maintaining the beampattern gain in the direction of the desired signal. The other algorithms are able to achieve the interference nulling performance for a higher SNR level, i.e., SNR = 10. As the level of SNR decreases, the compared beamformers, especially ABC-based beamformer and GA-based beamformer suffer from performance degradation of the corresponding metaheuristic-based beampatterns, and the nulls do not align precisely with the interference sources. This indicates and demonstrates that the proposed algorithm is more stable and finds better solutions with greater precision in ABF application. To more clearly illustrate and comprehensively examine the nulling degrees of the proposed FBS, we compare the results to the traditional classic closed-form method, and the separately independent average nulling levels of the FBS and the closed-form method are illustrated in Table 5. We can see from the table that compared to the sidelobe level of the closed-form method which performs the best among the compared methods in each case and is 46.79, 52.96, and 71.95 dB for the classic closed-formbased beamformer, either the objective function to be optimized or less computationally extensive, and more computationally stable routines are required or else, specific characteristics of a statistical decision-making problem are desired of; therefore, the superiority of computational complexity for FBS is evident relative to it. The specific experimental comparison results and computational complexity performance advantages of the FBS algorithm are described in Section 4.3.
(a) (b) (c) Figure 9. SINR performance versus SNR of the heuristic algorithms with varied array elements. (a) Six elements; (b) ten elements; (c) fourteen elements.

Array Elements Assessment of Output SINR
In this section, the output SINR performance is measured by the number of array elements in three various conditions in terms of the increasing input SNR value, and the SNR is assumed to be changed from −25 dB to 5 dB (centered at −10 dB) in 5 dB steps. The interference with 5 dB INR is considered in the experiment. The linear arrays in different scenarios are considered to be composed respectively of 6, 10, and 14 elements. The results of the output SINR for heuristic-based beamformer and the closed-form method are illustrated in Figure 9. From the graphs, it can be noted that closed-form method achieves the highest SINR value among all the algorithms. The proposed algorithm achieves better performance than the other optimization algorithms for all the array element scenarios and is able to achieve near optimal closed-form performance over the entire range of the input SNR values. CLPSO yields suboptimal higher values of SINR, but FBS yields optimal SINR values consistently in all cases. Moreover, we can also observe that the performance difference in reaching optimum weight vectors between the FBS and other algorithms is increased for the array element increment in each algorithm, which is consistent with our previous analysis owing to the increasing search dimension of the weight vectors solution in array element. With a view to the above fact, the global search capability of the proposed FBS algorithm could achieve the improvement of the output SINR more so than the compared metaheuristic-based beamformer in adaptive beamformer system.

Investigation of INR on the Output SINR
A ULA consisting of 6 monochromatic isotropic elements with different INRs is considered in this scenario. Three groups INRs of the interference are set as 5 dB, 20 dB, 35 dB which are established in different simulation scenarios. Figure 10 displays the SINR performance of these techniques versus the SNR under different power levels of interference sources by using the proposed and other algorithms. From the results depicted in Figure 10 we can know that in general, the optimization algorithms are all able to achieve near-satisfactory closed-form based beamformer SINR performance in the situation of INR = 5 dB, which means the lowest power process of the interference signal. The proposed algorithm achieves improved performance in SINR compared to the other algorithms in all the simulations even under the most severe interference situations when the value of INR is 30 dB. With the increase of INR for the interference, the SINR performances of all the algorithms are degraded, and the proposed algorithms have evident advantages over these algorithms. Therefore, note that the proposed algorithm can perform more robust results and suitable precisions in adaptive beamforming for high interference power levels.

Examination of the Interferences Number Impact on Output SINR
The simulations in this case are conducted to validate the effect of the interference quantity to the output SINR performance. The beamformer is equipped with 6 array elements, and the INR is fixed to 10 dB for the received different numbers of interference signals. Table 6 illustrates the different numbers of interferences and the corresponding incident angle values of the above-mentioned interferences. The SINR performance of the proposed FBS and other optimization algorithms for different numbers of interference signals is shown in Figure 11. As can be seen from Figure 11, closed form method performs the best among all those in comparisons for its individual algorithm solving characteristics. With regard to the proposed FBS and other optimization comparisons, when there are one interference at the receiver, all the optimization algorithms can achieve the close-to-optimal SINR performance by considering the requirement for maximizing SINR, and FBS demonstrates the best improvement, followed by DE. ABC shows the lowest value of SINR. As the number of interferences increases from one to six, the performance advantage of the FBS becomes more evident. The increase in the number of interference sources increases the difficulty of the optimization problem. Failure of ABC, GA, and PSO to achieve sufficiently high SINR clearly illustrates their limitations; therefore, the proposed FBS is more versatile and robust than the other optimization methods in ABF application.   Table 7, Table 8, and Table 9.   From the above tables, it can be observed that the proposed FBS which achieves the near optimal nulling level possesses a huge advantage in computational complexity compared to closed form method in all cases. FBS requires far fewer evaluations and lower CPU time than closed form method consistent with the computational costs, and FBS presents a more evident advantage over the algorithm in the large array element cases. CPU time cost of FBS in each case is 17.26 s, 20.68 s and 32.74 s, and the improvements of FBS over the closed form are 171.26%, 233.70%, 278.53%. This indicates that FBS requires much fewer function evaluations, and the closed-form approach needs to compute the matrix inverse process which introduces high computational complexity especially for large number of array elements, as shown in Table 8 and Table 9, since more array elements result in a larger dimensionality of the weight vector solution, which requires a greater search time and number of computations to optimize the beamformer. Although FBS achieves slightly less deep nulling level than the closedform solving algorithm, the percentage improvement of the CPU time can compensate and provide an acceptable performance for the proposed FBS in the experiment for certain real-time beamforming situations. Overall, the FBS approach is quite competitive in complexity computation and the global search optimization compared with the other methods.

CONCLUSIONS
In this paper, we present a novel heuristic algorithm, called Fibonacci branch search, for achieving the improved performance of adaptive beamforming. The interactive global and local searching rules are proposed to reduce the probability of falling into the local optima, and the global randomness characteristic and space region shortening fraction guarantee the convergence velocity in global optimization process. In addition, we devise a specific implementation architecture based on FBS for adaptive beamformer, and the amplitudes and phases of the weight vector acting as the solution were acquired in the search space by FBS. The beamforming results synthesized by the vectors are compared with conventional metaheuristic-based beamforming algorithms.
The simulation experiments in Section 4 demonstrate that the proposed FBS achieves increased SINR over the suboptimally performing algorithm refereed to DE, CLPSO for different cases. In addition, the significant improvements over PSO, GA, ABC have been achieved in separate scenarios. With respect to computation complexity, FBS avoids the inverse calculation of the interference correlation matrix compared to the classic closed form solving algorithm. Therefore, it is recognized from academic and practical implications that the global optimization ability and fast convergence searching of FBS-based beamformer would serve significant purpose for real-time spacial filtering electronic countermeasures and large array elements of antenna design in military confrontation field. However, the limitation of FBS caused by the uncertainty of the frequent changing outliers is a major issue that needs careful consideration, and the technique may have unacceptable nulling performance corresponding to dynamic and various interference scenarios. As a future work, the FBS will be explored to apply in a more complicated time-varying situation in ABF field.