一种动态分布式约束优化问题协同求解算法

多Agent协作过程中的许多问题都可在分布式约束优化问题(DCOP)框架下建模,但多局限于规划问题,且一般需Agent具有完全、准确收益函数.针对DCOP局限性,定义动态分布式约束优化问题(DDCOP),分析求解它的两个关键操作:Exploration和Exploitation,提出基于混沌蚂蚁的DDCOP协同求解算法(CA-DDCOP).该算法借鉴单只蚂蚁的混沌行为和蚁群的自组织行为,实现Exploration和Exploitation,根据玻尔兹曼分布,建立平衡Exploration和Exploitation的协同方法.通过多射频多信道无线AdHoc网络的信道分配验证该算法的有效性.     

基于约束图分片求解DCOP的Agent组织结构

MAS中许多分布式推理问题可以建模为分布式约束优化问题(DCOP),解决DCOP的分布式算法已经成为MAS中的重要基础.已有的Adopt等算法通过对等的Agent之间的平等协商完成求解,强调了异步通信、分布计算与对解质量的保证,在求解问题的组织结构方面仍有改进余地.可以采用一种基于分散与集中相结合的思路,基于对约束图分片的方法及核心结点、通信主干道等概念,构造新颖的Agent组织结构,完成DCOP问题的异步、分布求解.在该组织结构下求解DCOP的算法可在效率、适应动态性方面得到改善,并将一个Agent一个变量和一个Agent多个变量的DCOP求解方法统一起来.     

基于合作仲裁求解分布式约束优化问题的研究

MAS中许多分布式推理问题都可以建模为分布式约束优化问题(DCOP).在这里,我们把分布式会议调度DMS(Dis-tributed Meeting Scheduling)问题映射为DCOP,基于合作仲裁进行求解,并把结果与另一个DCOP算法比较.考虑到完全解决方案的时间复杂性,我们把局部约束图转换为伪树,加速了搜索速度,从而在较短的时间找到最优解决方案.     

基于局部并行搜索的分布式约束优化算法框架

针对当前局部搜索算法在求解大规模、高密度的分布式约束优化问题（DCOP）时,求解困难且难以跳出局部最优取得进一步优化等问题,提出一种基于局部并行搜索的分布式约束优化算法框架（LPOS）,算法中agent通过自身的取值并行地搜索局部所有邻居取值来进一步扩大对解空间的搜索,从而避免算法过早陷入局部最优。为了保证算法的收敛性与稳定性,设计了一种自适应平衡因子K来平衡算法对解的开发和继承能力,并在理论层面证明了并行搜索优化算法可以扩大对解空间的搜索,自适应平衡因子K可以实现平衡目的。综合实验结果表明,基于该算法框架的算法在求解低密度和高密度DCOP时性能都优于目前最新的算法。特别是在求解高密度DCOP中有显著的提升。     

基于群体多样性反馈控制的自组织微粒群算法

微粒群算法是一种新型的群智能算法,已被广泛用于各种复杂优化问题的求解,但算法依然面临着过早收敛问题.为克服算法的早熟问题,提出了自组织微粒群算法.将微粒群体视为自组织系统,引入负反馈机制.群体多样性是影响微粒群算法全局优化性能的关键因素,把群体多样性作为个体微粒可感知的群体动态信息,用于动态调整惯性权重或加速度系数,通过不同的特性参数实现微粒的集聚或分散,使群体维持适当的多样性水平以利于全局搜索.用于复杂函数优化问题的求解,并与其他典型改进算法进行了性能比较.仿真结果表明,基于多样性控制的自组织微粒群算法可以有效避免早熟问题,提高微粒群算法求解复杂函数的全局优化性能.     

一阶多智能体受扰系统的自抗扰分布式优化算法

研究一类具有未知外部干扰的一阶多智能体系统的分布式优化问题.在分布式优化任务中,每个智能体只被容许利用自己的局部目标函数和邻居的状态信息,设计一个分布式优化算法,使全局目标函数取得最小值,其中全局目标函数是所有局部目标函数之和.针对该问题,首先提出由扩张状态观测器和优化算法组成的自抗扰分布式优化算法.其次,在Lyapu...     

动态博弈框架下的分布式动态优化

