元胞自动机是由元胞组成的网格,每个元胞都根据邻域的状态来选择开或关。所有的元胞都遵循同样的规则,也称为元胞的更新规则,规则根据各元胞邻域的当前状态决定元胞的下一步状态。同自然界的复杂系统一样,元胞自动机也是由大量简单个体(元胞)组成,不存在中央控制,每个个体都只与少量其他个体交互。而且元胞自动机也能表现出非常复杂的行为,它们的行为很难甚至不可能通过其更新规则来预测。元胞自动机有很多种类型,著名的“生命游戏”也是元胞自动机的一种。
初等元胞自动机是一维两状态的元胞自动机,每个元胞仅与两个相邻元胞相连。元胞自动机的时空图表现了元胞自动机的立体构型随时间的变化,最顶上一行是一维元胞自动机的初始状态设置,下面跟着的依次是每一步更新后的状态。
该元胞自动机要能区分初始状态中是开状态还是关状态占多数。如果是开状态占多数,最后所有元胞就应当都变成开状态。同样,如果是关状态占多数,最后所有元胞就应该都变成关状态。多数分类任务有点类似于选举,是在大家都只知道最近邻居政治观点下预测两个候选人谁会赢。
我们使用一维元胞自动机,每个元胞与相邻的6个元胞相连,这样元胞的邻域中就有7个元胞(包括自己)。一个合理的想法是:“元胞应当变成邻域中当前占多数的状态。”这就好象根据你自己和邻居的多数意见来预测哪个候选人会当选。然而,这个“局部多数投票”元胞自动机并不能完成任务。
我们使用的是梅拉妮·米歇尔(Melanie Mitchell)在《复杂》(Complexity: A Guided Tour)一书第203页给出的规则:
0000010100000110000101011000011100000111000001000001010101
0101110110010001110111000001010000000101111101111111111011
011101111111
第1位是邻域全为0时中间元胞的更新状态,第2位是邻域为0000001时中间元胞的更新状态,依次往后。由于邻域状态有 27 = 128 种可能,因此该规则有128位。但是光看这些数位是看不出这个规则如何运作,也无法知道为何它进行多数分类时适应度很高。
下面就是相应的 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 }
该程序几次典型的运行结果如下所示:
上图显示白色占优,结果正确。这种情况很常见。
上图显示黑色占优,结果正确。这种情况也很常见。
上图显示白色占优,结果错误。这种情况比较少见。
上图显示黑色占优,结果错误。这个结果错误在于最终的迭代结果不是全黒,而混入了少量的白色元胞。这个程序只迭代 200 步,其实只要再迭代几步后就可以得到正确的结果。这种情况非常的少见。