一种基于路径层面的遗传算法

针对当前数据中心网络在路径选择过程中出现的资源分配不合理和资源利用率低的问题,提出一种基于路径层面的遗传算法(Path Level-based Genetic Algorithm,PLGA),以提高网络传输性能。利用软件定义网络(Software Define Network,SDN)在产生遗传算法的初始种群时,引用Yen算法产生第一代种群,对初始种群进行初步优化,选择出前K条最短路径。使用路径可用带宽质量、链路均衡度以及路由跳数等3个指标设计新的适应度函数,再对初始种群进行选择、交叉和变异操作,最终寻找最优路径。实验结果表明,PLGA算法在平均带宽利用率、吞吐量和时延抖动方面的性能优于等价多路径(Equal-Cost Multi-Path,ECMP)、基于多路径传输的动态负载均衡路由(Multipath Transmission-based Dynamic Load-balanced Routing,MTDLR)和全局负载均衡(Global Load Balancing,GLB)等算法。

交通分配中的梯度投影算法及其改进模型

最近的研究表明基于路径的交通分配算法具有很强的生命力和广阔的应用前景。在这些算法中,梯度投影算法(GP)由于其极高的计算效率引起了研究者极大的兴趣。但是研究同样表明GP算法在求高精度分配解时遇到了收敛问题。文章首先介绍了GP算法的理论基础及算法步骤,然后分析了算法产生收敛问题的关键原因,针对其高精度解不能很好收敛的问题,采用二分法改进了其中关键的步长确定策略,提出了改进的GP算法(IGP,Improved GP),并通过计算实例比较了GP和IGP的表现,分析了IGP的优势。并用计算实例证明IGP在求解高精度分配解和整体收敛速度两方面都优于GP。

基于路径的算法求解考虑排放的交通分配模型

分析了非可加路径费用的交通分配问题,考虑了排放对传统交通分配模型的影响,在Venigalla等研究基础上,给出了在不同发动机启动模式下考虑排放的交通分配模型,并采用基于路径的梯度投影算法(GP)和非集计的单纯分解算法(DSD)进行模型求解。数值验证结果表明:GP所占的CPU时间大致为DSD的1/25,所使用的路径为DSD的1/5,这两种基于路径的算法得出数值最优解的收敛速度比基于Frank-Wolfe(FW)的算法要快,适用于求解大规模非可加路径费用的交通分配问题。

基于终点的路径交通量求解方法

为求解用户均衡交通分配问题,提出了一种可以避免穷举网络中的所有路径的路径交通量求解方法。该方法是基于路段算法的扩展,利用改进的F rankW o lfe算法求解出满足用户均衡规则的基于终点的路段交通量,并通过最短路算法确定出此时交通网络中各个OD(orig in destination)对间的最短路集合,再运用所确定出的路段交通量及最短路集构造出一组满足用户均衡规则的路径交通量。通过算例说明了该方法的有效性,并通过比较分析说明了该方法所需计算内存比其他算法要少,且计算速度要快。