# Urban Free-Space Optical Network Optimization
## 3 A Genetic Algorithm for FSO Communication Networks  
This section presents an algorithm for creating connected FSO networks. As discussed in the previous section, the FSO problems at the focus of this paper are NP-hard. Consequently, there is no known algorithm for computing the optimal network in a reasonable time (for large networks). However, possible solutions for hard problems on graphs can be produced with low run time by applying heuristic methods [24]. The fast computation issue becomes all the more important due to dynamic changes that commonly occur in FSO networks, which are inherently sensitive to changes in climate and demand. For example, an office building may have great demand in the daytime, but most of the demand moves to nearby residential buildings in the evening. Another example is when fog blocks the LOS.  
Bio-inspired algorithms are a family of heuristic methods that simulate biological processes that exist in nature, such as the immune system, viral systems, and insect swarms. Evolution is the biological process that inspires GAs, which simulates DNA growth and mutation in cells. Next, we present a GA for solving the FSO problems at hand. The GA consists of a set of solutions, termed _population_, that iteratively changes for a given number of rounds (generations), after which the most fitting solution is obtained. The algorithm consists of five essential elements:  
1. Population initialization: This element, which constitutes the first stage of the algorithm, generates a set of possible valid solutions to the problem. This set of solutions is termed the _initial population_.
2. Crossover (merging): This element is an operator that receives as input two possible solutions and creates a new solution that combines the two. The idea is to improve the two solutions by taking valuable features from each (similarly to DNA).
3. Mutation: This element adds random changes to each solution. As in the biological process, the mutation operator creates arbitrary changes to a solution. These changes can create a high-grade solution that is unlikely to result from the crossover operator.
4. Evaluating solution: This element, often termed the _fitness function_, grades each solution. The grade determines the solution's quality, which affects the probability that the solution will survive to the next generation. For example, a fitness function on a weighted graph can be the sum of the edge/vertex weights.
5. Selection: This element is in charge of selecting the next generation of solutions according to their fitness score. The new population obtained from the selection process is further evolved by repeating the crossover and mutation steps and so forth. The basic GA structure is illustrated in Figure 7.  
The following subsections present a GA that has been specifically designed to solve the described FSO problems.  
Before proceeding to the details of the algorithm, we first present some notations:  
* Let \(CC(G,v)\) be the _connected component_ in \(G\) that contains vertex \(v\). This can be computed in \(O(E)\) time, where \(E\) is the number of edges in \(G\), by applying the \(DFS\) algorithm.  
Figure 7: Basic flow of the genetic algorithm (GA).  
* Let \(SP(v_{1},v_{2})\) be the _shortest path_ between two vertices \(v_{1}\) and \(v_{2}\). The shortest path is represented by an ordered set of vertices and edges in a graph. Accordingly, \(SP(v_{1},G_{2})\) represents the shortest path between vertex \(v_{1}\) and some vertex in the subgraph \(G_{2}\). In a slight abuse of notation, we denote by \(|SP(\cdot)|\) the length (number of edges) of the path \(SP(\cdot)\).