# Evolutionary Strategy for Practical Design of Passive Optical Networks
## 4 Proposed Algorithm for PON Optimization
### Our Proposed Genetic Algorithm for Optimization of PONs Planning
It is worth mentioning that topologies with two splitting stages will be represented with two population matrices (each one for each splitting level). The following matrices (\(A_{1}\) and \(A_{2}\)) represent a random initial population for an hypothetical scenario of a PON using two splitter stage. Figure 6 represents graphically the first individual of both matrices. \[A_{1}= \begin{bmatrix}0&1&0&0&0&1&0&0&\cdots&0\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&1&0&0&1&0&\cdots&0\end{bmatrix} , \tag{3}\]  
\[A_{2}= \begin{bmatrix}0&0&0&1&1&0&0&1&\cdots&1\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 0&1&0&1&1&0&0&0&\cdots&0\end{bmatrix} . \tag{4}\]  
Figure 5: Network initial state for non-dense and dense simulation scenarios, considering network topologies with 314 nodes (Region I) and 714 nodes (Region II). (**a**) NDS-Region I, (**b**) DS-Region I, (**c**) NDS-Region II, (**d**) DS-Region II. (5) Calculate the individual cost (fitness function): With the individuals generated in the previous step (step 4), and the obtained information from the map, the network is set up for each individual and the total cost (for each individual) is calculated. The network total cost (in R$) is represented by the sum of all materials and services involved in the network deployment. Figure 7 shows the flowchart and the following steps describe in details the fitness function steps:  
Figure 6: Graphical example of the first individuals of the initial population matrices (with two optical splitter levels) presented in Equations (3) and (4). Each pair of individuals in the matrices will represent a different solution for the problem. Figure 7: Flowchart of the fitness function steps. (5.1) Import table of costs: First of all, the table of costs for PON deployment containing materials and installing service costs is imported. These costs were reported by a real ISP of Salvador city, Brazil;  
(5.2) Find the shortest path between subscribers-splitters (respecting constraints) and discard unused splitters: Using matrix operations, the algorithm finds the shortest path between all subscribers and splitters (respecting the following constraints: (1) the last mile connection will always use a drop cable and must respect the maximum limit of 400 m; (2) the number of subscribers served by an optical splitter cannot be greater than the number of available ports; (3) every subscriber must be connected to an optical splitter). Splitters that do not have assigned subscribers are discarded (gene value in the specific position of the matrix is set to 0). Individuals who do not meet the restrictions have their costs defined as infinite and, consequently, are discarded in the next generations;  
(5.3) Find the shortest path between 2 nd level splitters and 1 st level splitters (respecting constraints) and discard unused splitters: Similarly to step (5.2), using matrix operations, the algorithm calculates the shortest path between all 2 nd and 1 st level splitters (if a multiple stage is adopted). Connections must respect the available ports of first level splitters. Empty splitters are discarded;  
(5.4) Find the shortest path between 1 st level splitters and CO (and check the cabling reuse possibility): Again, using matrix operations, the algorithm calculates the shortest path between all 1 st level splitters and CO. Based on the found minimum distances, the algorithm checks the possibility of creating a shared feeder cable route among 1 st level splitters;  
(5.5) Calculate the link budget for each individual and discard non-viable solutions: In this step, the individual optical power budget is also calculated. For the calculus of optical attenuation, typical attenuation values defined on the ITU-T G.671 recommendation [40] were used, which characterizes optical components. To complement and to increase the accuracy of the calculation, we also adopted a vendor (Furukawa) real typical values of attenuation for passive (Table 3) and active network elements (Table 4).