内容


细胞自动机和音乐

用 Java 语言进行算法作曲

Comments

很多计算机程序员都是很出色的音乐家,很少有组织不起像样的室内乐队的软件公司。不过,许多程序员/音乐家可能没有意识到这样一个能让他们的职业和业余爱好统一起来的有意思的领域:算法作曲。算法作曲将严格的、定义良好的算法应用到作曲过程中。 细胞自动机(Cellular automata,CA)——这是一种随时间而进化的数学结构——为算法作曲展现了一条迷人的大道。计算机特别适合计算细胞自动机(CA)的进化并以图形方式显示它们。还可以用声音表现进化,包括音乐。但是寻求将 CA 进化映射为动听和有意思的音乐不是一个简单的问题。本文展示了用 Java 语言进行基于 CA 的作曲的一些技术,并探讨了得到特别出色结构的某些映射。

细胞自动机概述

CA 包括:

  • 细胞矩阵或者网格,每个细胞可以处于有限种状态中的一种。
  • 定义细胞状态如何随时间更新的规则。

细胞矩阵可以有任意多维。给出一个细胞和它的邻居在时间 t时的状态,规则会决定在时间 t + 1时细胞的状态。(在分析了几个具体例子后会看得更清楚。)

基本细胞自动机

在本文中我将集中讨论一维细胞自动机,它的细胞可以有两种状态:0 或者 1。因为 CA 是一维的,所以可以将它想像为一行细胞。细胞在时间 t + 1的值将只取决于这个细胞和它的左右邻居在时间 t时的值。这种 CA 称为 初级细胞自动机

CA 图使用白表示 0,黑表示 1。最上面一行显示这个细胞和它的左右邻居可以有的八种颜色组合。底下一行显示中间这一个细胞下一步的颜色。例如,考虑图 1 中第四个方块。在这个方块中,可以看到如果细胞是白色的,它的左邻是黑色的,右邻是白色的,那么这个细胞在下一步将是黑色的。习惯称它为 150 规则(rule 150):如果想像黑白细胞分别表示二进制 0 和 1,那么底下一行就是加上二进制形式的十进制数 150。图 1 是 150 规则的虚拟表示。用音乐表示 CA 时,150 规则会生成一些有意思的曲调,因此在本文中我将用它作为例子。

图 1. 150 规则
150 规则的直观表示

现在,考虑一个 150 规则 CA,开始时,除了中间的细胞为黑色,其他所有细胞都是白色。这个 CA 会按照图 2 所示的一系列步骤进化。

图 2. 150 规则步骤序列
用 150 规则按一系列步骤进化

注意尽管自动机是一维的,但是用一组连续的行从上到下显示它的进化。图 2 显示 CA 前五步的进化(包括初始状态)。可以看到每一个细胞的颜色都是由上一行中它自己的颜色和最近的邻居的颜色根据 150 规则所决定的。同时,还要注意考虑一行中所有细胞的值是在进化的每一步中同时更新的。

图 3 显示 CA 在 100 步进化后的样子:

图 3. 150 规则 100 步后
150 规则 100 步后的进化

图 3 中 CA 的进化碰巧是对称的,但是并不是所有 CA 进化都是对称的。

Wolfram 对细胞自动机的研究

CA 半个世纪以来一直是研究的对象。Stanislaw Ulam 和 John von Neumann 于 20 世纪 40 年代发明了 CA 的概念,并于 40 和 50 年代作出了很多重要的发现。John Horton Conway 和 Bill Gosper 于 70 年代对 Conway 发明的一种称为 Life的特殊二维 CA 进行了更深入的研究。Stephen Wolfram 于 80 年代开始研究 CA(请参阅 参考资料)。

通过研究初级细胞自动机,Wolfram 发现简单的机制可以产生出复杂的行为。例如,考虑 30 规则。像所有初级细胞自动机一样,它的定义——如图 4 所示——是相当简单的:一个小图就可以完全定义它。

图 4. 30 规则
30 规则的直观表示

不过,30 规则所产生的进化是相当复杂的。图 5 显示了使用 30 规则时,这个 CA 100 步后的进化。

