馬爾科夫鏈與多目標(biāo)遺傳算法在自動(dòng)作曲中的應(yīng)用

朱澤鍵 楊其宇 陳填銳

摘要：

提出一種新的自動(dòng)作曲方法，利用馬爾科夫鏈的不確定性與多目標(biāo)遺傳算法的規(guī)則性，將二者相結(jié)合，應(yīng)用到自動(dòng)作曲中。在Musicxml文件下，統(tǒng)計(jì)訓(xùn)練樣本中相鄰音符之間音高與時(shí)值的前后關(guān)系，建立馬爾科夫概率轉(zhuǎn)換表。利用基于概率的多目標(biāo)遺傳算法，根據(jù)已建立的概率轉(zhuǎn)換表構(gòu)造關(guān)于音高、時(shí)值的適應(yīng)性函數(shù)，同時(shí)加入少量音程和諧約束作為第三條適應(yīng)性規(guī)則。實(shí)驗(yàn)表明，在同一樂(lè)理規(guī)則下，與僅用馬爾科夫鏈輸出結(jié)果進(jìn)行音樂(lè)質(zhì)量評(píng)分、對(duì)比，該方法在保證結(jié)果多樣性的同時(shí)提高了音樂(lè)質(zhì)量。

關(guān)鍵詞關(guān)鍵詞：

算法作曲；Musicxml文件；不確定性；馬爾科夫鏈；概率；多目標(biāo)遺傳

DOIDOI：10.11907/rjdk.172247

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：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.

英文關(guān)鍵詞Key Words：algorithmic composition； Musicxml format music document； uncertainty； Markov chain； multiobjective genetic algorithm

0引言

當(dāng)今社會(huì)對(duì)自動(dòng)化程度要求越來(lái)越高，如何正確使用機(jī)器，并盡量減少對(duì)人工操作的依賴，通過(guò)統(tǒng)計(jì)與自動(dòng)分析數(shù)據(jù)就能領(lǐng)會(huì)模式識(shí)別要領(lǐng)，成為一個(gè)愈發(fā)重要的課題。計(jì)算機(jī)音樂(lè)作為人工智能領(lǐng)域的一個(gè)典型代表，研究并開發(fā)一種實(shí)現(xiàn)更高程度自動(dòng)化的作曲算法，具有重要意義。

目前普遍使用的機(jī)器作曲方法有馬爾科夫鏈、規(guī)則知識(shí)庫(kù)、貝葉斯網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)、遺傳算法等。大致可以分為兩類：有監(jiān)督學(xué)習(xí)與無(wú)監(jiān)督學(xué)習(xí)?；诩兇饨y(tǒng)計(jì)的馬爾科夫鏈屬于無(wú)監(jiān)督學(xué)習(xí)，這種算法所作樂(lè)曲具有較大隨意性?；趯＜乙?guī)則知識(shí)庫(kù)的算法屬于監(jiān)督學(xué)習(xí)，音樂(lè)質(zhì)量良好但作曲風(fēng)格過(guò)于形式化。貝葉斯網(wǎng)絡(luò)在樣本量較小的情況下能有良好的表現(xiàn)，常被用于一次性學(xué)習(xí)（Oneshot Learning），但是現(xiàn)有的貝葉斯網(wǎng)絡(luò)作曲方法是在人為繪制旋律曲線的情況下，根據(jù)貝葉斯概率公式推理整首樂(lè)曲的音符[2]，即整首歌曲的旋律走勢(shì)是由人為標(biāo)定的。人工神經(jīng)網(wǎng)絡(luò)算法輸出樂(lè)曲極大受限于訓(xùn)練樣本風(fēng)格，通用性較差。當(dāng)今遺傳算法主要是基于人機(jī)交互的方式，即對(duì)音樂(lè)打分作為遺傳算法的適應(yīng)性函數(shù)，但是所有基于人機(jī)交互的學(xué)習(xí)算法其缺點(diǎn)主要在于人的主觀偏見(jiàn)很大程度上影響了輸出樂(lè)曲的質(zhì)量[3，6，9]。

