元胞自动机实现多数分类算法
元胞自动机(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 }简要分析
- 第9行的静态只读变量 sizeCellular 表示每个元胞方格的边长，必须为奇数。
- 第10行的静态只读变量 nCellular 表示每行有多少个元胞，最好为奇数，以免在多数分类时出现平局的情况。
- 第11行的静态只读变量 lines 表示要迭代多少次。
- 第13行的静态只读变量 strRuler 表示迭代的规则。
- 主要工作在从第29行到42行的 OnPaint 方法中进行。
- 第84行到第91行的 GetInitCellulars 方法随机地初始化元胞的初始状态。
- 第36行到第40行的循环按照指定的规则进行迭代。
- 第44行到第50行的 StepIt 方法执行具体的迭代步骤。
- 第52行到第60行的 GetValue 方法计算元胞邻域的值。
运行结果
该程序几次典型的运行结果如下所示：
上图显示白色占优，结果正确。这种情况很常见。
上图显示黑色占优，结果正确。这种情况也很常见。
上图显示白色占优，结果错误。这种情况比较少见。
上图显示黑色占优，结果错误。这个结果错误在于最终的迭代结果不是全黒，而混入了少量的白色元胞。这个程序只迭代 200 步，其实只要再迭代几步后就可以得到正确的结果。这种情况非常的少见。