图 5. 30 规则 100 步后
使用 30 规则 100 步后的进化

分析了 256 个初级 CA 和其他更复杂的 CA 后,Wolfram 发现 CA 可以分为四类。数学家和作家 Rudy Rucker 在其报告“Things Computer Science Tells Us About Philosophy”中准确地描述了这四种类型(请参阅 参考资料)。

  • 第 1 类恒定。(所有种子都“死了”)
  • 第 2 类重复。(循环,条带)
    • 第 2A 类: 嵌套。(正则分形)
  • 第 3 类: (伪)随机。(激变)
  • 第 4 类: 复杂。(“不规则”。滑行。 一般性计算)

Wolfram 作出了似乎有道理的声明,大多数第 3 类和第 4 类 CA 可能是 无法省略计算的(computationally irreducible):给出一个初始状态,要找出某一细胞在第 n步时的值,必须从初始配置开始,完成所有 n步计算。就是说,没有公式或者快捷方式可以预测 CA 的未来状态。

CA 的计算能力

此外,Wolfram 和 Matthew Cook 还证明了 110 规则在计算上等同于一个一般性图灵机。(之前 Conway 对 Life 证明了这一点。)即,可以用 110 规则计算任何一般性图灵机可以计算的函数。这对于其他第 4 类的初级 CA 可能也成立。就是说,一些 CA 尽管定义很简单,但是可以用于执行任何所需要的计算。

一个未决问题

当然,CA 是纯数学结构,CA 的直观表示帮助我们理解和讨论它们。在“Open Problems & Projects”中,Wolfram 提出了这个问题:是否可以有一个声音表示的 CA 进化,它提供了视觉表示不能提供的内部信息?这是一个有意思的问题。可以慢慢研究一幅图像,并关注感兴趣的地方,但是对声音的感受是随着时间进行的,当它结束后,只能再重新播放它。Wolfram 认为由于这个原因以及其他原因,可能不会有这样的声音表示。

音乐问题

我将关注一个与此有些关系的问题:是否可以用 CA 得到有趣和好听的音乐?一些 CA 的图像表示可以是相当动人和漂亮的。这种美是否也可以用音乐的方式呈现出来?同时,利用 CA 的一般性计算能力作曲会是很好的事,特别是,找出将 CA 进化映射为动听或者至少是有趣的音乐的方式。

用 Java 语言作曲

由 Andrew Sorensen 和 Andrew Brown 开发的 jMusic 是一个用 Java 语言编写音乐程序的开放源代码框架 (请参阅 参考资料)。它建立于 Java Sound APi 之上,并让作曲家可以在音乐水平上进行创作而不用担心低层音频编程细节。在 jMusic 中乐谱的结构是优雅而直观的。它与纸上乐谱的结构相对应:音符构成乐句,乐句构成声部,声部构成乐谱。清单 1 中的例子展示了这种简单性。

清单 1. Harry Dacre 用 jMusic 编写的“Bicycle Built for Two”
int[] pitches = { C5, A4, F4, C4, D4, E4, F4, D4, F4, C4 };
double[] rhythmValues =
 {
    DOTTED_HALF_NOTE,
    DOTTED_HALF_NOTE,
    DOTTED_HALF_NOTE,
    DOTTED_HALF_NOTE,
    QUARTER_NOTE,
    QUARTER_NOTE,
    QUARTER_NOTE,
    HALF_NOTE,
    QUARTER_NOTE,
    2 * DOTTED_HALF_NOTE };
Note[] notes = new Note[pitches.length];
for (int i = 0; i < notes.length; i++) {
  // A note is made up of a pitch and duration
  notes[i] = new Note(pitches[i], rhythmValues[i]);
}
// A phrase is made up of notes
Phrase phrase = new Phrase(notes);
Part pianoPart = new Part("Piano", PIANO);
// A part is made up of phrases
pianoPart.add(phrase);
// A score is made up of part(s)
int tempo = 180;
Score daisy = new Score("A Bicycle Built For Two", tempo, pianoPart);
// In key of F: 1 flat
daisy.setKeySignature(-1);
// In 3/4 time
daisy.setNumerator(3);
daisy.setDenominator(4);
// Display score in standard musical notation
View.notate(daisy);
// Write out score to MIDI file
Write.midi(daisy, "C:\\Daisy.mid");

