# Urban Free-Space Optical Network Optimization
## 3 A Genetic Algorithm for FSO Communication Networks
### Generate Initial Population  
The first stage of the algorithm is to generate a set of solutions (namely, graphs) that constitutes the first generation (i.e., the initial population). This is an important step because generating high-quality solutions for the initial population can significantly affect the quality of subsequent generations. The \(firstGeneration\) process, described in Algorithm 1, begins with an empty set of solutions (line 1) and an initial graph \(G_{init}\), which is the induced subgraph of a graph \(G\) for vertex subset \(B\) (line 2). \(G_{init}\) constitutes the basic graph from which all the \(k\) initial solutions are generated. ```
Input:\(G=(R,B,E)\) red-blue visibility graph, a sink vertex \(s\in B\), and an integer \(k=|Gen_{1}|\). Result: Population of the first generation of solutions \(Gen_{1}\). \(Gen_{1}=\emptyset\) \(G_{init}=G[B]\) while\(|Gen_{1}|<k\)do \(G^{\prime}=randomConnect(G,G_{init},s)\)  add \(G^{\prime}\) to \(Gen_{1}\)  end while return\(Gen_{1}\)
```  
**Algorithm 1**Pseudocode of \(firstGeneration\), which creates the initial population that consists of \(k\) random solutions. In most realistic settings \(|B|\ll|R|\), thus \(G[B]\) is most probably not connected. Therefore, to generate a population of _valid_ solutions, the solutions must be such that all \(B\) vertices are connected. To that end, \(randomConnect\) (see Algorithm 2) ensures that a solution is indeed \"blue-connected\" by invoking a stochastic process that commences from the sink \(s\) (Algorithm 1, line 4). Such a mode of operation enables adding \(k\) valid and possibly different solutions to the initial population (lines 3-6). Figure 8 illustrates the creation of two valid initial solutions. Figure 8: Example of valid random solutions. The left side of the figure shows an example red–blue visibility graph, whereas two different valid solutions are depicted to its right. ```
Input:\(G=(R,B,E)\) red-blue visibility graph, a possibly invalid (unconnected) subgraph \(G_{init}\), and a sink vertex \(s\in B\). Result: A connected red-blue visibility subgraph \(G^{\prime}\subseteq G\). \(G^{\prime}=CC\left(G_{init},s\right)\) while\(G^{\prime}\) is not blue-connecteddo  randomly choose \(v\in B\setminus V(G^{\prime})\) \(P=findPath(G,G^{\prime},v)\) \(G^{\prime}=G^{\prime}\cup P\) end return\(G^{\prime}\)
```  
**Algorithm 2**Pseudocode of \(randomConnect\), which iteratively adds blue vertices and connects them to the graph until a valid solution is obtained. The \(randomConnect\) process, presented in Algorithm 2, is a core ingredient in the GA scheme proposed herein. It is invoked in the generation of not only the initial population, but also subsequent generations, so as to validate solutions after the _crossover_ and \(mutation\) operations (explained in the next subsections). Thus, \(randomConnect\) is designed to be robust and fast. It starts with \(G^{\prime}\), which is the connected component in \(G_{init}\) that contains the sink vertex \(s\) (Algorithm 2, line 1). Next, the connected component \(G^{\prime}\) is iteratively extended until it contains all the blue vertices (lines 2-6). Each such iteration consists of three steps: (1) choose a blue vertex \(v\) that is currently not in \(G^{\prime}\) (line 3), (2) find a random path to this vertex from \(G^{\prime}\) (line 4), and (3) update \(G^{\prime}\) (line 5). The first two steps are random, which enables generating different solutions. A more elaborate discussion on these three steps is given after the following observation. **Observation 1**. : _The original graph \(G\) (including all red vertices) is connected, and \(randomConnect\) stops only when \(G^{\prime}\) contains all of the blue vertices. Each new vertex added to \(G^{\prime}\) maintains the connectivity of \(G^{\prime}\). Therefore, each solution created by randomConnect is valid._  
Once a new blue vertex \(v\in B\setminus V(G^{\prime})\) is selected, it needs to be connected to \(G^{\prime}\). Algorithm 3 describes the process of adding the path to that vertex.