# Urban Free-Space Optical Network Optimization
## 3 A Genetic Algorithm for FSO Communication Networks
### Creating the Next Generation  
Evolutionary algorithmic schemes such as GA simulate the change of population by creating generations of solutions. The formation of each new generation in the GA herein is performed by a process called _nextGeneration_. The goal of this process is to create increasingly stronger solutions in every round (generation) by attempting to produce strong new solutions that are based on solutions from the previous generation and on eliminating weak solutions. New solutions are obtained by invoking the _crossover_ and _mutation_ operators. Subsequently, the \(fitness\) function evaluates the quality of these newly obtained solutions. Finally, the new generation's population is selected according to the calculated fitness scores of the obtained solutions. The iterative flow of _nextGeneration_ is depicted in Figure 10.  
Figure 10: The iterative flow of _nextGeneration_.  
Figure 9: Illustration of two possible paths for connecting the blue vertex \(v\) to the component of the sink vertex \(s\), one through relay vertex \(v_{1}\), and another through relay vertex \(v_{2}\).  
Denote by \(Gen_{i}=g_{1},\ldots,g_{k}\) the population of solutions of the current generation \(i\). The population of the next generation \(Gen_{i+1}\) is a set of solutions with the following attributes; (1) \(|Gen_{i+1}|=|Gen_{i}|=k\); (2) \(Gen_{i+1}\) will contain solutions from \(Gen_{i}\) with the addition of new solutions obtained by using the _crossover_ and _mutation_ operators; (3) to obtain \"strong\" genes, the resulting \(k\) most-fit solutions will be chosen for \(Gen_{i}\). Algorithm 4 presents the pseudocode of the _nextGeneration_ process.  
```
Input: Population (set of solutions) of the current generation \(Gen_{i}\) and integers \(m,k\). Result: Population of size \(k\) of the next generation \(Gen_{i+1}\). for\(m\) times do  randomly choose \(G_{1},G_{2}\in Gen_{i}\) \(G^{\prime}=\textit{crossover}\left(G_{1},G_{2}\right)\) \(G^{\prime}=mutation\left(G^{\prime}\right)\) \(G^{\prime}.grade=fitness\left(G^{\prime}\right)\)  add \(G^{\prime}\) to \(Gen_{i}\) end  sort the solutions in \(Gen_{i}\) according to their \(grade\) field \(Gen_{i+1}=\) top \(k\) solutions of \(Gen_{i}\) return\(Gen_{i+1}\)
```  
**Algorithm 4**Pseudocode of _nextGeneration_, which creates the population of the next generation by applying the _crossover_ and _mutation_ operators on solutions from the previous generation.  
The new population consists of the \(k\) \"best\" obtained solutions.  
**Observation 2**.: _The quality of solutions can only improve from generation to generation._  
The above observation holds because all the \(m\) newly obtained solutions through _crossover_ and _mutation_ join the \(k\) original solutions of the current generation \(Gen_{i}\), before the next generation \(Gen_{i+1}\) is formed from the top \(k\) solutions (of the \(m+k\) possible solutions). Consequently, in the worst case, all newly obtained solutions are \"worse\" than the original \(k\) solutions of \(Gen_{i}\), leading to \(Gen_{i}=Gen_{i+1}\). Otherwise, the population \(Gen_{i+1}\) is strictly better than \(Gen_{i}\). The observation makes the present GA an \"anytime\" algorithm [35], which is a key feature for heuristic algorithms.  
The _nextGeneration_ process is invoked for a given number of times, according to the predefined number of generations (see Figure 7). Nevertheless, the anytime feature enables deciding at any point whether to continue the process or settle for the current best solution without the risk of ending up with some temporary bad solution.