局部信息的分布式联盟结构生成算法

已有的求解最优联盟结构方法大多假定Agent的全局信息已知,采用集中式求解思路,这种假设不适用于分布式环境,且没有充分利用Agent的自治性。在多Agent环境下,个体Agent往往只拥有部分联盟信息并且是自利的,如何在局部信息条件下寻找最优联盟结构是多Agent系统需要解决的关键问题。针对以上问题,基于个体Agent的局部信息及系统整体收益的考虑,通过局部Agent之间的优势信息传递,给出了最优联盟结构的分布式求解算法。该算法的特色是在局部最优假设下,通过局部信息的指导,n个Agent在深度方向上自顶向下对联盟结构图的并行搜索,从而达到缩短搜索时间,降低搜索复杂度的目的,该算法的时间复杂度为O（n2）。     

联盟结构图的性质及应用

形成有效的联盟是多Agent系统的一个重大课题.然而联盟结构的数目很大,对于包含n个Agent系统来说,其可能构成的联盟结构是O(nn),以至于通过穷举搜索最优联盟结构是不可能的.另外联盟结构空间是一个什么样的形态,这是目前为止很少有人系统研究的课题,尤其是其图性质的研究.从图的视点讨论多Agent系统中的最优联盟结构生成问题.首先将联盟结构空间抽象为一个联盟结构图,其中顶点代表联盟结构,有向边代表联盟结构的分解.随后总结和形式化该联盟结构图所具有的两个性质:最优子结构、重复子结构问题;推广了一个性质:关键搜索集;给出了一个新性质:较少冗余路径的图的连通性.为了理解联盟结构图的这些性质,将这些性质用到了有效动态规划法(effective dynamic programming,EDP)中,分析得到其时间复杂度的下界是Ω(2.1n),上界是O(3n).实验分析表明,EDP算法比DP算法的搜索次数更少,在含有21个Agent的系统中,EDP比DP减少42%的搜索次数.     

基于整数二部拆分的最优联盟结构求解

联盟结构是对Agent集合的一个划分,通过联盟形成联盟结构,可以使Agent之间形成有效合作,完成单个Agent所不能完成的任务。本文提出了BIDP来求最优联盟结构,该算法利用整数二部拆分来生成二部划分,并利用二部拆分的界来对搜索空间进行限界。随后把该算法与DP算法做了理论和实验分析,理论上得出BIDP所需要的空间比DP减少33.3%。实验表明,当联盟值满足均匀分布和正态分布,BIDP在21个Agent的情况下,搜索空间比DP减少35%和92%。最后对求最优联盟结构的确定式算法作了总结,即时间复杂度的上界是O(3n),下界是Ω(2n),空间复杂度是Θ(2n)。     

一种快速构建最优联盟结构的方法

联盟结构是对Agent集合的一个划分,通过联盟形成联盟结构,可以使Agent之间形成有效的合作,完成单个Agent所不能完成的任务。然而联盟结构的数目和解空间比较大,以至于通过穷举搜索最优联盟结构是很复杂的。动态规划法通常用于求解具有最优子结构性质和重叠子问题性质的问题,文章在给出了Agent联盟的相关概念之后,论证了构造最优联盟结构问题恰恰具有这两类性质,因此利用动态规划法可以求解。最后给出了相应的算法,并得出采用动态规划法实现最优联盟结构的时间复杂度为O(3n)。     

一种联盟结构的多Agent合作求解算法

为了测试和比较各种先进的多Agent合作求解智能算法,给多Agent合作策略提供一个比较与测试的平台。针对多Agent联盟数量是Agent个数指数倍的问题提出了一种对Agent联盟结构图自上而下的搜索算法,该算法可以对联盟结构图进行化简,降低搜索空间大小。在基于Agent合作收益独立性假设的基础上,证明了同构的联盟结构是最优的收益。最后,以机器人足球赛RoboCup为背景给出了仿真实验,表明了SCS算法的效率。     

基于势结构的任一时间联盟结构生成算法

联盟形成是多Agent系统中的一个关键问题.人们寻求能极大化联盟值总和的联盟结构,但通常情况下可能的联盟结构的数目太大,以致不允许进行穷尽搜索而找出最优解.Sandholm等人已经证明,要建立最坏情况下的限界K(n),搜索联盟结构图的最底两层是必要且是充分的.Dang等人给出的算法是所见到的第1个不以层为单位的搜索算法,对于较小的限界明显地优于Sandholm等人给出的算法.深刻分析了联盟结构间的关系,采用更小的搜索粒度(势结构),提出基于势结构的任一时间算法,在搜索最底两层及顶层后,进一步搜索势结构集合CCS(n,6)对应的未搜索过的联盟结构,渐进地给出越来越低的限界,大大改进了Sandholm等人(快1035倍,当n=100,K=2)和Dang等人(快1018倍,当n=100,K=3)的工作.     

