# Evolutionary Strategy for Practical Design of Passive Optical Networks
## 4 Proposed Algorithm for PON Optimization
### Our Proposed Genetic Algorithm for Optimization of PONs Planning  
Figure 3 shows the flowchart of our proposed genetic algorithm for optimization of PONs planning. The algorithm can be represented by the following steps:  
(1) Import the georeferencing data obtained from the map: In this step, the georeferenced data of the region of interest is imported to Matlab(r). OSM software is used to obtain the region's raw data. The region of interest is selected and, in the file exported by the OSM, the intersections between streets (corners) are identified with global position system (GPS), as well as the links among those intersections. These raw data (.xml file) are then imported into Matlab(r) and a georeferenced graph of the region of interest is created. The weight of each edge of the graph's adjacency matrix is the calculated distance (in meters) among the network nodes. Figure 4 shows a graphical example of importing georeferenced data to Matlab(r), considering: (a) example of a region of interest (Costa Azul neighborhood, Salvador city, Brazil) with overlapping graph; (b) example of a region of interest to be imported into Matlab(r); and (c) network graph, containing 108 nodes, imported to Matlab(r). (2) Set initial parameters: here, initial parameters must be defined. These parameters are:  
(2.1) Number of generations: defines how many iterations the GA will run;  
(2.2) Population size: defines the number of individuals of each GA generation;  
(2.3) Topology type: defines the topology (one of the four possible topologies described in Section 3);  
(2.4) Initial state: Defines the position of each potential subscriber in the respective scenario. Subscriber positions are represented by a matrix of \(N\times M\), where \(N\) is 1 and \(M\) is the map graph dimension. Each value of the matrix will be the number of subscribers in that specific node. In this paper, we defined as possibility only two, four or seven subscribers. In this stage, we also set the location of the CO using another matrix \(N\times M\). In the matrix, the node position holding the CO is set to 1 while other positions are set to 0. Figure 5 shows examples of initial states used as input of our simulations (as can be seen in Section 6). Green, yellow and red nodes represent, respectively: two, four and seven subscribers on the node;  
(2.5) Selection percentage: Defines the number of most fit individuals (in %) who will participate to the subsequent steps (genetic operators--crossover and mutation) in each generation. (3) Calculate the minimum graph distance matrix: Using the obtained data in the previous step (step 1), the algorithm performs the calculation of the graph minimum distance matrix, using a well-known Floyd-Warshall algorithm [39]. The choice of this algorithm is due to the good performance and simplicity of its implementation. The minimum distance matrix is \(M\times M\) (in which \(M\) is the graph dimension) and contains the minimum distances (in meters) among all graph nodes. Figure 4: Graphical example of importing georeferenced data to Matlab®, considering: (**a**) interest (Costa Azul neighborhood) with overlapping graph; (**b**) example of a region of interest to be imported into Matlab®; and (**c**) network graph, containing 108 nodes, imported into Matlab®. Figure 3: Flowchart of our proposed genetic algorithm for optimization of PONs planning. (4) Generate the initial population randomly with \(P\) individuals: In this step, a set of \(P\) random individuals is generated, allowing a wide range of possible initial solutions. Each individual will be represented by a line in the population matrix. This matrix will be \(P\times M\), in which \(P\) is the population size and \(M\) is the graph dimension. In addition, each gene (of the individuals) represents one possible node position for optical splitters in the network graph. Thus, each individual represents a possible solution to the problem.