3.2 Evolution Routing Algorithm Design
The basic idea of the evolution routing algorithm is to use an adaptive evolutionary strategy to find the best path between the two knots. As the network in Figure 7, the best path to 4 nodes is started by 0 nodes, and we give the following definition: 1, the node set NodeSet, that is, the collection of routers in the network, is also the node in the figure. set. Figure 7 NodeSet = {0, 1, 2, 3, 4}. However, during the implementation of the algorithm, we always treat NodeSet as vectors, ie the order of its element must be considered. 2, gene Gene, is a string of elements of node Node Set. For the gene assocization of the starting point and the end point, if all elements can constitute a path, we say that Gene is completed, ie in a maturity. In Figure 7, an immature Gene is: gene = 014; and a mature gener is: gene = 0234. 3. In the algorithm, the starting point and end point of the route are represented by from to TO, and it is always the first and last elements of non-empty Genes, respectively. Note that non-empty Gene's Rear-Node is defined as the pre-drive of TO. In Figure 7, if the 0 node is started to find the best path to 4 nodes, from = 0, to = 4. Moreover, Gene's Rear-Node = 0 is at this time. On this basis, we have the following procedure:
Original listing * Random (Node-Set) randomly takes a node-set * next (node) Take Node Neighbor Node Collection * Node (Gene) Node Collection of Gene Elements
Table 6 Evolution Routing Algorithm Original Operation Description Table and for each gene Gene, there is a Gene's opposite gene _Gene, which is the following relationship (_gene) Node (_gene) node Gene) = NODESET.
For gene Genes that become mature states, it is stored in a mature gene set. We define genes to have the following:
Operating name effect * geneset.addrear (); increasing get * geneSet.Getfirst () in the end (); get the first gene * geneSet.removefirst (); delete the first geneset.sort (); from good to bad For all GeneSet.getBest (); get the best get * geneSet.removehalf (); delete half of Gene * geneSet.removeAll (); Delete All GeneTures 7 GeneSet Operation Instructions, if Node starts to find the best path to 4 nodes, the basic principle of the evolution routing algorithm is that the gene Gene = 04, and we make Gene a mature state by evolutionary approach, a complete path. Finally, the population is sorted, we can get a good Gene, a good path, resulting in a next stop router from 0 nodes to 4 nodes. A key to evolution is that Gene is a growing process of immature to maturity. This growth process is based on the original operation in the above definition. Such as: GENE's new fragment (ie, new nodes), maybe new Gene = 034; if the new clip is Random (NeXthop (Gene's Rear-node) -Node (Gene)) It may be new Gene = 014. The new fragment is always successively added to the Gene's Rear-Node. One is that node (assoc) is still equal to NodeSet, but Gene is still a maturity. At this time we should start randomly delete a paragraph from Gene's REAR-NODE, and then let Gene grow up from the new beginning, so that the algorithm converges.
This is the basic principle of the evolution routing algorithm to find the best path. Now define the route algorithm. Algorithm 1. Gene-init.// gene Gene's initialization begin node (gene) = {from, to};
Algorithm 2. Random (node-set). Randomly removes an element from Node-SET to return operation failure with 0.1 probability possibility of 0.1; Size = Node-Set collecting courses; random returns Node from 0 to SIZE A node of the set; end.
In the Evolution Routing Algorithm, Gene's growth strategy is composite, and the basic growth process is conservative growth, and it will grow. They are defined as follows: Algorithm 3. Gene-builder1.// gene Gene's conservative growth begin newNode = random (General (Gene's Rear-node) -Node (Gene)); add new NEWNODE as a gene The length of the new front drive element, the length of Gene is 1; End.algorithm 4. Gene-builder2.// gene Gene's open-clear growth begin newode = random (Node (_GENE)); if there is no failure) Add NewNode as a gene The new front drive element, the length of Gene is increased by 1; EDN.
Algorithm 5. Gene-builder.// Gene Genes growth begin P = probability value between 0 to 1; if (p The next algorithm will determine if the geneNe cannot converge; if it is randomly deleted the Gene segment, the death cycle of the evolution routing algorithm will be released. Algorithm 6.// Decision Gene is impossible to be Complete's Begin if (Gene Is Not Complete and _Gene IS NIL) Return True; Else Return False; END. Algorithm 7. gene-randomdelete.// gene Gene randomly removes the length of partial segment begin size = gene; randinteger = a random integer between 0 to SIZE-2; for i = 0 to randinteger-1 Do Begin Delete Gene TO element of the TO element; end; end. Among them, in the operation of GeneSet.sort (), there is a good comparison between GeneNe. We define better genene, ie, the route representative of Genes is less dissipated in the network, which is the association of Gene's evaluation function. Suppose the dissipation information of the network is stored by the matrix Valarray [] []. Algorithm 8. Gene-Distance-function.// Calculate the dissipation value of Gene (class) begin distance = 0; Node-set = node (gene); size = node-set collection base; for i = 0 TO Size-2 do begin row = node-set [i]; col = node-set [i 1]; distance = distance value [row] [col]; END; return distance; end. Algorithm 9. Gene-evolution.// Gene Gene Mature Removal Begin {// Conservative Variation Randomly Select Two Adjacent Node XY in Node (Gene) Where Y! = TO; Node = Random (nexthop (x)); Change Y with node;} & {// Open Mutation Randomly Select Two Adjacent Node XY! = To; node = random (node (_gene)); change y with node;} & {// Self-owned A gene-randomdelete (gene);}; while (gene is not completion) {// Gene grows to mature gene-builder; if (gene-decomplete) gene-randomDelete;}; end. Note: Algorithm 9. 中 中A strategy that is selected by probability.
