# Urban Free-Space Optical Network Optimization
## 4 Results
### Genetic Algorithm Experiments
#### 4.2.1 Comparison with Other Heuristics  
The performance of the GA on the Steiner problem was compared to a standard 2-factor approximation method. The Networkx library has an implementation of the 2-factor approximation method, and we used it in our experiments. Figure 15 demonstrates the solutions of the 2-factor method and the GA on an example graph with 10 vertices. For the experiments herein, we generated random graphs with different densities and tested both the GA and the 2-factor approximation method on those graphs. The methods were tested for run-time performance and optimal cost. In the first set of experiments, we  
Figure 14: Manhattan Island visibility graph: (**a**) a map of Manhattan Island in New York, (**b**) a chart of all the buildings in that map (using OSM); and (**c**) the building visibility graph. Figure 15: Two methods comparison example. The full red–blue visibility graph (**top**) has a total cost of 60. The resulting graphs of the 2-factor (**bottom left**) method and the GA method (**bottom right**) have total costs of 15 and 12, respectively. 200 vertices and large graphs with 2000 vertices. For each graph size, we tested different densities. Figures 16 and 17 show the run-time performances of the two methods. The larger setting is limited to graphs with only 2000 vertices due to the run-time restrictions of the 2-factor method. As shown in Figure 17, the GA method exhibits better run time on the graphs with 2000 vertices. This is because the 2-factor method builds and searches over a complete graph (with 2000 vertices), whereas the GA searches for the shortest path in the original graph only, when creating the initial population. Further, in the _crossover_ function, the GA searches for the shortest path in much smaller graphs (the union between the trees). This may have low impact on the run time in small graphs (Figure 16) but is very significant as the graphs become larger (Figure 17). Figures 18 and 19 present the resulting average cost difference between the GA and the 2-factor approximation method. A negative cost difference means that the GA finds better (lower-cost) solutions than the 2-factor approximation method. Regions in which the 2-factor approximation method finds better solutions than the GA are colored in blue. Evidently, the GA method finds, on average, better solutions than the 2-factor approximation method on both sparse and dense problems, except for the intermediate blue regions. In urban cases, the graphs are expected to be dense (denser when the city is small, and sparser when the city is large). Therefore, the GA can be efficient for urban graphs. The fact that this algorithm is also faster makes it the preferable method for solving Steiner problems on urban graphs. Figure 16: Run time comparison on graphs with 200 vertices at different densities. This graph presents the run time of the 2-factor approximation method (**green**) and the GA (**blue**). Figure 17: Run time comparison on graphs with 2000 vertices at different densities. This graph presents the run time of the 2-factor approximation method (**green**) and the GA (**blue**). In an additional set of experiments we tested the performance of the two methods on different size graphs with fixed density (0.15). Figures 20 and 21 show the run time comparison and the differences in solution cost, respectively. As these experiments show, the GA is more efficient in terms of run time and solution cost on larger graphs. This confirms that the GA method is more suitable for urban visibility graphs, which are usually very large. Figure 19: Cost difference comparison on graphs with 2000 vertices at different densities. This graph presents the average cost difference between the solutions of the GA and those of the 2-factor approximation method, which are marked by the fixed black line. The blue region represents graph densities in which the 2-factor approximation method finds better solutions. Figure 20: Run time comparison on graphs with different sizes and 0.15 density.