Frank-Wolfe算法求解交通分配问题：比较不同流量更新策略和线搜索技术

Frank-Wolfe(FW)算法是一类广泛应用于求解交通分配问题的算法.它具有容易编程实现,所需内存少的特点.但是该算法收敛速度较慢,不能得到路径信息.为了提高算法的效率,本文研究三种流量更新策略(all-at-once,one-origin-at-a-time,one-OD-at-a-time)以及不同的步长搜索策略下的FW算法,其中步长搜索策略包括精确线性搜索方法(包括二分法、黄金分割法、成功失败法)和不精确的线性搜索方法(包括基于Wolfe-Powell收敛准则的搜索方法和Gao等提出的非单调线性搜索方法).最后,本文将上述策略应用于四种不同规模的交通网络中,并给出较适合求解的组合.

用于求解路径交通流量的改进Frank-Wolfe算法

Frank-Wolfe算法是用于求解交通流量分配问题的经典算法,但该算法是基于路段(Link-Based)的交通流量分配算法,无法用于求解路径交通流量。针对此问题,提出一种用于求解路径交通量的改进Frank-Wolfe算法。通过在Frank-Wolfe原算法中增加求解路径交通流量的计算步骤,根据原算法中"全有全无"加载方法获得的步长,更新源-目的(OD)间所有已配流的路径的交通流量,在原算法迭代计算路段流量的同时,同步计算路径流量。通过算例表明,改进算法是一个有效的算法,在Frank-Wolfe原算法的基础上增加少量的时间和空间成本即可求解路径交通流量,避免穷举交通网络中的所有路径,可以很好地用于用户均衡交通流量分配中。

Frank-Wolfe算法在输气管道内腐蚀预测中的应用

组合预测是对用多种预测方法进行预测的结果加权。建立了基于最小二乘法原理的组合预测模型,提出了求解此组合预测模型的一种新的算法,即Frank-Wolfe算法,并将其应用于四川某输气管道内腐蚀速度预测的研究,应用结果表明,Frank-Wolfe方法较适用于求解组合预测问题的权重。

一个改进的Frank—Wolfe算法及其收敛性质

对于线性约束非线性规划其中,而A是-m×n矩阵, Frank-Wolfe曾对f(x)是二次函数的情形给出了(P)的一个算法,该算法结构简单,易于实现,是求解非线性网络问题的一个行之有效的方法。其后,许多学者对该方法做了大量的改进工作。但这些改进的方法本质上与Frank-Wolfe方法没有太大差别,其收敛定理与Frank-Wolfe方法一样,在算法产生的点列{x^n}有极限点的条件下,说明该极限点是(P)的-Kuhn-Tuoker点,而对的情形却没有任何结果。

一类二层决策问题的Frank－Wolfe算法

提出了一类二层决策模型，在某些假设下研究了其解的若干性质，并给出基于Ｆｒａｎｋ－Ｗｏｌｆｅ算法．最后给出的算例表明，提出的算法是可行的且具有较好的可操作性．

对Frank-Wolfe算法在图像恢复中最小二乘问题的研究

在图像恢复问题中经常需要求解一个带箱约束的最小二乘问题。传统上,该问题通常先采用最速下降法求解一个无约束的最小二乘问题,然后将解投影到箱式约束中。这样一种途径得到的解是次优的。Frank-Wolfe算法是一个经典的求解带约束问题的迭代算法,其收敛速度为O(1/k)。本文采用该算法来解决图像恢复中的带箱式约束的最小二乘问题。数值结果表明,采用Frank-Wolfe算法得到的恢复图像要优于最速下降法。

自适应Frank-Wolfe算法及其在矩阵填充上的应用

提出一种矩阵填充问题的自适应Frank-Wolfe算法。首先,采用Nesterov加速策略加速Frank-Wolfe算法,然后,在迭代过程中对矩阵降秩,提高标准Frank-Wolfe算法收敛速率的同时,降低了迭代成本;最后,通过数值实验验证所提算法的有效性。

基于Frank-Wolfe算法的交通分配研究

为了提升交通分配算法的速度以适应现实业务需求。本文提出了一种改进Frank-Wolfe算法,该算法模型相较于传统模型,优化了道路路阻计算方法,使模型路径规划接近现实情况,并预设出行路径集,避免穷举网络所有路径。此外,本文还解决了路段途径车流OD无法溯源的问题。在测试实验中,本文以深圳市的交通数据为实验数据,用本文的方法进行OD溯源和交通分配,本文中的算法在运行速度上明显优于传统算法,更有利于部署在城市交通管理实际应用上。

一类非线性二层规划的Frank-Wolfe方法

利用下层问题的K-T最优性条件将下层为线性规划的一类非线性二层规划转化为相应的单层规划,同时取互补条件为罚项,得到该类问题的单层罚问题;然后利用Frank-Wolfe方法对单层罚问题进行求解.数值实验表明该方法是可行的.

利用Frank—Wolfe方法求解一般离散无记忆信道信道容量

