自适应分形：大规模群体控制的确定性混沌约束

导语

用传统的方法来解决诸如在一个战场空间中控制成千上万个实体的大规模集群或移动自组网无线电之类的问题是具有挑战性的。进入或离开这个空间的实体需要有某种协调手段或已知的约束。此外，每个实体应该对所有其他实体的相对位置有一定的了解，而不会因为组合爆炸而产生过高的计算成本。这可能会排除量子状态空间类型的方法，其中每个实体都是计算唯一的单位向量。为了控制这种行为，并允许自组织移动自组网中继节点以及集体群控制，作者使用了一种基于确定性混沌的拓扑结构——分形。约束实体“相信”它们只存在于自适应分形的边界内，迫使它们的拓扑布局映射到拓扑集群。分形拓扑的不变特征允许每个节点计算迭代函数系统，以有效地“知道”所有其他实体的相对位置，并形成自适应、自修复的移动自组织网络或集群。给出了自适应分形的许多可能方程之一，计算量复杂度为O(n)。由于它使用一个浮点数，每个实体/节点确定所有太空战场实体相对位置的计算量很小，因此每个实体都可以近乎实时地实现态势感知。该论文使用Mathematica编写的不同自适应分形拓扑进行动力学模拟。本文收录于国际复杂系统会议（ICCS2020）论文集。

研究领域：大规模群体动力学，自适应分形，大型自组织网络

Josef Schaff | 作者

李倩倩 | 译者

刘培源 | 审校

邓一雪 | 编辑

1. 问题：

在空间分布的大型动态网络中进行缩放

美国国会研究报告《网络中心战》[1]表明，缩放限制（scaling limitations）会影响大型动态网络（如太空战场）所需的大量网络节点，并导致边缘节点通信的丢失。而当前用于确定动态变化的网络连通性的方法，会导致大量路由排列的组合爆炸，进而不可计算。为了提高以网络为中心的云和智能集群的可用性和弹性，自组织节点必须通过使用共享拓扑数据来快速自组织。此外，拓扑会影响在线攻防中网络的失败或成功。大型网络上动态节点之间拓扑信息的有效共享允许快速的自组织发生，从而支撑了网络弹性。一个新兴的视角——涌现的宏观（即多智能体世界）可以解决计算的难题，例如对于节点数量超过10,000的大型网络，影响其点对点网络（ad-hoc network）和自适应集群（adaptive swarms）的自组织。因此，需要定义一种方法来实现这样的解决方案。

1.1大型点对点网络路由问题和解决方案

复杂系统中普遍存在的涌现现象，可能会造成多系统构成的大规模系统（large-scale system of systems，SOS）的局限性。Bar-Yam[2]讨论了复杂性科学对大型网络中心拓扑环境的潜在影响。虽然复杂系统的这些涌现行为如果不加以约束可能会导致问题，但它们也可能为涌现网络拓扑提供解决方案。正如Bar-Yam[2]所描述的那样，由于拓扑分布的节点需要共享本地和远程信息，因此观察自然如何创建自组织是明智的。自然界中使用的一种方法叫做间接通信（Stigmergy）[3]。这是对稀疏密集信息的共享[4]，在这种情况下，行为会受到不同拓扑结构的影响，特别是对于分布式网络节点[5]。

人们对互联网和较小的网络拓扑进行了深入的研究，以了解它们的积极属性和潜在弱点，正如Kleinberg等人所描述的那样，它们能够抵御随机故障，同时容易受到针对少数关键节点的攻击[6]。此外，这为开发弹性拓扑提供了理论依据，与互联网不同[7]，同时缓解了由于节点数量巨大而产生的不必要的涌现行为[2]。复杂网络的数学描述[8]、其构造[2]和涌现顺序[9]有助于指导我们寻找弹性点对点网络的数学拓扑。

1.2从混沌到迭代顺序：应用分形和迭代函数系统 (迭代函数系统)

许多现实世界的现象是自相似的（即整体的较小部分可以迭代缩放以表示整体）。例子包括有着大小枝杈的树、花椰菜；有多个卫星的行星，有多个行星的太阳系；可以向上缩小和向下放大的海岸线；还有许多其他现象。大量现象可以用递归生成函数或迭代函数系统来表示，迭代函数系统（Iterated Function Systems）通常能够生成分形[10–12]。迭代函数系统通过构建自身的许多副本并叠加这些副本来生成分形图案，从而生成分形形状。副本是原始形状的仿射变换（affine transformations），通常是收缩仿射或原始形状的缩小副本。这个迭代函数系统是一组压缩仿射元素的结果，通过使用Hutchinson算子，它收敛到一个唯一的吸引子[13]。这些仿射变换的覆盖在数学上是这些函数变换形状的并集，这些形状创建了分形拓扑。

