再次讨论自动生成 SATB 四部和声
在 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)\]最重要的是,动态规划在只有单节点和相邻节点代价的情况下,能够保证找到全局最优解。
实验结果
我们还是沿用原文结尾的题目:

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

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

这确实比之前的版本好太多了。
总结
这里的「全局最优」有个前提:
就算路径真的最短,短的只是我们自己写下的那个函数。我们给定的四个参数具体取多少、大跳罚多重,这并没有答案,我们的测试使用了完全相同的惩罚权重。这意味着我们虽然试图在解决更好的问题,我们实际上引入了更多的自由度,而这些自由度本身是「风格」。
进一步地,我们的旋律并没有特别清晰的旋律线,视线如果拉到整个乐句,还能不能生成足够质量的音频,恐怕要留给之后再讨论了。
Comments