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

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

基于混沌蚂蚁的分布式系统协同优化方法

针对复杂分布式系统的优化问题,提出基于混沌蚂蚁的复杂分布式系统协同优化方法.在系统理论指导下,分析复杂分布式系统中自主Agent的基本动力学特征,进而提出复杂分布式系统协同优化模型.在此基础上,借助混沌蚂蚁群算法(CAS)的思想,建立基于混沌蚂蚁的复杂分布式系统协同优化算法(CAS-CO).通过对复杂多Agent网络中基于位置的任务分配问题进行仿真实验,同时与已有算法仿真结果对比,表明CAS-CO算法可行有效,反映文中模型的正确性和Agent的自主性在复杂分布式系统设计和构建中的重要性.     

自组织分治求解分布式约束优化问题

分布式约束优化问题(DCOP)是在大规模、开放、动态网络环境中的优化问题,在计算网格、多媒体网络、电子商务、企业资源规划等领域中都有广泛应用.除了具有传统优化问题的非线性、约束性等特点,DCOP还具有动态演化、信息区域化、控制局部化、网络状态异步更新等特点.寻求一种解决DCOP的大规模、并行、具有智能特征的求解方法已成为一个具有挑战性的研究课题.目前已提出多种求解DCOP的算法,但大多不是完全分散的算法,存在集中环节,需要网络的全局结构作为输入,不适合处理由规模巨大、地理分布、控制分散等因素导致的全局结构难以获取的分布式网络.针对该问题,提出一个基于自组织行为的分治策略求解DCOP.在不具有全局网络知识的情况下,分布在网络中的多个自治Agent基于局部感知信息、采用自组织的方式协作求解.与已有算法相比,它是一个完全分散式算法,并在求解效率和求解质量方面都展现出很好的性能.     

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

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

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

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

DCSP和DCOP求解研究进展

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

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

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

分布式约束优化

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

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

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

多Agent系统问题求解的广义粒子模型方法

提出一种多Agent系统分布式问题求解的新的广义粒子模型,将复杂环境下多Agent系统资源分配和任务规划的优化问题转变为广义粒子模型中的粒子运动学和动力学问题.广义粒子模型可以描述和处理的复杂环境包括多Agent系统中的Agent之间存在的随机、并发、多类型的交互行为.各Agent有不同的个性、自治性、生命周期、拥塞程度和故障几率等.本文讨论了广义粒子模型和多Agent系统分布式问题求解的关系,提出了广义粒子模型的数学物理模型和多Agent系统分布式问题求解算法,并且证明了它们的正确性、收敛性、稳定平衡性等基本性质.通过复杂环境下多Agent系统资源分配和任务规划问题的实验和比较,证实了广义粒子模型方法的有效性及其特点.     

A novel quasi-oppositional chaotic antlion optimizer for global optimization

This paper proposes a novel quasi-oppositional chaotic antlion optimizer (ALO) (QOCALO) for solving global optimization problems. ALO is a population based algorithm motivated by the unique hunting behavior of antlions in nature and exhibits strong influence in solving global and engineering optimization problems. In the proposed QOCALO algorithm of the present work, the initial population is generated using the quasi-opposition based learning (QOBL) and the concept of QOBL based generation jumping is utilized inside the main searching strategy of the proposed algorithm. Utilization of QOBL ensures better convergence speed of the proposed algorithm and it also provides better exploration of the search space. Alongside the QOBL, a chaotic local search (CLS) is also incorporated in the proposed QOCALO algorithm. The CLS guides local search around the global best solution that provides better exploitation of the search space. Thus, a better trade-off between exploration and exploitation holds for the proposed algorithm which makes it robust. It is observed that the proposed algorithm offers better results than the original ALO in terms of solution quality and convergence speed. The proposed QOCALO algorithm is implemented and tested, successfully, on nineteen mathematical benchmark test functions of varying complexities and the experimental results are compared to those offered by the basic ALO and some other recently developed nature inspired algorithms. The efficacy of the proposed algorithm is further utilized to solve three real world engineering optimization problems viz. (a) the placement and sizing problem of distributed generators in radial distribution networks, (b) the congestion management problem in power transmission system and (c) the optimal design of pressure vessel.     

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.     

A Generic Framework for Constrained Optimization Using Genetic Algorithms

In this paper, we propose a generic, two-phase framework for solving constrained optimization problems using genetic algorithms. In the first phase of the algorithm, the objective function is completely disregarded and the constrained optimization problem is treated as a constraint satisfaction problem. The genetic search is directed toward minimizing the constraint violation of the solutions and eventually finding a feasible solution. A linear rank-based approach is used to assign fitness values to the individuals. The solution with the least constraint violation is archived as the elite solution in the population. In the second phase, the simultaneous optimization of the objective function and the satisfaction of the constraints are treated as a biobjective optimization problem. We elaborate on how the constrained optimization problem requires a balance of exploration and exploitation under different problem scenarios and come to the conclusion that a nondominated ranking between the individuals will help the algorithm explore further, while the elitist scheme will facilitate in exploitation. We analyze the proposed algorithm under different problem scenarios using Test Case Generator-2 and demonstrate the proposed algorithm's capability to perform well independent of various problem characteristics. In addition, the proposed algorithm performs competitively with the state-of-the-art constraint optimization algorithms on 11 test cases which were widely studied benchmark functions in literature.     

求解能耗成本平衡的分布式阻塞流水线调度群体迭代贪婪算法

在经典分布式流水车间调度问题基础上, 本文构建了具有序列相关准备时间的分布式阻塞流水线调度问题(DBFSP SDST)的混合线性整数规划模型(MILP), 以均衡各工厂能耗成本为优化目标, 提出了基于群体优化的迭代贪婪算法 (PEIG). 该算法针对零缓冲区和多工厂生产模式, 设计了问题特性的启发式方法; 针对迭代贪婪算法(IGA)的优势和不足, 提出了基于群体的局部搜索策略、多邻域搜索结构和增强的跨工厂破坏重构方法, 以进一步平衡所提算法的全局探索和局部搜索能力. 通过270个测试算例的数值仿真, 以及与最新4种代表算法的统计比较,本文验证了所提PEIG算法的优越性, 能为中大规模的DBFSP SDST提供更优的调度方案.     

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.     

基于蚁群混沌行为的离散粒子群算法及其应用

考虑蚁群算法与粒子群算法的各自特点,在粒子群算法的基础上借鉴蚁群算法的信息素机制,对粒子群算法的速度位置更新公式重新定义,提出了一种基于蚁群混沌行为的离散粒子群算法,并将其应用到背包问题中。实验结果表明,该算法可以得到较优解。