信道容量是指通过信道可以传输的最大信息量，是反映信道的最重要参数。将求解一般离散无记忆信道的信道容量问题转化为一个线性约束优化问题，并利用Frank-Wolfe方法对其进行了求解，并给出了具体算例。算例分析表明，利用Frank-Wolfe方法求解一般离散无记忆信道的信道容量问题比常用求解信道容量的迭代法更为简便。

采用WOLFE搜索的BFGS-SQP算法

采用WOLFE线性搜索原则来取代该BFGS -SQP算法的Armijo原则 ,经过类似的分析 ,同样得到了BFGS -SQP算法的全局收敛性及超线性收敛性 .

一类带Wolfe条件的修改的Broyden算法

本文提出一类带Wolfe条件的修改的Broyden算法,证明了在一定条件下,算法具有整体收敛性、超线性收敛率和二阶收敛性,及Broyden算法的一些收敛性质。1.

采用WOLFE搜索的BFGS—SQP算法

采用 Ｗｏｌｆｅ线性搜索原则来替代ＢＦＧＳ—ＳＱＰ算法的Ａｒｍｉｊｏ原则，经过类似的分 析，得到了ＢＦＧＳ—ＳＱＰ算法的全局收敛性及超线性收敛性．

采用WOLFE搜索的BFGSSQP算法

X .Chen给出了一个用于解决LC1 线性约束优化问题的BFGS SQP算法 ,这个算法是用Armijo线性搜索原则来求步长的 .采用Wolfe线性搜索原则来替代该BFGS SQP算法的Armijo原则 ,经过类似的分析 ,同样得到了BFGS SQP算法的全局收敛性及超线性收剑性 .

基于Wolf的数字化变电站通信网异常流量检测系统

数字化变电站通信网异常流量检测过程中易陷入局部最优,导致检测结果不精准。为了解决这个问题,提出了基于Wolf的数字化变电站通信网异常流量检测系统。构建系统总体结构,分析通信网流量异常频域特征。通过采集异常流量模块解析目的物理地址,检查组件为系统提供信息交互引擎。使用Wolf算法将混沌序列映射到数字化变电站通信网异常流量多维相空间,设置控制收敛因子,避免检测结果陷入局部最优。计算异常流量特征值的熵,判断流量异常类型。实验结果表明,该系统一次设备异常流量检测结果与实际数据一致,二次设备异常流量检测结果与实际数据存在最大为2 Mb/s的误差,说明使用所设计系统检测结果精准。

一种求解线性二层规划的修正Frank-Wolf方法

利用迭代点校正方法,将非线性规划中的F rank-W o lf方法应用于线性二层规划问题,从而提出了一种求解线性二层规划的简单算法,同时给出了算法的收敛性.数值结果表明,给出的算法是可行有效的.

一类二层决策问题的性质分析和基于Frank-Walfe方法的神经网络算法

提出一类二层决策问题的模型．在某些凸性假设下，研究它的一些性质，提出了一种基于Ｆｒａｎｋ－Ｗａｌｆｅ和人工神经网络方法的算法．并以算例说明该算法可行性．

基于灰狼-鸟群算法的特征权重优化方法

针对特征权重难以准确量化的问题,提出一种基于灰狼优化(grey wolf optimizer, GWO)算法和鸟群算法(bird swarm algorithm, BSA)的混合算法,用于特征权重的寻优。首先,将Chebyshev映射、反向学习与精英策略用于混合算法的初始种群生成;其次,将改进后的GWO算法位置更新策略融入BSA的觅食行为中,得到一种新的局部搜索策略;然后,将BSA的警觉行为与飞行行为用作混合算法的全局搜索平衡策略,从而得到一种收敛的灰狼-鸟群算法(grey wolf and bird swarm algorithm, GWBSA),通过GWBSA的迭代寻优可获得各特征的权重值。利用标准测试函数和标准分类数据集进行了对比实验,与遗传算法、蚁狮算法等方法相比,GWBSA具有较快的收敛速度且不易陷入局部最优,可以提高模式分类问题的求解质量。

一个新的交通网络平衡设计模型及其算法

针对城市道路网络改造问题中,待改造道路和拟添加道路均具有等级选择的特点,提出了一种更加符合实际的新的网络平衡设计二层规划模型,设计了粒子群求解算法,并给出了一个简单的算例,实际算例表明该算法具有计算简单,收敛速度快的特点.

基于均衡原理的定位-运输路线安排问题模型及求解算法

提出了物流配送均衡原理,构造了基于物流配送均衡原理的定位-运输路线安排问题的双层规划模型。运用Frank-Wolfe算法求解物流配送均衡模型,采用改进的禁忌算法优化选址问题和车辆路径问题,并通过双层规划模型将选址和车辆路径问题进行有机结合。应用提出的模型和算法求解了多个算例,并选取了其中一个算例试验结果进行分析。分析表明,基于均衡原理的双层规划模型和算法能够有效的求得定位-运输问题的优化解,是解决定位-运输问题的有效方法。