为了实时在线求解复杂的大规模动态优化问题,本文基于动态博弈理论提出了一种分布式动态优化方案,滚动合作博弈优化(RCGO).首先基于滚动时域优化框架,该方案将原本复杂的大规模动态优化问题分解为若干简单的小规模局部优化子问题,使得计算复杂度降低从而保证优化求解的实时性.之后本文基于动态博弈提出了分解迭代法求解各局部动态优化子问题,并对RCGO优化方案下系统稳定性进行分析.最后本文选择一个化工过程网络作为仿真案例,基于RCGO方案得到了极大化经济效益下该网络的最优操作.优化结果表明在求解复杂大规模动态优化问题时, RCGO方案较传统的集中式优化方案在由系统经济效益、闭环控制性能及优化求解实时性等组成的综合指标上有较大优势.     

DCSP和DCOP求解研究进展

分布式约束满足问题（DCSP）和分布式约束最优问题（DCOP）的研究是分布式人工智能领域的基础性工作。本文首先介绍了卿和DCOP的形式化描述及对实际应用问题的建模方法。在DCSP和DCOP的求解中，通常对问题要进行限制和要求，同时要满足分布性、异步性、局部性、完备性的原则。异步回溯（ABT）、异步弱承诺搜索（AWC）和分布式逃逸（DB）算法是求解DCSP的有代表性的算法；DCSP算法对DCOP求解产生了影响，但由DCSP一般化到DCOP的算法，仅适用于解决部分特定的问题，DCOP的最优、异步算法有异步分布式约束最优算法（A—dopt）和最优异步部分交叉算法（OptAPO）。本文讨论了上述算法的性能。相关的研究工作在多局部变量的处理、超约束DCSP、算法性能度量、通信的保密等方面进行了扩充，在对问题本身的研究、建模方法学、算法、与其他方法的结合以及拓展应用领域等方面仍有许多问题需要进一步研究。     

非平衡有向网络的完全分布式凸优化

分布式凸优化问题的目的是如何以分布式方法最小化局部智能体成本函数和,而现有分布式算法的控制步长选取依赖于系统智能体个数、伴随矩阵等全局性信息,有悖于分布式算法的初衷.针对此问题,提出一种基于非平衡有向网络的完全分布式凸优化算法(FDCOA).基于多智能体一致性理论和梯度跟踪技术,设计了一种非负余量迭代策略,使得FDCOA的控制步长收敛范围仅与智能体局部信息相关,进而实现控制步长的分布式设置.进一步分析了FDCOA在固定强连通和时变强连通网络情形下的收敛性.仿真结果表明本文构建的分布式控制步长选取方法对FDCOA在有向非平衡下的分布式凸优化问题是有效的.     

带有网络拓扑优化的分布式预测控制方法

通常在大系统中, 全局信息优化的系统, 其性能要高于局部信息优化系统. 全局信息优化的算法由于大系统的复杂程度往往不可行. 所以通常会用分布式算法来解决此类问题. 在分布式算法中, 为了获得更好的系统性能, 要尽可能多的采用更多的信息信息交换, 然而这样会带来信息网络的负担增大. 本文在预测控制性能指标中引入通信代价, 并提出了一种随着系统状态变化的通信网络拓扑切换方法. 文中给出了该算法在供水管网动态模型中的仿真结果, 表明本方法的可行性.     

Distributed constraint optimization with MULBS: A case study on collaborative meeting scheduling

This paper introduces MULBS, a new DCOP (distributed constraint optimization problem) algorithm and also presents a DCOP formulation for scheduling of distributed meetings in collaborative environments. Scheduling in CSCWD can be seen as a DCOP where variables represent time slots and values are resources of a production system (machines, raw-materials, hardware components, etc.) or management system (meetings, project tasks, human resources, money, etc). Therefore, a DCOP algorithm must find a set of variable assignments that maximize an objective function taking constraints into account. However, it is well known that such problems are NP-complete and that more research must be done to obtain feasible and reliable computational approaches. Thus, DCOP emerges as a very promising technique: the search space is decomposed into smaller spaces and agents solve local problems, collaborating in order to achieve a global solution. We show with empirical experiments that MULBS outperforms some of the state-of-the-art algorithms for DCOP, guaranteeing high quality solutions using less computational resources for the distributed meeting scheduling task.     

Node and Link Allocation in Network Virtualization Based on Distributed Constraint Optimization

Virtual Networks (VNs) offer a flexible and economic approach to deploy customer suited networks. However, defining how resources of a physical network are used to support VNs requirements is a NP-hard problem. For this reason, heuristics have been used on mapping of virtual networks. Although heuristics do not ensure the optimal solution, they implement fast solutions and showed satisfactory results. This work presents a modeling of the node and link allocation problem using Distributed Constraint Optimization Problem (DCOP) with factor graphs, which is a formalism widely used in real distributed optimization problems. In our approach, we use the max-sum algorithm to solve the DCOP. Correctness criteria for this approach are discussed and verifications are conducted through model checking.     

