动态最优路径技术的路径诱导方法的论文.docVIP

　　动态最优路径技术的路径诱导方法的论文 关键词：动态最优路径,遗传算法；动态路径诱导；最优路径；神经网络 abstract:e routing algorithms based on pure mathematical models have been confronted eet the requirements for real-time and reliability of ic route guidance method resolved the limitation of traditional dynamic route guidance algorithm by forecasting the e road atrix. this method is based on neural (ga), and it has been proven by lab experiments that it can significantly optimize the performance of 个时间段的网络流量和选路时间对未来时间段的选路时间进行预测。将 qi(τ)， qi (τ-1)max表示这一代所有个体中最大的有效基因片段数，加1是为避免出现适应度值为1的情况；当计算进行到某一遗传代数，以染色体的路阻(路由费用)和定义适应度函数。定义p为某一染色体从o到d所经过的路径的路阻之和，即该染色体的目标函数p=∑d(i,j ),d(i,j )为i和j 之间的费用，则适应度函数为f (k)=1-p(k)/∑p(i )，其中k =1，2，3……m，m为群体规模[4]。 论文动态最优路径技术的路径诱导方法来自免费 (3) 染色体的交叉 在父母染色体a、b中随机地选取一个交叉点q，交叉点q不能为起点和终点，q至少应从第三个节点开始；当max(pa,pb)≥min(za,zb)时，双亲染色体不交叉，以保证有效基因片段和零基因不被交叉，其中z表示染色体中非零基因的个数；当max(pa,pb)≤min(za,zb)时，q应在max(pa,pb)和min(za,zb)之间,以保证父母染色体的有效基因片段不被破坏，并去除交叉所得两个新染色体中重复的节点和冗余节点，在染色体的末端补0[4]。 (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。综合考虑论文所研究的网络规模、遗传算法的求解精度和遗传算法的收敛速度等方面的因素，并通过多次