A fast algorithm for computing minimum routing cost spanning trees

Communication networks have been developed based on two networking approaches: bridging and routing. The convergence to an all-Ethernet paradigm in Personal and Local Area Networks and the increasing heterogeneity found in these networks emphasizes the current and future applicability of bridging. When bridging is used, a single active spanning tree needs to be defined. A Minimum Routing Cost Tree is known to be the optimal spanning tree if the probability of communication between any pair of network nodes is the same. Given that its computation is a NP-hard problem, approximation algorithms have been proposed.We propose a new approximation Minimum Routing Cost Tree algorithm. Our algorithm has time complexity lower than the fastest known approximation algorithm and provides a spanning tree with the same routing cost in practice. In addition, it represents a better solution than the current spanning tree algorithm used in bridged networks.     

Stochastic adaptive control using a modified least squares algorithm

Recent papers on stochastic adaptive control have established global convergence for algorithms using a stochastic approximation iteration. However, to date, global convergence has not been established for algorithms incorporating a least squares iteration. This paper establishes global convergence for a slightly modified least squares stochastic adaptive control algorithm. It is shown that, with probability one, the algorithm will ensure that the system inputs and outputs are sample mean square bounded and the mean square output tracking error achieves its global minimum possible value for linear feedback control.     

Blending randomness in closed queueing network models

Random environments are stochastic models used to describe events occurring in the environment a system operates in. The goal is to describe events that affect performance and reliability such as breakdowns, repairs, or temporary degradations of resource capacities due to exogenous factors. Despite having been studied for decades, models that include both random environments and queueing networks remain difficult to analyse. To cope with this problem, we introduce the blending algorithm, a novel approximation for closed queueing network models in random environments. The algorithm seeks to obtain the stationary solution of the model by iteratively evaluating the dynamics of the system in between state changes of the environment. To make the approach scalable, the computation relies on a fluid approximation of the queueing network model. A validation study on 1800 models shows that blending can save a significant amount of time compared to simulation, with an average accuracy that grows with the number of servers in each station. We also give an interpretation of this technique in terms of Laplace transforms and use this approach to determine convergence properties.     

Machine allocation algorithms for job shop manufacturing

In this paper we present algorithms for the solution of two server (machine) allocation problems that occur in manufacturing networks. The manufacturing network is modelled as an open network of queues with general interarrival time and service time distributions. The queueing network is analyzed by using the parametric decomposition method: a two-moment approximation scheme. The server allocation problems are solved by means of a marginal analysis scheme. Numerical results on two manufacturing networks are presented.     

An approximate MVA algorithm for exponential, class-dependent multiple servers

Mean value analysis (MVA) is an efficient algorithm for determining the mean sojourn time, the mean queue length, and the throughput in a closed multiclass queueing network. It provides exact results for the class of product-form networks. Often different classes have different service requirements in FCFS queues, but such networks are not of product form. There are several possibilities to compute performance measure for such nodes and networks. In this paper we present an approximation formula for multiple-server FCFS queues with class-dependent service times as a Norton flow equivalent product node, where the departure rate of any class depends on the number of customers of all classes in the queue. We will use this approximation in the sojourn time formula of some exact and approximate MVA algorithms.     

遗传-蚁群算法在智能交通中的应用

随着私家车的增多,城市交通问题越来越严重。为了解决这个问题,人们将计算机技术运用于城市智能交通系统(intelligent transportation systems,ITS)中。行车路径规划是城市智能交通体系中重要的一个环节。目前,有不少路径优化算法被提出用于解决行车路径规划问题,但各有不足。因此,提出了一种混合遗传蚁群算法(GACHA)。从基本蚁群算法入手,结合遗传和蚁群算法的各自优点,将两种算法的寻优过程循环多次结合。在蚁群算法的一次迭代循环后,将蚁群算法产生的较优解代替遗传算法中的部分个体,用以加快遗传算法的迭代速度。同时,将遗传算法算出的解设为较优路径来更新蚁群算法中的信息素分配,实现参数调整。多次相互指导能有效解决蚁群算法前期效率低和遗传算法后期冗余迭代的问题。实验结果表明,遗传-蚁群混合算法可以有效地避免陷入局部最优解,提高计算效率。它具有良好的优化和收敛性,能够准确地找到满足路网综合要求的最优路径。     