DCOP FOR SMART HOMES: A CASE STUDY

The aim of this article is to bring forth the issue of integrating the services provided by intelligent artifacts in Ambient Intelligence applications. Specifically, we propose a Distributed Constraint Optimization procedure for achieving a functional integration of intelligent artifacts in a smart home. To this end, we employ Adopt-N , a state-of-the-art algorithm for solving Distributed Constraint Optimization Problems (DCOP). This article attempts to state the smart home coordination problem in general terms, and provides the details of a DCOP-based approach by describing a case study taken from the RoboCare project. More specifically, we show how (1) DCOP is a convenient metaphor for casting smart home coordination problems, and (2) the specific features which distinguish Adopt-N from other algorithms for DCOP represent a strong asset in the smart home domain.     

Leximin Asymmetric Multiple Objective Distributed Constraint Optimization Problem

The Distributed Constraint Optimization Problem (DCOP) lies at the foundations of multiagent cooperation. With DCOPs, the optimization in distributed resource allocation problems is formalized using constraint optimization problems. The solvers for the problem are designed based on decentralized cooperative algorithms that are performed by multiple agents. In a conventional DCOP, a single objective is considered. The Multiple Objective Distributed Constraint Optimization Problem (MODCOP) is an extension of the DCOP framework, where agents cooperatively have to optimize simultaneously multiple objective functions. In the conventional MODCOPs, a few objectives are globally defined and agents cooperate to find the Pareto optimal solution. However, such models do not capture the interests of each agent. On the other hand, in several practical problems, the share of each agent is important. Such shares are modeled as preference values of agents. This class of problems can be defined using the MODCOP on the preferences of agents. In particular, we define optimization problems based on leximin ordering and Asymmetric DCOPs (Leximin AMODCOPs). The leximin defines an ordering among vectors of objective values. In addition, Asymmetric DCOPs capture the preferences of agents. Because the optimization based on the leximin ordering improves the equality among the satisfied preferences of the agents, this class of problems is important. We propose several solution methods for Leximin AMODCOPs generalizing traditional operators into the operators on sorted objective vectors and leximin. The solution methods applied to the Leximin AMODCOPs are based on pseudo trees. Also, the investigated search methods employ the concept of boundaries of the sorted vectors.     

Privacy Loss in Distributed Constraint Reasoning: A Quantitative Framework for Analysis and its Applications

It is critical that agents deployed in real-world settings, such as businesses, offices, universities and research laboratories, protect their individual users’ privacy when interacting with other entities. Indeed, privacy is recognized as a key motivating factor in the design of several multiagent algorithms, such as in distributed constraint reasoning (including both algorithms for distributed constraint optimization (DCOP) and distributed constraint satisfaction (DisCSPs)), and researchers have begun to propose metrics for analysis of privacy loss in such multiagent algorithms. Unfortunately, a general quantitative framework to compare these existing metrics for privacy loss or to identify dimensions along which to construct new metrics is currently lacking. This paper presents three key contributions to address this shortcoming. First, the paper presents VPS (Valuations of Possible States), a general quantitative framework to express, analyze and compare existing metrics of privacy loss. Based on a state-space model, VPS is shown to capture various existing measures of privacy created for specific domains of DisCSPs. The utility of VPS is further illustrated through analysis of privacy loss in DCOP algorithms, when such algorithms are used by personal assistant agents to schedule meetings among users. In addition, VPS helps identify dimensions along which to classify and construct new privacy metrics and it also supports their quantitative comparison. Second, the article presents key inference rules that may be used in analysis of privacy loss in DCOP algorithms under different assumptions. Third, detailed experiments based on the VPS-driven analysis lead to the following key results: (i) decentralization by itself does not provide superior protection of privacy in DisCSP/DCOP algorithms when compared with centralization; instead, privacy protection also requires the presence of uncertainty about agents’ knowledge of the constraint graph. (ii) one needs to carefully examine the metrics chosen to measure privacy loss; the qualitative properties of privacy loss and hence the conclusions that can be drawn about an algorithm can vary widely based on the metric chosen. This paper should thus serve as a call to arms for further privacy research, particularly within the DisCSP/DCOP arena.     

基于分布式约束优化的武器目标分配问题研究

为解决舰艇编队协同防空中的武器目标分配(WTA)问题,提出一种将WTA问题建模为分布式约束优化问题的方法。介绍求解分布式约束优化问题的2个典型算法ADOPT和DPOP。通过Frodo软件平台对舰艇拦截多批反舰导弹过程进行仿真,比较2个算法在仿真时间、通信量等方面的性能,结果证明了该方法求解WTA问题的可行性。