马尔科夫链与多目标遗传算法在自动作曲中的应用

朱泽键 杨其宇 陈填锐

摘要：

提出一种新的自动作曲方法，利用马尔科夫链的不确定性与多目标遗传算法的规则性，将二者相结合，应用到自动作曲中。在Musicxml文件下，统计训练样本中相邻音符之间音高与时值的前后关系，建立马尔科夫概率转换表。利用基于概率的多目标遗传算法，根据已建立的概率转换表构造关于音高、时值的适应性函数，同时加入少量音程和谐约束作为第三条适应性规则。实验表明，在同一乐理规则下，与仅用马尔科夫链输出结果进行音乐质量评分、对比，该方法在保证结果多样性的同时提高了音乐质量。

关键词关键词：

算法作曲；Musicxml文件；不确定性；马尔科夫链；概率；多目标遗传

DOIDOI：10.11907/rjdk.172247

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2018）003001503

英文摘要Abstract：Our objective is to propose a new automatic composition method，which uses the Markov chain uncertainty and the regularity of multiobjective genetic algorithm， we combined the two algorithms and applied them to automatic composition. Under the Musicxml file， we statistics the correspondence between the pitch and the time value between adjacent notes in the training sample， and the Markov probability conversion table is established.Based on the probabilitybased multiobjective genetic algorithm， the adaptive function of pitch and time value is constructed according to the established probability conversion table， and a small interval harmony constraint is added as the third adaptive rule.In the experiment we compared the results with using Markov chain only in the same rationale rules and it is concluded that combing the two algorithms improves the quality of the music while ensuring the diversity of the results.

英文关键词Key Words：algorithmic composition； Musicxml format music document； uncertainty； Markov chain； multiobjective genetic algorithm

0引言

当今社会对自动化程度要求越来越高，如何正确使用机器，并尽量减少对人工操作的依赖，通过统计与自动分析数据就能领会模式识别要领，成为一个愈发重要的课题。计算机音乐作为人工智能领域的一个典型代表，研究并开发一种实现更高程度自动化的作曲算法，具有重要意义。

目前普遍使用的机器作曲方法有马尔科夫链、规则知识库、贝叶斯网络、神经网络、遗传算法等。大致可以分为两类：有监督学习与无监督学习。基于纯粹统计的马尔科夫链属于无监督学习，这种算法所作乐曲具有较大随意性。基于专家规则知识库的算法属于监督学习，音乐质量良好但作曲风格过于形式化。贝叶斯网络在样本量较小的情况下能有良好的表现，常被用于一次性学习（Oneshot Learning），但是现有的贝叶斯网络作曲方法是在人为绘制旋律曲线的情况下，根据贝叶斯概率公式推理整首乐曲的音符[2]，即整首歌曲的旋律走势是由人为标定的。人工神经网络算法输出乐曲极大受限于训练样本风格，通用性较差。当今遗传算法主要是基于人机交互的方式，即对音乐打分作为遗传算法的适应性函数，但是所有基于人机交互的学习算法其缺点主要在于人的主观偏见很大程度上影响了输出乐曲的质量[3，6，9]。

本文将马尔科夫链与多目标遗传算法结合起来应用到自动作曲中，为了方便描述，记为“Markov ChainMulti-objective Genetic Algorithm”算法（“马尔科夫链-多目标遗传算法”，简记为“M-MGA”算法）。由于使用马尔科夫链使音乐具有不确定性，通过多目标遗传算法的筛选，使这种算法生成的音乐，虽然不是全局最优解，但是在保证解的质量同时突出音乐的多样性，即保证算法所生成的音乐重复率较低。在同一形式规则库评分下，相比于单纯马尔科夫链的无监督学习而言能较好地限制结果的随意性。

1音乐信息整合

1.1训练样本中音乐信息转换

在Musicxml文件中用xml节点表示音符信息，step节点表示音阶（C，D，E，F，G，A，B），alter节点表示是否升半音（如alter节点的內容为1表示升一个半音），octave节点表示几个八度，type节点表示该音符是几分音符，type节点的内容若为16th，表示这是一个16分音符，用1表示；若为eighth，则表示其是一个八分音符，用2表示。用一个数字来概括这4个节点所描述的音乐信息，可以较为方便地处理，用infor表示音乐信息的转换结果，则转换公式如式（1）：

inf or=pitch+（octave-1）×12+0.1×notetype（1）

式中，pitch为根据step和alter节点确定的音阶，每一个八度相差12个半音，为了将时值信息与音高信息融合，将其用小数表示并与表示音高的整数部分加和，这里采用乘以0.1的方法将时值信息转换为小数。

