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

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

分布式约束优化

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

基于多种群的随机扰动蚁群算法求解分布式约束优化问题

针对现有的基于蚁群优化思想求解分布式约束优化问题的算法收敛较慢、容易陷入局部最优等问题,提出了一种基于多种群的随机扰动蚁群算法（random disturbance based multi-population ant colony algorithm to solve distributed constraint optimization problems,RDMAD）来求解分布式约束优化问题。首先,RDMAD提出了一种分工合作机制,将种群按比例划分为采用贪婪搜索的子种群和采用启发式搜索的子种群,同时构建分级更新策略,提高算法收敛速度和求解质量;然后对采用贪婪搜索的子种群设计自适应变异算子和奖惩机制,防止算法陷入局部最优;最后在算法陷入停滞时触发随机扰动策略,增加种群多样性。将RDMAD与七种最先进的非完备算法在三类基准问题上的寻优结果进行了实验对比,实验结果表明RDMAD在求解质量和收敛速度上优势明显,且稳定性较高。     

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

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

一种求解约束优化问题的新算法

演化算法基于达尔文的适者生存的原理,通过模拟大自然演化过程寻找问题的最优解。由于演化算法的全局性、灵活性、自适应性和稳健性,它特别适用于解象非线性、不可导和多峰等高难度优化问题。近年来,演化算法已经成功地解决了一些工程优化问题。毫无疑问,演化计算是一类解决高难度优化问题最重要的办法之一。     

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

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

求解约束优化问题的改进型免疫算法

为了提高免疫算法求解约束优化问题的性能,给出了一种融合乘子法的免疫算法。设计了乘子法对约束条件的转换过程,给出了基于实数编码的克隆变异算子、浓度抑制算子和免疫算法框架,并对标准测试函数进行了实验验证。实验结果表明,该算法优于文献算法,具有较好的应用价值。     

求解约束优化问题的文化算法研究

文化算法的主要思想是明确地从进化种群中获得求解问题的知识 (即信念) 并用于指导搜索过程. 本文提出了一种基于多层信念空间的文化算法, 该算法通过对多层信念空间的择优选用将提取的知识用于提高进化计算性能来解决约束优化问题. 应用实例表明该算法具有较好的结果和较少的计算量.     

基于文化粒子群算法的约束优化问题求解

提出一种基于文化算法的粒子群优化算法(PSO)。该算法在群体空间采用基于高斯概率分布和柯西概率分布的改进PSO算法,在信念空间根据形势知识和规范化知识指导种群的进化,充分利用优秀个体所包含的信息,提高了算法的进化速度。实验表明,该算法的优化性能和效率优于基本PSO算法。     

Pareto强度值演化算法求解约束优化问题

提出了一种求解约束函数优化问题的方法.它不使用传统的惩罚函数,也不区分可行解和不可行解.新的演化算法将约束优化问题转换成两个目标优化问题,其中一个为原问题的目标函数,另一个为违反约束条件的程度函数.利用多目标优化问题中的Pareto优于关系,定义个体Pareto强度值指标以便对个体进行排序选优,根据Pareto强度值排序和最小代数代沟模型设计出新的实数编码遗传算法.对常见测试函数的数值实验证实了新方法的有效性、通用性和稳健性,其性能优于现有的一些演化算法.特别是对于一些既有等式约束又有不等式约束的复杂非线性规划问题,该算法获得了更高精度的解.     

An Arc-Consistency Algorithm for Dynamic and Distributed Constraint Satisfaction Problems

This paper presents the new DDAC4 algorithm for dynamic arc consistency enforcement in distributed constraint satisfaction problems (CSP). The algorithm is an adaptation of the well-known AC-4 algorithm to system settings where constraints can be added and deleted in concurrent processes. It is the first algorithm for arc-consistency enforcement in this system setting. Arc-consistency is achieved whenever the overall system reaches quiescence after a constraint is added or deleted.     

求解非线性约束问题的混合粒子群优化算法

