实现路由模拟算法的步骤

实现路由模拟算法的步骤

 

/* 参数说明：

_netArray: routNum * routNum的矩阵，网络的拓扑信息

_valArray: routNum * routNum的矩阵，网络的耗散信息

result : routNum * 2的矩阵，路由表-返回

_routNum : 路由器数量

index : 源路由器号

*/

void RoutCompute::ComputeMethods(int ** _netArray, int ** _valArray,

int **& result, int _routNum, int index)

{

//初始化

Init(_netArray,_valArray,_routNum);

//局部变量的初始化

GeneSet halfGeneSet(nodeNum,netArray,valArray);

GeneSet bestGeneSet(nodeNum,netArray,valArray);

RoutGene gene(nodeNum);

RoutGene best(nodeNum);

int T;

for(int to=0;to<nodeNum;to++)

{//计算index到to路由表

T = 0;

pGeneSet->RemoveAll();

while(T<MAX_T)

{//最多演化MAX_T代

while(pGeneSet->REAR()<MAX_GENE_NUMBER)

{

gene.Init(index,to);

while(true)

{//gene的成长过程

Builder(gene);

//如果gene已经不可能成为完整的路由

if(DECOMPLETE(gene))

RANDOMDELETE(gene);

//如果gene是完整的路由

if(COMPLETE(gene))

break;

}//end of while

//把gene加入到成熟态gene集合

pGeneSet->AddRear(gene);

}//end of while

pGeneSet->Sort();

best = pGeneSet->GetBest();

bestGeneSet.AddRear(best);

//

pGeneSet->RemoveHalf();

/*注释部分为算法的最初设计方案，对所余留的gene进行进一步演化。

但此处暂时不设计，而仅仅是保留一半的gene直接进入下一代的竞争。

while(pGeneSet->REAR()>0)

{

gene = pGeneSet->First();

//gene演化

Evolution(gene);

halfGeneSet.AddRear(gene);

pGeneSet->RemoveFirst();

}

while(halfGeneSet.REAR()>0)

{

gene = halfGeneSet.First();

halfGeneSet.RemoveFirst();

pGeneSet->AddRear(gene);

}*/

//演化代数增加

T ++;

}//end of while(true)

bestGeneSet.Sort();

best = bestGeneSet.GetBest();

bestGeneSet.RemoveAll();

//填充路由表

result[to][0]=to;

result[to][1]=*(NODE(best).GetpNodeSet()+1);

}

}

void RoutCompute::Evolution(RoutGene & gene)

{//gene的演化暂时不进行设计

}

bool RoutCompute::COMPLETE(RoutGene & gene)

{//判断gene是否是完整的路由

NodeSet geneNodes = NODE(gene);

bool bVal = true;

int m,n;

int index = geneNodes.GetLastIndex();

if(index != -1)

{

for(int i=0;i<index;i++)

{

m = *(geneNodes.GetpNodeSet()+i);

n = *(geneNodes.GetpNodeSet()+i+1);

bVal = bVal && (netArray[m][n]==1);

}//end of for

return bVal;

}//end of if

return false;

}

bool RoutCompute::DECOMPLETE(RoutGene & gene)

{//判断gene是否已经不可能成为完整的路由

bool bVal = COMPLETE(gene);

NodeSet geneNodes = NODE(gene);

NodeSet _geneNodes= routNodes - geneNodes;

int index = _geneNodes.GetLastIndex();

if( !bVal && index==-1)

return true;

return false;

}

void RoutCompute::Builder1(RoutGene & gene)

{//保守成长

NodeSet geneNodes = NODE(gene);

NodeSet nextNodes(nodeNum);

int value,index = geneNodes.GetLastIndex();

int k = 0,newNode;

if(index > 0)

{

value = *(geneNodes.GetpNodeSet()+index-1);

for(int i=0;i<nodeNum;i++)

if( netArray[value][i]==1 )

*(nextNodes.GetpNodeSet()+ k++) = i;

nextNodes = nextNodes - geneNodes;

newNode = RANDOM(nextNodes);

if(newNode != -1)

gene.Increase(newNode);

}

}

void RoutCompute::Builder2(RoutGene & gene)

{//开明成长

NodeSet geneNodes = NODE(gene);

NodeSet _geneNodes= routNodes - geneNodes;

int newNode = RANDOM(_geneNodes);

if(newNode != -1)

gene.Increase(newNode);

}

void RoutCompute::Builder(RoutGene & gene)

{//成长方法

double p = ((double)RandInteger(1000))/1000.0;

if(p<PBUILDER)

Builder1(gene);

else

Builder2(gene);

}