精华内容
下载资源
问答
  • 几乎所有不明显的简单过程,都可以看作是具有复杂性相同的计算。 更具体来说,计算等价性原理表明,在自然界中发现的系统可以执行达到最高(“通用”)级别的计算能力的计算,并且大多数系统实际上实现了这种最高...

    五、细胞自动机

    原文:Chapter 5 Cellular Automatons

    译者:飞龙

    协议:CC BY-NC-SA 4.0

    自豪地采用谷歌翻译

    细胞自动机(CA)是一个世界的模型,带有非常简单的物理。 “细胞”的意思是世界被分成一个大口袋,称为细胞。 “自动机”是一台执行计算的机器 - 它可能是一台真机。 ,但更多时候,“机器”是数学抽象或计算机的模拟。

    本章介绍了史蒂文沃尔夫勒姆(Steven Wolfram)在 20 世纪 80 年代进行的实验,表明一些细胞自动机展示出令人惊讶的复杂行为,包括执行任意计算的能力。

    我讨论了这些结果的含义,在本章的最后,我提出了在 Python 中高效实现 CA 的方法。

    本章的代码位于本书仓库的chap05.ipynb中。 使用代码的更多信息,请参见第?章。

    5.1 简单的 CA

    细胞自动机 [1] 由规则来管理,它决定系统如何即时演化。 时间分为离散的步骤,规则规定了,如何根据当前状态计算下一个时间步骤中的世界状态。

    作为一个微不足道的例子,考虑带有单个细胞的细胞自动机(CA)。 细胞状态是用变量xi表示的整数,其中下标i表示xi是时间步骤i期间的系统状态。 作为初始条件,x0 = 0

    现在我们需要一个规则。 我会任意选择xi = x[i-1] + 1,它表示在每个时间步骤之后,CA 的状态会增加 1。到目前为止,我们有一个简单的 CA ,执行简单的计算:它用于计数。

    但是这个 CA 是不合规则的;可能的状态数通常是有限的。 为了使其成立,我将选择最小的感兴趣的状态数 2,和另一个简单的规则xi = (x[i-1] + 1) % 2,其中%是余数(或模)运算符。

    这个 CA 的行为很简单:闪烁。 也就是说,在每个时间步之后,细胞的状态在 0 和 1 之间切换。

    大多数 CA 是确定性的,这意味着规则没有任何随机元素;给定相同的初始状态,它们总是产生相同的结果。 也有不确定性的 CA,但我不会在这里涉及它们。

    5.2 Wolfram 的实验

    前一节中的 CA 只有一个细胞,所以我们可以将其视为零维,并且它不是很有趣。 在本章的其余部分中,我们将探索一维(1-D)CA,后者会变得非常有趣。

    说 CA 有维度就是说细胞被安排在一个连续的空间中,这样它们中的一些可以看作“邻居”。 在一维中,有三种自然配置:

    有限序列:

    数量有限的细胞排成一排。 除第一个和最后一个之外的所有细胞都有两个邻居。

    环:

    数量有限的细胞排列成一个环。 所有细胞都有两个邻居。

    无限序列:

    数量无限的细胞排列成一排。

    确定系统如何即时演化的规则,基于“邻域”的概念,即“邻域”,即决定给定细胞的下一个状态的一组细胞。

    在二十世纪八十年代初,斯蒂芬沃尔夫勒姆发表了一系列论文,对一维 CA 进行了系统的研究。 他确定了四大类行为,每一类都比上一个更有趣。

    Wolfram 的实验使用了三个细胞的邻域:细胞本身及其左右邻居。

    在这些实验中,这些细胞有两个状态,分别表示为 0 和 1,所以规则可以通过一个表格进行汇总,它将邻域状态(状态的三元组)映射为中心细胞的下一个状态。 下表展示了一个示例:

    prev 111 110 101 100 011 010 001 000
    next 0 0 1 1 0 0 1 0

    第一行显示邻居可能拥有的八个状态。第二行显示下一个时间步骤中的中心细胞的状态。 作为该表的简明编码,Wolfram 建议将第二行读作二进制数。 因为二进制 00110010 是十进制的 50,所以 Wolfram 称这个 CA 为“规则 50”。

    表 5.1:十个时间步骤之后的规则 50

    上图展示了规则 50 在 10 个时间步骤之后的效果。 第一行展示第一个时间步骤内的系统状态; 它起始于一个“开”细胞,其余都是“关”。 第二行展示下一个时间步骤中的系统状态,以此类推。

    图中的三角形是这些 CA 的典型;这是领域形状的结果吗? 在一个时间步骤中,每个细胞都会影响任一方向上的邻居的状态。 在下一个时间步骤中,该影响可以在每个方向上向一个细胞传播。 因此,过去的每个细胞都有一个“影响三角形”,包括所有可能受其影响的细胞。

    5.3 CA 的分类

    图 5.2:64 个步骤之后的规则 18

    有多少种不同的 CA?

    由于每个细胞都处于开或关的状态,我们可以用一位来指定细胞的状态。在三个细胞的邻域中,有 8 种可能的配置,因此规则表中有 8 个条目。由于每个条目都占一个位,我们可以使用 8 位指定一个表。使用 8 位,我们可以指定 256 个不同的规则。

    Wolfram 的第一个 CA 实验就是测试所有 256 种可能性并尝试对它们进行分类。

    在视觉上检查结果时,他提出 CA 的行为可以分为四类。第一类包含最简单(也是最不感兴趣)的 CA,即从几乎任何起始条件演变为相同统一图案的 CA。作为一个简单的例子,规则 0 总是在一个时间步后产生一个空的图案。

    规则 50 是第二类的一个例子。它生成一个带有嵌套结构的简单图案;也就是说,该图案包含许多自身的较小版本。规则 18 使嵌套结构更加清晰;图?显示了 64 步后的样子。

    这种模式类似于谢尔宾斯基三角形,你可以在 http://en.wikipedia.org/wiki/Sierpinski_triangle 上阅读。

    某些二类 CA 生成的图案复杂而美观,但与第三和第四类相比,它们相对简单。

    5.4 随机性

    图 5.3:100 个步骤之后的规则 30

    第三类包含产生随机性的 CA。规则 30 是一个例子;图?显示 100 个时间步后的样子。

    左侧有一个明显的图案,右侧有各种大小的三角形,但中心看起来很随意。 事实上,如果你把中间列看做一个比特序列,就很难将其区分于真正的随机序列。 它通过了许多统计测试,人们用来测试比特序列是否随机。

    产生看起来随机的数字的程序,称为伪随机数字生成器(PRNG)。 他们不被认为是真正的随机,因为:

    • 它们中的许多产生规律性序列,可以通过统计来检测。 例如,C 标准库中的rand的原始实现,使用了线性同余生成器,生成器生成的序列具有易于检测的序列相关性。

    • 任何使用有限状态(即存储)的 PRNG 最终都会重复。 生成器的特点之一就是这种重复周期。

    • 底层过程基本上是确定性的,不同于一些物理过程,如放射性衰减和热噪声,被认为是基本随机的。

    现代 PRNG 产生的序列,在统计上与随机值无法区分,并且它们以很长的周期实现,以至于在重复之前宇宙将崩溃。 这些发生器的存在,提出了一个问题,即质量好的伪随机序列与由“真正的”随机过程产生的序列之间,是否存在真正差异。 在“A New Kind of Science”中,沃尔夫勒姆认为没有(第 315-326 页)。

    5.5 确定性

    第三类 CA 的存在令人惊讶。 为了解释多么令人惊讶,让我从哲学确定性(决定论)开始(参见http://en.wikipedia.org/wiki/Determinism)。 许多哲学立场很难准确定义,因为它们有不同的风味。 我经常发现,使用从弱到强排列的陈述列表,来定义它们是有用的:

    D1:

    确定性模型可以对某些物理系统做出准确的预测。

    D2:

    许多物理系统可以用确定性过程建模,但有些系统本质上是随机的。

    D3:

    所有事件都是由先验事件造成的,但许多物理系统基本上是不可预测的。

    D4:

    所有事件都是由先验事件造成的,并且可以(至少原则上)预测。

    我构建这个范围的目标是,让 D1 如此弱以至于几乎每个人都会接受它,D4 如此强以至于几乎没有人会接受它,并且有些人会接受中间的陈述。

    作为对历史发展和科学发现的回应,世界舆论的质心沿着这个范围摆动。 在科学革命之前,许多人认为宇宙的运作基本上是不可预测的,或由超自然力量所控制。 在牛顿力学的胜利之后,一些乐观主义者开始相信像 D4 这样的东西;例如,皮埃尔-西蒙拉普拉斯(Pierre-Simon Laplace)在 1814 年写道:

    我们可以把宇宙的现状看作过去的果和未来的因。 一个智能在某个特定的时刻,知道所有使自然运动的力量,以及构成自然的所有物品的所有位置,如果它也足够大,来提交这些数据用于分析,它会将宇宙最大的天体和最小的原子的运动汇总成一个公式; 对于这样的智能来说,没有什么是不确定的,未来就像过去一样会存在于它的眼前。

    这种“智能”被称为“拉普拉斯的恶魔”。见

    5.6 飞船

    图 5.4:100 步之后的规则 110

    第四类 CA 的行为更令人惊讶。 几个一维 CA,最着名的是规则 110,是图灵完备的,这意味着他们可以计算任何可计算的函数。 这个属性也称为普遍性,由 Matthew Cook 在 1998 年证明。请参阅 http://en.wikipedia.org/wiki/Rule_110

    图?展示了初始条件为单个细胞和 100 个时间步骤的规则 110 的样子。 在这个时间尺度上,没有发生什么特别的事情。 有一些有规律的模式,但也有一些难以表述的特征。

    图?展示了更大的图像,它起始于一个随机的初始条件和 600 个时间步骤:

    图 5.5:初始条件随机和 600 个时间步骤的规则 110

    经过大约 100 个步骤后,背景变成了简单的重复模式,但背景中有一些持久性结构表现为干扰。 其中一些结构是稳定的,所以它们表现为垂直线条。 其他的在空间中平移,表现为不同斜率的对角线,取决于它们移动一列所需的时间步数。 这些结构被称为飞船。

    飞船之间的碰撞产生不同的结果,取决于飞船的类型和它们碰撞时的阶段。 一些碰撞歼灭两艘船,其他船只保持不变;还有一些产生不同类型的一艘或多艘船只。

    这些碰撞是 CA 规则 110 中的计算基础。 如果你将飞船视为通过电线传播的信号,并将碰撞视为计算 AND 和 OR 等逻辑运算的门,那么你可以看到 CA 执行计算的意义。

    5.7 通用性

    为了理解通用性,我们必须理解可计算性理论,它关于计算模型和计算的东西。

    最通用的计算模型之一是图灵机,它是由艾伦图灵在 1936 年提出的一种抽象计算机。图灵机是一个一维 CA,两个方向上都是无限的,并增加了一个读写头。在任何时候,头部都位于一个细胞上。它可以读取该细胞的状态(通常只有两种状态),并可以将新值写入细胞中。

    此外,该机器还有一个寄存器,用于记录机器的状态(有限数量的状态之一)和一张规则表。对于每个机器状态和细胞状态,表格规定一个操作。操作包括修改头部所在的细胞,并向左或向右移动一个细胞。

    图灵机并不是计算机的实际设计,但它模拟了常见的计算机体系结构。对于在真实计算机上运行的给定程序,(至少原则上)可以构造一个执行等效计算的图灵机。

    图灵机很有用,因为它可以刻画一组图灵机可以计算的函数,这就是图灵所做的事情。 这个集合中的函数被称为图灵可计算的。

    说图灵机可以计算任何图灵可计算函数,是一个赘述:根据定义它是真的。 但图灵可计算性比这更有趣。

    事实证明,任何人提出的每个合理的计算模型都是图灵完备的;也就是说,它可以计算与图灵机完全相同的一组函数。 其中一些模型,如 lamdba 演算,与图灵机非常不同,所以它们的等价性令人惊讶。

    这种观察产生了丘奇-图灵理论,它基本上定义了可计算的含义。 这个“理论”是,图灵可计算性是可计算性的正确,或至少是自然定义,因为它描述了这种计算模型的多样化集合的威力。

    CA 规则 110是另一种计算模型,其简单性非常出色。 它也是通用的,为丘奇-图灵理论提供了支持。

    在“A New Kind of Science”中,沃尔夫勒姆阐述了这个理论的一个变种,他称之为“计算等价性原理”:

    几乎所有不明显的简单过程,都可以看作是具有复杂性相同的计算。
    更具体来说,计算等价性原理表明,在自然界中发现的系统可以执行达到最高(“通用”)级别的计算能力的计算,并且大多数系统实际上实现了这种最高级别的计算能力。 因此,大多数系统在计算上是等效的(参见 http://mathworld.wolfram.com/PrincipleofComputationalEquivalence.html)。

    将这些定义应用于 CA,第一类和第二类“显然很简单”。 第三类可能不那么明显,但在某种程度上,完美的随机性就像完美的顺序一样简单;复杂性存在于中间。 所以 Wolfram 声称第四类行为在自然界中很常见,并且几乎所有表现它的系统在计算上都是等价的。

    5.8 可证伪性

    沃尔夫勒姆认为,他的原则比丘奇图灵理论更强大,因为它是关于自然界的,而不是抽象的计算模型。但是说自然过程“可以看作计算”,使我觉得像理论选择的陈述。而不仅仅是自然世界的假设。

    此外,对于像“几乎”和“明显简单”这样的未定义术语的资格,他的假设可能是不可证伪的。可证伪性是科学哲学的一个观点,由卡尔波普尔(Karl Popper)提出,作为科学假说与伪科学之间的界限。如果一个假设是假的,并且有一个实验,至少在实用性领域,它能反驳这个假设,那么这个假设是可证伪的。

    例如,地球上的所有生命都来自共同祖先的说法是可证伪的,因为它对现代物种(在其他东西中)的基因相似性做出了特定的预测。如果我们发现了一种新物种,它的 DNA 与我们的 DNA 几乎完全不同,那么这就反驳了共同血统理论(或者至少引起质疑)。

    另一方面,所谓“神创论”,即所有物种都是由超自然力量创造出来的,是不可证实的,因为没有任何我们可以观察到的,与自然世界相矛盾的东西。任何实验的结果都可以归因于创作者的意志。

    不可证伪的假设可能有吸引力,因为不可能反驳它们。如果你的目标是永远不会被证明是错误的,你应该尽可能选择不可证伪的假设。

    但是,如果你的目标是对世界做出可靠的预测 - 而这至少是科学的目标之一 - 那么不可证伪的假设是无用的。问题是他们没有结果(如果他们有结果,他们将是可证伪的)。

    例如,如果神创论是真实的,那我知道它有什么好处呢?它不会告诉我任何造物主的事情,除了他有一种“对甲虫的非常喜爱”(归因于 J. B. S. Haldane)。不同于共同血统理论,它通告许多科学和生物工程领域,理解这个世界或者为之行动是没有用的。

    5.9 这是什么模型?

    图 5.6:一个简单物理模型的逻辑结构

    一些细胞自动机主要是数学工艺品。 它们很有趣,因为它们令人惊讶,或者有用,或者漂亮,或者因为它们提供了创建新式数学的工具(比如丘奇图灵定理)。

    但是,它们是不是物理系统的模型还并不清楚。 如果他们是,他们是高度抽象的,也就是说他们并不很详细或现实。

    例如,某些锥螺物种在它们的壳上产生图案,类似于由细胞自动机产生的图案(参见en.wikipedia.org/wiki/Cone_snail)。 所以假设 CA 是随着壳长大而在壳上产生图案的机制的模型,这是很自然的。 但是,至少在最初阶段,模型元素(所谓的细胞,邻居之间的通信,规则)如何对应成长的蜗牛(真实细胞,化学信号,蛋白质交互网络)的元素,还并不清楚。

    对于传统的物理模型,现实是一种优点。如果模型的元素对应物理系统的元素,则模型和系统之间有明显的类比。总的来说,我们期望更现实的模型能够做出更好的预测,并提供更可信的解释。

    当然,这只是一个事实。更详细的模型更难以处理,并且通常不太适合分析。在某些时候,模型变得如此复杂,以至于直接对系统进行实验更容易。

    在另一个极端,简单的模型可以完全引人注目,因为它们很简单。

    简单模型提供了与详细模型不同的解释。使用详细的模型,论述就像这样:“我们对物理系统S感兴趣,所以我们构造了一个详细模型M,并且通过分析和模拟表明M表现出一种行为B,它与实际系统的观察O(定性或定量地)相似。那么为什么O会发生?因为S类似于M,而B类似于O,我们可以证明M导致B。”

    使用简单的模型,我们不能说SM相似,因为它不是。 相反,论述是这样的:“有一组模型共享一组共同的特征。 任何具有这些特征的模型都表现出行为B。如果我们进行类似于B的观察O,解释它的一种方式是,这表明系统S具有足以产生1的一组特征。”

    对于这种说法,增加更多的特征并没有帮助。 使模型更真实不会使模型更可靠;它只掩盖了导致O的基本特征,和S特有的附带特征之间的差异。

    图?显示了这种模型的逻辑结构。 特征xy足以产生行为。 增加更多细节,如特征wz,可能会使模型更加逼真,但是这种现实并没有增加解释力。

    5.10 CA 的实现

    图 5.7:列表的列表(左)和 NumPy 数组(右)

    为了生成本章中的图形,我编写了一个名为 CA 的 Python 类,它代表细胞自动机,以及用于绘制结果的类。在接下来的几节中,我会解释他们如何工作。

    为了存储 CA 的状态,我使用了 NumPy 数组,这是一个多维数据结构,其元素类型都相同。它与嵌套列表类似,但通常更小更快。图?说明了原因。左侧的图展示了整数列表的列表;每个点表示一个引用,它占用 4-8 个字节。要访问其中的一个整数,你必须跟随两个引用。

    右图显示了相同整数的数组。因为这些元素大小都相同,所以它们可以连续存储在内存中。这种安排节省了空间,因为它不使用引用,并且节省了时间,因为可以直接从下标计算元素的位置;没有必要跟随一系列的引用。

    为了解释我的代码如何工作,我将以一个 CA 开始,它计算每个邻域中细胞的“奇偶性”。如果数字是偶数,则数字的奇偶性为 0;如果数字为奇数,则奇偶性为 1。

    首先,我在第一行的中间,创建带有单个 1 的零数组。

    >>> rows = 5
    >>> cols = 11
    >>> ca = np.zeros((rows, cols))
    >>> ca[0, 5] = 1
    print(ca)
    [[ 0.  0.  0.  0.  0.  1.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
     [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]]

    plot_ca用图形展示了结果。

    mport matplotlib.pyplot as plt
    
    def plot_ca(ca, rows, cols):
        cmap = plt.get_cmap('Blues')
        plt.imshow(array, interpolation='none', cmap=cmap)

    按照约定,我使用缩写名称plt引入了pyplotimshow将数组视为“图像”并显示它。 使用颜色表'Blues',将“开”细胞绘制为深蓝色,“关”细胞绘制为淡蓝色。

    现在,为了计算下一个时间步中的 CA 状态,我们可以使用step

    
    def step(array, i):
        rows, cols = array.shape
        for j in range(1, cols):
            array[i, j] = sum(array[i-1, j-1:j+2]) % 2

    参数ca是表示 CA 状态的 NumPy 数组。 rowscol是数组的维数,而i是我们应该计算的时间步骤的索引。 我用i来表示数组的行,它们对应于时间,j表示对应于空间的列。

    step内部,我们遍历第i行的元素。 每个元素是来自上一行的三个元素的总和,并对 2 取余。

    5.11 互相关

    上一节中的step函数很简单,但速度并不是很快。 一般来说,如果我们用 NumPy 操作替换循环,我们可以加速这样的操作,因为 Python 解释器中的for循环会产生大量开销。 在本节中,我将展示如何使用NumPy函数相关来加快步骤。

    首先,我们可以使用数组乘法来代替切片运算符来选择邻域。 具体来说,我们将数组乘以一个窗口,其中我们想要选择的细胞为一,其余为零。

    例如,以下窗口选择前三个元素:

    
    >>> window = np.zeros(cols, dtype=np.int8)
    >>> window[:3] = 1
    >>> print(window)
    [1 1 1 0 0 0 0 0 0 0 0]

    如果我们乘以数组的最后一行,我们会得到前三个元素:

    >>> print(array[4])
    >>> print(window * array[4])
    [0 1 0 0 0 1 0 0 0 1 0]
    [0 1 0 0 0 0 0 0 0 0 0]

    现在我们可以使用sum和模运算符来计算下一行的第一个元素:

    
    >>> sum(window * array[4]) % 2
    1

    如果我们将窗口向右移动,它会选择接下来的三个元素,以此类推。所以我们可以像这样重写step

    
    def step2(array, i):
        rows, cols = array.shape
        window = np.zeros(cols)
        window[:3] = 1
        for j in range(1, cols):
            array[i, j] = sum(window * array[i-1]) % 2
            window = np.roll(window, 1)

    roll将窗口向右移动(它也把末尾的补在开头,但不影响这个函数)。

    step2产生step的相同结果。 它仍然不是非常快,但是它朝着正确的方向迈出了一步,因为我们刚刚执行的操作(乘以窗口,将结果相加,移动窗口并重复)用于各种应用。 它被称为互相关,而 NumPy 提供了一个称为correlate的函数来计算它。

    我们可以用它来编写更快,更简单的步骤:

    
    def step3(array, i):
        window = np.array([1, 1, 1])
        array[i] = np.correlate(array[i-1], window, mode='same') % 2

    当我们使用np.correlate时,窗口不必与数组大小相同,因此使窗口更简单一些。

    mode参数决定结果的大小。 你可以阅读 NumPy 文档中的详细信息,但是当模式为'same'时,结果与输入大小相同。

    5.12 CA 表

    现在还差一步。 如果 CA 规则仅取决于邻居的总和,那么我们迄今为止的函数仍然有效,但大多数规则还取决于哪些邻居是开或者关的。 例如,100 和 001 可能会产生不同的结果。

    我们可以使用一个包含元素[4,2,1]的窗口,使step更加通用,它将邻域解释为一个二进制数。 例如,邻域 100 产生 4;010 产生 2,001 产生 1。然后我们可以在规则表中查找这些结果。

    以下是更一般的步骤:

    
    def step4(array, i):
        window = np.array([4, 2, 1])
        corr = np.correlate(array[i-1], window, mode='same')
        array[i] = table[corr]

    前两行几乎相同。 最后一行在table中查找corr的每个元素,并将结果赋给array[i]

    最后,这是计算表的函数:

    
    def make_table(rule):
        rule = np.array([rule], dtype=np.uint8)
        table = np.unpackbits(rule)[::-1]
        return table

    参数rule是一个 0 到 255 的整数。第一行将规则放入单个元素的数组中,以便我们可以使用unpackbits,将规则编号转换为其二进制表示形式。 例如,以下是规则 150 的表:

    
    >>> table = make_table(150)
    >>> print(table)
    [0 1 1 0 1 0 0 1]

    thinkcomplexity.py中,你将找到CA的定义,它封装了本节中的代码,以及两个绘制 CA 的类,PyplotDrawerEPSDrawer

    5.13 练习

    练习 1

    本章的代码位于本书仓库的 Jupyter 笔记本chap05.ipynb中。打开这个笔记本,阅读代码,然后运行单元格。你可以使用这个笔记本来做本章的练习。我的解决方案在chap05soln.ipynb中。

    练习 2

    这个练习要求你试验规则 110 以及它的一些飞船。

    1. 阅读规则 110 的维基百科页面,其中描述了其背景图案和飞船:https://en.wikipedia.org/wiki/Rule_110

    2. 使用产生稳定背景图案的初始条件创建 CA 规则 110。

      请注意,CA 类提供了start_string,它允许你使用 1 和 0 的字符串初始化数组的状态。

    3. 通过在行的中心添加不同的图案来修改初始条件,并查看哪些产生了飞船。对于一些n的合理的值,你可能想列举所有可能的n位图案。对于每个飞船,你能找到平移的时间和速度吗?你能找到的最大的飞船是什么?

    4. 当宇宙飞船相撞时会发生什么?

    练习 3

    这个练习的目标是实现一个图灵机。

    1. 阅读 http://en.wikipedia.org/wiki/Turing_machine 来了解图灵机。
    2. 编写一个名为Turing的类来实现图灵机。对于动作表,使用三个状态的 Busy Beaver 的规则。
    3. 写一个名为TuringDrawer的类,该类生成一个图像,表示磁带状态以及磁头位置和状态。可能的外观的一个示例,请参阅 http://mathworld.wolfram.com/TuringMachine.html

    练习4

    1. 本练习要求你执行并测试几个 PRNG。为了进行测试,你需要安装 DieHarder,你可以从 https://www.phy.duke.edu/~rgb/General/dieharder.php 下载 DieHarder,也可能为你的操作系统作为软件包提供。
    2. 编写一个程序,实现 http://en.wikipedia.org/wiki/Linear_congruential_generator 中描述的线性同余生成器之一。使用 DieHarder 进行测试。
    3. 阅读 Pythonrandom模块的文档。它使用了什么 PRNG?测试它。
    4. 使用几百个细胞实现 CA 规则 30,在合理的时间内以尽可能多的时间步骤运行它,然后将中心列输出为位序列。测试它。

    练习5

    可证伪性是一个吸引人的和有用的想法,但在科学哲学家中,它并不普遍视为界限的解决方案,正如波普尔所声称的那样。

    阅读 http://en.wikipedia.org/wiki/Fififiability 并回答以下问题。

    1. 界限问题是什么?
    2. 根据波普尔的说法,可证伪性是否解决了界限问题?
    3. 给出两个理论示例,一个被认为是科学,另一个被认为是非科学,它们由可证伪性的标准成功地区分开。
    4. 你能总结出科学哲学家和历史学家对波普尔的主张提出的,一个或多个反对意见吗?
    5. 你是否有这样的感觉,即实践哲学家对波普尔的工作给予高度评价?
    展开全文
  • 复杂性思维第二版 四、无标度网络

    万次阅读 2017-11-05 10:44:31
    复杂性科学的许多领域中,重尾分布是一个常见特征,它们将成为本书的一个反复出现的主题。 我们可以在双对数轴绘制它,来获得重尾分布的更清晰的图像,就像上面那副图那样。这种转换突显了分布的尾巴;也就是较...

    四、无标度网络

    原文:Chapter 4 Scale-free networks

    译者:飞龙

    协议:CC BY-NC-SA 4.0

    自豪地采用谷歌翻译

    在本章中,我们将处理来自在线社交网络的数据,并使用 WS 图对其进行建模。WS 模型像数据一样,具有小世界网络的特点,但是与数据不同,它的节点到节点的邻居数目变化很小。

    这种差异是 Barabási 和 Albert 开发的网络模型的动机。BA 模型捕捉到邻居数量的观察到的变化,它具有小的世界属性之一,短路径长度,但它没有一个小世界网络的高聚类。

    本章最后讨论了 WS 和 BA 图,作为小世界网络的解释模型。

    本章的代码位于本书的仓库中的chap04.ipynb中。使用代码的更多信息,请参见第(?)章。

    4.1 社交网络数据

    WS 图的目的是,模拟自然科学和社会科学中的网络。Watts 和 Strogatz 在他们最初的论文中,查看了电影演员的网络(如果他们出现在同一部电影中,就是连接的)。美国西部的电网;和 C. elegans 线虫脑中的神经元网络 。他们发现,所有这些网络都具有小世界图的高群聚性和短路径长度特征。

    在本节中,我们将使用不同的数据集,Facebook 用户及其朋友的数据集,来进行相同的分析。如果你对 Facebook 不熟悉,那么彼此连接的用户被称为“朋友”,而不管他们在现实世界中的关系的性质如何。

    我将使用来自斯坦福网络分析项目(SNAP)的数据,该项目分享了来自在线社交网络和其他来源的大型数据集。具体来说,我将使用他们的 Facebook 数据集 [1],其中包括 4039 个用户和 88,234 个朋友关系。该数据集位于本书的仓库中,但也可以从 SNAP 网站上获取。

    [1] J. McAuley and J. Leskovec. Learning to Discover Social Circles in Ego Networks. NIPS, 2012.

    数据文件为每条边包含一行,用户由 0 到 4038 之间的整数标识。下面是读取文件的代码:

    
    def read_graph(filename):
        G = nx.Graph()
        array = np.loadtxt(filename, dtype=int)
        G.add_edges_from(array)
        return G

    NumPy 提供了函数loadtext,它读取给定的文件,并以 NumPy 数组的形式返回内容。参数dtype指定数组元素的类型。

    然后我们可以使用add_edges_from迭代数组的行,并创建边。结果如下:

    >>> fb = read_graph('facebook_combined.txt.gz')
    >>> n = len(fb)
    >>> m = len(fb.edges())
    >>> n, m
    (4039, 88234)

    节点和边的数量与数据集的文档一致。

    现在我们可以检查这个数据集是否具有小世界图的特征:高群聚性和短路径长度。

    第(?)节中,我们编写了一个函数,来计算网络平均群聚系数。NetworkX 提供了一个叫做的函数average_clustering,它可以更快地完成相同的工作。

    但是对于更大的图,它们都太慢,需要与nk^2成正比的时间,其中n是节点数,k是每个节点的邻居数。

    幸运的是,NetworkX提供了一个通过随机抽样来估计群聚系数的函数。你可以像这样调用它:

    
        from networkx.algorithms.approximation import average_clustering
        average_clustering(G, trials=1000)

    下面函数对路径长度做了类似的事情:

    
    def random_path_lengths(G, nodes=None, trials=1000):
        if nodes is None:
            nodes = G.nodes()
        else:
            nodes = list(nodes)
    
        pairs = np.random.choice(nodes, (trials, 2))
        lengths = [nx.shortest_path_length(G, *pair)
                   for pair in pairs]
        return lengths

    G是一个图,nodes是节点列表,我们应该从中抽样,trials是要抽样的随机路径的数量。如果nodesNone,我们从整个图表中进行抽样。

    pairs是随机选择的节点的 NumPy 数组,对于每个采样有一行两列。

    列表推导式枚举数组中的行,并计算每对节点之间的最短距离。结果是路径长度的列表。

    estimate_path_length生成一个随机路径长度列表,并返回它们的平均值:

    
    def estimate_path_length(G, nodes=None, trials=1000):
        return np.mean(random_path_lengths(G, nodes, trials))

    我会使用average_clustering来计算C

    C = average_clustering(fb)

    并使用estimate_path_lengths来计算L

    L = estimate_path_lengths(fb)

    群聚系数约为0.61,这是较高的,正如我们所期望的那样,如果这个网络具有小世界特性。

    平均路径为3.7,在 4000 多个用户的网络中相当短。毕竟这是一个小世界。

    现在让我们看看是否可以构建一个 WS 图,与此网络具有相同特征。

    4.2 WS 模型

    在 Facebook 数据集中,每个节点的平均边数约为 22。由于每条边都连接到两个节点,度的均值是每个节点边数的两倍:

    
    >>> k = int(round(2*m/n))
    >>> k
    44

    我们可以用n=4039k=44创建一个 WS 图。p=0时,我们会得到一个环格。

    
    lattice = nx.watts_strogatz_graph(n, k, 0)

    在这个图中,群聚较高:C是 0.73,而在数据集中是 0.61。但是L为 46,远远高于数据集!

    使用p=1我们得到一个随机图:

    random_graph = nx.watts_strogatz_graph(n, k, 1)

    在随机图中,L是 2.6,甚至比数据集(3.7)短,但C只有 0.011,所以这是不好的。

    通过反复试验,我们发现,当p=0.05时,我们得到一个高群聚和短路径长度的 WS 图:

    
    ws = nx.watts_strogatz_graph(n, k, 0.05, seed=15)

    在这个图中C0.63,比数据集高一点,L是 3.2,比数据集低一点。所以这个图很好地模拟了数据集的小世界特征。

    到现在为止还不错。

    4.3 度

    图 4.1:Facebook 数据集和 WS 模型中的度的 PMF。

    回想一下,节点的度是它连接到的邻居的数量。如果 WS 图是 Facebook 网络的一个很好的模型,它应该具有相同的总(或平均)度,理想情况下不同节点的度数相同。

    这个函数返回图中的度的列表,每个节点对应一项:

    
    def degrees(G):
        return [G.degree(u) for u in G]

    数据集中的度的均值是 43.7;WS 模型中的度的均值是 44。到目前为止还不错。

    但是,WS 模型中的度的标准差为 1.5;数据中的标准差是 52.4。有点糟。

    这里发生了什么?为了更好地查看,我们必须看看度的 分布,而不仅仅是均值和标准差。

    我将用一个 Pmf 对象来表示度的分布,它在thinkstats2模块中定义。Pmf 代表“概率质量函数”;如果你不熟悉这个概念,你可以阅读 Think Stats 第二版的第三章,网址是 http://greenteapress.com/thinkstats2/html/thinkstats2004.html

    简而言之,Pmf 是值到概率的映射。Pmf 是每个可能的度d,到度为d的节点比例的映射。

    作为一个例子,我将构建一个图,拥有节点1, 2, 3,连接到中心节点0

    G = nx.Graph()
    G.add_edge(1, 0)
    G.add_edge(2, 0)
    G.add_edge(3, 0)
    nx.draw(G)

    这里是图中的度的列表:

    
    >>> degrees(G)
    [3, 1, 1, 1]

    节点0度为 3,其它度为 1。现在我可以生成一个 Pmf,它表示这个度的分布:

    >>> from thinkstats2 import Pmf
    >>> Pmf(degrees(G))
    Pmf({1: 0.75, 3: 0.25})

    产生的Pmf是一个对象,将每个度映射到一个比例或概率。在这个例子中,75%的节点度为 1,25%度为 3。

    现在我们生成一个Pmf,包含来自数据集的节点的度,并计算均值和标准差:

    
    >>> pmf_ws = Pmf(degrees(ws))
    >>> pmf_ws.mean(), pmf_ws.std()
    (44.000, 1.465)

    我们可以使用thinkplot模块来绘制结果:

    thinkplot.Pdf(pmf_fb, label='Facebook')
    thinkplot.Pdf(pmf_ws, label='WS graph')

    图(?)显示了这两个分布。他们是非常不同的。

    在 WS 模型中,大多数用户有大约 44 个朋友;最小值是 38,最大值是 50。这个变化不大。在数据集中,有很多用户只有 1 或 2 个朋友,但有一个人有 1000 多个!

    像这样的分布,有许多小的值和一些非常大的值,被称为重尾。

    4.4 重尾分布

    图 4.2:Facebook 数据集和 WS 模型中的度的 PMF,在双对数刻度下。

    在复杂性科学的许多领域中,重尾分布是一个常见特征,它们将成为本书的一个反复出现的主题。

    我们可以在双对数轴绘制它,来获得重尾分布的更清晰的图像,就像上面那副图那样。这种转换突显了分布的尾巴;也就是较大值的概率。

    在这种转换下,数据大致在一条直线上,这表明分布的最大值与概率之间存在“幂律”关系。在数学上,

    PMF(k) ~ k^(−α)

    其中PMF(k)是度为k的节点的比例,α是一个参数,符号~表示当k增加时,PMF 渐近于k^(−α)

    如果我们把对两边取对数,我们得到:

    
    logPMF(k) ~ −α logk 

    因此,如果一个分布遵循幂律,并且我们在双对数刻度上绘制PMF(k)k的关系,那么我们预计至少对于k的较大值,将有一条斜率为的直线。

    所有的幂律分布都是重尾的,但是还有其他重尾分布不符合幂律。我们将很快看到更多的例子。

    但首先,我们有一个问题:WS 模型拥有高群聚性和短路径长度,我们在数据中也看到了,但度的分布根本不像数据。这种差异就启发了我们下一个主题,Barabási-Albert 模型。

    4.5 Barabási-Albert 模型

    1999 年,Barabási 和 Albert 发表了一篇论文“随机网络中的标度的出现”(Emergence of Scaling in Random Networks),描述了几个现实世界的网络的结构特征,包含一些图,它们展示了电影演员,万维网(WWW)页面和美国西部电网设施的互联性。你可以从 http://www.sciencemag.org/content/286/5439/509 下载该论文。

    他们测量每个节点的度并计算PMF(k),即节点度为k的比例。然后他们在双对数标度上绘制PMF(k)k的关系。这些曲线可用一条直线拟合,至少对于k的较大数值;所以他们得出结论,这些分布是重尾的。

    他们还提出了一个模型,生成了属性相同的图。模型的基本特征与 WS 模型不同,它们是:

    增长:

    BA 模型不是从固定数量的顶点开始,而是从一个较小图开始,每次添加一个顶点。

    优先连接:

    当创建一个新的边时,它更可能连接到一个已经有很多边的节点。这种“富者更富”的效应是一些现实世界网络增长模式的特征。

    最后,他们表明,由 Barabási-Albert(BA)模型模型生成的图,度的分布遵循幂律。

    具有这个属性的图有时被称为无标度网络,原因我不会解释;如果你好奇,可以在 http://en.wikipedia.org/wiki/Scale-free_network 上阅读更多内容。

    NetworkX 提供了一个生成 BA 图的函数。我们将首先使用它;然后我会告诉你它的工作原理。

    ba = nx.barabasi_albert_graph(n=4039, k=22)

    参数是n要生成的节点数量,k是每个节点添加到图形时的起始边数。我选择k=22,是因为这是数据集中每个节点的平均边数。

    图 4.3:Facebook 数据集和 BA 模型中的节点的 PMF,在双对数刻度上。

    所得图形拥有 4039 个节点,每个节点有 21.9 个边。由于每条边连接两个节点,度的均值为 43.8,非常接近数据集中的度的均值 43.7。

    度的标准差为 40.9,略低于数据集 52.4,但比我们从 WS 图得到的数值好 1.5 倍。

    图(?)以双对数刻度展示了 Facebook 网络和 BA 模型的度的分布。模型并不完美;特别k是在小于 10 时偏离了数据。但尾巴看起来像是一条直线,这表明这个过程产生了遵循幂律的度的分布。

    所以在重现度的分布时,BA 模型比 WS 模型更好。但它有小世界的属性?

    在这个例子中,平均路径长度L是 2.5,这比实际的网络的L = 3.69更小。所以这很好,虽然可能太好了。

    另一方面,群聚系数C为 0.037,并不接近数据集中的值 0.61。所以这是一个问题。

    下表总结了这些结果。WS 模型捕获了小世界的特点,但没有度的分布。BA 模型捕获了度的分布,和平均路径长度,至少是近似的,但没有群聚系数。

    在本章最后的练习中,你可以探索其他可以捕获所有这些特征的模型。

    Facebook WS 模型 BA 模型
    C 0.61 0.63
    L 3.69 3.23
    度的均值 43.7 44
    度的标准差 52.4 1.5
    幂律? 可能 不是

    表 4.1:与两个模型相比,Facebook 网络的特征。

    4.6 生成 BA 图

    在前面的章节中,我们使用了 NetworkX 函数来生成BA图。现在让我们看看它的工作原理。这是一个barabasi_albert_graph的版本,我做了一些更改,使其更易于阅读:

    def barabasi_albert_graph(n, k):
    
        G = nx.empty_graph(k)
        targets = list(range(k))
        repeated_nodes = []
    
        for source in range(k, n):
    
            G.add_edges_from(zip([source]*k, targets))
    
            repeated_nodes.extend(targets)
            repeated_nodes.extend([source] * k)
    
            targets = _random_subset(repeated_nodes, k)
    
        return G

    n是我们想要的节点的数量,k是每个新节点边的数量(近似为每个节点的边的数量)。

    我们从一个k个节点和没有边的图开始。然后我们初始化两个变量:

    targets

    k个节点的列表,它们将被连接到下一个节点。最初targets包含原来的k个节点;之后它将包含节点的随机子集。

    repeated_nodes

    一个现有节点的列表,如果一个节点有k条边,那么它出现k次。当我们从repeated_nodes选择时,选择任何节点的概率与它所具有的边数成正比。

    每次循环中,我们添加源节点到targets中的节点的边。然后我们更新repeated_nodes,通过添加每个目标一次,以及新的节点k次。

    最后,我们选择节点的子集作为下一次迭代的目标。以下是_random_subset的定义:

    
    def _random_subset(repeated_nodes, k):
        targets = set()
        while len(targets) < k:
            x = random.choice(repeated_nodes)
            targets.add(x)
        return targets

    每次循环中,_random_subsetrepeated_nodes选择,并将所选节点添加到targets。因为targets是一个集合,它会自动丢弃重复项,所以只有当我们选择了k不同的节点时,循环才会退出。

    4.7 累积分布函数(CDF)

    图 4.4:Facebook 数据集中的度的 CDF,以及 WS 模型(左边)和 BA 模型(右边),在双对数刻度上。

    图 4.3 通过在双对数刻度上绘制概率质量函数(PMF)来表示度的分布。这就是 Barabási 和 Albert 呈现他们的结果的方式,这是幂律分布的文章中最常使用的表示。但是,这不是观察这样的数据的最好方法。

    更好的选择是累积分布函数 (CDF),它将x值映射为小于或等于x的值的比例。

    给定一个 Pmf,计算累积概率的最简单方法是将x的概率加起来,包括x

    
    def cumulative_prob(pmf, x):
        ps = [pmf[value] for value in pmf if value<=x]
        return sum(ps)

    例如,给定数据集中的度的分布,pmf_pf,我们可以计算好友数小于等于 25 的比例:

    
    >>> cumulative_prob(pmf_fb, 25)
    0.506

    结果接近 0.5,这意味着好友数的中位数约为 25。

    因为 CDF 的噪音比 PMF 少,所以 CDF 更适合可视化。一旦你习惯了 CDF 的解释,它们可以提供比 PMF 更清晰的分布图像。

    thinkstats模块提供了一个称为Cdf的类,代表累积分布函数。我们可以用它来计算数据集中的度的 CDF。

    
    from thinkstats2 import Cdf
    cdf_fb = Cdf(degrees(fb), label='Facebook')

    thinkplot提供了一个函数,叫做Cdf,绘制累积分布函数。

    
    thinkplot.Cdf(cdf_fb)

    图 4.4 显示了 Facebook 数据集的度的 CDF ,以及 WS 模型(左边)和 BA 模型(右边)。x轴是对数刻度。

    显然,WS 模型和数据集的 CDF 很大不同。BA 模式更好,但还不是很好,特别是对于较小数值。

    在分布的尾部(值大于 100),BA 模型看起来与数据集匹配得很好,但是很难看出来。我们可以使用另一个数据视图,更清楚地观察数据:在对数坐标上绘制互补 CDF。

    互补 CDF(CCDF)定义为:

    
    CCDF(x) = 1 − CDF(x) 

    它很有用,因为如果 PMF 服从幂律,CCDF 也服从:

    CCDF(x) =(x/x_m)^(-α)

    其中x_m是最小可能值,α是确定分布形状的参数。

    对两边取对数:

    
    logCCDF(x) = −α (logx − logx_m) 

    因此,如果分布服从幂定律,在双对数刻度上,我们预计 CCDF 是斜率为的直线。

    图 4.5 以双对数刻度显示 Facebook 数据的度的 CCDF,以及 WS 模型(左边)和 BA 模型(右边)。

    通过这种查看数据的方式,我们可以看到 BA 模型与分布的尾部(值大于 20)匹配得相当好。WS 模型没有。

    4.8 解释性模型

    图 4.6:解释性模型的逻辑结构

    我们以 Milgram 的小世界实验开始讨论网络,这表明社交网络中的路径长度是惊人的小;因此,有了“六度分离”。

    当我们看到令人惊讶的事情时,自然会问“为什么”,但有时候我们不清楚我们正在寻找什么样的答案。一种答案是解释性模型(见图 4.6)。解释性模型的逻辑结构是:

    1. 在一个系统S中,我们看到一些可观察的东西O,值得解释。

    2. 我们构建一个与系统类似的模型M,也就是说,模型与系统之间的元素/组件/原理是对应的。

    3. 通过模拟或数学推导,我们表明,该模型展现出类似于O的行为B

    4. 我们得出这样的结论:S表现O,因为 S类似于MM表示B,而B类似于O

    其核心是类比论证,即如果两个事物在某些方面相似,那么它们在其他方面可能是相似的。

    类比论证是有用的,解释模型可以令人满意,但是它们并不构成数学意义上的证明。

    请记住,所有的模型都有所忽略,或者“抽象掉”我们认为不重要的细节。对于任何系统都有很多可能的模型,它们包括或忽略不同的特性。而且可能会出现不同的行为模式,BB'B'',这些模式与O不同。在这种情况下,哪个模型解释了O

    小世界现象就是一个例子:Watts-Strogatz(WS)模型和 Barabási-Albert(BA)模型都展现出小世界行为的元素,但是它们提供了不同的解释:

    • WS 模型表明,社交网络是“小”的,因为它们包括强连通的集群,和连接群集的“弱关系”(参见 http://en.wikipedia.org/wiki/Mark_Granovetter#The_strength_of_weak_ties)。
    • BA 模型表明,社交网络很小,因为它们包括度较高的节点,作为中心,并且随着时间的推移,由于优先添加,中心​​会增长。

    在科学的新兴领域,往往是这样,问题不是我们没有解释,而是它们太多。

    4.9:练习

    练习 1:

    上一节中,我们讨论了小世界现象的两种解释,“弱关系”和“中心”。这些解释是否兼容?也就是说,他们能都对吗?你觉得哪一个解释更令人满意?为什么?

    是否有可以收集的数据或可以执行的实验,它们可以提供有利于一种模型的证据?

    竞争模型中的选择,是托马斯·库恩(Thomas Kuhn)的论文“客观性,价值判断和理论选择”(Objectivity, Value Judgment, and Theory Choice)的主题,你可以在 https://github.com/AllenDowney/ThinkComplexity2/blob/master/papers/kuhn.pdf 上阅读。

    对于竞争模型中的选择,库恩提出了什么标准?这些标准是否会影响你对 WS 和 BA 模型的看法?你认为还有其他标准应该考虑吗?

    练习 2:

    NetworkX 提供了一个叫做powerlaw_cluster_graph的函数,实现了 Holme 和 Kim 算法,用于使用度的幂律分布和近似平均聚类,使图增长。阅读该函数的文档,看看是否可以使用它来生成一个图,节点数、度的均值和群聚系数与 Facebook 数据集相同。与实际分布相比较,模型中的度的分布如何?

    练习 3:

    来自 Barabási 和 Albert 论文的数据文件可从 http://www3.nd.edu/~networks/resources.htm 获得。他们的演员协作数据包含在名为actor.dat.gz的文件中。以下函数读取文件并构建图。

    
    import gzip
    
    def read_actor_network(filename, n=None):
        G = nx.Graph()
        with gzip.open(filename) as f:
            for i, line in enumerate(f):
                nodes = [int(x) for x in line.split()]
                G.add_edges_from(thinkcomplexity.all_pairs(nodes))
                if n and i >= n:
                    break
        return G

    计算图中的演员数量和度的均值。以双对数刻度绘制度的 PMF。同时在对数-线性刻度上绘制度的 CDF,来观察分布的一般形状,并在双对数刻度上观察,尾部是否服从幂律。

    注意:演员的网络不是连通的,因此你可能想要使用nx.connected_component_subgraphs查找节点的连通子集。

    展开全文
  • 他们得出结论:沙堆模型表现出“自组织临界”,这意味着从最初的状态开始,它不需要外部控制,或者称之为“微调”任何参数,就可以向临界状态发展。 随着更多沙粒的添加,模型仍处于临界状态。 在接下来的几节...

    八、自组织临界

    原文:Chapter 8 Self-organized criticality

    译者:飞龙

    协议:CC BY-NC-SA 4.0

    自豪地采用谷歌翻译

    在前一章中,我们看到了一个具有临界点的系统的例子,并且我们探索了临界系统 - 分形几何的一个共同特性。

    在本章中,我们将探讨临界系统的另外两个性质:重尾分布,我们在第五章中见过,和粉红噪声,我将在本章中解释。

    这些性质是部分有趣的,因为它们在自然界中经常出现;也就是说,许多自然系统会产生分形几何,重尾分布和粉红噪声。

    这个观察提出了一个自然的问题:为什么许多自然系统具有临界系统的特性?一个可能的答案是自组织临界性(SOC),这是一些系统向临界状态演化并保持它的趋势。

    在本章中,我将介绍沙堆模型,这是第一个展示 SOC 的系统。

    本章的代码位于本书仓库的chap08.ipynb中。使用代码的更多信息,请参见第?章。

    8.1 临界系统

    许多临界系统表现出常见的行为:

    • 分形几何:例如,冷冻的水倾向于形成分形图案,包括雪花和其他晶体结构。分形的特点是自相似性;也就是说,图案的一部分与整体的缩放副本相似。

    • 一些物理量的重尾分布:例如,在冷冻的水中,晶体尺寸的分布是幂律的。

    • 呈现粉红噪声的时间变化。复合信号可以分解为它们的频率分量。在粉红噪声中,低频分量比高频分量功率更大。具体而言,频率f处的功率与1 / f成正比。

    临界系统通常不稳定。例如,为了使水保持部分冷冻状态,需要主动控制温度。如果系统接近临界温度,则小型偏差倾向于将系统从一个相位移到另一个相位。

    许多自然系统表现出典型的临界性行为,但如果临界点不稳定,它们本质上不应该是常见的。这是 Bak,Tang 和 Wiesenfeld 的解决的困惑。他们的解决方案称为自组织临界(SOC),其中“自组织”意味着从任何初始状态开始,系统都会转向临界状态,并停留在那里,无需外部控制。

    8.2 沙堆

    沙堆模型由 Bak,Tang 和 Wiesenfeld 于 1987 年提出。它不是一个现实的沙堆模型,而是一个抽象,它用(1)大量(2)与邻居互动的元素来模拟物理系统。

    沙堆模型是一个二维细胞自动机,每个细胞的状态代表沙堆的部分斜率。在每个时间步骤中,检查每个细胞来查看它是否超过临界值K,通常是 3。如果是,则它会“倒塌”并将沙子转移到四个相邻细胞;也就是说,细胞的斜率减少 4,并且每个邻居增加 1。在网格的周边,所有细胞保持为斜率 0,所以多余的会溢出边缘。

    Bak,Tang 和 Wiesenfeld 首先将所有细胞初始化为大于K的水平,然后运行模型直至稳定。然后他们观察微小扰动的影响;他们随机选择一个细胞,将其值增加 1,然后再次运行模型,直至稳定。

    对于每个扰动,他们测量T,这是沙堆稳定所需的时间步数,S是倒塌的细胞总数 [1]。

    [1] 原始论文使用了S的不同定义,但是后来的工作使用了这个定义。

    大多数情况下,放置一粒沙子不会导致细胞倒塌,因此T = 1S = 0。 但偶尔一粒沙子会引起雪崩,影响很大一部分网格。 结果表明,TS的分布是重尾的,这支持了系统处于临界状态的断言。

    他们得出结论:沙堆模型表现出“自组织临界性”,这意味着从最初的状态开始,它不需要外部控制,或者称之为“微调”任何参数,就可以向临界状态发展。 随着更多沙粒的添加,模型仍处于临界状态。

    在接下来的几节中,我复制他们的实验并解释结果。

    8.3 实现沙堆

    为了实现沙堆模型,我定义了一个名为SandPile的类,该类继承自Cell2D.py中定义的Cell2D

    
    class SandPile(Cell2D):
    
        def __init__(self, n, m, level=9):
            self.array = np.ones((n, m)) * level

    数组中的所有值都初始化为level,这通常大于倒塌阈值K

    以下是step方法,它找到大于K的所有细胞并将它们推翻:

    kernel = np.array([[0, 1, 0],
                           [1,-4, 1],
                           [0, 1, 0]], dtype=np.int32)
    
    def step(self, K=3):
        toppling = self.array > K
        num_toppled = np.sum(toppling)
        c = correlate2d(toppling, self.kernel, mode='same')
        self.array += c
        return num_toppled

    为了解释这是如何工作的,我将从一小堆开始,只有两个准备推翻的细胞:

    
    pile = SandPile(n=3, m=5, level=0)
    pile.array[1, 1] = 4
    pile.array[1, 3] = 4

    最初,pile.array是这样:

    
    [[0 0 0 0 0]
     [0 4 0 4 0]
     [0 0 0 0 0]]

    现在我们可以选择高于倒塌阈值的细胞:

    
    toppling = pile.array > K

    结果是一个布尔数组,但是我们可以像整数数组一样使用它:

    
    [[0 0 0 0 0]
     [0 1 0 1 0]
     [0 0 0 0 0]]

    如果我们关联这个数组和核起来,它会在每个toppling是 1 的地方复制这个核。

    
    c = correlate2d(toppling, kernel, mode='same')

    这就是结果:

    
    [[ 0  1  0  1  0]
     [ 1 -4  2 -4  1]
     [ 0  1  0  1  0]]

    注意,在核的副本重叠的地方,它们会相加。

    这个数组包含每个细胞的改变量,我们用它来更新原始数组:

    
    pile.array += c

    这就是结果:

    
    [[0 1 0 1 0]
     [1 0 2 0 1]
     [0 1 0 1 0]]

    这就是step的工作原理。

    默认情况下,correlate2d认为数组的边界固定为零,所以任何超出边界的沙粒都会消失。

    SandPile还提供了run,它会调用step,直到没有更多的细胞倒塌:

    
    def run(self):
        total = 0
        for i in itertools.count(1):
            num_toppled = self.step()
            total += num_toppled
            if num_toppled == 0:
                return i, total

    返回值是一个元组,其中包含时间步数和倒塌的细胞总数。

    如果你不熟悉itertools.count,它是一个无限生成器,它从给定的初始值开始计数,所以for循环运行,直到step返回 0。

    最后,drop方法随机选择一个细胞并添加一粒沙子:

    
    def drop(self):
        a = self.array
        n, m = a.shape
        index = np.random.randint(n), np.random.randint(m)
        a[index] += 1

    让我们看一个更大的例子,其中n=20

    
    pile = SandPile(n=20, level=10)
    pile.run()

    图 8.1:沙堆模型的初始状态(左),和经过 200 步(中)和 400 步(右)之后的状态

    初始级别为 10 时,这个沙堆需要 332 个时间步才能达到平衡,共有 53,336 次倒塌。 图?(左)展示了初始运行后的状态。 注意它具有重复元素,这是分形特征。 我们会很快回来的。

    图?(中)展示了在将 200 粒沙子随机放入细胞之后的沙堆构造,每次都运行直至达到平衡。 初始状态的对称性已被打破;状态看起来是随机的。

    最后图?(右)展示了 400 次放置后的状态。 它看起来类似于 200 次之后的状态。 事实上,这个沙堆现在处于稳定状态,其统计属性不会随着时间而改变。 我将在下一节中解释一些统计属性。

    8.4 重尾分布

    如果沙堆模型处于临界状态,我们希望为一些数量找到重尾分布,例如雪崩的持续时间和大小。 所以让我们来看看。

    我会生成一个更大的沙堆,n = 50,初始水平为 30,然后运行直到平衡状态:

    
    pile2 = SandPile(n=50, level=30)
    pile2.run()

    下面我们会运行 100,000 个随机放置。

    
    iters = 100000
    res = [pile2.drop_and_run() for _ in range(iters)]

    顾名思义,drop_and_run调用droprun,并返回雪崩的持续时间和倒塌的细胞总数。

    所以res(T, S)元组的列表,其中T是持续时间,以时间步长为单位,并且S是倒塌的细胞。 我们可以使用np.transposeres解构为两个 NumPy 数组:

    
    T, S = np.transpose(res)

    大部分放置的持续时间为 1,没有倒塌的细胞,所以我们会将这些过滤掉。

    T = T[T>1]
    S = S[S>0]

    TS的分布有许多小值和一些非常大的值。 我将使用thinkstats2中的Hist类创建值的直方图; 即每个值到其出现次数的映射。

    
    from thinkstats2 import Hist
    
    histT = Hist(T)
    histS = Hist(S)

    图 8.2:雪崩持续时间(左)和大小(右)的分布,线性刻度。

    图 8.3:雪崩持续时间(左)和大小(右)的分布,双对数刻度。

    图?显示了值小于 50 的结果。但正如我们在第?节中看到的那样,我们可以通过将它们绘制在双对数坐标上,更清楚地了解这些分布,如图?所示。

    对于 1 到 100 之间的值,分布在双对数刻度上几乎是直的,这表示了重尾。 图中的灰线斜率为 -1,这表明这些分布遵循参数为α=1的幂律。

    对于大于 100 的值,分布比幂律模型下降更快,这意味着较大值比模型的预测更少。 一种解释是,这种效应是由于沙堆的有限尺寸造成的,因此我们可能预计,更大的沙堆能更好地拟合幂律。

    另一种可能性是,这些分布并不严格遵守幂律,你可以在本章结尾的一个练习中探索。 但即使它们不是幂律分布,它们仍然是重尾的,因为我们预计系统处于临界状态。

    8.5 分形

    临界系统的另一个属性是分形几何。 图中的初始状态 (左)类似于分形,但是你不能总是通过观察来分辨。 识别分形的更可靠的方法是估计其分形维度,正如第?节那样。

    我首先制作一个更大的沙堆,n = 131,初始水平为 22。

    
    pile3 = SandPile(n=131, level=22)
    pile3.run()

    顺便说一下,这个沙堆达到平衡需要 28,379 步,超过 2 亿个细胞倒塌。

    为了更清楚地看到生成的团,我选择水平为 0, 1, 2 和 3 的细胞,并分别绘制它们:

    
    def draw_four(viewer, vals=range(4)):
        thinkplot.preplot(rows=2, cols=2)
        a = viewer.viewee.array
    
        for i, val in enumerate(vals):
            thinkplot.subplot(i+1)
            viewer.draw_array(a==vals[i], vmax=1)

    draw_four需要SandPileViewer对象,它在Sand.py中定义。 参数vals是我们想要绘制的值的列表; 默认值是 0, 1, 2 和 3。

    以下是它的使用方式:

    
    viewer3 = SandPileViewer(pile3)
    draw_four(viewer3)

    图 8.4:沙堆模型的初始状态,从上到下,从左到右选择水平为 0, 1, 2 和 3 的细胞。

    图?展示了结果。 现在对于这些图案中的每一个,我们都可以使用方框计数算法来估计分形维数:我们将计算沙堆中心的小方框中的细胞数量,然后看看细胞数量随着方框变大而如何增加。 这是我的实现:

    def count_cells(a):
        n, m = a.shape
        end = min(n, m)
    
        res = []
        for i in range(1, end, 2):
            top = (n-i) // 2
            left = (m-i) // 2
            box = a[top:top+i, left:left+i]
            total = np.sum(box)
            res.append((i, i**2, total))
    
        return np.transpose(res)

    参数a是 NumPy 布尔数组,值为 0 和 1。 方框的大小最初为 1,每次循环中,它会增加 2,直到到达终点,它是nm中较小的一个。

    每次循环中,box都是一组宽度和高度为i的细胞,位于数组中心。 total是方框中“开”细胞的数量。

    结果是一个元组列表,其中每个元组包含ii ** 2,用于比较,以及方框中的细胞数量。

    最后,我们使用np.transpose生成一个 NumPy 数组,其中包含ii ** 2total

    为了估计分形维度,我们提取行:

    steps, steps2, cells = res

    之后绘制结果:

    
    thinkplot.plot(steps, steps2, linestyle='dashed')
    thinkplot.plot(steps, cells)
    thinkplot.plot(steps, steps, linestyle='dashed')

    然后使用linregress在双对数刻度上拟合直线:

    
    from scipy.stats import linregress
    
    params = linregress(np.log(steps), np.log(cells))
    slope = params[0]

    图 8.5:与斜率位 1 和 2 的虚线相比,水平为 0, 1, 2 和 3 的细胞的方框计数。

    图?展示了结果。 请注意,只有val = 2(左下)从方框大小 1 开始,因为中心细胞的值为 2;其他直线从包含非零细胞数的第一个方框大小开始。

    在双对数刻度上,细胞计数几乎形成直线,这表明我们正在测量方框大小的有效范围内的分形维度。

    估计的分形维度是:

    
    0  1.871
    1  3.502
    2  1.781
    3  2.084

    值为 0, 1 和 2 的分形维度似乎明显不是整数,这表明图像是分形的。

    严格来说,值为 3 的分形维度与 2 不可区分,但考虑到其他值的结果,线的表观曲率和图案的外观,似乎它也是分形的。

    本章结尾的练习之一,要求你使用不同的nlevel值,再次运行此分析,来查看估计的维度是否一致。

    8.6 频谱密度

    提出沙堆模型的原始论文的标题是《自组织临界:1/f 噪声的解释》(Self-Organized Criticality: An Explanation of 1/f Noise)。 正如小标题所述的那样,Bak,Tang 和 Wiesenfeld 正试图解释为什么许多自然和工程系统表现出 1/f 噪声,这也被称为“闪烁噪声”和“粉红噪声”。

    为了了解粉红噪声,我们必须绕路来了解信号,频谱分析和噪声。

    信号:

    信号是随时间变化的任何数量。 一个例子是声音,即空气密度的变化。 在本节中,我们将探讨雪崩持续时间和大小在不同时间段内的变化。

    频谱分析:

    任何信号都可以分解为一组具有不同音量或功率的频率分量。 例如,演奏中央 C 上方的 A 的小提琴的声音,包含频率为 440 Hz 的主要分量,但它也包含较低功率分量,例如 880 Hz,1320 Hz 和其他整数倍的基频。 频谱分析是寻找构成信号的成分和它们的功率的过程,称为其频谱。

    噪声:

    在通常的用法中,“噪声”通常是一种不需要的声音,但在信号处理的情况下,它是一个包含许多频率成分的信号。

    噪声有很多种。 例如,“白噪声”是一个信号,它在很宽的频率范围内拥有相同功率的成分。

    其他种类的噪声在频率和功率之间有不同的关系。 在“红噪声”中,频率为f的功率为1 / f ** 2,我们可以这样写:

    P(f) = 1 / f ** 2 

    我们可以把指数 2 换成β来扩展它:

    P(f) = 1 / f ** β 

    β= 0时,该等式描述白噪声; 当β= 2时,它描述红噪声。 当参数接近 1 时,我们将结果称为1 / f噪声。 更一般来说,任何介于 0 和 2 之间的噪声称为“粉红”,因为它介于白色和红色之间。

    那么这如何适用于沙堆模型呢? 假设每次细胞倒塌时,它会发出声音。 如果我们在运行中记录了沙堆模型,它会是什么样子?

    在我的SandPile实现运行时,它会记录在每个时间步骤中,倒塌的细胞数量,并将结果记录在名为toppled_seq的列表中。 例如,在第?节中运行模型之后,我们可以提取产生的信号:

    signal = pile2.toppled_seq

    为了计算信号的频谱(同样,这是它包含的频率和它们的功率),我们可以使用快速傅立叶变换(FFT)。

    唯一的问题是噪声信号的频谱往往是嘈杂的。 但是,我们可以通过将一个长信号分成多个段,计算每个段的 FFT,然后计算每个频率的平均功率来使其平滑。

    该算法的一个版本被称为“韦尔奇方法”,SciPy 提供了一个实现。 我们可以像这样使用它:

    
    from scipy.signal import welch
    
    nperseg = 2048
    freqs, spectrum = welch(signal, nperseg=nperseg, fs=nperseg)

    nperseg是信号分解成的片段长度。 对于较长的片段,我们可以获得更多的频率成分,但由于平均的片段数较少,结果更加嘈杂。

    fs是“采样频率”,即每单位时间的信号中的数据点数。 通过设置fs = nperseg,我们可以得到从 0 到nperseg / 2的频率范围,但模型中的时间单位是任意的,所以频率并不意味着什么。

    返回值,freqspowers是 NumPy 数组,包含成分的频率及其相应的功率。

    如果信号是粉红噪声,我们预计:

    P(f) = 1 / f ** β 

    对两边取对数会得到:

    
    logP(f) = −β logf 

    所以如果我们在双对数刻度上绘制功率与频率的关系,我们预计有一条斜率为β的直线。

    图 8.6:随着时间推移的倒塌细胞的功率频谱,双对数刻度

    图?显示结果。 对于 10 到 1000 之间的频率(以任意单位),频谱落在一条直线上。 灰线斜率为 -1.58,这对应于由 Bak,Tang 和 Wiesenfeld 报告的参数β= 1.58

    这个结果证实了沙堆模型产生粉红噪声。

    8.7 还原论与整体论

    Bak,Tang 和 Wiesenfeld 的原始论文是过去几十年中被引用次数最多的论文之一。 其他系统已被证明是自组织临界,特别是沙堆模型已被详细研究。

    事实证明,沙堆模型并不是一个很好的沙堆模型。 沙子密集且不太粘,所以动量对雪崩的行为有着不可忽视的影响。 因此,与模型预测的相比,非常大和非常小的雪崩数量更少,并且分布可能不是重尾。

    Bak 建议,这个观察没有考虑到这一点。 沙堆模型并是现实的沙堆模型;它旨在成为一大类系统的简单模型。

    为了理解这个要点,考虑两种模式,还原论和整体论,会有帮助。 还原论模型通过描述系统的各个部分及其相互作用来描述系统。 当还原论模型用于解释时,它取决于模型和系统组成部分之间的类比。

    例如,为了解释为什么理想气体定律成立,我们可以用点质量模拟组成气体的分子,并将它们的相互作用建模为弹性碰撞。 如果你模拟或分析这个模型,你会发现它服从理想的气体定律。 一定程度上,该模型满足了,气体中的分子表现为模型中分子。 类比位于系统的各个部分和模型的各个部分之间。

    图 8.7:还原论模型的逻辑结构

    整体论模型更关注系统之间的相似性,而对类比部分不太感兴趣。 整体论建模方法通常由两个步骤组成,不一定按以下顺序:

    • 识别出现在各种系统中的一种行为。
    • 寻找证明这种行为的简单模型。

    例如,在《自私的基因》(The Selfish Gene)中,理查德道金斯(Richard Dawkins)认为,遗传进化只是进化系统的一个例子。 他确定了这些类别的基本元素 - 离散复制器(discrete replicator),可变性和差异生殖(differential reproduction) - 并提出任何包含这些元素的系统都会显示类似的行为,包括不带设计的复杂性。

    作为演化系统的另一个例子,他提出了“模因”(memes),即通过人与人之间的传播而复制的思想或行为 [2]。 由于模因争夺人类的注意力的资源,它们的演变方式与遗传进化相似。

    [2] “模因”的用法源自 Dawkins,并且早于 20 年前这个词在互联网上的衍生用法。

    模因模型的批评者指出,模因是基因的一个很差的类比。 模因在许多方面与基因不同。 但道金斯认为,这些差异并不重要,因为模因不可能与基因类似。 相反,模因和基因是同一类别的例子:进化系统。 它们之间的差异强调了真正的观点,即进化是一个适用于许多看似不同的系统的通用模型。 图?显示了这个论述的逻辑结构。

    Bak 也提出了类似的观点,即自组织临界性是一大类系统的通用模型:

    由于这些现象无处不在,它们不能依赖于任何具体的细节……如果一大类问题的物理结果是相同的,这为【理论家】提供了选项,选择属于该类的最简单的可能的【模型】,来进行详细的研究 [3]。

    [3] Bak, How Nature Works, Springer-Verlag 1996, page 43.

    许多自然系统表现出临界系统的行为特征。 Bak 对这种普遍性的解释是,这些系统是自组织临界性的示例。 有两种方式可以支持这个论点。 一个是建立一个特定系统的现实模型,并显示该模型表现出 SOC。 其次是证明 SOC 是许多不同模型的一个特征,并确定这些模型共同的基本特征。

    第一种方法我称之为还原论,可以解释特定系统的行为。 第二种是整体论的方法,解释了自然系统中临界性的普遍性。 他们是不同目的的不同模型。

    对于还原论模型,现实主义是主要优点,简单性是次要的。 对于整体模型,这是相反的。

    8.8 SOC,因果和预测

    如果股市指数在一天内下跌一个百分点,则不需要解释。 但如果它下降 10%,人们想知道为什么。 电视上的专家愿意提供解释,但真正的答案可能是没有解释。

    股票市场的日常变化展示了临界性的证据:数值变化的分布是重尾的,时间序列表现出粉红噪音。 如果股票市场是一个临界系统,我们应该预计,偶尔的巨大变化是市场普通行为的一部分。

    地震强度的分布也是重尾的,并且存在可能解释这种行为的,地质断层动力学的简单模型。 如果这些模型是正确的,那就意味着大地震是普遍的; 也就是说,与小地震相比,他们不需要更多解释。

    同样,查尔斯·佩罗(Charles Perrow)认为,像核电厂这样的大型工程系统的故障,就像沙堆模型中的雪崩一样。 大多数故障是小的,孤立的和无害的,但偶尔坏运气的巧合会产生灾难。 当发生重大事故时,调查人员会去寻找原因,但如果佩罗的“正常事故理论”是正确的,那么可能没有特殊原因导致严重故障。

    这些结论并不令人欣慰。 除其他事情外,它们意味着大地震和某些事故从根本上是不可预测的。不可能观察临界系统的状态,并说大雪崩是否“来临”。 如果系统处于临界状态,则总是可能发生大型雪崩。 它只取决于下一粒沙子。

    在沙堆模型中,大雪崩的原因是什么?哲学家有时会将直接(proximate)原因与根本(ultimate)原因区分开来,前者是最直接的原因,无论出于何种原因,后者被视为真正的原因。

    在沙堆模型中,雪崩的直接原因是一粒沙子,但引起大雪崩的沙粒与其他沙粒相同,所以它没有提供特别的解释。大雪崩的根本原因是整个系统的结构和动态:大雪崩的发生是因为它们是系统的一个属性。

    许多社会现象,包括战争,革命,流行病,发明和恐怖袭击,其特点是重尾分布。如果这些分布的原因是社会系统是临界的,那么这表明主要的历史事件可能从根本上是不可预测的,并且无法解释。

    8.9 练习

    练习 1

    本章的代码位于本书仓库中的 Jupyter 笔记本chap08.ipynb中。打开这个笔记本,阅读代码,然后运行单元格。你可以使用这个笔记本来练习本章的练习。我的解决方案在chap08soln.ipynb中。

    练习 2

    为了检验TS的分布是否是重尾的,我们将它们的直方图绘制在双对数刻度上,这就是 Bak,Tang 和 Wiesenfeld 在他们的论文中所展示。但我们在第?节中看到,这种可视化可能掩盖分布的形状。使用相同的数据,绘制一个图表,显示ST的累积分布(CDF)。对于他们的形状你可以说什么?他们是否遵循幂律?他们是重尾的嘛?

    你可能会发现将 CDF 绘制在对数和双对数刻度上会有所帮助。

    练习 3

    在第?章,我们发现沙堆模型的初始状态会产生分形图案。但是在我们随机放置了大量的沙粒之后,图案看起来更随机。

    从第?章中的示例开始,运行沙堆模型一段时间,然后计算 4 个水平中的每个的分形维度。沙堆模型是否处于稳定状态?

    练习 4

    另一种沙堆模型,称为“单一来源”模型,从不同的初始条件开始:中心细胞设为较大值,除了中心细胞,所有细胞设为 0,而不是所有细胞都是同一水平的。编写一个创建SandPile对象的函数,设置单一来源的初始条件,并运行,直到达到平衡。结果出现了分形吗?

    你可以在 http://math.cmu.edu/~wes/sandgallery.html 上了解这个版本的沙堆模型。

    练习 5

    在 1989 年的一篇论文中,Bak,Chen 和 Creutz 认为生命游戏是一个 SOC 系统 [5]。

    [5] “Self-organized criticality in the Game of Life”,可以在这里获取:http://www.nature.com/nature/journal/v342/n6251/abs/342780a0.html

    为了复制他们的测试,运行 GoL CA 直到稳定,然后随机选择一个细胞并翻转它。运行 CA 直到它再次稳定下来,跟踪T,这个是它需要的时间步数,以及S,受影响的细胞数。重复进行大量试验并绘制TS的分布。同时,记录在每个时间步骤中改变状态的细胞数量,并查看得到的时间序列是否与粉红噪声相似。

    练习 6

    在《自然界的分形几何》(The Fractal Geometry of Nature)中,Benoit Mandelbrot 提出了自然系统中重尾分布的普遍性的解释,他称之为“异端”。 正如 Bak 所言,许多系统可以独立产生这种行为。 相反,它们可能只是少数,但系统之间可能会有交互,它们导致行为的传播。

    为了支持这个论点,Mandelbrot 指出:

    • 观测数据的分布通常是“一个固定的底层真实分布,和一个高度可变的过滤器的联合效应”。
    • 重尾分布对于过滤器是健壮的;也就是说,“各种过滤器使其渐近行为保持不变”。

    你怎么看待这个观点? 你会把它描述为还原论还是整体论?

    练习 7

    http://en.wikipedia.org/wiki/Great_man_theory 上阅读“伟人”的历史理论。 自组织临界对这个理论有什么暗示?

    展开全文
  • 但实际上,它提供了一个强有力论据,有关系统及其各部分之间关系的:如果你观察真实城市的隔离,你不能总结为,个人的种族主义是直接原因,或者,城市居民是种族主义者。 当然,我们必须牢记这个论述的局限:...

    九、基于智能体的模型

    原文:Chapter 9 Agent-based models

    译者:飞龙

    协议:CC BY-NC-SA 4.0

    自豪地采用谷歌翻译

    我们迄今为止看到的模型可能具有“基于规则”的特征,因为它们涉及受简单规则支配的系统。 在本章和以后的章节中,我们将探索基于智能体(agent)的模型。

    基于智能体的模型包含智能体,它旨在模拟人和其他实体,它们收集世界的信息,制定决策并采取行动。

    智能体通常位于空间或网络中,并在本地彼此交互。 他们通常有不完整的,不全面的世界信息。

    智能体之间经常存在差异,而不像以前的所有模型,它们的所有成分都相同。 基于智能体的模型通常包含智能体之间,或世界中的随机性。

    自 20 世纪 70 年代以来,基于智能体的模型已成为经济学和其他社会科学,以及一些自然科学中的重要工具。

    基于智能体的模型对非均衡系统的动态建模(尽管它们也用于研究均衡系统)非常有用。 它们对于理解个人决策和系统行为之间的关系特别有用。

    本章的代码位于chap09.ipynb中,它是本书仓库中的 Jupyter 笔记本。 使用此代码的更多信息,请参见第?节。

    9.1 谢林模型

    1971 年,托马斯谢(Thomas Schelling)发表了《隔离的动态模型》(Dynamic Models of Segregation),该模型提出了种族隔离的简单模型。 谢林模型的世界是一个网格;每个细胞代表一栋房子。 房屋被两种智能体占用,标记为红色和蓝色,数量大致相同。 大约 10% 的房屋是空的。

    在任何时候,智能体可能会高兴或不高兴,这取决于领域中的其他智能体,每个房屋的“邻居”是八个相邻细胞的集合。在一个版本的模型中,如果智能体至少有两个像他们一样的邻居,智能体会高兴,但如果是一个或零,他们就会不高兴。

    模拟的过程是,随机选择一个智能体并检查他们是否高兴。 如果是这样,没有任何事情发生。如果不是,智能体随机选择其中一个未占用的细胞并移动。

    听到这种模型导致一些隔离,你可能不会感到惊讶,但是你可能会对这个程度感到惊讶。 很快,会出现相似智能体的群落。 随着时间的推移,这些群落会不断聚合,直到有少量的大型群落,并且大多数智能体生活在同质社区中。

    如果你不知道这个过程,只看到结果,你可能会认为智能体是种族主义者,但实际上他们都会在一个混合的社区感到非常高兴。 由于他们不愿意数量过大,所以在最坏的情况下,他们可能被认为是排外的。 当然,这些智能体是真实人物的过度简化,所以这些描述可能根本不恰当。

    种族主义是一个复杂的人类问题; 很难想象这样简单的模型可以揭示它。 但实际上,它提供了一个强有力论据,有关系统及其各部分之间关系的:如果你观察真实城市的隔离,你不能总结为,个人的种族主义是直接原因,或者,城市居民是种族主义者。

    当然,我们必须牢记这个论述的局限性:谢林模型证明了隔离的一个可能原因,但没有提到实际原因。

    9.2 谢林模型的实现

    为了实现谢林模型,我编写了另一个继承Cell2D的类:

    
    class Schelling(Cell2D):
    
        def __init__(self, n, m=None, p=0.5):
            self.p = p
            m = n if m is None else m
            choices = [0, 1, 2]
            probs = [0.1, 0.45, 0.45]
            self.array = np.random.choice(choices, (n, m), p=probs)

    参数nm是网格的维度,p是相似邻居比例的阈值。 例如,如果p = 0.5,也就是其邻居中少于 50% 为相同颜色,则智能体将不高兴。

    array是 NumPy 数组,其中每个细胞如果为空,则为 0;如果由红色智能体占用,则为1;如果由蓝色智能体占用,则为 2。 最初,10% 的细胞是空的,45% 为红色和 45% 为蓝色。

    谢林模型的step函数比以前的step函数复杂得多。 如果你对细节不感兴趣,你可以跳到下一节。 但是如果你坚持要看,你可能需要一些 NumPy 的提示。

    首先,我将生成逻辑数组,表明哪些细胞是红色,蓝色和占用的:

    
    a = self.array
    red = a==1
    blue = a==2
    occupied = a!=0

    我将使用np.correlate2d来计算,对于每个细胞,红色相邻细胞的数量和被占用的细胞数量。

    options = dict(mode='same', boundary='wrap')
    
    kernel = np.array([[1, 1, 1],
                       [1, 0, 1],
                       [1, 1, 1]], dtype=np.int8)
    
    num_red = correlate2d(red, kernel, **options)
    num_neighbors = correlate2d(occupied, kernel, **options)

    现在对于每个细胞,我们可以计算出红色的邻居比例和相同颜色的比例:

    
    frac_red = num_red / num_neighbors
    frac_blue = 1 - frac_red
    frac_same = np.where(red, frac_red, frac_blue)

    frac_red只是num_rednum_neighbors的比率,而frac_bluefrac_red的补。

    frac_same有点复杂。 函数np.where就像逐元素的if表达式一样。 第一个参数是从第二个或第三个参数中选择元素的条件。

    在这种情况下,如果redTruefrac_same获取frac_red的相应元素。 在红色为False的情况下,frac_same获取frac_blue的相应元素。

    现在我们可以确定不满意的智能体的位置:

    unhappy_locs = locs_where(occupied & (frac_same < self.p))

    结果unhappy_locs是一个 NumPy 数组,其中每行都是占用的细胞的坐标,其中frac_same低于阈值p

    locs_wherenp.nonzero的包装函数:

    def locs_where(condition):
        return np.transpose(np.nonzero(condition))

    np.nonzero接受一个数组并返回所有非零元素的坐标,但结果是两个元组的形式。 np.transpose将结果转换为更有用的形式,即每行都是坐标对的数组。

    同样,empty_locs是一个数组,包含空细胞的坐标:

    empty_locs = locs_where(a==0)

    现在我们到达了模拟的核心。 我们遍历不高兴的智能体并移动它们:

    for source in unhappy_locs:
        i = np.random.randint(len(empty_locs))
        dest = tuple(empty_locs[i])
        a[dest] = a[tuple(source)]
        a[tuple(source)] = 0
        empty_locs[i] = source

    i是一个用来随机选择空细胞的索引。

    dest是一个包含空细胞的坐标的元组。

    为了移动智能体,我们将值从source复制到dest,然后将source的值设置为 0(因为它现在是空的)。

    最后,我们用source替换empty_locs中的条目,以便刚刚变为空的细胞可以由下一个智能体选择。

    9.3 隔离

    图 9.1:谢林的隔离模型,n = 100,初始条件(左),2 步后(中)和 10 步后(右)

    现在让我们看看我们运行模型时会发生什么。 我将以n = 100p = 0.3开始,并运行 10 个步骤。

    grid = Schelling(n=100, p=0.3)
    for i in range(10):
        grid.step()

    图?展示了初始状态(左),2 步(中)后和 10 步(右)后的模拟。

    群落迅速形成,红色和蓝色的智能体移动到隔离集群中,它们由空细胞的边界分隔。

    对于每种状态,我们可以计算隔离度,它是相同颜色的邻居的比例。在所有细胞中的平均值:

    np.sum(frac_same) / np.sum(occupied)

    在图?中,相似邻居的比例均值在初始状态中为 55%,两步后为 71%,10 步后为 80%!

    请记住,当p = 0.3时,如果 8 个邻居中的 3 个是他们自己的颜色,那么智能体会很高兴,但他们最终居住在一个社区中,其中 6 或 7 个邻居是自己的颜色。

    图 9.2:随着时间的推移,谢林模型中的隔离程度,范围为p

    图?显示了隔离程度如何增加,以及它在几个p值下的平稳位置。 当p = 0.4时,稳定状态下的隔离程度约为 88%,且大多数智能体没有不同颜色的邻居。

    这些结果令许多人感到惊讶,它们成为了个人决策与系统行为之间的,复杂且不可预测的关系的鲜明示例。

    9.4 糖域

    1996年,约书亚爱泼斯坦(Joshua Epstein)和罗伯特阿克斯特尔(Robert Axtell)提出了糖域(Sugarscape),这是一个“人造社会”的智能体模型,旨在支持经济学和其他社会科学的相关实验。

    糖域是一款多功能的模型,适用于各种主题。 作为例子,我将复制 Epstein 和 Axtell 的书《Growing Artificial Societies》的前几个实验。

    糖域最简单的形式是一个简单的经济模型,智能体在二维网格上移动,收集和累积代表经济财富的“糖”。 网格的一些部分比其他部分产生更多的糖,并且一些智能体比其他人更容易找到它。

    这个糖域的版本常用于探索和解释财富的分布,特别是不平等的趋势。

    在糖域的网格中,每个细胞都有一个容量,这是它可容纳的最大糖量。 在原始状态中,有两个高糖区域,容量为 4,周围是同心环,容量分别为 3, 2 和 1。

    图 9.3:原始糖域模型的复制品:初始状态(左),2 步后(中)和 100 步后(右)。

    图?(左)展示了初始状态,最黑暗的区域表示容量最高的细胞,小圆圈表示智能体。

    最初有随机放置的 400 个智能体。 每个智能体有三个随机选择的属性:

    糖:

    每个智能体最开始都有先天的糖分,从 5 到 25 之间均匀选择。

    代谢:

    在每个时间步骤中,每个智能体都必须消耗一定数量的糖,从 1 到 4 之间均匀选择。

    视力:

    每个智能体可以“看到”附近细胞中糖量,并移动到最多的细胞,但是与其它智能体相比,一些智能体可以看到更远的细胞。 智能体看到的距离从 1 和 6 之间均匀选择。

    在每个时间步骤中,智能体以随机顺序一次移动一格。 每个智能体都遵循以下规则:

    • 智能体在 4 个罗盘方向的每一个方向上调查k个细胞,其中k是智能体的视野范围。
    • 它选择糖分最多的未占用的细胞。 在相等的情况下,选择较近的细胞;在距离相同的细胞中,它随机选择。
    • 智能体移动到选定的细胞并收获糖分,将收获增加到其积累的财富并将细胞清空。
    • 智能体根据代谢消耗其财富的一部分。 如果结果总量为负数,智能体“饿死”并被删除。

    在所有智能体完成这些步骤之后,细胞恢复一些糖,通常为 1 单位,但每个细胞中的总糖分受其容量限制。

    图?(中)显示两步后模型的状态。 大多数智能体正在移到糖最多的地区。 视力高的智能体移动速度最快;视力低的智能体往往会卡在高原上,随机游走,直到它们足够接近来看到下一个水平。

    出生在糖分最少的地区的智能体可能会饿死,除非他们的视力很好,先天条件也很高。

    在高糖地区,随着糖分的出现,智能体相互竞争,寻找和收获糖分。 消耗高或视力低的智能体最有可能挨饿。

    当糖在每个时间步骤增加 1 个单位时,就没有足够的糖来维持我们开始的 400 个智能体。 人口起初迅速下降,然后缓慢下降,在大约 250 左右停下。

    图?(右)显示了 100 个时间步后的模型状态,大约有 250 个智能体。 存活的智能体往往是幸运者,出生时视力高和/或代消耗低。 存活到这里的话,它们可能会永远存活,积累无限量的糖。

    9.5 财富的不平等

    在目前的形式下,糖域建立了一个简单的生态学模型,可用于探索模型参数之间的关系,如增长率和智能体的属性,以及系统的承载能力(在稳定状态下生存的智能体数量)。 它模拟了一种形式的自然选择的,“适应度”较高的智能体更有可能生存下来。

    该模型还表现出一种财富不平等,一些智能体积累糖的速度比其他智能体快。 但是对于财富分布,很难说具体的事情,因为它不是“静止的”。 也就是说,分布随着时间的推移而变化并且不会达到稳定状态。

    然而,如果我们给智能体有限的寿命,这个模型会产生固定的财富分布。 然后我们可以运行实验,来查看参数和规则对此分布的影响。

    在这个版本的模型中,智能体的年龄在每个时间步增加,并且从 60 到 100 之间的均匀分布中,随机选择一个寿命。如果智能体的年龄超过其寿命,它就会死亡。

    当智能体因饥饿或年老而死亡时,它由属性随机的新智能体所取代,所以总人口是不变的。

    图 9.4:100, 200, 300 和 400 步(灰线)和 500 步(黑线)之后的糖(财富)的分布。 线性刻度(左)和对数刻度(右)。

    从接近承载能力的 250 个智能体开始,我运行了 500 个步骤的模型。 在每 100 步之后,我绘制了智能体积累的糖的分布。 图?在线性刻度(左)和对数刻度(右)中展示结果。

    经过大约 200 步(这是最长寿命的两倍)后,分布变化不大。 并且它向右倾斜。

    大多数智能体积累的财富很少:第 25 百分位数大约是 10,中位数大约是 20。但是少数智能体积累了更多:第 75 百分位数是大约 40,最大值大于 150。

    在对数刻度上,分布的形状类似于高斯或正态分布,但右尾被截断。 如果它在对数刻度上实际上是正态的,则分布是对数正态分布,这是一种重尾分布。 实际上,几乎每个国家和全世界的财富分布都是重尾分布。

    如果说糖域解释了为什么财富分布是重尾的,但是糖域变化中的不平等的普遍性表明,不平等是许多经济体的特征,甚至是非常简单的经济体。 一些实验表明避免或减轻并不容易,它们带有一些规则,对纳税和其他收入转移进行建模。

    9.6 实现糖域

    糖域比以前的模型更复杂,所以我不会在这里介绍整个实现。 我将概述代码的结构,你可以在 Jupyter 笔记本chap09.ipynb中查看本章的细节,它位于本书的仓库中。 如果你对细节不感兴趣,你可以跳到下一节。

    以下是带有step方法的Agent类:

    
    class Agent:
    
        def step(self, env):
            self.loc = env.look_around(self.loc, self.vision)
            self.sugar += env.harvest(self.loc) - self.metabolism
            self.age += 1

    在每个步骤中,智能体移动,收获糖,并增加年龄。

    参数env是环境的引用,它是一个Sugarscape对象。 它提供了方法look_around和收获:

    • look_around获取智能体的位置,这是一个坐标元组,以及智能体的视野,它是一个整数。 它返回智能体的新位置,这是糖分最多的可见细胞。
    • harvest需要智能体的(新)位置,并在移除并返回该位置的糖分。

    这里是Sugarscape类和它的step方法(不需要替换):

    class Sugarscape(Cell2D):
    
        def step(self):
    
            # loop through the agents in random order
            random_order = np.random.permutation(self.agents)
            for agent in random_order:
    
                # mark the current cell unoccupied
                self.occupied.remove(agent.loc)
    
                # execute one step
                agent.step(self)
    
                # if the agent is dead, remove from the list
                if agent.is_starving():
                    self.agents.remove(agent)
                else:
                    # otherwise mark its cell occupied
                    self.occupied.add(agent.loc)
    
            # grow back some sugar
            self.grow()
            return len(self.agents)

    Sugarscape继承自Cell2D,因此它与我们所见过的其他基于网格的模型相似。

    这些属性包括agents,它是Agent对象的列表,以及occupied,它是一组元组,其中每个元组包含智能体占用的细胞的坐标。

    在每个步骤中,Sugarscape以随机顺序遍历智能体。 它调用每个智能体的step,然后检查它是否已经死亡。 所有智能体都移动后,一些糖会恢复。

    如果你有兴趣更加了解 NumPy ,你可能需要仔细看看make_visible_locs,它构建一个数组,其中每行包含智能体可见的细胞坐标,按距离排序,但距离相同的细胞 是随机顺序。

    你可能想看看Sugarscape.make_capacity,它初始化细胞的容量。 它演示了np.meshgrid的使用,这通常很有用,但需要一些时间才能理解。

    9.7 迁移和波动行为

    图 9.5:Sugarscape中的波动行为:初始状态(左),6 步后(中)和 12 步后(右)

    虽然Sugarscape的主要目的不是探索空间中的智能体的移动,但 Epstein 和 Axtell 在智能体迁移时,观察到一些有趣的模式。

    如果我们开始把所有智能体放在左下角,他们会迅速走向最近的高容量细胞的“山峰”。 但是如果有更多的智能体,单个山峰不足以支持它们的话,他们很快就会耗尽糖分,智能体被迫进入低容量地区。

    视野最长的那些,首先穿过山峰之间的山谷,并且像波一样向东北方向传播。 因为他们在身后留下一些空细胞,所以其他智能体不会追随,直到糖分恢复。

    结果是一系列离散的迁移波,每个波都像一个连贯的物体,就像我们在规则 110 CA 和生命游戏中看到的飞船(参见第?节)。

    图?显示了初始条件下(左),6 个步骤(中)和 12 个步骤(右)之后的模型状态。 你可以看到,前两个波到达并穿过第二个山峰,留下了一串空细胞。 你还可以看到这个模型的动画版本,其中波形更清晰可见。

    虽然这些波动由智能体组成,但我们可以将他们视为自己的实体,就像我们在“生命游戏”中想到的滑翔机一样。

    这些波动的一个有趣的属性是,它们沿对角线移动,这可能是令人惊讶的,因为这些智能体本身只是向北或向东移动,从不向东北方移动。 像这样的结果 - 团队或“集合”拥有智能体没有的属性和行为 - 在基于智能体的模型中很常见。 我们将在下一章看到更多的例子。

    9.8 涌现

    本章中的例子展示了复杂性科学中最重要的想法之一:涌现。 涌现性是系统的一个特征,由它的成分相互作用而产生,而不是它们的属性。

    为了澄清什么是涌现,考虑它不是什么会有帮助。 例如,砖墙很硬,因为砖和砂浆很硬,所以这不是涌现。 再举一个例子,一些刚性结构是由柔性部件构成的,所以这看起来像是一种涌现。 但它至多是一种弱例,因为结构特性遵循已知的力学定律。

    相反,我们在谢林模型中看到的隔离是一种涌现,因为它不是由种族主义智能体造成的。 即使智能体只是轻微排外,系统的结果与智能体的决策意图有很大不同。

    糖域中的财富分配可能是涌现,但它是一个弱例,因为我们可以根据视力,代谢和寿命的分布合理预测它。 我们在最后一个例子中看到的波动行为可能是一个更强的例子,因为波动显示出智能体显然没有的能力 - 对角线运动。

    涌现性令人惊讶:即使我们知道所有规则,也很难预测系统的行为。难度不是偶然的;事实上,它可能是涌现的决定性特征。

    正如沃尔夫勒姆在“新科学”中所讨论的那样,传统科学是基于这样的公理:如果你知道管理系统的规则,那么你可以预测它的行为。 我们所谓的“法律”通常是计算的捷径,它使我们能够预测系统的结果而不用建立或观察它。

    但是许多细胞自动机在计算上是不可减少的,这意味着没有捷径。 获得结果的唯一方法是实现该系统。

    一般而言,复杂系统可能也是如此。 对于具有多个成分的物理系统,通常没有产生解析解的模型。 数值方法提供了一种计算捷径,但仍存在质的差异。

    解析解通常提供用于预测的恒定时间算法;也就是说,计算的运行时间不取决于预测的时间尺度t。 但数值方法,模拟,模拟计算和类似方法需要的时间与t成正比。 对于许多系统来说,我们无法计算出可靠的预测。

    这些观察表明,涌现性基本上是不可预测的,对于复杂系统我们不应该期望,通过计算捷径来找到自然规律。

    对某些人来说,“涌现”是无知的另一个名字; 根据这种思维,如果我们针对它没有还原论的解释,那么这个属性就是涌现的,但如果我们在将来更好地理解它,它就不再是涌现的。

    涌现性的状况是有争议的话题,所以对此持怀疑态度是恰当的。 当我们看到明显的涌现性时,我们不应该假设永远不会有还原论解释。但我们也不应该假设必须有。

    本书中的例子和计算等价原理提供了很好的理由,认为至少有些涌现性永远不会被古典还原论模型“解释”。

    你可以在这里更加了解涌现:http://en.wikipedia.org/wiki/Emergence

    9.9 练习

    练习 1

    本章的代码位于本书仓库的 Jupyter 笔记本chap09.ipynb中。打开这个笔记本,阅读代码,然后运行单元格。你可以使用这个笔记本来练习本章的练习。我的解决方案在chap09soln.ipynb中。

    练习 2

    《The Big Sort》的作者 Bill Bishop 认为,美国社会越来越由政见所隔离,因为人们选择生活在志趣相投的邻居之中。

    Bishop 所假设的机制并不是像谢林模型中的智能体那样,如果他们是孤立的,他们更有可能移动,但是当他们出于任何原因移动时,他们可能会选择一个社区,其中的人与他们自己一样。

    修改谢林模型的实现来模拟这种行为,看看它是否会产生类似程度的隔离。

    有几种方法可以模拟 Bishop 的假设。在我的实现中,随机选择的智能体会在每个步骤中移动。每个智能体考虑k个随机选择的空位置,并选择相似邻居的比例最高的位置。隔离程度和k有什么关系?

    练习 3

    在糖域的第一个版本中,我们从不添加智能体,所以一旦人口下降,它就不会恢复。 在第二个版本中,我们只是在智能体死亡时才取代,所以人口是不变的。 现在让我们看看如果我们增加一些“人口压力”会发生什么。

    编写糖域的一个版本,在每一步结束时添加一个新的智能体。 添加代码来计算每个步骤结束时,智能体的平均视力和平均消耗。 运行模型几百步,绘制人口,平均视力和平均消耗随时间的变化。

    你应该能够通过继承SugarScape并覆盖__init__step来实现这个模型。

    练习 4

    在心灵哲学中,强人工智能是这样的理论,即受到适当编程的计算机可以拥有思想,与人类拥有的思想相同。

    约翰·塞尔(John Searle)提出了一个名为“中文房间”的思想实验,旨在表明强 AI 是虚假的。 你可以在 http://en.wikipedia.org/wiki/Chinese_room 上阅读。

    对中文房间的论述的系统回复是什么? 你对涌现的认识如何影响你对系统回复的反应?

    展开全文
  • 计算思维及其培养方式

    千次阅读 2019-11-27 19:13:42
    计算思维(Computational Thinking)关于“思维”, 大家想必都听说过“逻辑思维”(“逻辑”不是“罗辑”)、“批判性思维”等名词。相比较而言,“计算思维...
  • 四个架构设计案例及其思维方式

    千次阅读 2019-02-11 12:45:51
    架构的本质是管理复杂性,抽象、分层、分治和演化思维是我们工程师/架构师应对和管理复杂性的四种最基本武器。 在上一篇架构之道~四种核心架构思维中,我先介绍了抽象、分层、分治和演化这四种应对复杂性的基本武器...
  • 复杂性科学

    2017-12-18 00:00:00
    复杂性是混沌性的局部与整体之间的非线形形式,由于局部与整体之间的这个非线性关系,使得我们不能通过局部来认识整体。简介 复杂性科学(Complexity Science)兴起于20世纪80年代的复杂性科学(complexity sciences)...
  • 可计算性与计算复杂性发展史

    千次阅读 2013-01-08 13:12:54
    可计算理论是由递归函数的产生而发展的,其核心问题是:什么是可计算的,以及如何保证计算的自动,有效和正确。数理逻辑学家研究定理证明及其推导的特殊计算,从而产生了可计算理论。 20世纪三十年代,数理学...
  • 批判性思维

    千次阅读 2018-08-01 09:05:27
    一、批判性思维基础 1. 概念 2. 相关技能 3. 断言 4.两种论证 5. 论证的结构 6. 影响批判性思维的错误观念 二、不清晰的表达 1. 模糊 2. 歧义 3. 抽象 4. 未界定术语 三、清晰的写作 论文写作 四、...
  • 随着思维导图的兴起,如今大家对思维导图都有一定的认识了。但大部分人都只是片面的认识思维导图,并不理解思维导图的原理和本质,对这款工具都有种极端的认知。一部分人认为它是一个万能的工具,十分依赖它,什么...
  • 20世纪中期开始的人工智能研究...在这里,我们要探讨人工智能产生的原因和条件、人工智能的本质、人工智能和思维的关系及其发展趋势等一系列理论问题。 目录 第一节 人工智能的可能、现实和界限 一 什么是人工智...
  • 写在前面架构的本质是管理复杂性,抽象、分层、分治和演化思维 是我们工程师 / 架构师应对和管理复杂性的四种最基本武器。在我之前写的文章 《优秀架构师必须掌握的架构思维》(点击标题查看原文) 中,我先介绍了...
  • 思维导图(脑图)软件及其应用

    千次阅读 2011-09-23 09:58:23
    而脑图软件节约了我们的时间,使我们的思维可视化,形象化。它不光在教育领域,实际上在各行各业都有着广泛的用途,脑图软件也许将像Word一样,成为我们生活,学习,工作的一部分,而它在某些方面更
  • 创造性思维(Creative Thinking)

    千次阅读 2014-09-18 16:27:24
    创造性思维是一种具有开创意义的思维活动,即开拓...从广义上讲,创造性思维不仅表现为作出了完整的新发现和新发明的思维过程,而且还表现为在思考的方法和技巧上,在某些局部的结论和见解上具有新奇独到之处的思维活动
  • 数源思维完成目标设定

    千次阅读 2017-03-24 09:59:21
    数源思维是为非专业...在本文中,数源思维通过问、拆、解、谋四步就能将数据及其方法很好的融合到业务问题的解决中,从而将业务解题能力从经验时代提升到数据时代。 本文选自《数源思维:业务导向的数据思维秘籍》。
  • 我的软件开发思维方法科学观

    千次阅读 2008-08-03 09:56:00
    我的软件开发思维方法科学观 [ 摘 要 ] 本文介绍了本人软件开发的体会,着重分析了软件开发几个问题的思维方法科学观,并提出在当前软件开发中对各种技术和思想中体会科学的思维方法,哲学的方法。 [ 关 键 词 ] ...
  • 最近和女友,咳咳…(说出来可能会被打s)学习JS数组方法,用几个字形容的话就是听说过,实际使用、遇到的时候就分不清具体方法会得到怎样的结果。 今天我将通过这篇文章好好整理一下关于JS数组的方法,让大家通过这...
  • 计算思维,是指运用计算机科学的基础概念、思想和方法去解决问题时的思维活动,涉及如何在计算机中表示问题、如何让计算机通过执行有效的算法过程来解决问题。 计算是利用计算机解决问题的过程,计算机科学是关于...
  • 量化投资数据挖掘及其相关方法

    千次阅读 2014-06-14 12:37:03
    由于是在高维特征空间中建立线性学习机,所以与线性模型相比,不但几乎不增加计算的复杂性,而且在某种程度上避免了维数灾难。这一切要归功于核函数的展开和计算理论。 正因为有这个优势,使得SVM特别适合于进行...
  • 系统思维与其他思维并列,例如:批判思维(评估或质疑某个说法的有效)、分析思维(根据一套规律或原则进行分析)、创新思维(从0到1或组合现有的创造新产品或想法)等。 一位牛逼的思考者(掌握数学、工程、物理...
  • 四种核心架构思维

    万次阅读 2019-02-11 11:56:35
    架构的本质是管理复杂性,抽象、分层、分治和演化思维是我们工程师/架构师应对和管理复杂性的四种最基本武器。 最近团队来了一些新人,有些有一定工作经验,是以高级工程师/架构师身份进来的,但我发现他们大部分人...
  • 试论软件的可靠性及其保证

    万次阅读 2013-11-27 11:23:00
    试论软件的可靠性及其保证 来源:ChinaItLab  用软件系统规模越做越大越复杂,其可靠越来越难保证。应用本身对系统运行的可靠要求越来越高,在一些关键的应用领域,如航空、航天等,其可靠要求尤为重要,在...
  • 微服务之核心架构思维

    千次阅读 2018-05-31 10:35:29
    一、介绍架构的本质是管理复杂性,抽象、分层、分治和演化思维是我们工程师/架构师应对和管理复杂性的四种最基本武器。最近团队来了一些新人,有些有一定工作经验,是以高级工程师/架构师身份进来的,但我发现他们大...
  • 灰色系统理论及其应用 (一) :灰色系统概论、关联分析、与传统统计方法的比较 灰色系统理论及其应用 (二) :优势分析 灰色系统理论及其应用 (三) :生成数 灰色系统理论及其应用 (四) :灰色模型 GM 灰色系统...
  • 思维导图的三招十八式

    千次阅读 2011-11-17 16:36:11
    思维导图的三招十八式  张鄂勇 编著 ISBN978-7-121-14010-5 2012年1月出版 定价:49.00元 16开 396页 宣传语:会降龙十八掌,才混得到九袋弟子。  懂点思维导图,方能笑看职场风云。 内容简介 “一图胜...
  • 程序员思维

    千次阅读 2014-05-15 22:45:26
    程序员思维
  • 逻辑思维

    千次阅读 2017-09-25 16:05:07
    逻辑思维,又称抽象思维,是人的理性认识阶段,人运用概念、判断、推理等思维类型反映事物本质与规律的认识过程。
  • 计算机思维

    2018-04-22 13:11:38
    计算机思维建立的基础是计算机处理的能力及其局限,不管是由人还是机器来执行。计算机方法和模型使我们有勇气去解决问题,设计出无论哪个个人都无法独立担纲的系统。计算机思维面对着有关机器智能的不解之谜:人做...
  • 思维导图”初认识

    万次阅读 2014-09-08 10:25:09
    思维导图  一、什么是思维导图 二、如何绘制思维导图 三、思维导图的应用 四、思维导图与知识树 五、齐伟系列(1):概念图/思维导图导论 ...
  • 突破思维的障碍

    万次阅读 2013-12-16 15:50:13
     在众多的讲述思维及创造的书中,这是一本普通的小册子,但它却是吸引人的。作者用妙趣横生而又日常可见的素材向我们娓娓叙说了人人都会关心的问题,即我们是否意识到自己的思维障碍,怎样克服它,让自己变得更...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,160
精华内容 10,864
关键字:

复杂性思维及其方法