1.2马尔科夫转换表构造

每一个音符可分为音高和时值两种属性，钢琴有88个琴键，故在音高属性方面，每一个音符有88种音高，而在时值方面，每一个音符又有16分音符、8分音符、4分音符、半音符和全音符5种时值，故每一个音符依照音高和时值属性划分可划分为88×5种可能情况，马尔科夫链表描述的是在当前音符取值情况下下一个音符取各值的概率。这里用各音符出现的频率代表概率。为了在音高和节奏上同时达到良好效果，该系统分别建立了音高和时值两个方面的马尔科夫链表。例如：基于音高的统计结果如表1所示。

2多目标遗传算法设计

2.1种群初始化

种群初始化即为解的初始化，解定义为每一代生成的音乐动机。在保证解的多样性和算法收敛时间的情况下，经实验可知，当初始化解的数目为100时可取得良好效果。

将马尔科夫链表中各音符有序组合出现的频率转换为对应的概率，解的初始化在本实验中为按照马尔科夫转换表输出长度不一的动机片段。经实验可得初始解的长度（动机的长度）在4～20之间可保证结果的多样性和不确定性。

2.2目标函数设计

2.2.1目标函数

在本实验的多目标遗传算法设计中，规定目标函数值大的种群有较大概率留存到下一代。目标函数有3个，即音高、時值对照马尔科夫转换表评分、对人为设定规则的适应值。在音高、时值方面的目标函数计算方法为依次记录输出的音乐动机的相邻两个音符，并在马尔科夫链表中寻找对应音符的有序组合，所有该有序组合频率之和的平均值即为输出音符在音高和节奏方面的评分。为了加大音高和时值质量的区分度，将每个音符所对应的数字拆成整数部分（即音高部分）和小数部分（即时值部分）分别进行评分，因此有音高和节奏两个目标函数。

2.2.2目标函数设定

设定本环节目标函数（以下称为人工目标函数）初始值为动机的长度，即动机片段音符的个数，本环节人为设定乐曲中的禁止音程，凡是出现禁止的音程，则目标函数值减1。根据音程和谐审美观，在每一段乐曲的动机首尾，不能出现F和A这两个音符，因为这两个音符出现在开头或者结尾，会给人听觉上极不稳定、不和谐的感受[4]，故作为人为制定规则加入；若动机首尾出现F或者A，则乐曲在本环节的目标函数值置1（不能置0，因为后文算法中将目标函数值取倒数转换为遗传算法中种群存活概率）。此外，一些音程由于会给人听觉上造成极不和谐的感觉，故如果输出乐曲动机中有这种音程，目标函数值减1。

音程为1个半音称为小二度（MI/FA）、增一度（DO/#DO），这两种音程虽然和谐，但不够饱满有力；音程为5个半音称为完全四度；音程为11个半音称为大七度；音程为12个半音称为完全八度[4]。

在遍历动机中所有音程后，为了便于长度不同的动机在本环节目标函数值的比较，将目标函数值除以动机长度，即得到解的人工目标函数值。

2.3基于Pareto支配等级的快速排序

2.3.1解的支配等级标定

由Pareto支配的定义可得，解A支配解B，即对于所有目标函数（音高、时值、人工目标函数），A在各个目标函数对应的值（评分）都大于等于B。在遍历整个种群中所有解后，可以快速标定各个解的支配数目，支配数目较多的解性能良好，在选择各个解进行遗传变异的时候应优先选择[5]。

2.3.2拥挤距离计算

在生物进化过程中，种群多样性能够保证生物种群朝着更好的方向进化，即解的多样性可以提升迭代遗传结果的质量。故采用拥挤距离的概念，目的是获取分散较为均匀的解集，Pareto拥挤距离定义为对于解P＼-k，拥挤距离PCD的计算公式如式（2）：

PCD（Pk）=1m×∑mi=1fi（pk+1）-fi（pk-1）fmaxi-fmini（2）

式中：fi（pk+1），f（pk），fi（pk-1）为连续的3个解的各个目标函数值，pk+1，Pk，pk-1为相应的Pareto解，fmaxi、fmini为当前获取的第i个目标函数的最大值和最小值[5]。

2.4遗传迭代算法