本文將馬爾科夫鏈與多目標(biāo)遺傳算法結(jié)合起來(lái)應(yīng)用到自動(dòng)作曲中，為了方便描述，記為“Markov ChainMulti-objective Genetic Algorithm”算法（“馬爾科夫鏈-多目標(biāo)遺傳算法”，簡(jiǎn)記為“M-MGA”算法）。由于使用馬爾科夫鏈?zhǔn)挂魳?lè)具有不確定性，通過(guò)多目標(biāo)遺傳算法的篩選，使這種算法生成的音樂(lè)，雖然不是全局最優(yōu)解，但是在保證解的質(zhì)量同時(shí)突出音樂(lè)的多樣性，即保證算法所生成的音樂(lè)重復(fù)率較低。在同一形式規(guī)則庫(kù)評(píng)分下，相比于單純馬爾科夫鏈的無(wú)監(jiān)督學(xué)習(xí)而言能較好地限制結(jié)果的隨意性。

1音樂(lè)信息整合

1.1訓(xùn)練樣本中音樂(lè)信息轉(zhuǎn)換

在Musicxml文件中用xml節(jié)點(diǎn)表示音符信息，step節(jié)點(diǎn)表示音階（C，D，E，F(xiàn)，G，A，B），alter節(jié)點(diǎn)表示是否升半音（如alter節(jié)點(diǎn)的內(nèi)容為1表示升一個(gè)半音），octave節(jié)點(diǎn)表示幾個(gè)八度，type節(jié)點(diǎn)表示該音符是幾分音符，type節(jié)點(diǎn)的內(nèi)容若為16th，表示這是一個(gè)16分音符，用1表示；若為eighth，則表示其是一個(gè)八分音符，用2表示。用一個(gè)數(shù)字來(lái)概括這4個(gè)節(jié)點(diǎn)所描述的音樂(lè)信息，可以較為方便地處理，用infor表示音樂(lè)信息的轉(zhuǎn)換結(jié)果，則轉(zhuǎn)換公式如式（1）：

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

式中，pitch為根據(jù)step和alter節(jié)點(diǎn)確定的音階，每一個(gè)八度相差12個(gè)半音，為了將時(shí)值信息與音高信息融合，將其用小數(shù)表示并與表示音高的整數(shù)部分加和，這里采用乘以0.1的方法將時(shí)值信息轉(zhuǎn)換為小數(shù)。

1.2馬爾科夫轉(zhuǎn)換表構(gòu)造

每一個(gè)音符可分為音高和時(shí)值兩種屬性，鋼琴有88個(gè)琴鍵，故在音高屬性方面，每一個(gè)音符有88種音高，而在時(shí)值方面，每一個(gè)音符又有16分音符、8分音符、4分音符、半音符和全音符5種時(shí)值，故每一個(gè)音符依照音高和時(shí)值屬性劃分可劃分為88×5種可能情況，馬爾科夫鏈表描述的是在當(dāng)前音符取值情況下下一個(gè)音符取各值的概率。這里用各音符出現(xiàn)的頻率代表概率。為了在音高和節(jié)奏上同時(shí)達(dá)到良好效果，該系統(tǒng)分別建立了音高和時(shí)值兩個(gè)方面的馬爾科夫鏈表。例如：基于音高的統(tǒng)計(jì)結(jié)果如表1所示。

2多目標(biāo)遺傳算法設(shè)計(jì)

2.1種群初始化

種群初始化即為解的初始化，解定義為每一代生成的音樂(lè)動(dòng)機(jī)。在保證解的多樣性和算法收斂時(shí)間的情況下，經(jīng)實(shí)驗(yàn)可知，當(dāng)初始化解的數(shù)目為100時(shí)可取得良好效果。

將馬爾科夫鏈表中各音符有序組合出現(xiàn)的頻率轉(zhuǎn)換為對(duì)應(yīng)的概率，解的初始化在本實(shí)驗(yàn)中為按照馬爾科夫轉(zhuǎn)換表輸出長(zhǎng)度不一的動(dòng)機(jī)片段。經(jīng)實(shí)驗(yàn)可得初始解的長(zhǎng)度（動(dòng)機(jī)的長(zhǎng)度）在4～20之間可保證結(jié)果的多樣性和不確定性。

