元胞自动机实现多数分类算法

元胞自动机(Cellular automaton)

元胞自动机是由元胞组成的网格,每个元胞都根据邻域的状态来选择开或关。所有的元胞都遵循同样的规则,也称为元胞的更新规则,规则根据各元胞邻域的当前状态决定元胞的下一步状态。同自然界的复杂系统一样,元胞自动机也是由大量简单个体(元胞)组成,不存在中央控制,每个个体都只与少量其他个体交互。而且元胞自动机也能表现出非常复杂的行为,它们的行为很难甚至不可能通过其更新规则来预测。元胞自动机有很多种类型,著名的“生命游戏”也是元胞自动机的一种。

初等元胞自动机(Elementary cellular automaton)

初等元胞自动机是一维两状态的元胞自动机,每个元胞仅与两个相邻元胞相连。元胞自动机的时空图表现了元胞自动机的立体构型随时间的变化,最顶上一行是一维元胞自动机的初始状态设置,下面跟着的依次是每一步更新后的状态。

执行“多数分类(Majority classification)”任务的元胞自动机

该元胞自动机要能区分初始状态中是开状态还是关状态占多数。如果是开状态占多数,最后所有元胞就应当都变成开状态。同样,如果是关状态占多数,最后所有元胞就应该都变成关状态。多数分类任务有点类似于选举,是在大家都只知道最近邻居政治观点下预测两个候选人谁会赢。

我们使用一维元胞自动机,每个元胞与相邻的6个元胞相连,这样元胞的邻域中就有7个元胞(包括自己)。一个合理的想法是:“元胞应当变成邻域中当前占多数的状态。”这就好象根据你自己和邻居的多数意见来预测哪个候选人会当选。然而,这个“局部多数投票”元胞自动机并不能完成任务。

我们使用的是梅拉妮·米歇尔(Melanie Mitchell)在《复杂》(Complexity: A Guided Tour)一书第203页给出的规则:

0000010100000110000101011000011100000111000001000001010101
0101110110010001110111000001010000000101111101111111111011
011101111111

第1位是邻域全为0时中间元胞的更新状态,第2位是邻域为0000001时中间元胞的更新状态,依次往后。由于邻域状态有 27 = 128 种可能,因此该规则有128位。但是光看这些数位是看不出这个规则如何运作,也无法知道为何它进行多数分类时适应度很高。

实现该算法的 C# 程序

下面就是相应的 C# 源程序 MainForm.cs:

  1 using System;
  2 using System.Drawing;
  3 using System.Windows.Forms;
  4 
  5 namespace Skyiv.CellularAutomaton.MajorityClassification
  6 {
  7   sealed class MainForm : Form
  8   {
  9     static readonly int sizeCellular = 3;
 10     static readonly int nCellular = 201;
 11     static readonly int lines = nCellular;
 12     static readonly Pen pen = new Pen(Color.Black, sizeCellular);
 13     static readonly string strRuler =
 14       "0000010100000110000101011000011100000111000001000001010101" +
 15       "0101110110010001110111000001010000000101111101111111111011" +
 16       "011101111111";
 17     static readonly bool[] ruler = new bool[strRuler.Length];
 18 
 19     Graphics gc;
 20 
 21     MainForm()
 22     {
 23       Text = "Majority Classification";
 24       BackColor = Color.White;
 25       ClientSize = new Size(nCellular * sizeCellular + 1, lines * sizeCellular + 1 + 32);
 26       for (var i = 0; i < ruler.Length; i++) ruler[i] = strRuler[i] == '1';
 27     }
 28 
 29     protected override void OnPaint(PaintEventArgs e)
 30     {
 31       gc = e.Graphics;
 32       DrawGrid(true);
 33       var cellulars = GetInitCellulars();
 34       DrawCellulars(cellulars, 0);
 35       DisplayMessage(cellulars);
 36       for (var i = 1; i < lines; i++)
 37       {
 38         StepIt(cellulars);
 39         DrawCellulars(cellulars, i);
 40       }
 41       base.OnPaint(e);
 42     }
 43 
 44     void StepIt(bool[] cellulars)
 45     {
 46       var buf = new bool[cellulars.Length];
 47       for (var i = 0; i < nCellular; i++)
 48         buf[i] = ruler[GetValue(cellulars, i)];
 49       Array.Copy(buf, cellulars, cellulars.Length);
 50     }
 51 
 52     int GetValue(bool[] cellulars, int idx)
 53     {
 54       var n = 0;
 55       idx = (idx + 3) % nCellular;
 56       for (var i = 0; i < 7; i++)
 57         if (cellulars[(idx - i + nCellular) % nCellular])
 58           n += 1 << i;
 59       return n;
 60     }
 61 
 62     void DrawCellulars(bool[] cellulars, int line)
 63     {
 64       for (var i = 0; i < cellulars.Length; i++)
 65         if (cellulars [i])
 66           Set(i, line);
 67     }
 68 
 69     void DisplayMessage(bool[] cellulars)
 70     {
 71       var blacks = 0;
 72       foreach (var cellular in cellulars)
 73         if (cellular)
 74           blacks++;
 75       Out("Black:{0} White:{1}", blacks, cellulars.Length - blacks);
 76     }
 77 
 78     void Out(string fmt, params object[] args)
 79     {
 80       gc.DrawString(string.Format(fmt, args), new Font("Courier New", 10),
 81         Brushes.Blue, new Point(5, lines * sizeCellular + 9));
 82     }
 83 
 84     bool[] GetInitCellulars()
 85     {
 86       var rand = new Random();
 87       var cellulars = new bool[nCellular];
 88       for (var i = 0; i < cellulars.Length; i++)
 89         cellulars [i] = rand.Next() % 2 == 0;
 90       return cellulars;
 91     }
 92 
 93     void DrawGrid(bool onlyBorder)
 94     {
 95       var pen = new Pen(Color.Red, 1);
 96       var len = nCellular * sizeCellular;
 97       for (var i = onlyBorder ? lines : 0; i <= lines; i++)
 98       {
 99         var k = i * sizeCellular;
100         gc.DrawLine(pen, 0, k, len, k);
101       }
102       len = lines * sizeCellular;
103       for (var i = onlyBorder ? nCellular : 0; i <= nCellular; i++)
104       {
105         var k = i * sizeCellular;
106         gc.DrawLine(pen, k, 0, k, len);
107       }
108     }
109 
110     void Set(int x, int y)
111     {
112       var y2 = y * sizeCellular + sizeCellular / 2;
113       gc.DrawLine(pen, x * sizeCellular, y2, (x + 1) * sizeCellular, y2);
114     }
115 
116     static void Main()
117     {
118       Application.Run(new MainForm());
119     }
120   }
121 }

