§3.3 FLOYED Routing Algorithm and Evolution Routing Algorithm Experiment Data Analysis Algorithm Test Data Using the Network Structure of Figure 7. Then the network's topology information and dissipation information are:
Topological information matrix dissipation information matrix 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 0 0 1 1 0 2 3 1000000 1000000 2 0 1000000 6 1000000 3 1000000 0 4 1000000 1000000 6 4 0 5 1000000 1000000 1000000 5 0
Table 8 Algorithm Test Data Network Information Table Note: Among the dissipation information, 1000000 is infinite. 3.3.1 FLOYED Routing Algorithm Analysis We know that the complexity of the FLOYED algorithm is O (N3), but the complexity of the transformed FLOYED routing algorithm is slightly greater than this. Because the stop condition of the algorithm is the completion of the routing table. It can be proved that the routing table obtained by the FLOYED routing algorithm is the optimal optimal optimal. Proof this paper is from the reference information [2]. Here is the test results of the five experimental algorithms:
Experimental Number Source Router Number Calculation Routing Table Time (MS) Average Time (MS) 1 0 109 - 2 0 109 - 3 0 110 - 4 0 110 - 5 0 109 -
Table 9 FLOYED Algorithm Test Results The table's data will be compared to the test data of the algorithm with the late evolutionary routing algorithm. 3.3.2 Evolution Routing Algorithm Analysis 1. The parameter setting of the parameter setting of the evolution routing algorithm is set as follows:
Name Description Algorithm Setting Value MAX_GENE_NUMBER Pop Group 20GENE_LENGTH Gene The maximum length 100PBUILDER Conservative growth and openness growth probability 0.08max_t Evolution Algebra 10
Table 10 Evolution Routing Algorithm Parameter Setting Description The settings of these parameters are based on personal experience. But it is not necessarily the optimal. We will analyze the performance of the algorithm by experimental data. 2. The evolution of the routing algorithm convergence, but the first thing to explain is that the evolution routing algorithm is convergent. Research Evolution Routing Algorithm Algorithm EvoroutCompute, the key to the convergence of algorithm is the following process convergence: while (gene is not completion) {// Gene grows to mature Gene-Builder; if (gene-decomplete) gene-randomDelete;}; The process is used for the Gerne initialization, or in the further evolution of Gene. As defined, the elements in non-empty Genes always contain from the from and TO. And by algorithm Algorithm 5. Gene-Builder, GeneNe added segments of GeneNe's allele _Gene, which is defined by the allele: The sequence of elements in Gene is a nodeset collection or its subset of elements. Arrange, recorded as from p1 ... pm to. Where P1, ..., PM is all the node set of elements in the figure. (1) If the "path" formed in (1) is legal in the figure, that is, Gene is in a mature state (Complete), the process ends, the evolution routing algorithm converges. If the "path" formed in (1) is not legal in the figure, General Gene continues to grow; if the allele _Gene has been empty, the algorithm Algorithm 6. Gene-Decomplete can determine this situation, by algorithm Algorithm 7. Gene-randomDelete is randomly deleted with Gene (Gene may become an initial state again) and reappension. In other words, the process is a sequence point in which the element arrangement space in the Nodeset collection is searched in accordance with the random policy, and if the sequence is the legal path in the figure, the search process ends. Due to the connection between the graph, the legal path is inevitable in this space, which will also converge, and the evolution routing algorithm is convergent. 3. Evolution Routing Algorithm Analysis The following is the test results of the evolution routing algorithm: the target router label evolution algebra (No.
Generation) Routing calculation time (MS) Average time (ms) 0 0 0 47 - 0 1 16 - 0 2 0 - 0 3 18 - 0 4 0 - 0 5 26 - 0 6 0 - 0 7 16 - 0 8 15- 0 9 16 15.4 1 0 15 - 1 1 0 - 1 2 16 - 1 3 16 - 1 4 0 - 1 5
15 - 1 6 16 - 1 7 16 - 1 8 15 - 1 9 16 12.5 2 0 16 - 2 1 16 - 2 2 15 - 2 3 16 - 2 4 16 - 2 5 31 - 2 6 15 - 2 7 16 - 2 8 16 - 2 9 15 17.2 3 0 0 - 3
1 31 - 3 2 16 - 3 3 15 - 3 4 16 - 3 5 16 - 3 6 15 - 3 7 32 - 3 8 15 - 3 9 16 17.2 4 0 62 - 4 1 47 - 4 2 31 - 4 3 32 - 4 4 31 - 4 5 31 - 4 6 31
- 4 7 32 - 4 8 62 - 4 9 31 39.0 - - Total Time: 101.3 Table 11 Evolution Routing Algorithm Test Results See Figure 7's test data, experimental results show that the evolutionary routing algorithm is in the implementation process, each generation The route path of evolution is global (of course, one of the reasons is that the amount of test data for the network structure is too small). The total time in the test results table is to obtain the average total time of the routing table through generation evolution. Compared with the FLOYED routing algorithm experiment data, the evolution routing algorithm is not very advantageous in the test data in the network:
The FLOYED Routing Algorithm completes the routing table of the No. 0 router, the average total time is at 109-110ms; the evolutionary routing algorithm completes the routing table calculation of the router (according to the evolution generation), the average total time is 101.3ms.
However, the advantage of the evolution algorithm is to have good processing capabilities for large-scale growth speed, so the advantage of the network in Figure 7 does not exactly exactly. In addition, the defense probability of conservative growth and the opening of the open growth is a key parameter, which enlightenhes the growth of the search space, and the conservative growth causes the algorithm search process to converge faster, so PBuilder adjusts two opposite factors, in the figure 7 In the test data, this value is set for the scale of the problem. There is reason to believe that this parameter needs to adjust the scale of the problem to achieve better performance. Also, the size of the population and the extension of the evolutionary algebra, affect the efficiency of the algorithm, and also need to consider the scale of the problem. 3.3.3 Recommendations for the improvement of the evolutionary routing algorithm have also been explained, the algorithm is implemented in the second draft, half gene in the mature Geneset does not further evolve, and the maturity Gene Further evolution (Algorithm 9. gene-evolution.) Is still just a frame and does not consider hybridization factors; these will be the factors that are first considered during the improvement of the evolutionary routing algorithm. In the comparative analysis of experimental data, it can also be seen that the evolutionary parameters of the evolutionary routing algorithm are also critical. A good suggestion is that conservative growth and the boundary probability of the winning growth of the PBUILDER and the evolutionary algebra MAX_T are set to function of the problem scale. Explore these functions is meaningful. In addition, the implementation of the program can use an efficient way. If there is a sorting algorithm in the evolutionary routing algorithm, this paper takes the interpolation sorting algorithm, but the problem can be taken after an increased scale, such as rapid sorting. The overall framework of the evolution routing algorithm can also be further explored. This article is no longer detailed.