2.2目標(biāo)函數(shù)設(shè)計(jì)

2.2.1目標(biāo)函數(shù)

在本實(shí)驗(yàn)的多目標(biāo)遺傳算法設(shè)計(jì)中，規(guī)定目標(biāo)函數(shù)值大的種群有較大概率留存到下一代。目標(biāo)函數(shù)有3個(gè)，即音高、時(shí)值對(duì)照馬爾科夫轉(zhuǎn)換表評(píng)分、對(duì)人為設(shè)定規(guī)則的適應(yīng)值。在音高、時(shí)值方面的目標(biāo)函數(shù)計(jì)算方法為依次記錄輸出的音樂(lè)動(dòng)機(jī)的相鄰兩個(gè)音符，并在馬爾科夫鏈表中尋找對(duì)應(yīng)音符的有序組合，所有該有序組合頻率之和的平均值即為輸出音符在音高和節(jié)奏方面的評(píng)分。為了加大音高和時(shí)值質(zhì)量的區(qū)分度，將每個(gè)音符所對(duì)應(yīng)的數(shù)字拆成整數(shù)部分（即音高部分）和小數(shù)部分（即時(shí)值部分）分別進(jìn)行評(píng)分，因此有音高和節(jié)奏兩個(gè)目標(biāo)函數(shù)。

2.2.2目標(biāo)函數(shù)設(shè)定

設(shè)定本環(huán)節(jié)目標(biāo)函數(shù)（以下稱為人工目標(biāo)函數(shù)）初始值為動(dòng)機(jī)的長(zhǎng)度，即動(dòng)機(jī)片段音符的個(gè)數(shù)，本環(huán)節(jié)人為設(shè)定樂(lè)曲中的禁止音程，凡是出現(xiàn)禁止的音程，則目標(biāo)函數(shù)值減1。根據(jù)音程和諧審美觀，在每一段樂(lè)曲的動(dòng)機(jī)首尾，不能出現(xiàn)F和A這兩個(gè)音符，因?yàn)檫@兩個(gè)音符出現(xiàn)在開頭或者結(jié)尾，會(huì)給人聽覺(jué)上極不穩(wěn)定、不和諧的感受[4]，故作為人為制定規(guī)則加入；若動(dòng)機(jī)首尾出現(xiàn)F或者A，則樂(lè)曲在本環(huán)節(jié)的目標(biāo)函數(shù)值置1（不能置0，因?yàn)楹笪乃惴ㄖ袑⒛繕?biāo)函數(shù)值取倒數(shù)轉(zhuǎn)換為遺傳算法中種群存活概率）。此外，一些音程由于會(huì)給人聽覺(jué)上造成極不和諧的感覺(jué)，故如果輸出樂(lè)曲動(dòng)機(jī)中有這種音程，目標(biāo)函數(shù)值減1。

音程為1個(gè)半音稱為小二度（MI/FA）、增一度（DO/#DO），這兩種音程雖然和諧，但不夠飽滿有力；音程為5個(gè)半音稱為完全四度；音程為11個(gè)半音稱為大七度；音程為12個(gè)半音稱為完全八度[4]。

在遍歷動(dòng)機(jī)中所有音程后，為了便于長(zhǎng)度不同的動(dòng)機(jī)在本環(huán)節(jié)目標(biāo)函數(shù)值的比較，將目標(biāo)函數(shù)值除以動(dòng)機(jī)長(zhǎng)度，即得到解的人工目標(biāo)函數(shù)值。

2.3基于Pareto支配等級(jí)的快速排序

2.3.1解的支配等級(jí)標(biāo)定

由Pareto支配的定義可得，解A支配解B，即對(duì)于所有目標(biāo)函數(shù)（音高、時(shí)值、人工目標(biāo)函數(shù)），A在各個(gè)目標(biāo)函數(shù)對(duì)應(yīng)的值（評(píng)分）都大于等于B。在遍歷整個(gè)種群中所有解后，可以快速標(biāo)定各個(gè)解的支配數(shù)目，支配數(shù)目較多的解性能良好，在選擇各個(gè)解進(jìn)行遺傳變異的時(shí)候應(yīng)優(yōu)先選擇[5]。