多Agent联盟结构动态生成算法

针对多Agent联盟数量是Agent个数指数倍的问题,基于Agent合作收益独立性,给出了Agent联盟快速动态生成算法--SCS(search of coalition structure)算法;依Agent联盟之间的同构关系,将Agent联盟结构图剪枝,然后进行Agent联盟结构搜索,可降低搜索空间大小,并证明了是剪枝前搜索量的n(k-1)^n-k.最后,以机器人足球赛RoboCup为背景给出了实验分析,表明了SCS算法的效率.SCS算法是     

最坏情况具有限界的联盟结构生成

联盟形成是多Agent系统中的一个关键问题. 寻求能极大化联盟值总和的最优联盟结构是NP-完全的. Sandholm等人已经证明要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的,在搜索联盟结构图的最底两层之后如何进一步搜索,是个长期以来未能解决的问题. Dang等人给出的算法,对于奇数限界k≥3,在搜索最底两层及顶层后,进一步搜索最大联盟的势不小于- n(k-1)/(k+1) - 的所有联盟结构,是迄今所知的第1个不以层为搜索单位的算法,对于较小的限界明显地优于Sandholm等人给出的算法. 文中深刻分析了联盟结构间的关系,提出的算法在搜索最底两层后,只需进一步搜索最大联盟的势等于- n(k-1)/(k+1) - 的所有联盟结构,从而使需要搜索的联盟结构数大大减少,并进一步将搜索某些层最大联盟的势等于- n(k-1)/(k+1) - 的联盟结构巧妙地改为搜索联盟结构数更少的相应层,使需要搜索的联盟结构数进一步减少,较大地改进了Sandholm等人和Dang等人的工作.     

联盟结构图的代数性质及应用

将联盟结构的空间抽象为联盟结构图,并在该图上定义2种运算并和交,从而联盟结构图中所有顶点关于并和交构成代数结构--联盟结构格.为了简化该格性质的研究,又引入整数拆分图,并在联盟结构图和整数拆分图之间建立映射关系F,且由映射关系,诱导一个等价关系E_F.这样在联盟结构图中搜索最优联盟结构时,可以利用某个联盟结构对E_F产生的等价类的上界和平均值作为剪枝函数,当某个等价类的上界低于剪枝函数时,该等价类中的大量联盟结构就被剪枝掉.最后设计一种动态规划算法.实验表明它的有效性.在20个Agent时,它比原动态规划算法减少43%的搜索次数.     

给定限界要求的联盟结构生成

