分布式训练系统及其优化算法综述

人工智能利用各种优化技术从海量训练样本中学习关键特征或知识以提高解的质量,这对训练方法提出了更高要求.然而,传统单机训练无法满足存储与计算性能等方面的需求.因此,利用多个计算节点协同的分布式训练系统成为热点研究方向之一.本文首先阐述了单机训练面临的主要挑战.其次,分析了分布式训练系统亟需解决的三个关键问题.基于上述问题归纳了分布式训练系统的通用框架与四个核心组件.围绕各个组件涉及的技术,梳理了代表性研究成果.在此基础之上,总结了基于并行随机梯度下降算法的中心化与去中心化架构研究分支,并对各研究分支优化算法与应用进行综述.最后,提出了未来可能的研究方向.     

Aug-PDG:带不等式约束凸优化算法的线性收敛性

原始-对偶梯度算法广泛应用于求解带约束的凸优化问题, 大部分文献仅证明了该算法的收敛性, 而没有分析其收敛速度. 因此, 本文研究了求解带有不等式约束凸优化的一类离散算法, 即增广原始-对偶梯度算法 (Aug-PDG), 证明了Aug-PDG 算法在一些较弱的假设条件下可以半全局线性收敛到最优解, 并明确给出了算法中步长的上界. 最后, 数值算例证实了所得理论结果的有效性.     

梯度微粒群优化算法及其收敛性分析

针对标准微粒群优化算法微粒运动轨迹的收敛性进行了分析.给出并证明了微粒运动轨迹收敛的充分条件.提出一种简便的等高线图判别法,该方法能够通过参数的位置判断微粒轨迹是否收敛并衡量收敛速度.为提高算法的收敛速度.构造出一种梯度微粒群优化算法,给出并证明了该方法收敛的充分条件.仿真结果表明,梯度微粒群优化算法具有优良的搜索性能.     

低约束密度分布式约束优化问题的求解算法

多Agent协作过程中的许多挑战都可以建模为分布式约束优化问题.针对低约束密度的分布式约束优化问题,提出了一种基于贪婪和回跳思想的求解算法.在该算法中,各Agent基于贪婪原则进行决策,能够利用低约束密度问题中大量赋值组合代价为0这一特点来加快求解速度.同时,Agent间的回跳机制可以在贪婪原则陷入局部最优时保证算法的完全性.相对于已有主流算法,该算法可以在保持多项式级别的消息长度/空间复杂度的前提下,以较少的消息数目求解低约束密度的分布式约束优化问题.给出了算法关键机制的正确性证明,并通过实验验证了算法的上述性能优势.     

分布式约束优化方法研究进展

多agent系统作为分布式人工智能研究领域的重要分支,已被广泛应用于多个领域中复杂系统的建模.而分布式约束优化作为一种多agent系统求解的关键技术,已成为约束推理研究的热点.首先对其适用性进行分析,并基于对已有算法的研究,总结出采用该方法解决问题的基本流程,在此基础上,从解的质量保证、求解策略等角度对算法进行了完整的分类;其次,根据算法分类结果以及执行机制,对大量经典以及近年来的分布式约束优化算法进行了深入分析,并从通信、求解质量、求解效率等方面对典型算法进行了实验对比;最后,结合分布式约束优化技术的求解优势给出了分布式约束优化问题的实际应用特征,总结了目前存在的一些问题,并对下一步工作进行了展望.     

分布式数据驱动的多约束进化优化算法

泛在计算模式下,数据分布式获取和处理带来了分布式数据驱动优化的需求。针对数据分布获取、约束异步评估且信息缺失的挑战,构建分布式数据驱动的多约束进化优化算法(DDDEA)框架,由一系列终端节点负责数据提供和分布式评估,服务器节点负责全局进化优化。基于该框架具体实现了一个算法实例,终端节点利用局部数据构建径向基函数(RBF)模型,辅助驱动服务器节点差分进化(DE)算法对问题进行寻优。通过与3个集中式数据驱动的多约束进化优化算法在两个标准测试集的实验对比,DDDEA在68.4%的测试用例中取得显著最优结果,在84.2%的测试用例中找到可行解的成功率为1.00,表明该算法具有良好的全局搜索能力和收敛能力。     

集合约束下多智能体系统分布式固定时间优化控制

