东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

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

ISSN号：1000-1239
期刊名称：计算机研究与发展
时间：0
页码：1831-1839
语言：中文
分类：TP393[自动化与计算机技术—计算机应用技术;自动化与计算机技术—计算机科学与技术]
作者机构：[1]吉林大学计算机科学与技术学院,长春130012, [2]吉林大学符号计算与知识工程教育部重点实验室,长春130012
相关基金：国家自然科学基金重大项目（60496321）;国家自然科学基金项目（60573073,60503016,60603030,60773099,60703022）;国家“八六三”高技术研究发展计划基金项目（2006AA10Z245,2006AA10A309）;吉林省科技发展计划基金重大项目（20020303）;吉林省科技发展计划基金重点项目（20060213）,吉林省科技发展计划基金项目（20030523）;欧盟项目TH/Asia Link/010（111084）
相关项目：复杂时空推理及应用研究

关键词：分布式约束优化问题, 多AGENT系统, 自组织, 分散式算法, 分治法, distributed constraint optimization problem DCOP, multi-agent system, self- organization, decentralized algorithm, divide and conquer

中文摘要：

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

英文摘要：

Distributed constraint optimization problem （DCOP） is a kind of optimization problem oriented to large-scale, open and dynamic network environments, which has been widely applied in many fields such as computational grid, multimedia networks, e-business, enterprise resource planning and so on. Besides the features such as non-linear and constraint-satisfaction which the traditional optimization problems have, DCOP has its distinct features including dynamic evolution, regional information, localized control and asynchronous updating of network states. It has become a challenge for computer scientists to find out a large-scale, parallel and intelligent solution for DCOP. So far, there have been a lot of methods for solving this problem. However, most of them are not completely decentralized and require prior knowledge such as the global structures of networks as their inputs. Unfortunately, for many applications the assumption that the global views of networks can not be obtained beforehand is not true due to their huge sizes, geographical distributions or decentralized controls. To solve this problem, a self-organizing behavior based divide and conquer algorithm is presented, in which multiple autonomous agents distributed in networks work together to solve the DCOP through a proposed self-organization mechanism. Compared with existing methods, this algorithm is completely decentralized and demonstrates good performance in both efficiency and effectiveness.

同期刊论文项目