【作者】 黄晶；

【导师】 刘大有；

【作者基本信息】 吉林大学 ， 计算机应用技术， 2008， 博士

【摘要】 分布式约束优化问题是在大规模、开放、动态分布式网络环境中的优化问题,除了具有传统优化问题的非线性、约束性、建模困难等特点外,还具有随机、动态演化、信息局部化、控制分散化和网络状态异步更新等特点。针对分布式约束优化问题的特征,本文研究基于多Agent系统求解分布式约束优化问题的方法。本文的主要研究内容包括:(1)系统分析了基于多Agent系统求解分布式约束优化问题所涉及到的相关概念、理论和方法;(2)分析和总结了分布式约束优化问题的研究现状和存在问题,提出了基于多Agent系统求解分布式约束优化问题的一般方法,并给出了相应的算法SODC;(3)分析了现有复杂网络聚类算法存在的问题,进而在SODC基础之上,提出了一个基于自组织多Agent系统的分散式网络聚类算法D-P*;(4)分析了强化学习和Q-学习算法的特点和本质,提出了一种基于多Agent系统的分布式Q-学习算法MQ-L;(5)研究了移动Agent在电子商务领域的应用,分析和讨论了建立自主拍卖系统所涉及的主要问题,基于博奕论,提出了一种面向移动Agent的自主拍卖模型;(6)分析和指出现有中间件技术存在的不足,采用Agent技术和本文提出的分布式约束优化问题求解策略,提出一种支持Web智能应用系统快速开发和高效运行的Agent中间件解决方案,并开发了基于Agent中间件的Web智能系统集成开发平台和一批面向不同生产领域的专家系统。本文在基于多Agent系统的分布式约束优化问题求解、复杂网络聚类、增强学习、电子商务拍卖模型等方面的研究具有重要的理论意义和应用价值,丰富了多Agent系统和分布式约束优化问题求解的研究。更多还原