这些生成函数可以迭代到相对于现实世界观察所需的行为保真度。这意味着，尽管真正的分形可能是无限的，但我们可以将迭代函数系统的计算提高到几乎任何任意水平，并且仍然可以看到由此产生的涌现斑图（emergent pattern，译为涌现斑图或涌现模式，类似于全息图，全息图的每个小元素仍然包含足够的关键属性来重建完整的图像）。

静态还是动态？

上面的方法会给我们一个静态的画面，但是一般的动态系统呢？这确实是我们世界的本质——动态的。如果我们考虑另一种方法，即使用自适应的独立迭代函数系统来生成唯一的自组织斑图（pattern）合集，并让这些斑图集演化为有序结构的表示，会怎么样？这种动态的迭代函数系统将适应、变形和扭曲分形，以便在获得新的节点时容纳它们（例如，实体可以加入或离开群或自组织网络）。因为分形是自相似的，所以它们的基本部分可以各自代表现实世界的一个方面。这种“橡胶”分形（rubber fractal）可以伸展和适应，本质上是结合或收缩成一组稳定的斑图。通过类比，这个分形上的顶点（vertices）将与真实世界的参数相关联。这产生了一种范式，允许机器表现得更接近自然现象的动力学机制。

动态迭代函数系统——是什么？

下面描述的动态迭代函数系统只是可能无限多的新的或未知的数学函数之一，这些函数不是从形式证明和现有的数学函数中导出的，而是使用实验数学进行研究的产物。在此背景下，它是作者从Barnsley的“混沌游戏”[11，14]的一个方面推导出来的，是一种简单的线性算法，只需要最小的计算能力就能生成可重复和可预测的复杂系统。这种特定的算法，作者命名为非预定参数随机（Non-predetermined Parametric Random，NPPR）迭代函数系统[15]：创建一个自适应分形，其形状由许多自相似或重复斑图中的点形成，最小尺度上类似于树的末端枝杈，在最大尺度上则类似于树干。

这个动态迭代函数系统是从拓扑上表示节点或简单主体位置的点创建的。这些节点的位置被映射到迭代函数系统方程，该方程依赖于几个参数，特别是成为吸引子的初始点或顶点的小子集（例如，移动实体的目标或航路点）和标度缩放因子（contractive scaling factor）。当缩放因子接近+1或-1时，系统显示节点随机分散。当缩放因子接近0时，这些点在任意吸引子周围聚集成集群（cluster，集群或团簇），覆盖所有吸引子顶点。这些涌现集群提供了点对点通信链路所需的拓扑，以及集群间路由拓扑的选择。

这解决了几个问题，包括那些与拓扑分布式网络或集群相关的问题。它还通过信息共享创建涌现解决方案，解决了一些目前难以解决的分布式信息问题。当所有节点共享少量信息密集的数据（在本例中是顶点位置和缩放因子值）时，就会产生一个共识主动性的（stigmergic）解决方案。通过每个节点了解这些稀疏的数据量，它们各自都可以重建复杂系统的整个拓扑结构。

## 译注：stigmergy共识主动性，社会网络中生物个体自治的信息协调机制。在没有中枢控制和接触交流的条件下，群体通过同频共振，达到信息对称，然后独立行动，相互修正，自我更新，逐步完善群体的生态环境。共识主动性一般表现为生物界的自组织或人类的民主，在本文中被拓展应用于信息网络和自组织集群等。

这就缩小了我们使用动态迭代函数系统方法的范围。该方法产生依赖于一个或多个变量中相对较小的变化的涌现解决方案。这一解决方案还需要表示大型点对点自组织网络中的随机变化。最后，每次将相关参数设置为相同的值时，结果都需要是可重复的。通过将网络传感器数据添加到系统中，非预定参数随机迭代函数系统（NPPR IFS）可以修改（适应）自身以适应动态变化的环境或变化的威胁行为。网络化的智能主体中之间的通信，将允许共享知识来增强和更新每个主体的知识地图[13]，促进网络环境中一致地共享知识。

非预定参数随机自适应分形——工作原理与软件工具内容显示

