多智能体中的图论 |
您所在的位置:网站首页 › 图论权转移方法 › 多智能体中的图论 |
目前人工智能分为:大数据智能,跨媒体智能,群体智能,混合增强智能,自主无人系统五类,若想要深入群体智能则图论的基础是非常必要的! 目录 一、引言 1.1、专业词汇: 1.2、图基交互模型 1.2.1、网络科学关注原因 1.2.2、Boids Model 1.2.3、网络系统的组成及挑战 1.2.4、通过局部交互的信息交换 1.2.5、图基交互模型(graph-based interaction models) 二、图论 2.1、专业词汇 2.2、图的相关概念 2.2.1、图、边、点的表示 2.2.2、子图及子图运算 2.2.3、图概念中的其它定义 2.3、图和矩阵 2.3.1、邻接矩阵和度 2.3.2、关联矩阵 2.3.3、图的拉普拉斯表示 2.3.4、代数和谱图论 一、引言 1.1、专业词汇:distributed network:分布式网络 distributed multiagent network:分布式多智能体网络 boids model:柏兹模型(类鸟型) topology:拓扑结构 directed undirected:有向、无向 separation:分隔 alignment:对准 cohesion:内聚 velocity:速率,速度 flocking:群集 formation:编队 robotic network:机器人网络 resolution:分辨率 1.2、图基交互模型 1.2.1、网络科学关注原因(1)大量的学科(尤其生物及材料科学)需要对元素间的交互对于多层级系统所扮演的角色有更深层次的理解 (2)科技的发展促进了综合网络工程系统的能力 1.2.2、Boids Modelboids model由Reynolds结合计算机图形和动画提出,这个模型尝试去寻找社会中鸟群、兽群在集群中排列他们的方式。并提出了以下重要的协议: (1)分隔原则(separation):群体内所有个体有避免相互碰撞的趋势 (2)对准原则(alignment):群体内个体与其相邻个体速度保持一致的趋势 (3)内聚原则(cohesion):群体内所有个体有趋向邻近个体的趋势 根据以上原则,杂乱的方向的图形一段时间后变为右图 (1)网络系统的组成: 动态单元(dynamic units):彼此之间能够传递和发送信息; 信号交换网络(signal exchange network):能够通过有线或者无线协议实现信息交换; (2)网络系统所遇到的挑战: 系统理论不得不混合信息网络数学; 面临跨学科结合,如网络几何学; 1.2.4、通过局部交互的信息交换(1)局部通信 局部通信目前收到以下两点的约束 信息交换频道:传送和接受信息需要能量,因此只有在有限范围能够接受信息,在网络中可通过中间节点来扩大传递范围; 可靠的带宽:如果许多机构同时传播大量的数据,交互频道将会饱和并且会导致通信系统急速的恶化。因此,为了满足带宽要求信息交换应保持过分节俭的。 (2)局部感知 a、视觉传感器(vision-based sensor):能够有很长的有效范围,但为锲型几何区域; b、 范围传感器(range sensor):如声呐、激光雷达(sonars,laser scanners)等,不同传感器有着不同的分辨率和有效范围,为环形全方向; 1.2.5、图基交互模型(graph-based interaction models)交互几何图形将在多智能体网络系统的分析和综合中扮演重要角色,能够让我们集中研究拓扑结构内部连接所起到的作用 一个具有全方向范围传感器机构网络其相应的机构和交互边显示在下图中: edge(边):可描述为能使信息在边连接的顶点之间传递,分为有向和无向(directed or undirected),其中有向是带箭头的单向,而无向是指无箭头的双向; 根据边可能的消失和再现分为三类:静态、动态和随机网络(Static, Dynamic, and Random Networks) 静态网络:边是静态的,即非时变; 动态,状态相关网络:边集可能是时变的,边可能由于网络机构状态的功能消失或再现; 随机网络:由特别的动态网络组成,边是概率发布而非确定性发布。 二、图论 2.1、专业词汇vertex:顶点 subset:子集 subgraph:子图 adjacent vertex:邻接节点 Connected graph:连通图 connected component:连通分量 Isomorphic:同构 boundary:边界 closure:闭合 degree:度 matrix:度 Degree matrix:度矩阵 adjacency matrix:邻接矩阵 spectral:谱 2.2、图的相关概念 2.2.1、图、边、点的表示一个有限的,无向的简单图(或简称为图)是建立在一个有限点集上的,即具有有限数量元素的集合。 将该集称为顶点集,用V表示,那么 现在考虑由 图本质上是一个理论对象的集合,但是,它可以方便地以图形表示。图 顶点 设定对于 如果对于图 无标签图(Unlabeld):为了更清楚的表述图中的逻辑结构,删除各顶点的明确身份信息; 标签图(Labeld):将无标签图重新给予身份,下面分别为无标签和标签图: 同构(isomorphic):对于两个图 完全图(complete graph):每一个顶点均邻接任何一个其他顶点 路径图(path graph):与上诉彼此邻接的 环形图(cycle graph):路径形成闭环 下图中分别为完全图和路径图 (1)子图及生成子图(生成树及生成森林) 子图(subgraph): 事实上对于 生成树(spanning tree):包含连通图中所有的顶点;任意两顶点之间有且仅有一条通路; 生成森林(forest):生成树是对应连通图来说,而生成森林是对应非连通图来说的。非连通图可分解为多个连通分量,而每个连通分量又各自对应多个生成树(至少是 1 棵),因此与整个非连通图相对应的,是由多棵生成树组成的生成森林。 图a中包含有子图b;c为b的边界图(boundary),即为与子图b存在边的点和其够成的边;图d为子图b的闭合图(closure),即为子图b与其边界图的结合。 (2)子图中的操作 边图: 闭合图: (1)赋权图(weighted graphs):如果图G中的每一条边都相应地赋有一个数值 (2)有向图(digraphs):如下图当给图中的边赋予方向,即变为有向图,记为 (3)强连接(strongly connected):有向图中任意两点 上图中V = {v1,v2,v3,v4},边集为{(v1,v3),(v1,v2),(v4,v3)} 2.3、图和矩阵上诉中,确立了图形用顶点和边的表述形式,下面将会建立图形和矩阵的表述形式。 2.3.1、邻接矩阵和度 对于一个无向图G,其内在顶点 度矩阵(degree matrix):一个图形的度矩阵是其顶点度的集合,∆(G),为一个对角矩阵,在对角线上包含了G中的各个顶点度,即: 邻接矩阵A(G)(adjacency matrix):对称的n×n矩阵,邻接矩阵的值为: 上图中的度矩阵和邻接矩阵为: 关联矩阵(incident matrix)D(D):假设在具有n个顶点和m条边的有向矩阵 即对于 上诉的关联矩阵可以看到,每一列的和均为0,这位关联矩阵的共同属性,这是由于每一列为一条有向边,而有向边又对应着头和尾巴(1和-1)。 定义弱连接有向图的循环空间(cycle space)为关联矩阵的零空间(null space),即为D(D)z = 0中z列向量的集合。 假定在关联矩阵D(D)中,一个符号路径向量(signed path vector)是向量z在D中所对应的一条路径(非边),z中第i个指数为+1表示第i条边(edge)是积极遍历(traversed positively)(符合路径遍历方向),-1为消极遍历,0为未在该条路径中使用。 公理:有向图中,一个符号向量Z所对应的通路(path),有着不同的起点和终点,向量y=D(G)z中,第i个元素,其值为1则为起点,值为-1则为终点,0为其他。 定理:一个弱连接连通有向图D,其关联矩阵D(D)的零空间(null space)是由D的循环(cycle)所对应的符号向量路径所决定的。 2.3.3、图的拉普拉斯表示(1)图拉普拉斯矩阵 图G的另一个矩阵描述为图拉普拉斯矩阵(graph laplacian),L(G)。 无向图G拉普拉斯矩阵:(度矩阵-邻接矩阵) 有向图G的拉普拉斯矩阵为: 其中D( 上诉对于有向图和无向图的定义是等效的,并且在无向图计算公式的定义中不需要方向。我们习惯采用D(G)即关联矩阵的方法来计算有向图。抛开方向,有时采取上诉两个定义中的一个对于图的拉普拉斯矩阵是有用的。 赋权图拉普拉斯矩阵: W为一个mXm的对角矩阵,w( (2)边拉普拉斯矩阵 边拉普拉斯(edge laplacian):对于一个任意方向的图G,边拉普拉斯定义为 两个 具有p个连通分量Gi的图G,其关联矩阵为: 图G的边拉普拉斯矩阵具有块对角线矩阵的形式: (3)有向图拉普拉斯(在两个矩阵计算中不包含由于出度导致的度减少) 定义有向赋权图的邻接矩阵为:(即对于 对于对角度矩阵,定义为: 记度矩阵为:(即为A(D)与1列向量的对角阵,这是由于A(D)每一行相加即为 对应的赋权拉普拉斯(内度 in-degree)定义为: 对于所有的有向图,均有(即全部为1的向量是L(D)矩阵中0特征值所对应的特征向量)(N是指矩阵的0空间,即Av=0,由于特征值及其特征向量的计算公式固有v为0特征值所对应的特征向量) 在多智能体网络中我们选择入度(In-degree)而非出度(out-degree),这是由于入度显示机构被其他影响,而出度显示影响其他机构。 2.3.4、代数和谱图论事实上,对于度、邻接、关联、拉普拉斯矩阵特征值的研究属于图论中的子学科,名为谱图论(spectral graph theory)。 图拉普拉斯L(G)是对称且半正定的(特征值均为非负),因此其特征值可写为: 其中: 理论:图G是连通图的充要条件为
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |