复杂网络上多智能体系统的一致性研究

doi:10.11896/j.issn.1002-137X.2019.04.015

摘要/Abstract

摘要： 如何有效提高多智能体系统的一致性收敛速度是一致性问题中的一个重要研究内容。一致性收敛速度可通过拉普拉斯矩阵的最小非零特征值来衡量,文中通过计算机仿真发现,对于不同的复杂网络模型,影响其一致性收敛速度的因素也不同。提高网络一致性收敛速度的具体方法是:在最近邻耦合网络中,减少节点数N或增大耦合数K;在NW小世界网络中,增加节点数N或者增大随机化加边概率p,因为收敛速度与二者具有良好的线性关系;在Waxman随机图网络中,增加节点数N或增大其模型中的参数α和β,当β增大时,收敛速度整体上呈线性增长,但会出现较小的波动。该研究结果对优化多智能体网络的一致性收敛速度有一定的指导作用。

关键词: NW小世界网络, 多智能体系统, 复杂网络, 随机图网络, 一致性, 最近邻耦合网络

Abstract: How to improve uniform convergence rate of multi-agent systems is an important issue in uniform research.The uniform convergence rate can be well performed by the smallest non-zero eigenvalues of the Laplacian matrix.According to the computer simulation,this paper found that the uniform convergence rate is significantly led by different factors in different complex networks.The methods for impraing uniform convergence rate on the different complex networks are listed as follows.For the nearest-neighbor coupled network,the number of nodes N should be reduced,or the number of coupling K should be increased.For the NW small-world network,the number of nodes N should be increased,or the probability of random edged p should be increased.This paper found that the convergence rate has a good linear relationship between the number of nodes N and the probability of random edges p.For the Waxman random graph network,the number of the nodes N should be increased,or the network parameters α and β should be increased.The convergence rate is linear when β increases,but there is a slight fluctuation.The results can help to optimize the convergence rate of multi-agent network.

Key words: Complex network, Consensus, Multi-agent systems, Nearest-neighbor coupled network, NW small-world network, Random graph network

中图分类号:

TP18

张森, 刘文奇, 赵宁. 复杂网络上多智能体系统的一致性研究[J]. 计算机科学, 2019, 46(4): 95-99. https://doi.org/10.11896/j.issn.1002-137X.2019.04.015

ZHANG Sen, LIU Wen-qi, ZHAO Ning. Research of Consensus in Multi-agent Systems on Complex Network[J]. Computer Science, 2019, 46(4): 95-99. https://doi.org/10.11896/j.issn.1002-137X.2019.04.015

参考文献

[1]WANG K,GU L,HE X,et al.Distributed Energy Management for Vehicle-to-Grid Networks[J].IEEE Network,2017,31(2):22-28.
[2]GIL P,MARTINS H,JANUÁRIO F.Detection and accommodation of outliers in Wireless Sensor Networks within a multi-agent framework[J].Applied Soft Computing,2016,42:204-214.
[3]OLFATI-SABER R,MURRAY R M.Consensus problems in networks of agents with switching topology and time-delays[J].IEEE Transactions on Automatic Control,2004,49(9):1520-1533.
[4]FAX J A,MURRAY R M.Information flow and cooperative control of vehicle formations[J].IEEE Transactions on Automatic Control,2004,49 (1):115-120.
[5]MOREAU L.Stability of multiagent systems with time-depen- dent communication links[J].IEEE tran sactions on Automatic Control,2005,50(2):169-182.
[6]ZHAO J C.Pinning control of general complex dynamical net- works with optimization[J].Science China,2010,53(4):813-822.
[7]LIU X,CHEN T.Cluster Synchronization in directed Networks Via Intermittent pinning control[J].IEEE Transactions on Neural Networks,2011,22(7):1009-1020.
[8]HATANO Y,MESBAHI M.Agreement over random networks[J].IEEE Transactions on Automatic Control,2005,50(11):1867-1872.
[9]YANG W.Consensus problem in multi-Agent Systems[D]. Shanghai:Shaihai Jiao Tong University 2009.(in Chinese) 杨文.多智能体系统一致性问题研究[D].上海:上海交通大学,2009.
[10]孙玺菁,司守奎.复杂网络算法与应用[M].北京:国防工业出版社,2015:3-5.
[11]WAXMAN B M.Routing of multipoint connections[J].IEEE Journal on Selected Areas in Communications,1988,6(9):1617-1622.
[12]WATTS D J,STROGATZ S H.Collective dynamics of ‘small-world’ networks[J].Nature,1998,393(6684):440-442.
[13]NEWMAN M E J,WATTS D J.Renormalization group analysis of the small-world network model [J].Physics Letters A,1999,263(4-6):341-346.
[14]MENG Y,JIANG C,CHEN H H,et al.Cooperative Device-to-Device Communications:Social Net working Perspectives[J].IEEE Network,2017,PP(99):12-18.
[15]BENSON A R,GLEICH D F,LESKOVEC J.Higher-order organization of complex networks[J].Science,2016,353(6295):163-166.
[16]BOCCALETTI S,BIANCONI G,CRIADO R,et al.The structure and dynamics of multilayer networks[J].Physics Reports,2014,544(1):1-122.
[17]XU L L,DONG Y H,PAN J F.Survey of Graph Sparsification Algorithms for Complex Networks[J].Computer Science,2018,45(5):24-30,43.(in Chinese) 徐丽丽,董一鸿,潘剑飞,等.面向复杂网络的图稀疏算法综述[J].计算机科学,2018,45(5):24-30,43.
[18]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.
[19]HORN R A,JOHNSON C R.Matrix analysis[M].Cambridge:Cambridge University Press,1985.
[20]OLFATI-SABER R.Ultrafast consensus in small-world net- works[C]∥Proceedings of American Control Conference.New York:IEEE Press,2005:2371-2378.
[21]FIEDLER M.Algebraic Connectivity of Graphs[J].Czechoslovak Mathematical Journal,1973,23(23):298-305.