类似于线的简单点斜率方程，我们给出确定性混沌方程如下:

X(n-1)是当前点，X(n)是下一个点，M是标度缩放参数（scale parameter），它控制当前节点生成下一个点之间的距离，Z对应于随机选择的“顶点”之一，这些顶点是约束所有网络节点的一组初始点，在我们的例子中可以表示网络集线器。如果需要，初始点的数量可以从3个到超过100个不等，尽管实验结果表明，大多数独特的涌现行为是用12个或更少的初始点观察到的。特定的Z是从这组初始点中随机选择的。M的值为0 < |M| < 1，需要实验发现才能确定什么样的M值能给出期望的涌现行为。一旦确定了这些值，在相似的拓扑中，用选定的M和相同数量的初始点对该方程进行的任何随机运行，都将产生相同的整体拓扑结构。这是特别有趣的，因为改变随机数种子几乎不会对生成的拓扑产生明显的影响，尽管事实上所有的点都是新生成的。这还证明了该数学函数是属于确定性混沌的。变量M和变量Z都具有影响整个网络拓扑的相互依赖性，包括控制集群的程度，以及在不同尺度上特定集群子集之间的隐式映射。

该算法具有“可调”值，可控制从有序到混沌的可重复转变。这是由与初始顶点集耦合的变量M控制的。除了为网络路由生成拓扑图之外，生成的数据点还可用于创建几类信息。这些信息可以来自传感器数据，包括与特征类别相关联的几个特征，并且可以由拓扑关系来表示。如果位于不同位置的几个传感器检测到同一个位置的东西，但对其进行了不同的分类，那么传感器的数据将映射到多个相关的类别中。“拓扑地图”（topological map）将包含传感器位置和数据，并将它们之间的关系联系起来，同时保留差异。这允许共享信息定义那些不同但又常见的特征。传感器元件之间传输的少量数据可用于共享传感器节点的全局图像，即共识主动性关系。大自然也使用类似的研究方法，比如蚂蚁和其他群居昆虫标记一个感兴趣的地点。当其他蚂蚁经过标记的位置，它们也会标记它，足够多的标记会使所有蚂蚁跟随地标的踪迹。这一小块信息会变得非常强大，类似于非预定参数随机算法中用于定义行为的稀疏数据元素。为了研究非预定参数随机算法，在Mathematica®中构建了一个工具，用于显示用户动态进行的参数更改。

对比图1中的两幅图，可以看到初始点之间的关系，也可以认为是五个类别的拓扑表示，每个吸引子/顶点代表一个类别。如前所述，每张图片中左上角（较小）的矩形包含五个点，表示空间分离的初始类别（在本数据分析示例中）。每张图片中的大矩形中的一组聚类点代表数据。左图显示了由类别的对称布局产生的对称集群（symmetric clusters，对称集群）。当左下类别顶点移动到更靠近其他类别时，聚类数据点会发生变化，以匹配相对的类别位置。

图1. 一个顶点被移动

为了观察参数M对拓扑结构的影响，在图2中，M被选为大于0.5的值，五个初始点的结果模式是随机散射，这将是默认模式，任何人都可以使用非预定参数随机算法的随机方面的简单函数。现在，在图3中，M变为0.33左右，其结果与经典电子游戏《太空入侵者》相似。本章末尾还包括其他示例模式。

图2. M>0.5

图3. M~0.33

从上面我们可以看到，图3中出现的集群模式是由图2中看似随机的点云产生的。因此，在这种情况下，对于5个顶点，将标度缩放参数M从大约0.5或更大改变到大约0.33会导致该顺序出现。将图片划分为平铺部分的线条是对屏幕上的点应用Voronoi 函数映射的结果。Voronoi 镶嵌提供了一种无偏的方法来确定哪些点映射到一个特定聚类。这避免了由于估计集群开始和结束的位置或集群位于某个位置的错觉（即pareidolia）而导致的人为错误或偏见。Voronoi 并非万无一失，因为有时集群的某些部分会出现在两个镶嵌盘之间的边线上。但它为集群何时易于分离提供了一个通用指标。

1.3建议的解决方案：应用非预定参数随机算法解决自组织路由问题

我们现在有足够的信息来解决我们的大型自组织网络路由问题。使用图3中所示的先前高度结构化的拓扑，我们现在添加路由，并定义通信距离。这个结果我们标记为图4，就像标记为图3一样。

图4. 图3的路由标记