将处理约束问题的乘子法与改进的粒子群算法相结合,提出了一种求解非线性约束问题的混合粒子群算法。此算法兼顾了粒子群优化算法和乘子法的优点,对迭代过程中出现的不可行粒子,利用乘子法处理后产生可行粒子,然后用改进的粒子群算法来搜索其最优解,这样不仅减小了粒子群算法在寻优过程中陷入局部极小的概率,而且提高了搜索精度。数值试验结果表明提出的新算法具有搜索精度更高、稳定性更强、鲁棒性更好等特点。     

An Approximate Gradient Algorithm for Constrained Distributed Convex Optimization

In this paper, we propose an approximate gradient algorithm for the multi-agent convex optimization problem with constraints. The agents cooperatively compute the minimum of the sum of the local objective functions which are subject to a global inequality constraint and a global constraint set. Instead of each agent can get exact gradient, as discussed in the literature, we only use approximate gradient with some computation or measurement errors. The gradient accuracy conditions are presented to ensure the convergence of the approximate gradient algorithm. Finally, simulation results demonstrate good performance of the approximate algorithm.      

链路约束的分布式网络监测模型

分布式网络监测系统能够实时有效地收集网络性能数据,但收集过程受到链路延迟和路由跳数的约束．链路约束的分布式网络监测模型研究如何在链路约束下用最小的代价部署整个分布式网络监测系统;链路约束的演化网络监测模型研究在网络演化的情况下,如何用最小的更新代价重新部署监测系统使之满足链路约束．求取这两个模型的最优解的问题都是NP难的．通过指定权函数的形式,两个模型对应的最优化问题能够映射成带权的集合覆盖问题,采用贪婪策略能够得到近似比不超过ln n＋1的近似算法,其中n是被监测节点的数目．通过仿真实验还讨论了如何选择恰当的链路延迟约束值．     

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.     

Finding a Feasible Solution for a Class of Distributed Problems with a Single Sum Constraint Using Agents

In this paper, we describe a Multi-Agent System which is capable of finding a feasible solution of a class of distributed problems, in which the subproblems share a single a sum constraint. Emphasis is given to correctness issues and termination detection.     

Boosting Search with Variable Elimination in Constraint Optimization and Constraint Satisfaction Problems

There are two main solving schemas for constraint satisfaction and optimization problems: i) search, whose basic step is branching over the values of a variables, and ii) dynamic programming, whose basic step is variable elimination. Variable elimination is time and space exponential in a graph parameter called induced width, which renders the approach infeasible for many problem classes. However, by restricting variable elimination so that only low arity constraints are processed and recorded, it can be effectively combined with search, because the elimination of variables may reduce drastically the search tree size.In this paper we introduce BE-BB(k), a hybrid general algorithm that combines search and variable elimination. The parameter k controls the tradeoff between the two strategies. The algorithm is space exponential in k. Regarding time, we show that its complexity is bounded by k and a structural parameter from the constraint graph. We provide experimental evidence that the hybrid algorithm can outperform state-of-the-art algorithms in constraint satisfaction, Max-CSP and Weighted CSP. Especially in optimization tasks, the advantage of our approach over plain search can be overwhelming.     

Guided Genetic Algorithm and its Application to Radio Link Frequency Assignment Problems

The Guided Genetic Algorithm (GCA) is a hybrid of Genetic Algorithm and Guided Local Search, a meta–heuristic search algorithm. As the search progresses, GGA modifies both the fitness function and fitness template of candidate solutions based on feedback from constraints. The fitness template is then used to bias crossover and mutation. The Radio Link Frequency Assignment Problem (RLFAP) is a class of problem that has practical relevance to both military and civil applications. In this paper, we show how GGA can be applied to the RLFAP. We focus on an abstraction of a real life military application that involves the assigning of frequencies to radio links. GGA was tested on a set of eleven benchmark problems provided by the French military. This set of problems has been studied intensively by a number of prominent groups in Europe. It covers a variety of needs in military applications, including the satisfaction of constraints, finding optimal solutions that satisfy all the constraints and optimization of some objective functions whenever no solution exist (partial constraint satisfaction). Not only do these benchmark problems vary in problem nature, they are reasonably large for military applications (up to 916 variables, and up to 5548 constraints). This makes them a serious challenge to the generality, reliability as well as efficiency of algorithms. We show in this paper that GGA is capable of producing excellent results reliably in the whole set of benchmark problems.