A generalisation of Norton's theorem for multiclass queueing networks

Consider an arbitrary subset σ of service centres in a locally balanced multiclass queueing network for which a parametric analysis is to be undertaken. It is shown that the complete network only has to be solved once using the convolution algorithm, after which statistical measures for σ can be calculated repeatedly without re-evaluating the rest of the network. It has also been proved that the concept of replacing a subnetwork in a closed multiclass queueng network with a single composite service centre with a state dependent service rate (also called Norton's Theorem for queuing networks) is a very special case of the more general result mentioned above. An example is given in which the theoretical results are applied when σ is a subnetwork of a closed multiclass queueing network satisfying local balance.     

Online adaptive algorithm for optimal control with integral reinforcement learning

In this paper, we introduce an online algorithm that uses integral reinforcement knowledge for learning the continuous‐time optimal control solution for nonlinear systems with infinite horizon costs and partial knowledge of the system dynamics. This algorithm is a data‐based approach to the solution of the Hamilton–Jacobi–Bellman equation, and it does not require explicit knowledge on the system's drift dynamics. A novel adaptive control algorithm is given that is based on policy iteration and implemented using an actor/critic structure having two adaptive approximator structures. Both actor and critic approximation networks are adapted simultaneously. A persistence of excitation condition is required to guarantee convergence of the critic to the actual optimal value function. Novel adaptive control tuning algorithms are given for both critic and actor networks, with extra terms in the actor tuning law being required to guarantee closed loop dynamical stability. The approximate convergence to the optimal controller is proven, and stability of the system is also guaranteed. Simulation examples support the theoretical result. Copyright © 2013 John Wiley & Sons, Ltd.     

On Adaptive Learning Rate That Guarantees Convergence in Feedforward Networks

This paper investigates new learning algorithms (LF I and LF II) based on Lyapunov function for the training of feedforward neural networks. It is observed that such algorithms have interesting parallel with the popular backpropagation (BP) algorithm where the fixed learning rate is replaced by an adaptive learning rate computed using convergence theorem based on Lyapunov stability theory. LF II, a modified version of LF I, has been introduced with an aim to avoid local minima. This modification also helps in improving the convergence speed in some cases. Conditions for achieving global minimum for these kind of algorithms have been studied in detail. The performances of the proposed algorithms are compared with BP algorithm and extended Kalman filtering (EKF) on three bench-mark function approximation problems: XOR, 3-bit parity, and 8-3 encoder. The comparisons are made in terms of number of learning iterations and computational time required for convergence. It is found that the proposed algorithms (LF I and II) are much faster in convergence than other two algorithms to attain same accuracy. Finally, the comparison is made on a complex two-dimensional (2-D) Gabor function and effect of adaptive learning rate for faster convergence is verified. In a nutshell, the investigations made in this paper help us better understand the learning procedure of feedforward neural networks in terms of adaptive learning rate, convergence speed, and local minima.     

批量减数更新方差缩减梯度下降算法BSUG

机器学习问题通常会转换成求解一个目标函数问题。继随机梯度下降（Stochastic Gradient Descent,SGD）之后,随机方差缩减梯度法（Stochastic Variance Reduction Gradient,SVRG）成为如今优化目标函数参数的主流算法,它由于不受方差影响达到线性收敛而被人们广泛研究。它的提出导致陆续出现如SAGA（Stochastic Average Gradient Average）和SCSG（Stochastically Controlled Stochastic Gradient）等新型方差缩减算法,它们有着过量消耗内存、迭代缓慢等问题。为了实现小成本存储以及快速迭代的目的,设计了一种以SVRG为基础的新型变异方差缩减算法BSUG（Batch Subtraction Update Gradient）。改进在于：使用小批量样本代替全部样本进行平均梯度计算,同时对平均梯度进行减数更新。每轮迭代中,随机抽取一批小样本进行平均梯度计算,同时在内部迭代时通过对过去模型梯度的舍去来达到更新平均梯度的目的。通过合适地降低批大小[B],可以减少内存存储以及迭代次数。理论分析算法的收敛性,并基于Python进行算法实现,通过与Mini-Batch SGD、AdaGrad、RMSProp、SVRG和SCSG等算法进行比较证明了BSUG算法的有效性,并且通过对超参数进行探究证明了算法的稳定性。     

Comparison of Stochastic Global Optimization Methods to Estimate Neural Network Weights

Training a neural network is a difficult optimization problem because of numerous local minima. Many global search algorithms have been used to train neural networks. However, local search algorithms are more efficient with computational resources, and therefore numerous random restarts with a local algorithm may be more effective than a global algorithm. This study uses Monte-Carlo simulations to determine the efficiency of a local search algorithm relative to nine stochastic global algorithms when using a neural network on function approximation problems. The computational requirements of the global algorithms are several times higher than the local algorithm and there is little gain in using the global algorithms to train neural networks. Since the global algorithms only marginally outperform the local algorithm in obtaining a lower local minimum and they require more computational resources, the results in this study indicate that with respect to the specific algorithms and function approximation problems studied, there is little evidence to show that a global algorithm should be used over a more traditional local optimization routine for training neural networks. Further, neural networks should not be estimated from a single set of starting values whether a global or local optimization method is used.     

Two-loop reinforcement learning algorithm for finite-horizon optimal control of continuous-time affine nonlinear systems

This article proposes three novel time-varying policy iteration algorithms for finite-horizon optimal control problem of continuous-time affine nonlinear systems. We first propose a model-based time-varying policy iteration algorithm. The method considers time-varying solutions to the Hamiltonian–Jacobi–Bellman equation for finite-horizon optimal control. Based on this algorithm, value function approximation is applied to the Bellman equation by establishing neural networks with time-varying weights. A novel update law for time-varying weights is put forward based on the idea of iterative learning control, which obtains optimal solutions more efficiently compared to previous works. Considering that system models may be unknown in real applications, we propose a partially model-free time-varying policy iteration algorithm that applies integral reinforcement learning to acquiring the time-varying value function. Moreover, analysis of convergence, stability, and optimality is provided for every algorithm. Finally, simulations for different cases are given to verify the convenience and effectiveness of the proposed algorithms.     

基于神经网络的特征结构并行提取算法研究

为并行实时地提取数据协方差矩阵的信号特征结构,从特征结构并行提取的约束优化问题表示入手,利用梯度方法和迭代法构建了可实时并行提取信号特征向量矩阵的直接神经网络求解法和基于能量函数的神经网络求解算法,并形成了相关迭代学习算法.理论分析表明当数据样本足够大时,算法的迭代结果就是数据协方差矩阵信号特征结构的一个良好估计,同时计算机仿真亦验证了算法的有效性.另外,仿真试验亦表明可以通过调节加权矩阵D的对角元来控制算法的收敛速度.     

神经网络BP学习算法动力学分析

研究神经网络BP学习算法与微分动力系统的关系.指出BP学习算法的迭代式与相 应的微分动力系统数值解Euler方法在一定条件下等价,且二者在解的渐近性方面是一致的. 给出了神经网络BP学习算法与相应的微分动力系统解的存在性、唯一性定理和微分动力系统 的零解稳定性定理.从理论上证明了神经网络的学习在一定条件下与微分动力系统的数值方法 所得的数值解在渐近意义下是等价的,从而借助于微分动力系统的数值方法可以解决神经网络 的学习问题.最后给出了用改进Euler方法训练BP网的例子.     

LEACH-C协议中模拟退火算法的改进

无线传感器网络的LEACH-C协议在实现过程中,使用了模拟退火算法进行簇头节点集合的选择。虽然该算法选举的簇头能够使整个网络的传输代价最小,但是算法执行的效率比较低。因此,在原来算法的基础上,提出了一种改进的算法。理论上表明该算法在每次迭代后得到的新解必然比原来的解更优;实验结果表明,该方法能够更快地得到一个局部最优解,改进后的算法在整体性能上比原算法有很大提高,尤其是在网络中的节点数不断增加的情况下,从而缩短了选举簇头节点的时间消耗。     

A feasible framework of traffic control on an ATM wide-area network

In this paper, we propose a framework of traffic control to accommodate multimedia connections on an ATM wide-area network. At the lower layer, an efficient bandwidth allocation method and a constant time cell scheduling algorithm are provided in each network node. These mechanisms have the capability of multiplexing traffics and satisfying diverse delay and loss performance requirements. At the higher layer, a three-phase connection establishment procedure is applied. It transforms the end-to-end performance requirement of a connection request into local requirements for each intermediate node of a routing path. If the requirements for each intermediate node can be satisfied, the connection is accepted; otherwise, another routing path will be examined. Without resort to any complicated rate control inside the network, in our system, time distances between successive cells while they are passing through the network are maintained by imposing an upper bound on the end-to-end queueing delay of each cell. Simulation results show that the connection establishment overhead of our system is almost independent of the traffic load of the network. Its value is very small so that the proposed framework is feasible in the future ATM networks. Besides, optimally transforming end-to-end performance requirement into those for each intermediate node to maximize the saturation load of the network has been proved to be an NP-Hard problem. Two heuristic algorithms are proposed. Experiments are performed to evaluate these algorithms.     

Experiments with improved approximate mean value analysis algorithms

Approximate mean value analysis (MVA) is a popular technique for analyzing queueing networks because of the efficiency and accuracy that it affords. In this paper, we present a new software package, called the improved approximate mean value analysis library (IAMVAL), which can be easily integrated into existing commercial and research queueing network analysis packages. The IAMVAL packages include two new approximate MVA algorithms, the queue line (QL) algorithm and the fraction line (FL) algorithm, for analyzing multiple class separable queueing networks. The QL algorithm is always more accurate than, and yet has approximately the same computational efficiency as, the Bard–Schweitzer proportional estimation (PE) algorithm, which is currently the most widely used approximate MVA algorithm. The FL algorithm has the same computational cost and, in noncongested separable queueing networks where queue lengths are quite small, yields more accurate solutions than both the QL and PE algorithms.     

一个新的分布式最小连通支配集近似算法

在计算机网络中广泛使用广播来解决一些网络问题,设计有效的广播算法是一项重要的课题。文中提出一种分布地计算网络最小连通支配集的近似算法并给出了它的正确性证明。它只需要网络节点具有局部的网络状态信息,可伸缩性强。通过此算法可以在网络中自动形成一个虚拟骨干网,从而可为网络中的广播和路由操作提供一个有效的通信基础。模拟结果表明,文中提出的算法求得的连通支配集小,能较好地应用于一般网络以及移动自组网络中。     

Local convergence of the fuzzy c-Means algorithms

Much understanding has recently been gained concerning global convergence properties of the fuzzy c-Means (FCM) family of clustering algorithms. These global convergence properties, which hold for all iteration sequences, guarantee that every FCM iteration sequence converges, at least along a subsequence, to a stationary point of an FCM objective function. In this paper we prove a local convergence property, that is, a property pertaining to iteration sequences started near a solution. Specifically, a simple result is proved which shows that whenever an FCM algorithm is started sufficiently near a minimizer of the corresponding objective function, then the iteration sequence must converge to that particular minimizer. The result guarantees that once captured by the local neighborhood of a minimizer, the succeeding iterate sequence will not escape—thus, infinite oscillation of such a sequence cannot occur. The rate of convergence of the sequence to such a point is also discussed.     

基于分层和强化学习的改进路径搜索算法

复杂网络下的路径搜索问题是网络寻优中的一个难点。现有算法主要存在以下问题：一是往往只能侧重于求解效率和求解精度中的一点;二是对动态变化的复杂网络适应性不强,求解效果不佳。因此,本文提出一种基于双分层和优化Q-Learning的改进路径搜索算法。对于求解时间随规模增加而急剧增长的问题,提出k-core和模块度结合的双分层划分网络的策略,以合理有效地减小网络规模。在子网络求解中,引入强化学习机制对网络进行动态感知,针对算法收敛较慢问题,加入自适应学习因子和记忆因子,优化更新公式,提高收敛速度。最后,在不同幂律指数（2~3）和不同规模的复杂网络下,将所提算法与Dijkstra算法、A*算法和Qrouting算法进行实验对比,结果表明该算法在保证较好求解精度的情况下,能有效地改善求解效率。