现在, 聆听得到的 MIDI 文件。

除了 MIDI 功能,jMusic 还有许多其他好功能。例如,可以用常规音符显示自己的乐谱。而且 mod 包可以对乐句进行转换,如置换或者换向。

Automatous Monk

以伟大的爵士钢琴家和作曲家 Thelonious Monk 命名的 Automatous Monk (又叫 Monk),是我用 Java 语言编写的一个开放源代码程序,它通过 CA 进化生成旋律 (请参阅 参考资料)。Monk 使用 jMusic 框架表示得到的音乐,因为 jMusic 乐谱可以保存为 MIDI 文件并播放。我将用 Monk 的代码示例和短的 MIDI 文件示例说明我的观点。

用 Java 语言表示 CA

我将不深入用 Java 语言表示 CA 的细节,不过如果了解如何用细胞的当前状态和其邻居的当前状态计算细胞的下一个状态会有帮助。如您所见,可以用一个二进制数表示一个规则,可以用一个整数表示 CA 细胞在给定步数时的状态。清单 2 中的代码计算细胞的下一个状态。

清单 2. 计算细胞的下一个状态
/**
 * Computes the next state of a cell.
 * @param nWCellState State of the cell to the left of the current cell in
 *    preceding generation.
 * @param nCellState State of the current cell in preceding generation.
 * @param nECellState State of the cell to the right of the current cell in
 *    preceding generation.
 * @return Next state of the cell.
 */
int getNextStateOfCell(int nWCellState, int nCellState, int nECellState) {
  // Find the index of the current state in the rule pattern
  int index = 4 * nWCellState + 2 * nCellState + nECellState;
  // Get the value of the digit in that place
  int nextState = (rule >> index) % 2;
  return nextState;
}

CA 进化的音乐表示

现在进入困难部分了:如何用 CA 进化构造音乐?有一个事实看来很明显:有了 CA 进化的直观表示,在页中向下走时,时间是增加的。这对于音乐表示也是有意义的。因此,CA 进化的每一行表示一个节拍。

我将在展示 Monk 中得到好的音乐结果的一些映射。嵌套的 CA 一般会得到好听的音乐,可以听到在音乐中反映出来的直观规律性。嵌套的 150 规则是一个好的例子。Wolfram 的 A New Kind of Science一书简单描绘了一些用音乐表示 CA 的方式 (请参阅 参考资料)。我的映射就基于这些思路。

“键盘”映射

这个“键盘”映射可能是最明显的一个方法。CA 中每一个细胞(或者列)都对应于特定的音高(pitch)。可以将每一个细胞想像为钢琴键的映射。不过,我的实现使计算有些复杂,因为它考虑了所使用的音阶的类型——如半音阶、大音阶或者小音阶——和在这种类型的音阶中音符的音高。清单 3 中的映射计算给定细胞的音高。

清单 3. 计算细胞的音高
/**
 * @param cellPos Position of the cell. The position of the center cell is
 *        0, while positions to the right are positive and positions
 *        to the left are negative.
 * @param normalize If true, make sure return value is a valid
 *         MIDI pitch. That is, make sure that it is between 0 and
 *         128.
 * @return The starting pitch of the cell.
 */
int getStartingPitch(int cellPos, boolean normalize) {
  int[] scale = scaleType.getScale();
  int interval;
  int scaleWidth = scale.length;
  // Compute the interval from middle C to this pitch.
  if (cellPos >= 0) {
    interval =
      (cellPos / scaleWidth) * HALF_STEPS_IN_OCTAVE + scale[cellPos % scaleWidth];
  } else {
    interval = (-cellPos / scaleWidth) * HALF_STEPS_IN_OCTAVE;
    if (-cellPos % scaleWidth != 0) {
      interval += 12 - scale[scaleWidth - (-cellPos % scaleWidth)];
    }
    interval *= -1;
  }
  // Add interval to middle C, C4.
  int pitch = C4 + interval;
  if (normalize) {
    pitch %= 128;
    if (pitch < 0) {
      pitch += 128;
    }
  }
  return pitch;
}

