路由算法的构想
2004-4-9
一，对于这个网络，有如下定义：
1, nodeSet = { A,B,C,D,E,F,G }.
* 原操作 NEXTHOP() : NEXTHOP(node) = set with all the node’s adjacent-nodes.
* 原操作 RANDOM() : RANDOM(set of nodes) = one random node in set of nodes.
2, gene : string of element in nodeSet.
* 原操作 NODE() : NODE(gene) = node set which constructs the string of gene.
gene’: NODE(gene’) = nodeSet – NODE(gene).
3, geneSet = 成熟态gene的集合.
* geneSet 的操作：
(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), geneSet.RemoveFirst();
(8), geneSet.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 };
二， 构想的算法过程为：
1, gene.Init() : NODE(gene.Init) = { 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 is the element just before the last one, that is, the one before the ‘to’.
2, (1), gene.Builder1() { //保守成长
newNode = RANDOM( NEXTHOP( gene’s rear-node) );
ADJUST( gene’);
}.
(2), gene.Builder2() { //开明成长
newNode = RANDOM( NODE( gene’) );
ADJUST( gene’);
}.
(3), if ( gene is COMPLETE ) {
gene 进入成熟态;
geneSet.AddRear( gene );
}.
//
While( geneSet.geneNumber < MAX_GENE_NUMBER ) {
(1) & (2);
(3);
if (gene can’t be COMPLETE )
random-delete some nodes from the rear of NODE(gene);
}.
3, geneSet : 成熟态的gene的集合.
4, best = geneSet.GetBest();
COPY( best );
If( best is BEST)
停机.
5, //
geneSet.ReBuilder() {
give up half genes of the geneSet which are not so good;
while( geneSet.geneNumber >0){
gene = geneSet. First();
(1) gene 演化;
存储 gene in another half genes’ set;
geneSet.RemoveFirst();
};
put another half genes into geneSet;
}.
转1继续填充geneSet.
(1) gene演化 {
{ //保守变异
random-select two node XY in NODE(gene);
node = RANDOM( NEXTHOP( X));
change Y with node;
} & { //开明变异
random-select two node XY in NODE(gene);
node = RANDOM( NODE(gene’) );
change Y with node;
} & { //自舍一段
random-delete some nodes in NODE(gene);
};
gene 成长至成熟.
}.
注：& 是一种选择策略.
<2004-4-12 完成草稿>