图中的五个主要集群，即每个Voronoi图块为一个主要集群（clusters），其被划分为五个子集群（sub-clusters），其中一个子集群以紫色圈为例。由于迭代函数系统的自相似性质，这些子集群再次被划分为子子集群（sub-sub-clusters），并进一步细分。让我们假设包含集群的窗口是指向这些点所在的区域一个二维映射。让我们假设屏幕上的每一个最小点都对应于一个自组织无线电（或物联网设备），这个设备可能位于某个智能主体或无人机内。请注意，这张图片中的每个单独的点都不是显式可见的，因为该工具此次运行绘制了20,000个唯一的点，其中许多点是紧密聚集的。对于用紫色圈起来的子集群，让我们假设圆的直径是两个节点之间点对点通信的一般范围。最后，选择两个节点（实际上为了便于查看，选择了两个子集群），并用绿色圈标记。为了显示路由，在窗口的对角两端选择了绿色圆圈节点。

由于每个节点都能够计算出所有其他节点的总体布局，因此它能够决定将自己的消息哪个方向，以用于其路由的下一站或下一跳，如图4中的红色弧线所示。涌现的自相似性使其更容易，因为尽管节点是随机迭代的，但总体拓扑将保持自相似，至少对于标度缩放参数M的某些值而言是如此。如果每个节点都知道其范围限制，即紫色圆圈的直径，那么它将在其范围边缘以适当的方向向子集群广播，以到达目标节点。

每个节点都有计算所有其他节点的位置所需的信息，在本例中，这些信息由五个顶点的位置和标度缩放参数M的值组成。随着顶点位置的改变或M的改变，这些值可以在短时间内广播到所有节点。对于任何现代化的处理节点来说，重新计算都是微不足道的，因为它由一个线性加法和一个浮点数作为乘法器组成。这些节点拓扑的内部计算为所有节点提供了创建与整体拓扑一致的内部世界模型的能力，因此能够派生出一个共享世界模型。这就为节点之间的通信提供了一个共同的理解，即使参数动态变化。

遍历点对点网络连接

当我们沿着从源节点到目的地的路线移动时，最容易的方法是按某种顺序对集群和子集群进行编号。任意地，让我们在每个集群和子集群内顺时针移动，从左下角开始，到右下角结束。因此，对于左下方的绿色圆圈节点，我们可以用三个数字（cluster集群、sub子集群、sub-sub子子集群）来表示这些集群元素，如1，2，1。红色弧线表示每个节点范围限制内的每一跳的路径。从1，2，1中的绿色圆圈节点到4，4，5中的目的地绿色圆圈节点的大致跳跃顺序如下：

1, 2, 1 to 1, 3, 3 to 2, 5, 1 to 2, 4, {3, 4, or 5} to 3, 2, 1 to 3, 3, 2 to 3, 4, {1 or 2} to 4, 2, 2 to 4, 3, 2 to 4, 4, {3, 4, 5}。

大括号表示近似的跳数，因为大括号中的所有节点都在范围内，所以如果一些节点不可用，其他节点可以代替它们。

虽然选择的确切路由可能并非每次都是最优的，但这种类型的路由拓扑为边缘节点和更集中的节点提供了弹性能力的度量。因为即使某些子集群和子集群丢失了多达一半的节点，通信路由也可以工作。与现有的自组织路由协议相比，它有一个明显的优势。例如AODV协议（ad-hoc On Demand Distance V-Vector routing），在路由发现过程中存在较大的延迟时间。相反，这种使用非预定参数随机的方法只需要计算几个路由排列，就可以找到一条高效（尽管不是最优）的路由。

这种自适应分形拓扑也可以应用于大规模群体的涌现组织，因为一个参数的变化可以导致整个自动驾驶群体产生涌现群集行为[17]，或者分散成随机模式。共享的共识主动性世界模型仍然是已知的，尽管节点随机分散，但额外的消息仍可以被路由传递。这种群体应用程序还可以为许多车辆（或无人机）提供单点控制，这些车辆的目标是到达几个目的地（即顶点可以代表目的地）。

2. 结论和未来工作