2.3.2擁擠距離計(jì)算

在生物進(jìn)化過(guò)程中，種群多樣性能夠保證生物種群朝著更好的方向進(jìn)化，即解的多樣性可以提升迭代遺傳結(jié)果的質(zhì)量。故采用擁擠距離的概念，目的是獲取分散較為均勻的解集，Pareto擁擠距離定義為對(duì)于解P＼-k，擁擠距離PCD的計(jì)算公式如式（2）：

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

式中：fi（pk+1），f（pk），fi（pk-1）為連續(xù)的3個(gè)解的各個(gè)目標(biāo)函數(shù)值，pk+1，Pk，pk-1為相應(yīng)的Pareto解，fmaxi、fmini為當(dāng)前獲取的第i個(gè)目標(biāo)函數(shù)的最大值和最小值[5]。

2.4遺傳迭代算法

個(gè)體生存概率大小由個(gè)體支配數(shù)目和擁擠距離共同決定。支配數(shù)目越高的個(gè)體說(shuō)明性能優(yōu)良，有較大的概率被保留下來(lái)，擁擠距離越大，說(shuō)明多樣性越強(qiáng)，越容易被保留。Pareto支配數(shù)目和擁擠距離共同決定了個(gè)體的優(yōu)劣，其中Pareto支配數(shù)目反映解在音高、節(jié)奏和人工目標(biāo)函數(shù)3個(gè)方面絕對(duì)占優(yōu)的性能，故在決定時(shí)具有較大權(quán)重。適應(yīng)度函數(shù)值越高反映解的性能越好，而且解的多樣性越強(qiáng)，在遺傳時(shí)有幾率通過(guò)交叉得到性能更佳的子代，故被保留的概率越高，適應(yīng)度函數(shù)計(jì)算公式如式（3）：

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

式中：n（x）為解x的支配數(shù)目，PCD（x）為解x的擁擠距離，為支配數(shù)目相對(duì)于擁擠距離的權(quán)值。

個(gè)體生存概率采用輪盤賭的方法計(jì)算，定義如公式（4）：

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

其中m為種群個(gè)體數(shù)。

3算法穩(wěn)定性

本實(shí)驗(yàn)從https：//musescore.org網(wǎng)站上選取40個(gè)Musicxml文件，在matlab上進(jìn)行單獨(dú)馬爾科夫鏈訓(xùn)練和馬爾科夫鏈結(jié)合遺傳算法訓(xùn)練，初始化解的數(shù)目設(shè)為100，經(jīng)過(guò)39代遺傳，最終剩下一組解，算法終止。本實(shí)驗(yàn)記錄多目標(biāo)遺傳算法進(jìn)行中每一代所有解中的最高目標(biāo)函數(shù)值，在圖1、2中如虛線所示。

將已構(gòu)造的馬爾科夫概率轉(zhuǎn)換表作為音樂(lè)質(zhì)量的評(píng)價(jià)標(biāo)準(zhǔn)，選擇評(píng)價(jià)標(biāo)準(zhǔn)的原因是馬爾科夫轉(zhuǎn)換表是基于對(duì)樣本音樂(lè)的統(tǒng)計(jì)，具有較高的客觀性。單獨(dú)使用馬爾科夫鏈輸出39次得到39個(gè)動(dòng)機(jī)片段，對(duì)照概率表，計(jì)算出音高、時(shí)值和人工目標(biāo)函數(shù)的評(píng)分，在圖1、2中如實(shí)線所示。

在算法接近停止時(shí)，目標(biāo)函數(shù)值可以穩(wěn)定收斂到一個(gè)與連續(xù)39次馬爾科夫鏈輸出結(jié)果中最佳情況接近的值，說(shuō)明算法取得了良好效果。遺傳算法終止時(shí)，音高目標(biāo)函數(shù)值為258，時(shí)值目標(biāo)函數(shù)值為1 763。故由圖1、2可以看出，遺傳的最終結(jié)果朝著最符合統(tǒng)計(jì)規(guī)律和人類聽覺(jué)審美的方向收斂，可以有效彌補(bǔ)馬爾科夫鏈的隨意性。