本文研究一类具有状态约束的多智能体系统优化控制问题, 提出了一种具有固定时间收敛特性的分布式优化控制算法. 该控制算法由局部投影模块、一致性模块和梯度模块构成, 其中局部投影模块确保智能体的状态在固定时间内收敛到局部约束集合, 基于时变增益的一致性模块实现所有智能体的状态在固定时间内收敛到一致值, 基于时变增益的梯度模块实现智能体的状态在固定时间内收敛到最优解. 利用凸优化理论和固定时间李雅普诺夫理论, 分析了算法的固定时间收敛特性. 算法收敛时间的上界值不依赖系统的初始条件, 因而可以根据任务需求来预先设计收敛时间. 最后通过数值仿真验证了理论结果的有效性.     

基于事件驱动的二次凸优化问题分布式优化算法

针对多智能体系统中等式约束下的二次凸优化问题,给出一种事件驱动机制下的分布式优化算法.该算法可以降低每个智能体控制协议的更新频率以及智能体之间的通信负担.基于图论和李雅普诺夫函数方法给出两种不同的事件触发条件,其中第2种事件触发条件不需要拉普拉斯矩阵的最大特征根的信息,可实现算法全分布式实施.两种事件触发条件均可实现算法渐近收敛到优化值,避免智能体控制协议的连续更新以及智能体之间的连续通信,同时保证每个智能体相邻事件触发时刻的时间间隔大于0,避免持续事件触发.将所提出的算法应用于Matlab仿真环境中进行仿真验证,仿真结果验证了所提出算法的有效性.     

分布式约束优化

多Agent系统由于拥有智能性、自主性以及协同性等一系列的特性受到人们广泛的关注.分布式约束优化是协调多个Agent解决分布问题的有效技术,目前是多Agent领域的研究热点.本文将首先介绍分布式约束优化问题的基本概念和框架结构,总结现有的解决该问题的主要算法.并通过效率、性能、隐私等各方面对这些算法进行全面的比较与分析,然后介绍分布式约束优化问题的一些典型应用,最后还将对分布式约束优化问题及其算法未来的研究发展方向进行论述.     

多个体网络分布式随机投影无梯度优化算法

研究了有向多个体网络的无梯度优化问题,提出了一种分布式随机投影无梯度优化算法。假定网络的优化目标函数可分解成所有个体的目标函数之和,每个个体仅知其自身的目标函数及其自身的状态约束集。运用无梯度方法解决了因个体目标函数可能非凸而引起的次梯度无法计算问题,并结合随机投影算法解决了约束集未知或约束集投影运算受限的问题。在该算法作用下,所有个体状态几乎必然收敛到优化集内,并且网络目标函数得到最优。     

分布式预测控制优化算法

复杂大规模预测控制系统的在线实施一直是工业界十分关注的问题之一, 本文针对工业环境下分布式网络结构的特点, 提出了一种基于纳什最优的分布式预测控制优化算法, 在以低成本在线实施的同时, 保持了良好的控制性能, 文中进一步给出了分布式线性模型预测控制算法的收敛条件, 仿真结果表明了该算法的有效性.     

Distributed Nash Equilibrium Seeking Strategies Under Quantized Communication

This paper is concerned with distributed Nash equi librium seeking strategies under quantized communication. In the proposed seeking strategy, a projection operator is synthesized with a gradient search method to achieve the optimization o players’ objective functions while restricting their actions within required non-empty, convex and compact domains. In addition, a leader-following consensus protocol, in which quantized informa tion flows are utilized, is employed for information sharing amon...     

预设时间下的分布式优化和纳什均衡点求解

本文研究了预设时间下的分布式优化和纳什均衡点求解问题. 假设每个智能体只能通过局部的信息更新 自身的状态, 设计了一类预设时间下的分布式协议. 该协议可以在任意预设的时间内实现收敛, 并且不需要依赖智 能体的初始状态和系统参数. 当目标函数是强凸函数时, 通过选取一个适当的Lyapunov函数, 利用代数图论和凸分 析理论等工具严格的证明了多智能体系统在预设时间下能够收敛到优化问题的最优解和非合作博弈问题的纳什均 衡点. 最后, 通过仿真算例进一步验证了本文所设计协议的有效性.     

非光滑聚合博弈纳什均衡的分布式连续时间算法