现在, 聆听对这个映射使用 150 规则时的结果。

可以听到,结果有些不和谐(尽管大体可以听到它的嵌套结构)。“和弦”太密集了。在本文的其余部分,我将展示生成没有多个同时音符的简单旋律的映射。这些类型的映射结合正确的规则,可以生成异常吸引人和迷人的旋律。

“行到二进制数”的映射

“行到二进制数”的映射将每一行考虑为表示一个音高的二进制数。不过有一个微妙之处:如何排列数字?通常,从右到左排列,最右边的数字是最低有效位。不过,一个一维 CA 没有最右(或者最左)细胞。我们把 CA 的“宇宙”看作是在左右两个方向上无限扩展的。因此,在笛卡尔平面使用 x轴时,考虑一个特定的细胞为原点。在原点右边的细胞为正数,原点左边的细胞为负数。本文中所有示例 CA 都以一个黑色细胞开始,因此自然就以这个细胞为原点。

为了从最低到最高有效位排列二进制数,从原点开始,向前排列。可以有两种方式,取决于是喜欢细胞原点左边还是原点右边的细胞:

  • 喜欢左边:0, -1, 1, -2, 2, -3, 3, ...
  • 喜欢右边:0, 1, -1, 2, -2, 3, -3, ...

不管是哪种情况,都可以将 CA 的一行作为二进制数相加。因为只有 0 和 128 之间的数指定 MIDI 音高,所以可以通过将这个数值取 128 的模将它转换为 MIDI 音高。清单 4 包含 Automatous Monk 中的相应代码。

清单 4. 重新排列一行并计算音高
/**
 * Reorders a row according to significance of digits.
 * @param rowIndex The generation number of the row
 * @param cA The CA containing the row
 * @param bias Left- or right-side bias
 * @return The reordered row with least-significant digits to right
 */
int[] reorderRow(
  int rowIndex,
  CellularAutomaton cA,
  HorizontalBias bias) {
  int[][] cAHistory = cA.getGenerations();
  int[] row = cAHistory[rowIndex];
  int len = row.length;
  int[] reordered = new int[len];
  int mid = len / 2;
  reordered[len - 1] = row[mid];
  for (int i = 0; i < (len - 1) / 2; i++) {
    // Note that this favors one side of the CA over the
    // other side, but there seems to be no way to get around this.
    if (bias.equals(HorizontalBias.LEFT)) {
      reordered[len - (2 * i + 1) - 1] = row[mid - (i + 1)];
      reordered[len - (2 * i + 2) - 1] = row[mid + i + 1];
    } else {
      reordered[len - (2 * i + 1) - 1] = row[mid + i + 1];
      reordered[len - (2 * i + 2) - 1] = row[mid - (i + 1)];
    }
  }
  return reordered;
}
/**
 * Computes a MIDI pitch from a row of 0s and 1s.
 * @param rowIndex The generation number of the row
 * @param clllrAutmtn The CA containing the row
 * @param bias Left- or right-side bias
 * @return A valid MIDI pitch
 */
int getPitchFromRow(
  int rowIndex,
  InfiniteCellularAutomaton clllrAutmtn,
  HorizontalBias bias) {
  int[] reorderedRow = reorderRow(rowIndex, clllrAutmtn, bias);
  int pitch = 0;
  for (int i = 0; i < reorderedRow.length; i++) {
    pitch = (2 * pitch + reorderedRow[i]) % 128;
  }
  return pitch;
}

现在, 聆听对这个映射使用 150 规则所产生的旋律。注意使用左或者右方式得到同样的结果,因为 150 规则是对称的。

“累积行到二进制数”的映射

“累积行到二进制数”的映射与上一个映射一样,但是累积行值——每次计算总值。清单 5 是这种映射的代码。