當(dāng)算法終止時(shí)生成動(dòng)機(jī)如圖3，分析此動(dòng)機(jī)，動(dòng)機(jī)的首尾并不是F或者A音符，動(dòng)機(jī)中只有一對(duì)音符前后相差1個(gè)半音，但其它音符并沒(méi)有這種情況，故整體效果較好。單用馬爾科夫鏈生成的樂(lè)曲中，挑選音高、時(shí)值、人工目標(biāo)函數(shù)處于平均水平的樂(lè)曲。如圖4，出現(xiàn)4對(duì)只相差一個(gè)半音的音符，在整體效果上顯得不夠和諧[7]，且從右至左的第1-4個(gè)音符中相鄰音符之間音程較大，且變化較劇烈，在聽覺(jué)上造成過(guò)于緊張且不和諧的感覺(jué)，原因是在單獨(dú)使用馬爾科夫鏈生成樂(lè)曲的過(guò)程中，音符沒(méi)有按照馬爾科夫鏈中概率較大的鏈接關(guān)系進(jìn)行轉(zhuǎn)換。這是由于沒(méi)有加入多目標(biāo)遺傳算法輔助選擇符合統(tǒng)計(jì)規(guī)律的音高和時(shí)值所造成的。

4結(jié)語(yǔ)

本文在馬爾科夫鏈的基礎(chǔ)上加入多目標(biāo)遺傳算法進(jìn)行約束并應(yīng)用到自動(dòng)作曲中，優(yōu)點(diǎn)在于使用多目標(biāo)遺傳算法限制了馬爾科夫鏈較大的隨意性，使得輸出結(jié)果的性能隨著迭代遺傳得到較穩(wěn)定的提升。實(shí)際上幫助馬爾科夫鏈轉(zhuǎn)換時(shí)確保前一時(shí)刻與后一時(shí)刻有較大概率進(jìn)行轉(zhuǎn)換，盡量避免出現(xiàn)小概率事件，同時(shí)使得轉(zhuǎn)換不僅基于概率與數(shù)理統(tǒng)計(jì)，還取決于人為規(guī)定對(duì)結(jié)果的需求。在工程上不僅可以應(yīng)用于計(jì)算機(jī)音樂(lè)方面，還涉及概率與統(tǒng)計(jì)中的馬爾科夫鏈。這種方法在保留決策多樣性的同時(shí)，盡量使決策符合馬爾科夫決策規(guī)律與人對(duì)結(jié)果的需求。

參考文獻(xiàn)參考文獻(xiàn)：

[1]馮寅，周昌樂(lè).算法作曲的研究進(jìn)展[J].軟件學(xué)報(bào)，2006（2）：209215.

[2]翁詩(shī)杰，李維華，丁海燕.基于貝葉斯網(wǎng)研究自動(dòng)作曲中音高的表示和推理[J].計(jì)算機(jī)科學(xué)，2014（S2）：216.

[3]謝力榮.計(jì)算機(jī)作曲中存在的問(wèn)題及對(duì)策探究[J].電化教育研究，2013（3）：322.

[4]杜鵬.基于遺傳算法與人工神經(jīng)網(wǎng)絡(luò)的二聲部創(chuàng)意曲自動(dòng)生成[D].廈門：廈門大學(xué)，2007.

[5]張長(zhǎng)勝.多目標(biāo)人工蜂群算法及遺傳算法的研究與應(yīng)用[M].沈陽(yáng)：東北大學(xué)出版社，2013.

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

[7]蔡天芳，佘守憲.簡(jiǎn)單與和諧——談?wù)剺?lè)音、音程與和弦[J].現(xiàn)代物理知識(shí)，2001（6）：38.

[8]曹西征，毛文濤，喬錕，等.基于音高旋律元的柔和樂(lè)曲的自動(dòng)作曲算法[J].自動(dòng)化學(xué)報(bào)，2012（10）：1723.

[9]張英俐，劉弘，宋寶亞.一種交互式遺傳算法生成帶主題樂(lè)曲的方法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012（16）：2434.

責(zé)任編輯（責(zé)任編輯：劉亭亭）