个体生存概率大小由个体支配数目和拥挤距离共同决定。支配数目越高的个体说明性能优良，有较大的概率被保留下来，拥挤距离越大，说明多样性越强，越容易被保留。Pareto支配数目和拥挤距离共同决定了个体的优劣，其中Pareto支配数目反映解在音高、节奏和人工目标函数3个方面绝对占优的性能，故在决定时具有较大权重。适应度函数值越高反映解的性能越好，而且解的多样性越强，在遗传时有几率通过交叉得到性能更佳的子代，故被保留的概率越高，适应度函数计算公式如式（3）：

F（x）=×n（x）+PCD（x）（3）

式中：n（x）为解x的支配数目，PCD（x）为解x的拥挤距离，为支配数目相对于拥挤距离的权值。

个体生存概率采用轮盘赌的方法计算，定义如公式（4）：

P（Xi）=F（Xi）/∑mi=1F（Xi）（4）

其中m为种群个体数。

3算法稳定性

本实验从https：//musescore.org网站上选取40个Musicxml文件，在matlab上进行单独马尔科夫链训练和马尔科夫链结合遗传算法训练，初始化解的数目设为100，经过39代遗传，最终剩下一组解，算法终止。本实验记录多目标遗传算法进行中每一代所有解中的最高目标函数值，在图1、2中如虚线所示。

将已构造的马尔科夫概率转换表作为音乐质量的评价标准，选择评价标准的原因是马尔科夫转换表是基于对样本音乐的统计，具有较高的客观性。单独使用马尔科夫链输出39次得到39个动机片段，对照概率表，计算出音高、时值和人工目标函数的评分，在图1、2中如实线所示。

在算法接近停止时，目标函数值可以稳定收敛到一个与连续39次马尔科夫链输出结果中最佳情况接近的值，说明算法取得了良好效果。遗传算法终止时，音高目标函数值为258，时值目标函数值为1 763。故由图1、2可以看出，遗传的最终结果朝着最符合统计规律和人类听觉审美的方向收敛，可以有效弥补马尔科夫链的随意性。

当算法终止时生成动机如图3，分析此动机，动机的首尾并不是F或者A音符，动机中只有一对音符前后相差1个半音，但其它音符并没有这种情况，故整体效果较好。单用马尔科夫链生成的乐曲中，挑选音高、时值、人工目标函数处于平均水平的乐曲。如图4，出现4对只相差一个半音的音符，在整体效果上显得不够和谐[7]，且從右至左的第1-4个音符中相邻音符之间音程较大，且变化较剧烈，在听觉上造成过于紧张且不和谐的感觉，原因是在单独使用马尔科夫链生成乐曲的过程中，音符没有按照马尔科夫链中概率较大的链接关系进行转换。这是由于没有加入多目标遗传算法辅助选择符合统计规律的音高和时值所造成的。

4结语

本文在马尔科夫链的基础上加入多目标遗传算法进行约束并应用到自动作曲中，优点在于使用多目标遗传算法限制了马尔科夫链较大的随意性，使得输出结果的性能随着迭代遗传得到较稳定的提升。实际上帮助马尔科夫链转换时确保前一时刻与后一时刻有较大概率进行转换，尽量避免出现小概率事件，同时使得转换不仅基于概率与数理统计，还取决于人为规定对结果的需求。在工程上不仅可以应用于计算机音乐方面，还涉及概率与统计中的马尔科夫链。这种方法在保留决策多样性的同时，尽量使决策符合马尔科夫决策规律与人对结果的需求。

参考文献参考文献：

[1]冯寅，周昌乐.算法作曲的研究进展[J].软件学报，2006（2）：209215.

[2]翁诗杰，李维华，丁海燕.基于贝叶斯网研究自动作曲中音高的表示和推理[J].计算机科学，2014（S2）：216.

[3]谢力荣.计算机作曲中存在的问题及对策探究[J].电化教育研究，2013（3）：322.

[4]杜鹏.基于遗传算法与人工神经网络的二声部创意曲自动生成[D].厦门：厦门大学，2007.

[5]张长胜.多目标人工蜂群算法及遗传算法的研究与应用[M].沈阳：东北大学出版社，2013.

[6]CHIP BELL. Algorithmic music composition using dynamic Markov Chains and Genetic Algorithms[J].Journal of Computing Sciences，2011：26.

[7]蔡天芳，佘守宪.简单与和谐——谈谈乐音、音程与和弦[J].现代物理知识，2001（6）：38.

[8]曹西征，毛文涛，乔锟，等.基于音高旋律元的柔和乐曲的自动作曲算法[J].自动化学报，2012（10）：1723.

[9]张英俐，刘弘，宋宝亚.一种交互式遗传算法生成带主题乐曲的方法[J].数学的实践与认识，2012（16）：2434.

责任编辑（责任编辑：刘亭亭）