清单 5. 计算连续各行的音高总值
/**
 * Converts the successive rows of a CA to a musical phrase.
 * @param cA A cellular automaton
 * @param bias Favor left- or right-side in generating pitches
 * @return A musical phrase corresponding to cA
 */
public Phrase convertCAHistoryToPhrase(
  CellularAutomaton cA,
  HorizontalBias bias) {
  Phrase phr = new Phrase();
  int cumulativePitch = 0;
  for (int i = 0; i < cA.getGenerationCnt(); i++) {
    int pitch = getPitchFromRow(i, cA, bias);
    // Need to take mod 128 to keep it a valid MIDI pitch.
    cumulativePitch = (cumulativePitch + pitch) % 128;
    Note n = new Note(cumulativePitch, CAConstants.DEFAULT_NOTE);
    phr.add(n);
  }
  return phr;
}

现在, 听听它是什么样的声音。

这个结果比前一个例子旋律更动听,它听起来有一些像节奏片段。

组合映射

组合映射可以得到好的结果。例如,可以 将 150 规则与节奏片段组合在一起。还可以 将使用 60 规则的二进制与累积二进制映射组合起来。注意左右方式的映射是不同的,因为 60 规则不是对称的。这会得到四种声音和更丰富的音响。

必须承认我认为 60 规则是相当吸引人的!我曾花了大量时间(肯定比大多数人要多)聆听 CA,我经常发现 60 规则更适合于我。 我认为它是 CA 世界中的 Hanson 或者 Jackson 5。

保持简单

如前所述,我发现最好专注于生成单音旋律的映射(虽然可能叠加这些旋律,正如我使用二进制和累积二进制映射一样),并本质上忽略和声和节奏。这并不像它看上去那样是一个很大的限制。很多巴洛克式音乐,如 J.S. Bachs 的音乐就是这种类型的。它甚至有一个单词: 复音(polyphony)。(当然,我作了相当的简化:在复音中,确实有不同声音的和声,节奏也没有完全忽略。)这些映射的复音组合是用 CA 创作音乐的很好的第一步。

我还发现简单映射会得到最动听的结果。不过,这并不意外,因为即使简单的直观映射——将 1 映射为黑方块,0 映射为白方块——也可以生成漂亮和复杂的样式。而且,考虑一些 CA,如 110 规则可以进行一般性计算这一事实。假设现在作曲是纯粹理性的行为——可以编写算法作曲。那么对于一般性 CA, 如 110 规则,可以自己生成音乐,而不用我们在映射内部“编写”任何音乐智能或者知识。当然,我一直只使用特别简单的开始状态,而 110 规则有可能要求更复杂的程序和在初始状态中编入更复杂的输入数据以生成真正动听的音乐。要点是从 CA 状态到音符的 映射应当是相当“透明”的:“CA 应当完成所有作曲工作。”

让映射复杂化的另一危险之处在于容易在映射中编写自己的音乐偏好(东方或者西方,有音调或者无音调)。编写一个计算机程序,让它可以写出肖邦或者巴赫风格的作品,并与肖邦或者巴赫作品几乎一样好,这可能是一个很困难的问题,但这是一个令人钦佩的成就:无论如何,有另一个“新的”肖邦或者巴赫的作品总是好事。但是为什么仅限于此呢?我认为算法音乐作曲只有不仅可以产生美妙的音乐,而且还能生成与我们以前没有听到过的完全不同类型的美妙音乐,才能算做真正成功。肖邦或者巴赫不仅因为写出伟大的音乐而伟大:他们伟大是因为他们带来了全新的音乐思路。我认为最好的结果将来自使用简单的映射并让 CA 生成所有音乐观念。

Gnarl

Rudy Rucker 定义了一个他称为 Gnarl的概念:具有某种杂乱水平的东西,它正好处在有序与无序之间的边界。

当我第一次开始聆听 Monk 生成的 CA 音乐时,一些最好听的 CA 对我来说就像是 Gnarl 的例子。后来,我在 Rucker 的“Things Computer Science Tells Us About Philosophy”中了解到他认为第 4 级 CA 是 Gnarl 的例子。

