求解最小Steiner树的蚁群优化算法及其收敛性

最小Steiner树问题是NP难问题,它在通信网络等许多实际问题中有着广泛的应用．蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法．本文以无线传感器网络中的核心问题之一,路由问题为例,给出了求解最小Steiner树的蚁群优化算法的框架．把算法的迭代过程看作是离散时间的马尔科夫过程,证明了在一定的条件下,该算法所产生的解能以任意接近于1的概率收敛到路由问题的最优解．     

求解无线传感器网络路由问题的蚁群最优化算法及其收敛性

首先将无线传感器网络的路由问题转化成求解最小Steiner树问题,然后给出了求解无线传感器网络路由的蚁群优化算法,并对算法的收敛性进行了证明．最后对找到最优解后信息素值的变化进行了分析．即在限制信息素取值的条件下,当迭代次数充分大时,该算法能以任意接近于1的概率找到最优解,并且当最优解找到后,最优树边上的信息素单调增加,而最优解以外边上的信息素在有限步达到最小值．     

基于双尺度方程近似解的适合任何连续信号的近似采样定理

提出了一个对任何连续信号,利用双尺度方程的近似解的近似采样定理.采样函数是一个双尺度方程的近似解,是一个逐段线性函数,有明确的计算公式,且精度可以控制.采样函数由双尺度方程的系数唯一决定,可以通过选择双尺度方程的系数而使采样函数具有良好的性质.     

带方向信息的薄板样条插值函数及其应用北大核心CSCD

薄板样条(TPS)函数是一个很好的形变分析工具,常用于图像配准,传统的薄板样条函数只是利用特征点的坐标信息,而现实中很多特征点都带有方向信息,比如指纹细节点和sift特征点.为了在薄板样条函数中利用方向信息,本文在传统薄板样条目标函数基础上增加了方向平行惩罚项及方向一致性惩罚项,根据变分法的结论,目标函数的求解转换为求解一个微分方程,用格林函数法求解这个微分方程,从而得到带方向信息的薄板样条函数新形式.本文得到的薄板样条函数适合于任意维度的点集,在指纹图像配准和人造点集插值上的实验表明,和传统薄板样条函数相比,本文提出的薄板样条函数对于带方向信息的图像配准和点集插值更加准确.     

几何随机图大连通分支覆盖面积及其在传感器网络中的应用

随机网络中的大连通分支能体现一个网络的连通情况,是几何随机图研究的-个热点,具有重要的理论意义和应用价值.本文利用渗流理论,研究了几何随机图大连通分支覆盖面积所具有的性质,并将理论结果应用到大型无线传感器网络中,研究了无线传感器网络覆盖的性质.研究结果表明,对于节点服从泊松分布的大型无线传感器网络,其大连通分支覆盖区域大小与总区域大小的比值趋于-个常数,且并估计出了2维空间中没有被大连通分支所覆盖的连通区域(本文称为空洞)的大小.这些结果为衡量无线传感器网络性能提供了理论基础,对实际布网和网络优化等具有一定的指导意义.     

二次规划的内椭球算法

对于标准型的凸二次规划问题本文给出了一个新算法，算法的一每步迭代，利用内椭球的思想来近似求解一个线性质规划子问题而得到迭代方向，再适当选取步长而使之成为多项式算法，其迭代步数为Ｏ（ｎＬ＾２），每一步迭代所需计算量为Ｏ（ｎ＾３）。其中ｎ为变量个数，Ｌ为问题的输入长度。     

AN EXTENSION OF PREDICTOR-CORRECTOR ALGORITHM TO A CLASS OF CONVEX SEPARABLE PROGRAM

1.IntroductionIn[1]Mizuno,ToddandYepresentedapredictor-correctoralgorithmforlinearpramgrammingwhichpossessesaquadraticconvergencerateofthedualgaptozero.GuoandWul6]gaveamodificationofthisalgorithmforsolvingconvexquadraticprogramwithupperbounds.Itisshownthatthemodifiedmethodnotonlypreservesalltheoriginalmerits,butalsoreducesthedualgapbyaconstantfactorineachcorrectorstep,incontrasttotheMizuno,TOddandYe'soriginalpredictor--correctormethodwherethedualgapremainsunchanged.Thealgorithmdiscussedint…     

真实利率波动对长期资产配置的影响(英)

对于单期的投资者而言,无违约风险的固定收益证券被视为无风险资产.这是因为固定收益证券的收益率在投资的初期就能确定.然而在考虑长期的投资时,投资者可以调整资产配置,固定收益证券也将面临再投资的利率波动风险,因此不能再被视为无风险资产.本文在一类特殊的``习惯形成"效用函数的框架下讨论长期资产配置.在一系列为简化问题而作的假设之下,本文推导出了真实利率波动对风险资产配置权重的影响,并且为计算实际长期资产配置的最优比例提供了理论依据和算法.     

新的梯度算法求解单位球笛卡尔积约束优化问题

本文主要研究了单位球笛卡尔积作为约束的优化问题,给出了此类问题的最优性条件.同时将求解此问题的一些经典的梯度算法推广到了更加一般的形式,并证明了新算法的收敛性.随机二次规划问题和求解图像变分去噪模型的数值结果表明新算法并不弱于一些经典的算法,特别是在精度要求较高的情形下.     

时变挥发率条件下求解Steiner树蚁群优化算法的收敛性

蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法.在蚁群优化算法中,信息素的更新规则直接影响着算法性能,固定挥发率条件下,虽然也能得到求解Steinei树蚁群优化算法的收敛性结果,但算法的探优能力差,易于陷入局部最优.本文在设计求解最小Steiner树蚁群优化算法时,采用了动态更新信息索挥发率的方法,并给出了时变挥发率条件下算法的收敛性证明.具体的,在时变挥发率条件下,当迭代次数充分大时,该算法能以概率1找到最优解.另外,在动态更新信息素下界的条件下,也能得到类似的收敛性结果.