求助，基于遗传改进算法的路由最短路径算法C语言仿真

jl646360594

3.1.1求解SP路由问题的数学网络模型
最短路径算法，关键是将一个物理网络结构抽象为一个数学网络结构，再利用数学方法进行求解。
我们在研究路由问题时，一个网络可表示成一个加权图G(N，E)，其中N表示节点集，E表示连接节点的通信链路集。N和E分别表示该网络中的节点数和链路数，Cij为链路(i，j)的代价，代价矩阵为C=[Cij]源节点和目的节点分别用S和D表示，每个链路的连接用Iij表示，定义如下：

3.1.2算法编码的设计
    为了下面描述问题的方便，这里首先给出一张仿真路由图，如图3．2所示．图
中的A、B、C等表示节点，在实际网络路由中表示网络的路由器：节点之间的
数值称为权值，在实际网络中则表示通过这条线路所要消耗的时间(代价)。

图中的信息在程序编码中转换成邻接矩阵的形式，这样方便编码的实现，矩
阵是一个a*a矩阵，a[i][j]表示从节点i到到达节点j所需要的网络消耗。如果该数值为0，这说明从节点i=j，如果等于∞则表示节点i到节点j没有直接路径到达。为了方便叙述，本文所采用的图均是无向图，即任意两节点如果存在直接的通路则两节点可以互传信息。
3.1.3算法种群的初始化
这里种群中的个体不能采用传统遗传算法中的数值编码方式(如二进制和实数编码)，而只能采用符号编码方式。这样才能更直接、更具体地表达路径的实际意义，同时也有利于适应度函数的选取和适应度的计算。在上图中，一条从起始节点A到目标节点P的路径可以编码成沿路径的一串节点，如个体(A，C，F，J，M，0．P)，每个个体都必须对应着网络中的一个实质上的连接。
此外，种群中不同个体的长度也不尽相同，这主要因为从初始节点到目标节点的多条路径中，各条路径所经过的节点数很可能不同．例如在上图中，从起始节点A到目标节点P，如果按照(A，B，E，H，K，N，L，0，P)行进，则经过7个中间节点，对应的个体长度M为9：而如果按照(A，B，D，G K N，P)行进，则经过5个中间节点，对应的个体长度M为7。
最后需要说明的是初始种群的产生方法．初始种群中的个体必须不能是断路或环路，否则以后的进化将毫无意义。为克服这种现象的出现，确保不出现断路，本文使用一个函数，具体执行过程如下：从起始点出发，随机选取与起始点直接相连的一个点作为下一个节点，如果此节点还有下一个节点与其相连，则将下一结点添加进去，如此反复，直到找到终点为止。这就保证了不会出现断路的情况。同时，在路径的产生过程中为了避免出现环路，规定在一条路径中，当一个路径节点被选中以后，则给该节点一个标记，只有没有标注标记的节点才能被选作新的路径节点，每条路径选择完后标记全部刷新，编码后的个体以数组的形式存储。
3.1.4算法适应度函数的设计
3.1.5算法的选择操作
    选择操作是用来确定或交叉个体，以及被选个体将产生多少个子代个体。选择操作一般有两个过程：首先是计算适度值；其次是按照适度值从大到小进行排序，即f(h1)≥f(h2)≥…≥f(hp)，则适度值最大的就是最好的个体，将最好的个体选做父个体。各个个体的选择概率和其适度值成比例，个体适度值越大，则被选择的概率就越高。如果产生相同的染色体，则只保留一个染色体，将其余的染色体删除，这个过程重复进行完成个体的选择。
3.1.6算法的交叉和变异
这里同样不能采用传统遗传算法中随机进行一点或多点杂交的操作，因为这样很容易产生断路或坏路而使得进化过程前功尽弃，针对网络路由算法的具体需要，这里采用只允许在重复节点位置杂交且只进行一点杂交的操作方式．当杂交运算应用于父代个体V1和V2时，其操作过程如下：
(1)列举出V1和V2中均含有的节点集合Nc(不包括起始节点和目标节点)作为潜在的杂交位置；
    (2)从Nc中随机选择一个节点i∈Nc作为杂交点：
    (3)检查V1和V2中在节点i之前或之后的内容是否相同，如相同，则取消本次杂交操作：否则进行下一步：此步骤防止杂交的两个个体相同，如果相同则无法杂交，因为杂交出来的结果也是一样的，没什么意义。
    (4)通过交换杂交点后的所有节点得到杂交后新的子代个体：
    (5)若杂交后的子代个体中存在环路，则找到环路中的所有节点，将其从个体中删除，如：杂交后得到(A->B->C->D->E->F->G->H->E->J->K->L)，则此路径中存在环路E->F->G->H->E，出现上述情况则把F,G，H，E从个体中删除，这样就得到不包含环路的个体。
下面通过一个具体实例来说明杂交操作．设从起始节点A到目标节点P的一对父代个体V1和V2如下所示：
     父代个体V1(A，B，E，H，K，N，L，O，P)
     父代个体V2(A，B，D，G，K，N，P)
     可以看出，两个体潜在的交叉位置是节点B、K和N，即Nc={B，K，N)．当选择节点K作为交叉位置时，产生的子代个体V`1和V`2分别为：
    子代个体V`l(A，B，E，H，K'N，P)
    子代个体V`2(A，B，D，G K N，L，O，P)
    杂交完了得到两个新的个体，但是种群的数量是不能改变的。为此在原来的两个父体和得到的两个后代中要淘汰两个个体。淘汰的方法本文采用的是适者生存原则，即整个个体(路径)消耗时间最长的两个个体将被淘汰。
3.3本章小结
本章首先针对最短路径路由问题，建立了求解SP路由问题的数学网络模型，接着针对最短路径路由问题从遗传算法编码的设计、初始种群的产生、适应度函数的设计、选择操作的设计、交叉和变异等方面介绍了改进后的遗传算法；并说明了改进的遗传算法在求解最短路进路由问题中的实现过程。

jl646360594

有好心人帮我整这个程序吗{:1_1:}:cry