不规则的 CA 听起来是什么样的? 聆听225 规则。

当我聆听 225 规则时,我感觉几乎可以捕捉到它的结构,但是又不是很清晰。这样可以长时间地聆听它而不会乏味。另一方面,嵌套模式的 60 规则如果偶尔听一听是不错的,但是它不能让我长时间保持兴趣。60 规则结构太容易捕捉了,它可能是不错的、经嚼的、能嚼出声音(crunchy mind)的糖果,但是它不是 Gnarl 的例子。即使 225 规则从我给出的简单初始状态得到一个规则的、嵌套的模式——因而不是第 4 类——但是它对我来说听起来仍然是相当不规则的。(需要完整的另一篇文章来说明为什么 CA 听起来比看起来通常更不规则 。)

那么真正的第 4 类 CA 听起来是什么样的呢?110 规则是第 4 类的: 听听它吧。

它听起来绝对像我们进入了 Gnarl 的老家。像许多好的音乐一样,需要听几遍才能欣赏它。

其他算法作曲项目

在算法作曲方面的研究比您所想像的要多得多。基本上有两种用计算机进行音乐作曲的方式:自上而下和自下而上。使用计算机程序作为辅助手段的作曲家大多数使用自上而下的方式——通过将音乐构造块加入到较大的结构中。Automatous Monk 采用了自下而上的方式:它在音符级别上创建音乐。

CAMUS

CAMUS 由 Eduardo Reck Miranda 编写,是另一种使用 CA 生成音乐的自下而上的方式(请参阅 参考资料)。它使用 Life 和 Demon Cyclic Space 生成音乐。与我展示的一维 CA 不同,Life 和 Demon Cyclic Space 都是二维 CA,就是说,细胞是排列在二维网格中的。Life 特别有意思(编写和观看都很有趣)。CAMUS 使用 Life 生成音符组,同时用 Demon Cyclic Space 生成各个音符的音色(或者音质)。

Music Sketcher

Music Sketcher 是一个 IBM alphaWorks 项目(请参阅 参考资料)。与 Monk 和 CAMUS 不同,Music Sketcher 使用自上而下的方式,将用户将段落或者重复段放入较大的音乐结构中。Music Sketcher 中特别有意思的是它能够用于创建作品的和弦数,同时程序完成必要的转换以保证构造块符合指定的和弦数。(这样,它成为苹果公司的新 GarageBand 应用程序的先驱。) 这是一个有趣的程序,我建议您试试它。

结束语

有许多使用 CA 进行算法作曲的有趣方式有待探索。我提供的例子只能说是简单的起始状态。如果利用更复杂起始状态的 CA 会是什么样的音乐呢?同时,大多数西方音乐作品的旋律要符合和弦数。设计一种映射技术,使 CA 生成符合特定用户和弦变化的旋律将会很有意思(换句话说,一种CA Charlie Parker),尽管使 CA 符合音乐偏见可能会限制它们。

当前版本 Monk 的一个限制是它只使用常规西方音高:128 MIDI 音调。在将 CA 行解释为二进制数的 128 模数时,实际上只用到了一行中的 7 个数或者单元。七个单元是完整 CA 的一个很窄部分,很多信息丢失了。我们可以通过使用微音程(microtone)而不是只使用西方音乐中的半音(semitone)来保留这些信息。这会产生音色更丰富的音乐还是只产生不和谐呢?我准备扩展 Monk 以检验其中一些想法。

Automatous Monk 和 jMusic 都可以在 SourceForge.net 上免费获得,我鼓励读者进行自己的试验。您也可从 Wolfram 的论文“Open Problems & Projects”中获得灵感。细胞自动机的研究可以有多种角度,并涉及不同程度的技术复杂性,从高中水平到研究生水平。用 Rudy Rucker 的话说,就是“寻找 Gnarl!”


相关主题


评论

添加或订阅评论,请先登录注册

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Java technology
ArticleID=53462
ArticleTitle=细胞自动机和音乐
publish-date=06012004