一般克隆选择算法的收敛性证明*

克隆选择算法已经广泛应用于计算智能领域,而针对克隆选择算法理论方面的分析和研究工作却很少。为了丰富克隆选择算法的理论基础,采用了与研究遗传算法相似的方法,研究了克隆选择算法的收敛性,推导出克隆选择算法在求解优化问题时,收敛到全局最优解的充分条件。因此,对基于克隆选择算法的各种应用如BCA和CLONALG算法,只要检查这些充分条件是否满足就可以证明算法的收敛性。     

Elman人工神经网络的收敛性分析

应用Lyapunov稳定性理论分析了Elman人工神经网络的收敛性,讨论了基本的Elman人工神经网络收敛的充分条件,以及改进的Elman人工神经网络收敛的充分条件。     

警示传播算法收敛的充分条件

信息传播算法求解可满足问题时有惊人的效果,难解区域变窄.然而,因子图带有环的实例,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.警示传播（warning propagation,简称WP）算法是一种基础的信息传播算法,对WP算法的收敛性研究是其他信息传播算法收敛性研究的重要基础.在WP算法中,将警示信息的取值从{0,1}松弛为[0,1],利用压缩函数的性质,给出了WP算法收敛的一个充分条件.选取了两组不同规模的随机3-SAT实例进行实验模拟,结果表明：当子句与变元的比值α<1.8时,该判定条件有效.     

Development of multivariable PID controller gains in presence of measurement noise

This paper examines the ability of a multivariable PID controller rejecting measurement noise without the use of any external filter. The work first provides a framework for the design of the PID gains comprising of necessary and sufficient conditions for boundedness of trajectories and zero-error convergence in presence of measurement noise. It turns out that such convergence requires time-varying gains. Subsequently, novel recursive algorithms providing optimal and sub-optimal time-varying PID gains are proposed for discrete-time varying linear multiple-input multiple-output (MIMO) systems. The development of the proposed optimal algorithm is based on minimising a stochastic performance index in presence of erroneous initial conditions, white measurement noise, and white process noise. The proposed algorithms are shown to reject measurement noise provided that the system is asymptotically stable and the product of the input–output coupling matrices is full-column rank. In addition, convergence results are presented for discretised continuous-time plants. Simulation results are included to illustrate the performance capabilities of the proposed algorithms.     

Effiziente Schrittweitenfunktionen bei unrestringierten Optimierungsaufgaben

In the present paper we discuss several steplength procedures from a general point of view. We consider their influence on the convergence of algorithms for the numerical treatment of optimization problems without constraints. We define efficient step-size functions and show that well known steplength procedures are efficient. Necessary and sufficient conditions for convergence of descent methods with efficient step-size functions and applications to conjugate gradient methods are given.     

Weighted averaging and stochastic approximation

We explore the relationship between weighted averaging and stochastic approximation algorithms, and study their convergence via a sample-path analysis. We prove that the convergence of a stochastic approximation algorithm is equivalent to the convergence of the weighted average of the associated noise sequence. We also present necessary and sufficient noise conditions for convergence of the average of the output of a stochastic approximation algorithm in the linear case. We show that the averaged stochastic approximation algorithms can tolerate a larger class of noise sequences than the stand-alone stochastic approximation algorithms.This research was supported by the National Science Foundation through Grants ECS-9410313 and ECS-9501652.This research was supported by the National Science Foundation through NYI Grant IRI-9457645.     

On almost sure convergence of adaptive algorithms

We present an extension of the Furstenberg-Kesten theorem on the convergence of random matrices. This extension is applied to the study of almost sure convergence of certain adaptive algorithms. In particular, we establish that the NLMS algorithm is almost surely convergent under extremely weak necessary and sufficient conditions. We also discuss the relationship of sufficient conditions that have appeared in the literature with our results.     

Iterative algorithm for minimal norm least squares solution to general linear matrix equations

