(4) 染色体的变异
将无效基因片段的第一位进行变异，变异后的染色体如果比原染色体的有效基因片段长，即P值增加，则替换母染色体，否则不予替换；当无效基因片段的第一位为D，且该染色体是不合理的，则在D的前一个位置插入一个节点，插入后要保证所得染色体仍是合法的，即符合编码规则，且不能改变染色体的长度。染色体的选择：首先将本代染色体经轮盘赌选择、交叉、变异后得到下一代染色体。由于在前几代的遗传计算中，大量的染色体都是不合理的，因此，将本代中合理的染色体代替下一代中基因片段小的不合理的染色体；如果本代中没有合理的染色体，则不进行替换。当遗传计算进行到一定代数时，染色体大部分是合理的，这时将本代路阻(选路费用)和最小的染色体与下一代路阻(算路费用)和最大的染色体进行比较，如果本代最优的染色体比下一代最差染色体的路阻小，则进行替换，反之则不替换；如果本代群体中路阻和最小的个体不是合理的路径，也不进行替换操作。
(5) 染色群体的更新方式
群体的设计需要平衡群体多样性维护和快速收敛，从数学的角度讲，允许父辈中的优良个体进入下一轮的竞争确保了最优解的迭代稳定性，而将后代中劣化的个体提前淘汰出局加速了寻优过程的实现。采取让子代中的优秀个体和父辈中的优良个体同时进入下一代的群体更新方式，即父辈个体经过交叉、变异操作后得到临时子个体，将父辈个体和临时子代个体进行比较，选择适应度高的个体作为子代个体进入下一代的竞争。这种群体更新方式能保证每一次交叉、变异操作都将产生两个更好的子个体，从而保证该算法的收敛性。
3 仿真研究
研究结果用如图3所示的网络连接图测试。
以路由时间最短作为最优目标，通过神经网络对路由网各路径任意时刻的平均路由时间进行预测，动态地得出该路网任意时刻的权重。取t -1、t -2、t -3、t -4四个时间段路网的数据流量和平均路由时间作为神经网络的输入，因此神经网络输入层取8个节点；输出层取1个节点，输出为t时刻该路由网各路径的行程时间。根据实验，隐层取3个节点。由神经网络预测所得t时刻路网各路段的平均行程时间构成路阻矩阵，路阻矩阵的大小是16×16，两节点间的路段不连通时，用一个大于所有路阻和的数1 000表示。
求得t 时刻路网的路阻矩阵后，采用遗传算法进行最优路径的选择，遗传算法参数的确定如下：由于网络节点数为16，所以染色体的编码长度为16。综合考虑论文所研究的网络规模、遗传算法的求解精度和遗传算法的收敛速度等方面的因素，并通过多次仿真实验的验证可知，种群规模选为160时，最优路径选择算法的性能最好。经仿真实验验证，遗传终止代数可取为8[5]。
用Matlab对上述试验模型进行仿真试验，仿真结果表明，对于86个OD对寻优，遗传算法计算得到77条最优路径，83条有效路径，求解准确率为0.895，有效率为0.989，平均寻优时间为8 ms~15 ms，满足了路径诱导的准确性和实时性。
对随机产生的OD对(1，16)分别求解t1、t2、t3时刻的最优路径，可得R1为t1时刻最优路径1-5-6-11-12-16，R2为t2时刻最优路径1-2-6-11-15-16，R3为t3时刻最短路径1-2-3-4-8-12-16。具体计算结果见表1所示。
从表1可以看出，当网络流量在不断变化时，在不同时刻对应各条路径的费用也在不断的变化，路径最短的所需的费用并不是最少的。
4 结束语
实验室模拟条件下不存在路由拥塞导致的网络延迟以及真实环境中存在各种网络问题。从表3的试验结果来看，基于神经网络的遗传算法的动态路径诱导算法在动态路由中可以得到很好的预测流量，并且最优路径的求解率达到89.5％、有效率达到98.9％，解决了传统的诱导算法带来的收敛慢的问题，满足路由的实时性。但是对于大规模的复杂的Internet路由，需要做进一步的研究来保证选路问题的及时性和收敛性，从而使选路在各方面得到最优化保证。
5 参考文献
[1]景玲,黄席樾,潘娅. 基于遗传算法的动态路径诱导[J]. 重庆大学学报, 2002, 25(4): 68-71.
[2]徐仙伟,叶小岭.遗传算法优化BP网络初始权重用于入侵检测[J].计算机应用研究,2005,22(3): 127-128, 132.
[3]吴成东,杨丽英,许可.神经网络和遗传算法在动态路径诱导中的应用[J].计算机应用研究,2006,25(4): 23-28.
[4]FUL.An adaptive routing algorithm for in-vehicle route guidance systems with real-time information [J].Transportation Research: Part B, 2001, 35( 8) : 749-765.
[5]Wahlej,Annen o, Schuster c, et al. A dynamic route guidance system based on real traffic data [J]. European Journal of Operational Research, 2001, 13(1): 302-308.
作者简介：
朱能方，本科毕业于安徽大学，硕士毕业于电子科技大学。现工作于中兴通讯股份有限公司，主要研究方向为网络信息安全。黄迪明，电子科技大学计算机系教授。主要研究方向为网络信息技术、信息安全、软件工程等，已发表学术论文20余篇。