简要分析

  1. 第9行的静态只读变量 sizeCellular 表示每个元胞方格的边长,必须为奇数。
  2. 第10行的静态只读变量 nCellular 表示每行有多少个元胞,最好为奇数,以免在多数分类时出现平局的情况。
  3. 第11行的静态只读变量 lines 表示要迭代多少次。
  4. 第13行的静态只读变量 strRuler 表示迭代的规则。
  5. 主要工作在从第29行到42行的 OnPaint 方法中进行。
  6. 第84行到第91行的 GetInitCellulars 方法随机地初始化元胞的初始状态。
  7. 第36行到第40行的循环按照指定的规则进行迭代。
  8. 第44行到第50行的 StepIt 方法执行具体的迭代步骤。
  9. 第52行到第60行的 GetValue 方法计算元胞邻域的值。

运行结果

该程序几次典型的运行结果如下所示:

上图显示白色占优,结果正确。这种情况很常见。

上图显示黑色占优,结果正确。这种情况也很常见。

上图显示白色占优,结果错误。这种情况比较少见。

上图显示黑色占优,结果错误。这个结果错误在于最终的迭代结果不是全黒,而混入了少量的白色元胞。这个程序只迭代 200 步,其实只要再迭代几步后就可以得到正确的结果。这种情况非常的少见。

参考资料

  1. Wikipedia: Majority problem (cellular automaton)
  2. Wikipedia: Cellular automaton
  3. Wikipedia: Elementary cellular automaton
  4. 《复杂》,梅拉妮·米歇尔著,唐璐译,湖南科学技术出版社,2011年6月第1版

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

Jeff Dean推荐:用TPU跑Julia程序,只需不到1000行代码

Julia是一门集众家所长的编程语言。随着Julia 1.0在8月初正式发布,Julia语言已然成为机器学习编程的新宠。

11910
来自专栏灯塔大数据

每周学点大数据 | No.40单词共现矩阵应用

No.40期 单词共现矩阵应用 Mr. 王:这个算法的优势在于,它的 key 空间相比前面的词对要小得多,这意味着它能够更好地利用 combiner。 但是这种...

325110
来自专栏牛客网

网易考拉前端开奖啦~分享一波面筋

内推投了十几二十家公司,大多没消息。BAT都没有面(百度投了没消息,腾讯打了一次电话来没接到就变灰了,阿里问我有没兴趣改测试岗(表示没兴趣))。于是最终面试的就...

14320
来自专栏程序人生

谈谈状态机

题记:上周做 BBL 里讲了我们 Tubi TV 内部做 DSL 的一些简单实践,大家反馈不错。有同事建议我给大家先补补 FSM,之后再进阶 CFG,可能会更顺...

41270
来自专栏opengps

新手入门百度地图开发的(0,0)坐标问题

        对于大部分人来讲,由于百度地图资料众多,过度依赖搜索引擎等等原因。新接触百度地图开发工作其实并不容易。今天说说关于坐标(0,0)的问题。 ...

39160
来自专栏程序员叨叨叨

6.4 移位操作符

Cg语言中的移位操作符,功能和C语言中的一样,也可以作用在向量上,但是向量类型必须是int类型。例如:

13620
来自专栏PPV课数据科学社区

用 Python 做文本挖掘的流程

作者:肖智博 来源:https://zhuanlan.zhihu.com/p/19630762 点击阅读原文可进入超链接。 收集数据 数据集。如果是已经被人做...

50080
来自专栏移动开发面面观

OpenGL ES——打光

15850
来自专栏opengps

新手入门百度地图开发的(0,0)坐标问题

        对于大部分人来讲,由于百度地图资料众多,过度依赖搜索引擎等等原因。新接触百度地图开发工作其实并不容易。今天说说关于坐标(0,0)的问题。 ...

39690
来自专栏数据派THU

一文盘点三大顶级Python库(附代码)

Python在许多方面有着强大的吸引力 - 例如效率、代码可读性和速度方面,也正因为如此,对于希望提升应用程序功能的数据科学家和机器学习专家来说,Python通...

24740

扫码关注云+社区

领取腾讯云代金券