在 2024 年我们曾经写过一篇关于自动生成 SATB 和声的文章。在那篇文章中我们使用的是基于 Prolog 的回溯搜索。在这个实验中,我们很好处理了四部和声中的很多硬约束,比如:

  • 所有声部都在允许音域内
  • 和弦的必需组成音必须出现
  • 避免声部交叉
  • 在严格的传统和声练习中禁止特定的平行五八度

另外在上篇文章中有一些明显的错误,例如:

(SopranoValue1 - AltoValue1) // 7 =:= 0

这判断的并不是平行五度,应该用的是 $(d \mod 12) = 7$ 来判断,八度检查也有这个问题。

另一个很直观的问题是 Prolog 程序的实现方式不利于优化

正确与更好

然而正如文章末尾所说的,我们也发现「Prolog 不会总是选那个离自己最近的音来过渡」,这使得自动生成的和声配置不够好,而且灵活性也不够,只能算是一个玩具。

我觉得我们需要进一步把问题转化成一个 约束规划(Constraint Programming) 问题,我们可以先枚举每个和弦的合法 SATB 排列,再构建和弦连接图,寻找总代价最低的路径。

我觉得我们可以把问题分成两个部分:

Hard constraints:不应该违反的规则

例如:

  • 所有声部都在允许音域内。
  • 和弦的必需组成音必须出现。
  • 避免声部交叉。
  • 在严格的传统和声练习中禁止特定的平行五八度。

Soft constraints:可以违反,但违反需要付出代价的规则

例如:

  • 尽量使用级进。
  • 尽量保留共同音。
  • 避免不必要的大跳。
  • 让旋律线具有一定方向性。
  • 避免某个声部长时间停留在一个音。
  • 偏好合理的声部运动与音域分布。

如果我们的系统只回答「这个和声是否合法」,就很难实现真正好用的自动配和声。

但如果我们能够为结果定义一个目标函数,例如:

\[\min_{\mathbf X} \left[ \lambda_1 E_{\text{voice-leading}} +\lambda_2 E_{\text{melodic}} +\lambda_3 E_{\text{spacing}} +\lambda_4 E_{\text{harmonic}} \right]\]

并让求解器满足所有必要的硬约束,那么问题就从「寻找一个解」变成了「寻找一个好的解」。

最短路径问题

在这里我有一个很巧妙的想法,我们可以问题转换为最短路径问题。

假设有一个 8 和弦的进行:

\[I \rightarrow vi \rightarrow ii^6 \rightarrow V \rightarrow I \rightarrow IV \rightarrow V^7 \rightarrow I\]

在每个时刻 $t$,我们已经知道应该演奏什么和弦。

那么首先可以枚举这个和弦的所有合法 SATB 配置。

例如,C 大调的 I 级和弦:

\[C-E-G\]

可能出现以下配置:

配置 S A T B
A G4 E4 C4 C3
B C5 G4 E4 C3
C E5 C5 G4 C3

这只是几个示意候选,真实系统需要枚举完整的合法集合。

对于每个和弦时刻 $t$,我们得到一个候选集合:

\[V_t=\{v_{t,1},v_{t,2},\dots,v_{t,n_t}\}\]

其中每个状态包含四个音高:

\[v_{t,i}=(S,A,T,B)\]

接下来构建一个分层有向图:

Chord 1        Chord 2        Chord 3        Chord 4

   A ────────── A ──────────── A ────────── A
    ╲         ╱ │            ╱
     ╲       ╱  │           ╱
   B ────────── B ──────────── B ────────── B
    ╲         ╲ │          ╱
     ╲         ╲│         ╱
   C ────────── C ──────────── C ────────── C

节点代表合法的四声部配置。

边代表两个配置之间允许的声部连接。

如果违反平行五度或其他硬约束,我们直接删除对应的边。

对于剩下的边,计算代价:

\[w(u,v)=E_{\text{voice-leading}}(u,v)\]

例如:

\[E_{\text{motion}}(u,v) = \sum_{p\in\{S,A,T,B\}} \alpha_p |v_p-u_p|\]

但仅仅对移动的半音数求和还不够。我们可以进一步设计:

\[E_{\text{voice-leading}} = \alpha E_{\text{motion}} +\beta E_{\text{leap}} +\gamma E_{\text{contrary}} +\delta E_{\text{tendency}}\]

其中:

  • $E_{\text{motion}}$:移动音程总量。
  • $E_{\text{leap}}$:超过指定音程的大跳惩罚。
  • $E_{\text{contrary}}$:对运动方向的偏好。
  • $E_{\text{tendency}}$:导音、七音等倾向音的解决情况。

最后,我们只需要在分层有向无环图上寻找最短路径。

动态规划

如果用特别 naïve 的方法思考,很容易这个问题复杂度会退化到 NP-Complete 的程度(等效于图染色问题),但是我们不妨考虑下面的状态转移方程。

定义 $D_t(j)$ 为前 $t$ 个和弦中,第 $t$ 个和弦采用状态 $j$ 时的最小累计代价。

则:

\[D_t(j)= c_t(j)+ \min_i\left[ D_{t-1}(i)+w(v_{t-1,i},v_{t,j}) \right]\]

其中 $c_t(j)$ 是某个和弦配置本身的代价。

动态规划仅需要考虑相邻状态的转换。

最坏情况下,算法复杂度应该是:

\[O(Tn^2)\]

最重要的是,动态规划在只有单节点和相邻节点代价的情况下,能够保证找到全局最优解。

实验结果

我们还是沿用原文结尾的题目:

SATB 样例题目

我们得到下面的最优答案:

SATB 生成答案

听起来真的好很多。我们可以让节奏更复杂一点,比如我们可以索性玩个花的,让 S 和 A 演奏三连音,然后我们寻找一组最优答案:

SATB 生成答案

这确实比之前的版本好太多了。

总结

这里的「全局最优」有个前提:

就算路径真的最短,短的只是我们自己写下的那个函数。我们给定的四个参数具体取多少、大跳罚多重,这并没有答案,我们的测试使用了完全相同的惩罚权重。这意味着我们虽然试图在解决更好的问题,我们实际上引入了更多的自由度,而这些自由度本身是「风格」。

进一步地,我们的旋律并没有特别清晰的旋律线,视线如果拉到整个乐句,还能不能生成足够质量的音频,恐怕要留给之后再讨论了。

Comments