联盟形成是多Agent系统中的一个关键问题,目的是通过寻找使联盟值的总和最大的联盟结构来使系统得到最大的效益。但通常可能的联盟结构的数目太大,不允许穷尽搜索来找出最优解。当实际问题提出最坏情况的具体限界要求时,如何以最小的搜索达到这个要求是需要解决的。文中给出的算法对给定的限界要求K*≥2以最少的搜索层数解决了这个问题。Sandholm等人已经证明,要建立最坏情况下的限界K（n),搜索联盟结构图的最底两层是必要且是充分的,此时限界是n(系统的Agent 数）。以此为基础,文中给出了算法,在搜索最底两层之后,只要搜索一层就能保证K(n)≤3;而在搜索最底两层之后,最多搜索两层就能保证K(n)≤2。与Samdholm等人给出的算法相比,文中给出的算法达到指定限界的搜索量显著减少。     

Call for Papers The 6^th International Conference on Grid and Cooperative Computing

Recent years have seen rapid advances in various grid-related technologies, middleware, and applications. The GCC conference has become one of the largest scientific events worldwide in grid and cooperative computing. The 6th international conference on grid and cooperative computing (GCC2007) Sponsored by China Computer Federation (CCF),Institute of Computing Technology, Chinese Academy of Sciences (ICT) and Xinjiang University ,and in Cooperation with IEEE Computer Soceity ,is to be held from August 16 to 18, 2007 in Urumchi, Xinjiang, China.     

煤矿井下安全监控分站的设计及其仿真实现

为了设计一种具有低成本、低功耗、易操作、功能强且可靠性高的煤矿井下安全分站,针对煤矿安全生产实际,文章提出了采用MCS-51系列单片机为核心、具有CAN总线通信接口的煤矿井下安全监控分站的设计方案;首先给出煤矿井下安全监控分站的整体构架设计,然后着重阐述模拟量输入信号处理系统的设计过程,最后说明单片机最小系统及其键盘、显示、报警、通信等各个组成部分的设计;为验证设计方案的可行性与有效性,使用Proteus软件对设计内容进行仿真验证,设计的煤矿井下安全监控分站具有瓦斯、温度等模拟量参数超标报警功能和电机开停、风门开闭等开关量指示功能;仿真结果表明:设计的煤矿井下安全监控分站具有一定的实际应用价值.     

法律信息库系统

本文分析了法律数据库的结构和特点，介绍了采用面向对象设计方法和超文本数据库技术开发和实现法律信息库系统将作为重要网络资源之一为不同用户进行法律咨询服务。     

View-based model-driven architecture for enhancing maintainability of data access services

In modern service-oriented architectures, database access is done by a special type of services, the so-called data access services (DAS). Though, particularly in data-intensive applications, using and developing DAS are very common today, the link between the DAS and their implementation, e.g. a layer of data access objects (DAOs) encapsulating the database queries, still is not sufficiently elaborated, yet. As a result, as the number of DAS grows, finding the desired DAS for reuse and/or associated documentation can become an impossible task. In this paper we focus on bridging this gap between the DAS and their implementation by presenting a view-based, model-driven data access architecture (VMDA) managing models of the DAS, DAOs and database queries in a queryable manner. Our models support tailored views of different stakeholders and are scalable with all types of DAS implementations. In this paper we show that our view-based and model driven architecture approach can enhance software development productivity and maintainability by improving DAS documentation. Moreover, our VMDA opens a wide range of applications such as evaluating DAS usage for DAS performance optimization. Furthermore, we provide tool support and illustrate the applicability of our VMDA in a large-scale case study. Finally, we quantitatively prove that our approach performs with acceptable response times.     

International Journal of Automation and Computing Table of Contents

正~~     

Information for authors

正SCIENCE CHINA Information Sciences(Sci China Inf Sci),cosponsored by the Chinese Academy of Sciences and the National Natural Science Foundation of China,and published by Science China Press,is committed to publishing highquality,original results of both basic and applied research in all areas of information sciences,including computer science and technology;systems science,control science and engineering(published in Issues with odd numbers);information and communication engineering;electronic science and technology(published in Issues with even numbers).Sci China Inf Sci is published monthly in both print and electronic forms.It is indexed by Academic OneFile,Astrophysics Data System(ADS),CSA,Cabells,Current Contents/Engineering,Computing and Technology,DBLP,Digital Mathematics Registry,Earthquake Engineering Abstracts,Engineering Index,Engineered Materials Abstracts,Gale,Google,INSPEC,Journal Citation Reports/Science Edition,Mathematical Reviews,OCLC,ProQuest,SCOPUS,Science Citation Index Expanded,Summon by Serial Solutions,VINITI,Zentralblatt MATH.     

Erratum to: Fast global kernel fuzzy c-means clustering algorithm for consonant/vowel segmentation of speech signal

正Erratum to:J Zhejiang Univ-Sci C(ComputElectron)2014 15(7):551-563doi:10.1631/jzus.C1300320The original version of this article unfortunately contained mistakes.Algorithm 6 should be as follows:Algorithm 6 FGKFCM-F clustering Input:(1)X={x_1,x_2,…,x_N},,x_iR~d,i=1,2,…,N,the dataset;(2)C,1C≤N,the number of clusters;(3)ε0,the stopping criterion;     

Journal of Zhejiang University-SCIENCE C (Computers & Electronics) Total contents

正~~     

A pragmatic multi-method investigation of discrepant technological events: Coping,attributions, and ‘accidental’ learning

Discrepant technological events or situations that entail a problem, a misunderstanding or a difficulty with the Information Technology (IT) being employed, are common in the workplace, and can lead to frustration and avoidance behaviors. Little is known, however, about how individuals cope with these events. This paper examines these events by using a multi-method pragmatic approach informed by coping theory. The results of two studies – a critical incident study and an experiment – serve to build and test, respectively, a theoretical model that posits that individuals use a variety of strategies when dealing with these events: they experience negative emotions, make external attributions, and adopt engagement coping strategies directed at solving the event, eventually switching to a disengagement coping strategy when they feel they have no control over the situation. Furthermore, users’ efforts may result in ‘accidental’ learning as they try to overcome the discrepant IT events through engagement coping. The paper ends with a discussion of the results in light of existing literature, future opportunities for research, and implications for practice.