# Genetic Algorithms Optimized Adaptive Wireless Network Deployment
## 3 Problem Formulation
### Genetic Algorithms  
A (\(\mu+\lambda\)) elist genetic algorithm shown in Algorithm 1 searches through the space of potential field parameter values, which is encoded in the real-value chromosome. The (\(\mu+\lambda\)) elist genetic algorithm is a variant of the genetic algorithm that combines the best individuals from the parent population and offspring population to form a new population. It uses elitism to ensure that the best individuals are preserved from one generation to the next [38]. In Algorithm 1 \(P_{x}\), \(P_{m}\) are probabilities of crossover and mutation, \(g\) is the number of generations, \(h\) is the number of hops for communication between UAVs, \(\mu\) is the population size, and \(\lambda\) is the number of children generated through recombination. A number of prototyping experiments were conducted to explore different \(\mu\) and \(g\) values, types of selection strategies, crossover types, and mutation algorithms and associated probabilities. Based on these preliminary experiments, simulated binary crossover, polynomial mutation, and binary tournament selection were chosen.  
```
Input :\(P_{x},P_{m},g,\mu,\lambda,h\) \(P_{0}\gets Initialize(\mu)\) \(Evaluate(P_{0},H)\) \(P_{c}\) = [] forgen in \(g\)do fori in \(\lambda\)do \(p_{1},p_{2}\gets Tournament\ Selection(P_{t})\) \(c_{1},c_{2}\gets SBX\ Crossover(p_{1},p_{2},P_{x})\) \(c_{1},c_{2}\gets Polynomial\ Mutation(c_{1},c_{2},P_{m})\) \(P_{c}\)-add(\(c_{1},c_{2}\)) \(i=i+2\)  end for\(Evaluate(P_{c},h)\) \(P_{t+1}\gets BestHalf(P_{t},P_{c})\) \(P_{c}\) = []  end for
```  
**Algorithm 1** An elitist genetic algorithm  
The aim is to show that the genetic algorithm evolved potential field parameters that work across a wide range of user distributions in the AOI, and the results (Section 6) show that using the average performance over the four training scenarios translates robustly to testing scenarios. The next section explains the UAV's movement under the influence of potential fields. Subsequently, Section 5 explains how to derive these potential field parameters to deploy a static network in the search phase and how to use GA-tuned parameters to reconfigure the deployed network.  
The aim is to evolve high-quality and _robust_ solutions for wireless network deployment. However, earlier work has shown that solutions evolved on one scenario (user distribution) may not be robust [13; 39]; that is, potential field parameters evolved on one scenario may over-fit and thus not work well in other scenarios. Therefore, four _training_ scenarios with different user distributions were created to evolve robust solutions, as shown in Figure 1. The genetic algorithm seeks to maximize the average objective function value, computed using Equation (3), over all four scenarios. The robustness of the best-evolved solution was tested on 100 different unseen _test_ scenarios, and three of those are shown in Figure 2.  
Figure 1: Four training scenarios, where blue dots show the location of users. Lighter color represents low-bandwidth-demanding users and darker color shows higher bandwidth demand.  
Figure 2: The figures show three testing scenarios (\(T_{c1},T_{c2}\), and \(T_{c3}\)). The robustness of the best-evolved solution will be tested in these scenarios.