相关文章 15

[1]	郑文萍, 刘美麟, 杨贵. 一种基于节点稳定性和邻域相似性的社区发现算法 Community Detection Algorithm Based on Node Stability and Neighbor Similarity 计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[2]	周慧, 施皓晨, 屠要峰, 黄圣君. 基于主动采样的深度鲁棒神经网络学习 Robust Deep Neural Network Learning Based on Active Sampling 计算机科学, 2022, 49(7): 164-169. https://doi.org/10.11896/jsjkx.210600044
[3]	何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超. 比特币实体交易模式分析 Analysis of Bitcoin Entity Transaction Patterns 计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[4]	杨波, 李远彪. 数据科学与大数据技术课程体系的复杂网络分析 Complex Network Analysis on Curriculum System of Data Science and Big Data Technology 计算机科学, 2022, 49(6A): 680-685. https://doi.org/10.11896/jsjkx.210800123
[5]	靳利贞, 李庆忠. 基于接缝一致性准则的结构纹理图像快速合成算法 Fast Structural Texture Image Synthesis Algorithm Based on Seam ConsistencyCriterion 计算机科学, 2022, 49(6): 262-268. https://doi.org/10.11896/jsjkx.210400039
[6]	王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[7]	许华杰, 陈育, 杨洋, 秦远卓. 基于混合样本自动数据增强技术的半监督学习方法 Semi-supervised Learning Method Based on Automated Mixed Sample Data Augmentation Techniques 计算机科学, 2022, 49(3): 288-293. https://doi.org/10.11896/jsjkx.210100156
[8]	陈世聪, 袁得嵛, 黄淑华, 杨明. 基于结构深度网络嵌入模型的节点标签分类算法 Node Label Classification Algorithm Based on Structural Depth Network Embedding Model 计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[9]	赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[10]	李家文, 郭炳晖, 杨小博, 郑志明. 基于信息传播的致病基因识别研究 Disease Genes Recognition Based on Information Propagation 计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129
[11]	刘意, 毛莺池, 程杨堃, 高建, 王龙宝. 基于邻域一致性的异常检测序列集成方法 Locality and Consistency Based Sequential Ensemble Method for Outlier Detection 计算机科学, 2022, 49(1): 146-152. https://doi.org/10.11896/jsjkx.201000156
[12]	夏中, 向敏, 黄春梅. 基于CHBL的P2P视频监控网络分层管理机制 Hierarchical Management Mechanism of P2P Video Surveillance Network Based on CHBL 计算机科学, 2021, 48(9): 278-285. https://doi.org/10.11896/jsjkx.201200056
[13]	穆俊芳, 郑文萍, 王杰, 梁吉业. 基于重连机制的复杂网络鲁棒性分析 Robustness Analysis of Complex Network Based on Rewiring Mechanism 计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108
[14]	胡军, 王雨桐, 何欣蔚, 武晖栋, 李慧嘉. 基于复杂网络的全球航空网络结构分析与应用 Analysis and Application of Global Aviation Network Structure Based on Complex Network 计算机科学, 2021, 48(6A): 321-325. https://doi.org/10.11896/jsjkx.200900112
[15]	赵潇, 李仕林, 李凡, 余正涛, 张林华, 杨勇. 局部细粒度信息引导的双循环一致性绝缘子缺陷样本生成 Double-cycle Consistent Insulator Defect Sample Generation Method Based on Local Fine-grainedInformation Guidance 计算机科学, 2021, 48(6A): 581-586. https://doi.org/10.11896/jsjkx.200500026

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed