§3.2 演化路由算法设计
演化路由算法的基本思想是使用自适应的演化策略，来寻找两结点间的最佳路径。如图7中的网络，由0结点开始寻找到4结点的最佳路径，我们下给出如下定义：
1， 结点集合NodeSet，即是网络中路由器的集合，也是图中的结点集。
图7中NodeSet = { 0，1，2，3，4 }。但算法的实现过程中，我们总把NodeSet视为向量，即其元素的序是必须考虑的。
2， 基因gene，即是结点集合NodeSet的元素组成的字符串。对于预先设置起点与终点的基因gene，如果按字符串的顺序，所有元素能构成图的一条路径，我们称gene是完成的(COMPLETE)，即处于成熟态。
图7中，一个不成熟的gene是：
gene = 014 ；
而一个成熟gene是：
gene = 0234 。
3， 在算法中，路由的起点与终点用from与to表示，而且，始终分别为非空gene的第一个和最后一个元素。注意，非空gene的rear-node定义为to的前驱。
图7中，若由0结点开始寻找到4结点的最佳路径，则 from = 0，to = 4。而且，此时gene’s rear-node = 0 。
在此基础上，我们有如下原操作：
原操作名称 作用
*RANDOM(node-set) 在node-set中随机取一个结点
*NEXTHOP(node) 取node的邻接结点集合
*NODE(gene) 取gene元素构成的结点集合
表6 演化路由算法原操作说明表
而对于每一个基因gene，在一个网络中(其结点集合为NodeSet)，都存在一个gene的对立基因_gene，满足如下关系：
NODE(_gene) + NODE(gene) = NodeSet .
对于成为成熟态（COMPLETE）的基因gene，都存储于成熟的基因集合GeneSet中。我们定义GeneSet有如下操作：
操作名称 作用
*GeneSet.AddRear(); 在尾端增加gene
*GeneSet.GetFirst(); 获得第一个gene
*GeneSet.RemoveFirst(); 删除第一个gene
*GeneSet.Sort(); 从好到坏对所有的gene排序
*GeneSet.GetBest(); 获得最好的gene
*GeneSet.RemoveHalf(); 删除一半的gene
*GeneSet.RemoveAll(); 删除所有的gene
表7 GeneSet操作说明表
如上，若由0结点开始寻找到4结点的最佳路径，则演化路由算法的基本原理是，初始化基因gene = 04，我们通过演化的方法使gene成为成熟态，即一个完整的路径。最后对种群进行排序，我们可以获得一个好的gene，即好的路径，从而得到0结点至4结点的下一站路由器。演化的一个关键是，gene由不成熟的状态到成熟态的成长过程。这个成长过程，基于上述定义中的原操作。如：
获得gene的新片段（即新结点）若为 RANDOM（ NODE（_gene）），则可能新的 gene = 034；若新片段为 RANDOM（ NEXTHOP（gene’s rear-node ）-NODE（gene） ），则可能新的 gene = 014。新片段总是作为gene的 rear-node的后继加入gene中。
有一种情况是，NODE（gene）已经等于NodeSet，但gene仍然不是成熟态，此时我们应从gene的rear-node开始向前驱方向随机删除一段，然后让gene从新开始成长，从而使算法收敛。
此即演化路由算法寻找最佳路径的基本原理。现在定义演化路由算法。
Algorithm 1. Gene-Init.
//基因gene的初始化
BEGIN
NODE(gene) = { from , to };
END.
Algorithm 2. RANDOM( node-set ).
//从node-set中随机取出一个元素
BEGIN
以0.1的概率可能性返回操作失败;
SIZE = node-set 的集合基数;
从0到SIZE间随机返回node-set的一个结点;
END.
演化路由算法中，gene的成长策略是复合的，而基本的成长过程为保守成长、开明成长。分别定义如下：
Algorithm 3. Gene-Builder1.
//基因gene的保守成长
BEGIN
newNode = RANDOM( NEXTHOP(gene’s rear-node)-NODE(gene) );
If( RANDOM没有失败 )
增加newNode作为gene中to的新前驱元素,gene的长度增1;
END.
Algorithm 4. Gene-Builder2.
//基因gene的开明成长
BEGIN
newNode = RANDOM( NODE( _gene ) );
If( RANDOM没有失败 )
增加newNode作为gene中to的新前驱元素,gene的长度增1;
EDN.
Algorithm 5. Gene-Builder.
//基因gene的成长
BEGIN
p = 一个0到1之间的概率值;
If( p < PBUILDER ) //PBUILDER是预设的一个值
Gene-Builder1;
Else
Gene-Builder2;
END.
接下来的算法，将判断gene是否无法收敛；如果是将对gene片段进行随机删除而解除演化路由算法的死循环。
Algorithm 6. Gene-DECOMPLETE.
//判断gene是否已经不可能成为COMPLETE的了
BEGIN
If( gene IS NOT COMPLETE AND _gene IS NIL )
Return TRUE;
Else
Return FALSE;
END.
Algorithm 7. Gene-RANDOMDELETE.
//基因gene随机删除部分片段
BEGIN
SIZE = gene的长度;
randInteger = 在0到SIZE-2之间的一个随机整数;
For I = 0 To randInteger-1 Do
BEGIN
删除gene中to元素的前驱;
END;
END.
其中对GeneSet.Sort()的操作中，有gene的好与坏的比较。我们定义较好的gene，即是gene所代表路由路径在网络中耗散较少，此即gene的评价函数定义。假设网络的耗散信息由矩阵ValArray[ ][ ]存储。
Algorithm 8. Gene-Distance-Function.
//计算gene的耗散值(类于距离)
BEGIN
distance = 0;
node-set = NODE( gene );
SIZE = node-set 的集合基数;
For i = 0 To SIZE-2 Do
BEGIN
row = node-set[ i ];
col = node-set[ i +1 ];
distance = distance + ValArray[ row ][ col ];
END;
返回distance;
END.
Algorithm 9. Gene-Evolution.
//基因gene成熟后的再演化
BEGIN
{ //保守变异
Randomly select two adjacent node XY in NODE(gene) where Y != to;
node = RANDOM( NEXTHOP( X));
Change Y with node;
} & { //开明变异
Randomly select two adjacent node XY in NODE(gene) where Y != to;
node = RANDOM( NODE( _gene ) );
Change Y with node;
} & { //自舍一段
Gene-RANDOMDELETE(gene);
};
While ( gene IS NOT COMPLETE )
{ // gene成长至成熟
Gene-Builder;
If ( Gene-DECOMPLETE )
Gene-RANDOMDELETE;
};
END.
注释： Algorithm 9. 中 & 是一种按概率进行选择的策略。
本文地址：http://com.8s8s.com/it/it36712.htm