本文研究多智能体聚合博弈的分布式算法设计.其中,个体的成本函数具有非光滑性.提出一个连续时间分布式算法,使得每个个体仅利用本地数据及局部的信息交互就能达到纳什均衡.利用李雅普诺夫方法,证明了算法的收敛性.在此基础上,进一步研究了带有耦合不等式约束博弈的广义纳什均衡求解.仿真结果验证了方法的有效性.     

The particle swarm optimization algorithm: convergence analysis and parameter selection

The particle swarm optimization algorithm is analyzed using standard results from the dynamic system theory. Graphical parameter selection guidelines are derived. The exploration-exploitation tradeoff is discussed and illustrated. Examples of performance on benchmark functions superior to previously published results are given.     

Space mapping algorithm with improved convergence properties for microwave design optimization

Space mapping is one of the most efficient techniques for microwave design optimization. Still, it is well known that space mapping algorithms may suffer from convergence issues, which are consequences of certain fundamental features. In many cases, the space mapping algorithm quickly finds an acceptable solution, but then falls into oscillations with respect to the design variables and/or the objective function value; as a consequence, there are no clear criteria for terminating the optimization process. In this article, we investigate some techniques for improving the convergence properties of the space mapping algorithm, which are based on the general convergence results for such algorithms. Our approach is verified using several microwave design optimization problems. © 2010 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2010.     

态空间系统的梯度优化辨识及收敛性分析*

为解决状态空间系统的预报误差与系统参数之间的非线性、非凸性给参数估计带来的困难,提出了状态空间系统的梯度优化辨识方法。分析了基于局部线性化的梯度辨识原理,给出了基于QR分解、奇异值分解(SVD)确定参数搜索方向的实现方案,得到了估计系统参数的迭代辨识算法。探讨了算法的收敛性、给出了算法收敛速度的解析表达式,最后进行了数值仿真,实验结果说明了所提出方法的有效性。     

一种新型高效的计算机寻优算法

提出一种全新的寻找无约束最优解的计算机算法。该算法能使得目标函数梯度的模逐渐收缩到零,以达到目标函数极小化,因此命名“梯度收缩法”。它同时利用了牛顿法和共轭梯度法的优点,应用目标函数的二阶导数,收敛很快,且具有牛顿法的“二次终止”特性。但Hessian矩阵奇异时,牛顿法将无法进行下去,该文算法可以克服这个缺点且能快速确定是否收敛到一个鞍点。     

Distributed second-order multi-agent constrained optimization algorithm with time-varying cost function

This paper mainly discusses distributed constrained optimization problem for second-order multi-agent system under undirected communication network. The task of all agents is to minimize the sum of the local convex functions, where each agent is individual and only accesses to one objective function. Different from the most existing results, where the objective functions are assumed to be time-invariable, this paper considers the situation of time-varying objective function. Besides, we don't require that the Hessian matrices are identical and the gradients are bounded. First, a novel time-varying optimization algorithm is proposed based on the projection algorithm. Second, by using convex analysis and Lyapunov theory, it is shown that the states of all agents can reach consensus and asymptotically converge to the neighborhood of the optimal solution. Finally, some numerical examples are given to verify the effectiveness of our algorithms.     

A space search optimization algorithm with accelerated convergence strategies

Evolutionary algorithms (EAs), which have been widely used to solve various scientific and engineering optimization problems, are essentially stochastic search algorithms operating in the overall solution space. However, such random search mechanism may lead to some disadvantages such as a long computing time and premature convergence. In this study, we propose a space search optimization algorithm (SSOA) with accelerated convergence strategies to alleviate the drawbacks of the purely random search mechanism. The overall framework of the SSOA involves three main search mechanisms: local space search, global space search, and opposition-based search. The local space search that aims to form new solutions approaching the local optimum is realized based on the concept of augmented simplex method, which exhibits significant search abilities realized in some local space. The global space search is completed by Cauchy searching, where the approach itself is based on the Cauchy mutation. This operation can help the method avoid of being trapped in local optima and in this way alleviate premature convergence. An opposition-based search is exploited to accelerate the convergence of space search. This operator can effectively reduce a substantial computational overhead encountered in evolutionary algorithms (EAs). With the use of them SSOA realizes an effective search process. To evaluate the performance of the method, the proposed SSOA is contrasted with a method of differential evolution (DE), which is a well-known space concept-based evolutionary algorithm. When tested against benchmark functions, the SSOA exhibits a competitive performance vis-a-vis performance of some other competitive schemes of differential evolution in terms of accuracy and speed of convergence, especially in case of high-dimensional continuous optimization problems.