涌现行为通常被视为一种倾向性，尽管涌现行为在自然界中得到已经得到有效利用（例如结晶、成群的鸟等）。当前解决系统的系统（system of system，SOS）的方法没有利用这些，甚至可能没有考虑到大规模系统中出现的涌现行为[18]。一般来说，这些系统的系统会表现出广泛的复杂行为，从有序的预测行为到完全混沌的行为。到目前为止，一些标度的问题还没有成功解决，如大规模群体行为和大型点对点自组织通信网络的路由动力学。使用适当选择的约束条件，随机迭代函数系统（如非预定参数随机方法）可以收敛到有序模式[19]，并动态地适应环境的变化。这种涌现拓扑为大规模分布式智能体感知[20]提供了解决方案，并适用于认知传感器、通信节点和智能群体等。

参考文献

1. Library of Congress, Congressional Research Service. Network centric operations: background and oversight issues for Congress (Report Order Code RL32411) (2007). https://www.fas.org/ sgp/crs/natsec/RL32411.pdf. Accessed 02 Jan 2015

2. Bar-Y am, Y .: About engineering complex systems: multiscale analysis and evolutionary engineering (2005). https://necsi.edu/research/multiscale/ESOA04.pdf. Accessed 01 Apr 2017

3. Stygmergy. https://en.wikipedia.org/wiki/Stygmergy. Accessed 01 May 2016

4. Masoumi, B., Meybodi, M.R.: Speeding up learning automata based multi agent systems using the concepts of stigmergy and entropy. Expert Syst. Appl. 38(7), 8105–8118 (2011)

5. Dagon, D., Guofei, G., Lee, C.P ., Wenke, L.: A taxonomy of botnet structures. In: Computer Security Applications Conference, 2007, ACSAC 2007, pp. 325–339. ACSAC (2007)

6. Kleinberg, J., Sandler, M., Slivkins, A.: Network failure detection and graph connectivity. In: SODA ‘04 Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 76–85. Society for Industrial and Applied Mathematics, Philadelphia (2004)

7. Dorogovtsev, S., Mendes, J.: The shortest path to complex networks. Am. J. Med. Genet. 71, 47–53 (2004)

8. Shargel, B., Sayama, H., Epstein, I., Bar-Y am, Y .: Optimization of robustness and connectivity in complex networks. Phys. Rev. Lett. 90(6) (2003)

9. Bak, P ., Tang, C., Wiesenfeld, K.: Self-organized criticality: an explanation of 1/f noise. Phys. Rev. Lett. 59, 381–384 (1987)

10. Park, K., Willinger, W.: The internet as a large-scale complex system. In: Santa Fe Institute Studies on the Sciences of Complexity, Oxford University Press, New Y ork (2005)

11. Barnsley, M.F.: Fractals Everywhere. Academic Press, San Diego, CA (1988)

12. Demko, S., Hodges, S., Naylor, B.: Construction of fractal objects with IFS. Comput. Graph. 19(3), 271–278 (1985)

13. Peitgen, H., Jurgens, H., Saupe, D.: Chaos and Fractals: New Frontiers of Science. Springer (1992)

14. Barnsley, M.F., Vince, A.: The chaos game on a general iterated function system. Ergodic Theory Dyn. Syst. 31(4), 1073–1079 (2010)

15. Schaff, J.: Creating human-like behavior in a UA V: a counter-terrorism model. In: Proceedings of the Fourteenth Annual Software Technology Conference (2002)

16. Diacu, F.: The solution of the n-body problem. Math. Intell. 18(3), 66–70 (1996)

17. Reynolds, C.: Flocks, herds and schools: a distributed behavioral model. In: SIGGRAPH ‘87: Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, pp. 25–34. Association for Computing Machinery (1987)

18. Office of the Deputy Under Secretary of Defense for Acquisition and Technology: Systems and software engineering. Systems engineering guide for systems of systems, version 1.0. ODUSD(A&T) SSE, Washington, DC (2008)

19. McKelvey, B.: Complexity science as order-creation science: new theory, new method. ECO 6(4), 2–27 (2004)

20. Brooks, R.A.: Intelligence without reason. In: IJCAI’91 Proceedings of the 12th International Joint Conference on Artificial Intelligence, vol. 1, pp. 569–595. Sydney (1991)

（参考文献可上下滑动查看）

原文地址：

https://link.springer.com/chapter/10.1007/978-3-030-67318-5_18

复杂科学最新论文

集智斑图顶刊论文速递栏目上线以来，持续收录来自Nature、Science等顶刊的最新论文，追踪复杂系统、网络科学、计算社会科学等领域的前沿进展。现在正式推出订阅功能，每周通过微信服务号「集智斑图」推送论文信息。扫描下方二维码即可一键订阅：

推荐阅读

点击“阅读原文”，追踪复杂科学顶刊论文