# An Evolutionary Algorithm to Optimise a Distributed UAV Swarm Formation System
## 4 Optimisation Approach
### Evolutionary Algorithm (EA)  
The proposed optimisation algorithm is a hybrid EA consisting of two stages (Algorithm 2). First, a genetic algorithm (GA) approach is used during the first 90% of evaluations where the solution space is explored while the GA is converging to competitive solutions [4]. Secondly, a local search (LS) is applied to the best solution found by the GA in order to explore its neighbourhood. In doing so, this high-level relay hybridisation (HRH) approach [21] improves the final solution found by the EA.  
The GA approach mimics processes present in evolution such as natural selection, gene recombination after reproduction, gene mutation, and the dominance of the fittest individuals over the weaker ones. This is a steady-state GA whereby an offspring of \(\lambda\) individuals is obtained from the population \(\mu\), so that the auxiliary population \(Q\) contains the subset of individuals (10 in our implementation) from the population \(Pop\) (20 individuals). This decision finds its justification in the long evaluation times required to evaluate each individual through realistic simulations, especially in the most dense scenarios.  
Following the EA's pseudocode, after initialising \(t\), \(N_{ev}\), and \(Q(0)\), the initial population \(Pop(0)\) is filled with random individuals by the _Initialisation_ function. Then, the main loop is executed while the termination condition is not fulfilled (270 evaluations in our case). Binary tournament [22] was used as selection operator, integer polynomial mutation [23] as mutation operator, and an elitist replacement was used to update the algorithm population after each generation. Regarding the crossover operator, we propose two candidates: the well-known uniform crossover [24] and a novel variant adapted to this problem, the drone crossover, both described later in Section 4.2.  
The parameters of the GA were calculated as described in Section 4.5, using the irace package. After the GA stage, the best solution obtained is fed into the LS performed bythe hill climbing algorithm [25] (HC), which will explore the best solution neighbourhood during the last 30 evaluations. By doing so, we have first explored the search space and then exploited the best solution found. Figure 3 shows the block diagram of the proposed EA where the differences between it and a canonical GA are highlighted by coloured blocks. Specifically, it can be seen that the last 10% of evaluations are used for LS and that in the GA phase, two different recombination operators (crossover) have been proposed to work in combination with a different mutation operator for integer numbers (instead of bit flip).  
```
functionEA(\(P_{c},P_{m}\)) \(t\gets 0\)\(\triangleright\) Genetic Algorithm \(N_{ev}\gets 0\)\(\triangleright\)\(Q(0)\leftarrow\emptyset\)\(\triangleright\) Q=auxiliary population \(Pop(0)\gets Initialisation(\mu)\)\(\triangleright\) Pop=population of \(\mu\) individuals while\(N_{ev}<MAX\_EVALLATIONS*0.9\)do\(\triangleright\) 2 iterations reserved for LS \(Q(t)\leftarrow Selection(Pop(t))\)\(\triangleright\)\(\lambda\) individuals \(Q(t)\leftarrow Crossover(Q(t),P_{c})\) \(Q(t)\gets Mutation(Q(t),P_{m})\) \(Evaluation(Q(t))\)\(\triangleright\) Also increases \(N_{ev}\) \(Pop(t+1)\leftarrow Replacement(Q(t),Pop(t))\) \(t\gets t+1\) endwhile best_solution(\(t\))\(\leftarrow\) BestSolution(\(Pop(t)\)) distance\(\leftarrow\) 1 while\(N_{ev}<MAX\_EVALLATIONS\)do\(\triangleright\) Local Search: Hill Climbing \(Solutions(t)\leftarrow Neighbours(best\_solution(t),distance)\) \(Evaluation(Solutions(t))\) \(\triangleright\) Also increases \(N_{ev}\) \(best\_solution(t+1)\leftarrow\) BestSolution(\(Solutions(t)\cup best\_solution(t))\) distance\(\leftarrow\) distance\(+\) \(t\gets t+1\) endwhile returnbest_solution(\(t\)) endfunction
```  
**Algorithm 2** Pseudocode of the hybrid evolutionary algorithm (EA).