This paper is concerned with minimal norm least squares solution to general linear matrix equations including the well-known Lyapunov matrix equation and Sylvester matrix equation as special cases. Two iterative algorithms are proposed to solve this problem. The first method is based on the gradient search principle for solving optimization problem and the second one can be regarded as its dual form. For both algorithms, necessary and sufficient conditions guaranteeing the convergence of the algorithms are presented. The optimal step sizes such that the convergence rates of the algorithms are maximized are established in terms of the singular values of some coefficient matrix. It is believed that the proposed methods can perform important functions in many analysis and design problems in systems theory.     

A deterministic analysis of stochastic approximation withrandomized directions

We study the convergence of two stochastic approximation algorithms with randomized directions: the simultaneous perturbation stochastic approximation algorithm and the random direction Kiefer-Wolfowitz algorithm. We establish deterministic necessary and sufficient conditions on the random directions and noise sequences for both algorithms, and these conditions demonstrate the effect of the “random” directions on the “sample-path” behavior of the algorithms studied. We discuss ideas for further research in the analysis and design of these algorithms     

Distributed formation‐containment control with Euler‐Lagrange systems subject to input saturation and communication delays

This paper is concerned with the problem of formation‐containment on networked systems, with interconnected systems modeled by the Euler‐Lagrange equation with bounded inputs and time‐varying delays on the communication channels. The main results are the design of control algorithms and sufficient conditions to ensure the convergence of the network. The control algorithms are designed as distributed dynamic controllers, in such a way that the number of neighbors of each agent is decoupled from the bound of the control inputs. That is, in the proposed approach the amplitude of the input signal does not directly increase with the number of neighbors of each agent. The proposed sufficient conditions for the asymptotic convergence follow from the Lyapunov‐Krasovskii theory and are formulated in the linear matrix inequalities framework. The conditions rely only on the upper bound of delays and on a subset of the controller parameters, but they do not depend on the model of each agent, which makes it suitable for networks with agents governed by distinct dynamics. In order to illustrate the effectiveness of the proposed method we present numerical examples and compare with similar approaches existing in the literature.     

Stability analysis of the particle dynamics in bat algorithm: standard and modified versions

Stability and convergence analysis have been previously accomplished for some population-based search and swarm intelligence algorithms like Particle Swarm Optimization and Gravitational Search Algorithm. However, there is no adequate theoretical analysis for Bat Algorithm (BA) in the literature. The BA is a type of optimization algorithms which is inspired by the motion of small bats searching for hunting their preys. In this study, stability and convergence of the particle dynamics in the standard version BA are analyzed, and some restrictions are described. Then, new updating relations have been proposed. Also the dynamics of the algorithm have been investigated, and sufficient conditions for stability have been derived using Lyapunov stability analysis. Extensive simulation is used to examine the findings. The results confirm the theoretical predictions and indicate the stability and convergence of the proposed updating relations.

     

Continuous relaxation and local maxima selection: conditions for equivalence

Relaxation labeling processes are a class of iterative algorithms for using contextual information to reduce local ambiguities. This paper introduces a new perspective toward relaxation-that of considering it as a process for reordering labels attached to nodes in a graph. This new perspective is used to establish the formal equivalence between relaxation and another widely used algorithm, local maxima selection. The equivalence specifies conditions under which a family of cooperative relaxation algorithms, which generalize the well-known ones, decompose into purely local ones. Since these conditions are also sufficient for guaranteeing the convergence of relaxation processes, they serve as stopping criteria. We feel that equivalences such as these are necessary for the proper application of relaxation and maxima selection in complex speech and vision understanding systems.     

Pareto optimal mapping for tile-based network-on-chip under reliability constraints

Mapping for network-on-chip (NoC) is one of the key steps of NoC design. To improve the performance and reliability of NoC architectures, we present a comprehensive optimization algorithm with multiple objectives. We propose to find the Pareto optimal solutions, rather than a single solution usually obtained through scalarization, e.g. weighting the objective functions. In order to meet the NoC mapping requests and strengthen the capability of searching solutions, the standard particle swarm optimization (PSO) algorithm is improved and a fault-tolerant routing is proposed. These methods help to solve the tradeoff between high performance and system reliability. We present a mathematical analysis of the convergence of the improved algorithms, and prove sufficient conditions of convergence. The improved algorithms are implemented on the Embedded Systems Synthesis Benchmarks Suite (E3S). Experimental results show our algorithms achieve high performance and reliability compared with the standard PSO.     