【Abstract】 With the development of the communications infrastructure, computer technology and the applications of computer network, a passel of difficult requirements of new applications have occurred in the fields of scientific computing, business activities and so on. The distributed constraint optimization problem (DCOP) is one typical problem among them. The 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 (ERP) and so on. Besides the features such as non-linear and constraint-satisfaction which traditional optimization problems have, the 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 researchers to find out a large-scale, parallel as well as intelligent solution for the DCOP.Decentralized control in terms of multi-solver rather than central and global control is adopted by a desired DCOP solving mechanism. During the DCOP solving process, multi solvers autonomously run . Each solver possesses regional knowledge of the problem in question, but not the global information of the whole problem space. The compute environment where the multi solvers situate is not static but dynamically evolving. Because the agent technology matches most features of the DCOP solving mechanism, it has been considered as a promising solution to it. However, the problem solving system of the DCOP is required to be self-adaptive for dealing with the stochastic and dynamically evolving features of the DCOP. Furthermore, it is also required to be self-organized due to the features of regional information, localized controlling and asynchronous updating of network states However, the solving mechanism for the DCOP provided by current agent technologies can not meet above requirements. So, To present a general approach for solving the DCOP by considering the features of the DCOP and integrating the self-adaptive and self-organized mechanisms into agent technology is able to not only shed new light to solving large-scale and complex DCOP but also push the academic and industrial research of agent technology. Based on the analysis of related research and existing methods, we put forward a self-organized multi-agent based general approach to solving the DCOP. Using this approach, facing the all kinds of DCOPs in different fields such as complex network analysis, multi-agent learning, e-business and middleware based Web intelligent application system, the thesis has presented several specific multi-agent based algorithms for different DCOPs. The main results obtained by this thesis are listed as follows:(1) The thesis has analyzed the related concepts, theories and methods about solving DCOP based on self-organized multi-agent, including the concepts and features of agent, distributed artificial intelligence and multi-agent system, self-organization theory, swarm intelligence, constraint optimization problem, distributed constraint optimization problem, distributed complex network clustering, multi-agent learning, auctions in E-commerce based on agent, and so on.(2) The thesis has presented a general approach to solving the DCOP based on self-organized multi-agent. After analyzing and summarizing the existing research methods for solving DCOP, this thesis has pointed out the shortcomings of the existing algorithms for solving DCOP. So far, there have been a lot of methods for solving DCOP. 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 we can obtain the global views of networks beforehand is not true due to their huge sizes, geographical distributions or decentralized controls. To solve this problem, this thesis has presented a general approach to solving DCOP based on self-organized multi-agent. The method is named as SODC. Compared with the existing algorithms, the SODC has two main advantages. Firstly, it is a completely decentralized algorithm. Without global information of the whole network, it demonstrates the self-organizing behaviors based on divide and conquer strategy, in which multiple autonomous agents distributed in networks work together to solve the DCOP through a proposed self-organization mechanism. Secondly, it demonstrates better performance in both efficiency and effectiveness.(3) The thesis has presented an agent based decentralized algorithm for clustering complex networks. After thoroughly analyzing the complex networks’structures and the features of existing algorithms of complex network clustering, this thesis has shown that though many related methods have been proposed and applied to different areas including complex network analysis, gene network analysis and web clustering engine, most of them are centralized. They need centralized disposal strategy and are not suitable for dealing with distributed networks, whose global structures are hard to be obtained due to their huge sizes, geographical distributions, decentralized controls or updating randomly. In this thesis, based on the SODC, we present a multi-agent based decentralized algorithm called as D-P*, in which a group of autonomous agents work together to cluster a network through a proposed self-aggregation and self-organization mechanism. Compared with the existing algorithms, the D-P* runs concurrently and asynchronously without any synchronized mechanism. It is able to rapidly find an approximately optimal network cluster structure hidden in the given network.(4) The thesis has presented a distributed multi-agent Q-learning algorithm. After analyzing the features and the essence of reinforcement learning and Q-learning, this thesis has shown that the typical Q-learning algorithm is not suitable for multi-agent learning because the size of state-action space is huge and will exponentially grow as the number of agents increasing and that multi-agent learning is more widely than single agent learning. Based on the SODC, the thesis has presented an online multi-agent learning algorithm called as MQ-L. It integrates many good features such as sharing Q function, dynamic updating search strategy and action-state space pruning and so on. Essentially, the MQ-L is an approach to solving distributed constraint optimization problem, in which multiple agents collaborate to maximize their sharing Q function defined beforehand based on their respective local information. Experiments have shown that the MQ-L algorithm greatly improves the performance of multi-agent learning compared with the typical Q-learning algorithm.(5) The thesis has investigated the application of mobile agent in e-commerce. After analyzing and discussing the main issues in establishing autonomous auction system, the thesis has shown that multi-agent based auction system is a distributed constraint optimization problem in essence. An agent plays with others based on its local information and constraint conditions to maximize its own cost function. However, distinct from all DCOPs discussed above, agents in the auctions compete rather than work together with others to maximize their own profits. According to some predefined auction protocols, agents in an auction system compete as well as compromise each other in order to get into a fix point state corresponding to a globally optimal solution in which every agent’s profit is maximized. Based on the SODC and the game theory, the thesis has presented a mobile agent based autonomous auction model. The model supports to model auction hall, search auction hall, locate trade partners, synchronize different roles involved in an auction transaction and provides two typical auction protocols, which are the first price sealed-bid auction and double auction. After receiving tasks, agents in the model can autonomously search auction halls distributed in networks, take part in auctions and return the final auction results to their respective owners. (6) The thesis has developed a web intelligent system integrated development platform based on agent middleware technology. It has shown that the existing middleware can preferably solve traditional problems frequently occurred in the process of developing distributed systems in most application fields. However, there exist some disadvantages listed as follows: first, it is difficult to support the abstraction, encapsulation and expendability of special issues (especially distributed constraint optimization problems) effectively. Second, it is difficult to meet the requirements of rapid building and effective running web based intelligent application system. Based on the adequate analysis of current middleware and intelligent application system, by adopting the agent technology and the strategies for solving the DCOP presented in above chapters, the thesis has presents an intelligent agent middleware based solution for rapidly building and effectively running the web intelligent applications. It has implemented the collaboration of distributed and heterogeneous intelligent components and permitted accessing, reusing and sharing the distributed and heterogeneous knowledge. The web intelligent application system integrated development platform based on agent middleware and several expert systems for different producing fields have been developed by utilizing the solution. They have demonstrated good results in practice.The research results of the thesis including the general approach to solving the DCOP, the decentralized approach for clustering complex networks, multi-agent reinforcement learning, autonomous auction model for e-business and agent middleware based web intelligent application system, will greatly enrich and push the studies of the DCOP as well as the agent in both theoretical and technological aspects.更多还原