Conception of routing algorithm
2004-4-9
First, for this network, there is a definition:
1, NodeSet = {A, B, C, D, E, F, G}.
* Original operation nexthop (): NextHop (Node) = set with all the node's adjacent-nodes.
* Original action Random (): random (set of nodes) = one random node in set of nodes.
2, Gene: String of element in nodes.
* Original operation node (): node (gene) = node set which constructs the string of gene.
Gene ': node (gene') = nodeset - node (gene).
3. GENESET = Collection of mature genes.
* GENESET's operation:
(1), best = geneSet.getBest ();
(2) WORST = geneSet.getWorst ();
(3), gene = geneSet.first ();
(4), gene = geneset.random ();
(5) GENESET.ADDFirst (Gene);
(6) GENESET.ADDREAR (Gene);
(7), meneset.removefirst ();
(8), meneset.removerear ();
(9), geneset.sort ();
4, from, to, pre, next: node in nodeset.
E.G. NexThop (a) = {B, C, D};
Gene = Abfc;
Gene '= deg;
Node (gene) = {a, b, f, c};
Second, the algorithm process of conception is:
1, gene.init (): node (gene) = {from, to};
Gene-set.init () {
For i: = 0 to Gene Number DO
Gene_i.init ();
}.
P. S. after Gene.init (), The Rear of The Gene, That IS, The One Before The 'To'.
2, (1), gene.builder1 () {// Conservative growth
NewNode = Random (nexthop (gene's rear-node);
Adjust (gene ');
}.
(2), gene.builder2 () {// Open
NewNode = Random (Node (Gene '));
Adjust (gene ');
}.
(3), IF (Gene is complete) {
Gene enters maturity;
GeneSet.Addrear (Gene);
}.
//
While (geneSet.GENENUMBER (1) & (2); (3); Gene can't be complete Random-delete some nodes from the rear of node (assoc); }. 3, GENESET: Collection of mature genes. 4, best = geneSet.getBest (); copy (best); Best Is Best Stop. 5, // GeneSet.rebuilder () { Give Up Half Genes of The GeneSet Which Are Not So Good; While (geneset.genenumber> 0) { Gene = geneSet. first (); (1) GeneE evolution; Store Gene in Another Half Genes' Set; GeneSet.RemoveFirst (); } Put Another Half Genes Into GeneSet; }. Turn 1 Continue to fill the GeneSet. (1) Gene Evolution { {// conservative variation Random-select two node xy in node (gene); Node = random (nexthop (x)); Change y with node; } & {// Immine variation Random-select two node xy in node (gene); Node = Random (Node (Gene ')); Change y with node; } & {// Self-house Random-delete Some Nodes in node (gene); } Gene greped to mature. }. Note: & is a choice policy. <2004-4-12 Completed Draft>