Topological properties of measurable structures and sufficient conditions for uniform convergence of frequencies to probabilities

The event-uniform convergence of frequencies to probabilities is one of the main tools of the today theory of learning pattern recognition which enables one to substantiate the generalizability of the learning algorithms. Proposed was a new approach to derivation of the sufficient conditions for such convergence on the basis of only the topological properties of the event σ-algebra induced by the class under consideration.     

Hammerstein Models for Identification of Stochastic Systems

Identification of nonlinear stochastic systems in the class of Hammerstein models is investigated with regard for the nonlinearities of the investigated object. Hammerstein models are constructed with regard for the output noise in the form of a martingale sequence and moving mean are constructed. Necessary and sufficient conditions for the strong consistency of estimates of parameters of stochastic gradient algorithms are formulated. Their convergence rates are estimated. The results are applicable to adaptive tracking of the output of an object.     

Input conditions for continuous-time adaptive systems problems

The authors develop persistence-of-excitation conditions for the exponential convergence of continuous-time adaptive algorithms. Exponential convergence is important for robustness. Adaptive algorithms without such convergence can behave unacceptably in the presence of modeling inadequacies. Conditions for convergence are usually framed as spanning conditions on a regressor vector involving the output of the unknown system. In this study the authors translate these conditions into ones involving the system input only     

Parallel asynchronous team algorithms: convergence and performanceanalysis

This paper formalizes a general technique to combine different methods in the solution of large systems of nonlinear equations using parallel asynchronous implementations on distributed-memory multiprocessor systems. Such combinations of methods, referred to as team algorithms, are evaluated as a way of obtaining desirable properties of different methods and a sufficient condition for their convergence is derived. The load flow problem of electrical power networks is presented as an example problem that, under certain conditions, has the characteristics to make a team algorithm an appealing choice for its solution. Experimental results of an implementation on an Intel iPSC/860 Hypercube are reported, showing that considerable speedup and robustness can be obtained using team algorithms     

Using a Local Discovery Ant Algorithm for Bayesian Network Structure Learning

Bayesian networks (BNs) are knowledge representation tools capable of representing dependence or independence relationships among random variables. Learning the structure of BNs from datasets has received increasing attention in the last two decades, due to the BNs' capacity of providing good inference models and discovering the structure of complex domains. One approach for BNs' structure learning from data is to define a scoring metric that evaluates the quality of the candidate networks, given a dataset, and then apply an optimization procedure to explore the set of candidate networks. Among the most frequently used optimization methods for BN score-based learning is greedy hill climbing (GHC) search. This paper proposes a new local discovery ant colony optimization (ACO) algorithm and a hybrid algorithm max-min ant colony optimization (MMACO), based on the local discovery algorithm max-min parents and children (MMPC) and ACO to learn the structure of a BN. In MMACO, MMPC is used to construct the skeleton of the BN and ACO is used to orientate the skeleton edges, thus returning the final structure. The algorithms are applied to several sets of benchmark networks and are shown to outperform the GHC and simulated annealing algorithms.      

基于BMI方法的线性系统的关联稳定与协调控制

本文研究了线性大系统的关联稳定与协调控制问题. 基于双线性矩阵不等式, 给出了两个子系统关联稳定与协调镇定的充分与必要条件. 结论表明, 即使子系统不稳定, 组成的大系统也易能被协调镇定, 而不需要假定子系统的稳定. 其次, 协调控制器的设计问题转化为 BMI 约束下的优化问题, 为求解此问题, 提出了优化交替算法, 并给出了此算法收敛性的简单证明. 最后, 数值算例表明了优化算法的有效性.     

Sulla convergenza dei metodi a gradiente coniugato

A sufficient condition of convergence for unconstrained optimization methods is introduced. An alternative proof for the convergence of some algorithms is presented too.