# A Hybrid Metaheuristic Algorithm for the Efficient Placement of UAVs
## 4 The Biased Randomized and Iterated Local Search (BR-ILS) Algorithm  
The metaheuristic methodology integrates a Biased Randomized (BR) technique and the Iterated Local Search (ILS) method. The interest of applying such a hybrid strategy is due to the capacity that these techniques have for dealing with different real-world applications. It has been observed that population-based metaheuristics are predominant over single-solution ones when designing communication networks [31]. However, single-solution metaheuristics might offer some advantages over populational approaches. In particular, the ILS metaheuristic employs less parameters and might be easier to implement. By including BR within the ILS, some random choices are included, so that different outcomes at each execution of the metaheuristic are generated. Moreover, the uncapacitated single allocation \(p\)-hub median problem is a well-known NP-hard problem. Once the set of hubs is found, the sub-problem of optimal allocation of non-hub nodes to hubs is also NP-hard for \(p\geq 3\)[32]. Thus, the application of a hybrid methodology seems to be an appropriate choice. Even though exact optimization methods provide an assured convergence to the optimal solution, the computational complexity with respect to the problem size may cause severe limitations. Thus, for larger instances, an attractive possibility is the adoption of metaheuristic algorithms, which trade optimality for runtime. These methods allow the resolution of large-scale instances of a specific problem by providing satisfactory solutions in a reasonable execution time. The ILS, which is a single solution-based method based on the Hill Climbing algorithm [33], explores a sequence of solutions that were created as perturbations of a promising candidate solution. The method finds a solution, known as current solution, and goes to a better solution by exploring the search space in steps within its neighborhood. This better solution is then used as the current solution in the next iteration. The process is repeated until a stop condition is fulfilled. In the ILS approach, the perturbations are applied to the current solution to generate neighboring solutions. A key point of our proposed methodology is the application of BR during the iterative construction of possible solutions. In this regard, every time that the algorithm constructs a solution, the eligible elements of a feasible solution are ranked according to some criteria, and then chosen according to a skewed probability function biased towards the most promising elements. Among the candidate distributions that are to be considered are the geometric distribution and triangular descendent, among others. However, we pick the geometric distribution, because it only has one parameter (\(\beta\)), which is an attractive choice to be applied in our approach. It assigns higher selection probabilities to more promising solution elements instead of relying, for example, on a restricted candidate list, as some frameworks do [34; 35]. This allows us to take advantage of BR features to improve the search space generated by the ILS and, thus, to complement the search [36]. The motivation for implementing hybrid algorithms is usually to obtain better performance approaches that take advantage of the properties of each individual strategy [37]. Algorithm 1 summarizes the logic behind the integration of BR into ILS; hence, named BR-ILS. The procedure starts by generating an initial solution. The input parameters to the algorithm are: (\(i\)) the number of users \(n\) and the number of UAVs \(p\); (\(ii\)) the stopping criterion, in our case, it is based on a time limit _maxTime_; (\(iii\)) the percentage _per_ of UAVs of the current solution to be changed during the perturbation stage; (\(iv\)) the \((x,y)\) coordinates of users _coords_; (\(v\)) the capacity between users _capacity_; and, (\(vi\)) the parameter \(\beta\) for the geometric distribution function.