李東洋，郭為安，鄭曉妹，康琦，汪鐳，吳啟迪

基于隱馬爾可夫和交互式遺傳算法的計(jì)算機(jī)作曲算法設(shè)計(jì)

李東洋，郭為安，鄭曉妹，康琦，汪鐳，吳啟迪

“電腦音樂”自出現(xiàn)以來就受到廣泛的關(guān)注。90年代后，越來越多的算法被應(yīng)用于計(jì)算機(jī)作曲。主流的計(jì)算機(jī)作曲算法有馬爾可夫轉(zhuǎn)換表、遺傳算法、神經(jīng)網(wǎng)絡(luò)、隨機(jī)過程以及基于規(guī)則的知識(shí)庫(kù)系統(tǒng)。提出了一種基于隱馬爾科夫模型和交互式遺傳算法的計(jì)算機(jī)作曲算法。通過將旋律元以及節(jié)奏融合進(jìn)傳統(tǒng)的僅以音符或節(jié)奏為單元的馬爾可夫模型中，建立新型的隱馬爾可夫音樂預(yù)測(cè)模型，并采用交互式遺傳算法對(duì)產(chǎn)生音樂片段進(jìn)行優(yōu)化。仿真結(jié)果表明，該算法可以利用較小的數(shù)據(jù)集快速生成具有一定旋律邏輯并符合用戶個(gè)性的音樂片段。

計(jì)算機(jī)作曲；隱馬爾科夫模型；遺傳算法；節(jié)奏；旋律元

0 引言

算法作曲（Algorithmic Composition）或稱自動(dòng)作曲（Automated Composition）是為了按照一定的規(guī)則將多個(gè)音樂片段組成一個(gè)有機(jī)整體的一系列的規(guī)則集合。算法作曲并不一定需要計(jì)算機(jī)，在古典時(shí)期，莫扎特就運(yùn)用過隨機(jī)方式來組合不同的音樂模塊創(chuàng)作“Musical Dice Game”，并取得了良好的效果。

Markov在計(jì)算機(jī)作曲算法中是一種相對(duì)簡(jiǎn)單直接的技術(shù)。Markov轉(zhuǎn)換表作曲主要針對(duì)單個(gè)音符或者和弦甚至旋律之間的聯(lián)系。Bruno在其論文中提出可以利用某一特定風(fēng)格的音樂作品，構(gòu)造出一個(gè)Markov轉(zhuǎn)換表，音符集即是該Markov模型的狀態(tài)空間，從而根據(jù)Markov模型的狀態(tài)轉(zhuǎn)移矩陣計(jì)算下一個(gè)要出現(xiàn)音符的可能性[1]。Ames和 Domino的Cybernetic Composer系統(tǒng)對(duì)節(jié)奏也建立了Markov轉(zhuǎn)換表，可以創(chuàng)造出搖滾樂、爵士樂及拉格泰姆樂風(fēng)格的音樂片段[2]。 Karsten Verbeurgt 和Michael Dinolfo等人在訓(xùn)練模型中創(chuàng)造性的提出了音樂模式提取，在一定程度上解決了傳統(tǒng)的一階馬爾可夫模型不能很好地描述樂曲結(jié)構(gòu)的問題[3]。曹西征、毛文濤和喬錕等人提出的旋律元概念[4]。

在利用遺傳算法進(jìn)行作曲時(shí)，系統(tǒng)的適應(yīng)度函數(shù)設(shè)置至關(guān)重要，黃澄宇在其研究中采用人工交互式評(píng)價(jià)，取得良好的效果[5]。

綜上所述可以看出目前計(jì)算機(jī)作曲的主要技術(shù)瓶頸包括：

（1）音樂創(chuàng)作風(fēng)格問題。

（2）音樂知識(shí)的表達(dá)問題。

（3）創(chuàng)造性和人機(jī)交互問題。

（4）音樂作品的評(píng)價(jià)問題。

為解決前兩個(gè)問題，本文采用隱馬爾科夫模型對(duì)旋律和節(jié)奏建模并加入旋律元概念，學(xué)習(xí)同一種曲風(fēng)作品的方法；對(duì)于后兩個(gè)問題利用交互式遺傳算法進(jìn)行人機(jī)交互和結(jié)果尋優(yōu)。文章剩余內(nèi)容主要包含以下3個(gè)方面：

（1）介紹隱馬爾科夫模型基本原理，詳述本文中的模型構(gòu)建以及參數(shù)訓(xùn)練過程。

（2）建立改進(jìn)的交互式遺傳算法優(yōu)化模型，構(gòu)造出完整的作曲算法。

（3）設(shè)計(jì)仿真實(shí)驗(yàn)，通過對(duì)比，驗(yàn)證算法性能。

1 基于隱馬爾科夫的音樂創(chuàng)作模型設(shè)計(jì)

傳統(tǒng)的Markov鏈作曲是基于馬爾科夫模型的作曲方法。通常學(xué)習(xí)一定量樂曲，構(gòu)建以音符或者節(jié)奏為狀態(tài)空間的馬爾科夫模型[1,2]。然而，對(duì)音樂來說，節(jié)奏和曲調(diào)（音高起伏，即旋律）是音樂中最重要的兩個(gè)要素，而且是不可分割的整體。為了簡(jiǎn)化計(jì)算，在算法研究中通常只考慮一種或少數(shù)幾種音樂要素。然而目前的研究通常將所考慮的音樂要素分離開來，例如將節(jié)奏和旋律分開建模研究，這顯然不滿足音樂創(chuàng)作的需求。本文將對(duì)此改進(jìn)。利用隱馬爾科夫模型描述音樂的節(jié)奏和旋律關(guān)系，將二者作為關(guān)聯(lián)因素進(jìn)行創(chuàng)作。

1.1 隱馬爾科夫模型（HMM）

HMM是一種時(shí)域上的統(tǒng)計(jì)模型。通常用來描述一個(gè)含有隱含未知參數(shù)的馬爾可夫過程。在正常的馬爾可夫過程中，狀態(tài)對(duì)于觀察者來說是直接可見的。狀態(tài)之間的轉(zhuǎn)換概率就是模型的全部參數(shù)。在HMM中，狀態(tài)并不直接可見，但受到狀態(tài)影響的某些變量則是可見的。每一個(gè)狀態(tài)在可能輸出的符號(hào)上都有一個(gè)概率分布，因此輸出符號(hào)的序列能夠透露出狀態(tài)序列的一些信息。因此，HMM包含兩個(gè)概率矩陣，狀態(tài)自身存在的轉(zhuǎn)移概率矩陣和狀態(tài)轉(zhuǎn)移時(shí)生成或接受某個(gè)符號(hào)所對(duì)應(yīng)的發(fā)射概率矩陣一個(gè)HMM中包含一下5個(gè)參數(shù)：

（1）隱含狀態(tài)為式（1）：

其中n表示所有可能出現(xiàn)的狀態(tài)個(gè)數(shù)；

（2）觀察符號(hào)集合為式（2）：

其中m表示每一個(gè)狀態(tài)對(duì)應(yīng)的可能觀察符號(hào)數(shù)；

（3）狀態(tài)轉(zhuǎn)移矩陣為式（3）：

其中qt表示在t時(shí)刻所處的狀態(tài)；

（4）發(fā)射矩陣，即觀察概率矩陣為式（5）：

其中ot表示在t時(shí)刻狀態(tài)為xi的觀測(cè)值；

（5）初始狀態(tài)分布式（7）：

一個(gè)簡(jiǎn)單的HMM狀態(tài)變遷如圖1所示：

圖1 HMM狀態(tài)變遷圖

因此，一個(gè)HMM模型，可以描述一個(gè)未知的隱含狀態(tài)在已知的觀察狀態(tài)下的狀態(tài)轉(zhuǎn)移過程。也就是在模型的各參數(shù)已知的情況下，給定觀察序列，去選擇一個(gè)最具可能的狀態(tài)序列。也就是HMM中的解碼問題。本文中我們采用Viterbi算法進(jìn)行求解。

1.2 Viterbi 算法

維特比算法（Viterbi algorithm）是一種動(dòng)態(tài)規(guī)劃算法。經(jīng)常被應(yīng)用于隱馬爾科夫模型的解碼問題中，根據(jù)已知的觀察狀態(tài)序列求出最有可能生成該觀察狀態(tài)序列的隱含狀態(tài)序列。

公式（10）中為前t個(gè)最終狀態(tài)為xi的觀測(cè)結(jié)果最有可能對(duì)應(yīng)的狀態(tài)序列的概率。通過保存向后指針記下在公式（10）中的狀態(tài)可以獲得維特比路徑。另外設(shè)計(jì)一個(gè)函數(shù)，返回若t＞1時(shí)計(jì)算中的或t=1時(shí)的xi。由此可得到式（11）：

那么，根據(jù) Viterbi算法，我們可以利用系統(tǒng)已知的觀察狀態(tài)，推斷出最有可能的隱含狀態(tài)。

1.3 基于節(jié)奏-旋律元的HMM創(chuàng)作模型設(shè)計(jì)

節(jié)奏是音樂的骨架，即使一段旋律起伏優(yōu)雅動(dòng)聽，如果沒有合適的節(jié)奏作為基礎(chǔ)，旋律也會(huì)變得雜亂無章。對(duì)于將節(jié)奏和旋律關(guān)聯(lián)考慮的問題，HMM為我們提供了良好的解決辦法。本文將節(jié)奏視為HMM的觀察狀態(tài)，旋律為HMM中的隱含狀態(tài)。首先生成一個(gè)節(jié)奏序列，而后根據(jù)這個(gè)觀察序列，應(yīng)用Viterbi算法產(chǎn)生新的旋律序列。

在以往的普通馬爾可夫作曲研究中，大多是以單個(gè)音符或者音符的時(shí)長(zhǎng)作為一個(gè)隨機(jī)過程的狀態(tài)空間，例如統(tǒng)計(jì)每個(gè)音符下一時(shí)刻出現(xiàn)的狀態(tài)的頻率作為當(dāng)前狀態(tài)跳轉(zhuǎn)到下一個(gè)狀態(tài)的轉(zhuǎn)移概率。這種方法只能反映學(xué)習(xí)樣本的表面結(jié)構(gòu)。要表達(dá)深層結(jié)構(gòu)，就必須構(gòu)造更高階的馬爾科夫鏈，將會(huì)提升算法的復(fù)雜度，往往得不償失。對(duì)此，本文借鑒文獻(xiàn)[3,4]，加入旋律元的概念，提升HMM對(duì)音樂特征的表達(dá)能力。

1.3.1 基于字典樹搜索的旋律元提取

為了能夠在基于一階HMM的前提下，能夠最大程度地挖掘音樂知識(shí)的內(nèi)部結(jié)構(gòu)，本文采用旋律元與單個(gè)音符并進(jìn)的學(xué)習(xí)方式。文獻(xiàn)[4]中基于音樂規(guī)則的旋律元構(gòu)建，更類似于基于知識(shí)庫(kù)系統(tǒng)和基于音樂文法的創(chuàng)作模式，在一定程度上會(huì)限制旋律元的結(jié)構(gòu)，并且本文前面已經(jīng)提出，要構(gòu)建出完整有效的音樂規(guī)則系統(tǒng)是非常困難的，這樣，基于音樂規(guī)則的旋律元生成系統(tǒng)會(huì)產(chǎn)生許多不符合要求的旋律元。而Karsten Verbeurgt的方法中，基于字典樹查詢?cè)硖崛⌒稍?，但不?duì)旋律元長(zhǎng)度加以限制，將導(dǎo)致學(xué)習(xí)樣本的幾個(gè)小節(jié)同時(shí)定義為一個(gè)旋律元，這對(duì)樂曲創(chuàng)作的創(chuàng)造性設(shè)置了很大障礙。

因此，本文中定義旋律元為：在一段音樂中出現(xiàn)次數(shù)大于兩次，并且長(zhǎng)度在2到5個(gè)音符之間的音樂片段為旋律元。有關(guān)字典樹本文不再詳細(xì)介紹，具體可以參考文獻(xiàn)[3]。我們將舉例介紹如何根據(jù)字典樹搜索原理提取出待學(xué)習(xí)音樂片段中的旋律元。首先我們將每一個(gè)音符的所有出現(xiàn)位置都視為一個(gè)根節(jié)點(diǎn)向下查詢，直到一個(gè)根節(jié)點(diǎn)的所有分支都出現(xiàn)不同音符為止。例如一段音樂的編碼為“ABCABCDE”。則根據(jù)這段音樂所構(gòu)建的搜索樹如圖2所示：

圖2 根據(jù)“ABCABCDE”構(gòu)建的旋律元搜索樹

如圖2所示，出現(xiàn)過兩次以上的小片段總共有3個(gè)，ABC、 BC和C。但是符合出現(xiàn)次數(shù)大于兩次，同時(shí)長(zhǎng)度在3個(gè)到5個(gè)音符之間的音樂片段只有ABC，因此，根據(jù)本文對(duì)旋律元的定義，在這段實(shí)例音樂中，旋律元即是ABC。

通過這種方法，可以將一系列待學(xué)習(xí)音樂中的所有符合條件的旋律元全部提取出來。在訓(xùn)練HMM的轉(zhuǎn)移概率參數(shù)矩陣時(shí)，將旋律元與單個(gè)音符融合在一起，構(gòu)成描述音樂多層結(jié)構(gòu)的狀態(tài)空間，彌補(bǔ)一階馬爾科夫中存在的只能描述音樂表層的音符之間概率組合的問題。

1.3.2 HMM參數(shù)訓(xùn)練

綜上所述，我們已經(jīng)可以確定HMM的隱含狀態(tài)包含待學(xué)習(xí)音樂中的單個(gè)音符以及提取出的旋律元。根據(jù)本文定義，待學(xué)習(xí)音樂的節(jié)奏為觀察狀態(tài)。下面需要確定的3個(gè)參數(shù)分別是：狀態(tài)轉(zhuǎn)移概率矩陣、發(fā)射概率矩陣以及初始概率矩陣。

在確定了模型的隱含狀態(tài)之后,我們可以統(tǒng)計(jì)出所有狀態(tài)在待學(xué)習(xí)音樂片段中出現(xiàn)的次數(shù)。統(tǒng)計(jì)一個(gè)狀態(tài)（音符或者旋律元）后所有的可能狀態(tài)以及這些狀態(tài)出現(xiàn)的頻率作為狀態(tài)之間的轉(zhuǎn)移概率矩陣。如式（12）：

發(fā)射概率矩陣，是從某個(gè)隱含狀態(tài)到某個(gè)觀察狀態(tài)的概率。我們定義音符為隱含狀態(tài)，音符所對(duì)應(yīng)的時(shí)值為觀察狀態(tài)。那么發(fā)射概率矩陣就是統(tǒng)計(jì)一個(gè)音符在待學(xué)習(xí)音樂中所有可能的時(shí)值，以及它們出現(xiàn)的頻率。計(jì)算公式與狀態(tài)轉(zhuǎn)移概率矩陣相同，如式（13）：

初始狀態(tài)分布決定模型的初始狀態(tài)。本文分別統(tǒng)計(jì)每個(gè)待學(xué)習(xí)音樂片段中所有音符第一次出現(xiàn)的位置以及出現(xiàn)的次數(shù)。則某一音符的初始概率為式（14）：

由于樂曲節(jié)奏的表層結(jié)構(gòu)顯著，通常呈現(xiàn)周期性，平穩(wěn)性。因此，本文初始化模型的觀察狀態(tài)一階馬爾可夫鏈。以樣本集中的單個(gè)時(shí)長(zhǎng)為狀態(tài)空間，狀態(tài)的出現(xiàn)頻率為初始分布概率，狀態(tài)轉(zhuǎn)移矩陣以公式（12）計(jì)算。為簡(jiǎn)化算法，本文將模型生成的狀態(tài)序列長(zhǎng)度限制為50。

基于HMM的作曲算法分流程圖如圖3所示：

圖3 基于HMM的作曲算法流程圖

2 交互式遺傳算法優(yōu)化模型

本文所提出的基于 HMM的作曲算法理論上可以產(chǎn)生與學(xué)習(xí)樣本風(fēng)格類似的音樂作品。但音樂是一個(gè)具有很強(qiáng)主觀性感覺的產(chǎn)物，不同的人即是對(duì)同樣的曲風(fēng)的歌曲，也會(huì)有不同的感受。因此，如何使作曲算法能夠產(chǎn)生符合使用者要求的歌曲也是需要考慮的問題。

對(duì)于此問題，本文將采用交互式遺傳算法。一方面，遺傳算法的交叉算子可以將產(chǎn)生出的音樂片段中的優(yōu)秀片段保留下來，變異算子可以使樂曲突變，恰似作曲家在作曲中既借鑒優(yōu)秀作品又發(fā)揮靈感的創(chuàng)作行為。另一方面，交互式遺傳算法采用人工評(píng)價(jià)函數(shù)，可以使樂曲的進(jìn)化沿著使用者的意圖進(jìn)行演化，達(dá)到產(chǎn)生符合使用者要求的目的。樂曲編碼采用MIDI實(shí)數(shù)編碼，考慮本文中所選取的學(xué)習(xí)樣本，限制節(jié)奏編碼為三十六分之一音符到全音符。定義全音符時(shí)長(zhǎng)為單位一，節(jié)奏編碼集合為：[1/32 1/16 1/8 1/4 1/2 1]。一段音樂最終將被編碼為一個(gè)矩陣。例如式（15）：其中第一行為音高，第二行為節(jié)奏值。

選擇算子、交叉算子分別為輪盤選擇法、多點(diǎn)交叉。在變異算子中，采用以下3種變異方式。

（1）某一染色體中的一段音高同時(shí)升高或降低n階，n變化范圍設(shè)為[1,2,3]。如式（16）：

（2）某一染色體中的一段節(jié)奏同時(shí)升高或者降低k拍，k的取值范圍為[0.25,1,1.5,2]。如式（17）：

（3）單點(diǎn)隨機(jī)突變

突變過程中音符或者節(jié)奏值越界則隨機(jī)初始化為各自狀態(tài)空間中的某一狀態(tài)。

本文適應(yīng)度函數(shù)擬采用人工評(píng)價(jià)給出樂曲的適應(yīng)度值，主導(dǎo)算法優(yōu)化方向。為了減輕用戶在算法進(jìn)化過程中的試聽工作量。定義一個(gè)個(gè)體的適應(yīng)度值為人工評(píng)價(jià)值與基于樂曲形態(tài)特征相似度的加權(quán)和，如公式（18）：

其中，H( i)和S( i)分別是歸一化后的人工評(píng)價(jià)值和基于樂曲形態(tài)特征的相似度，w為連接適應(yīng)度兩個(gè)部分的權(quán)重。取值規(guī)則如式（19）：

其中，n為進(jìn)化代數(shù)，k?N，N為自然數(shù)，λ和β為正整數(shù)，本文中分別取20和4。這樣可以保證人工評(píng)價(jià)可以隨著進(jìn)化代數(shù)完全主導(dǎo)進(jìn)化方向。w

類似的音高w節(jié)奏可以表達(dá)相近的聽覺。 為1時(shí)的適應(yīng)度由用戶給出。 為0時(shí)，用最優(yōu)個(gè)體的形態(tài)特征來衡量群體進(jìn)化后的優(yōu)劣，同樣可以達(dá)到引導(dǎo)進(jìn)化向用戶需求方向發(fā)展的目的。本文將音符序列的形態(tài)特征符號(hào)化，上升，平穩(wěn)和下降分別映射為[1,0,-1]。則利用形態(tài)特征相似度計(jì)算個(gè)體的適應(yīng)度函數(shù)如式（20）：

其中l(wèi)為個(gè)體的長(zhǎng)度，SPop和Sbest分別為符號(hào)化后的種群和最佳個(gè)體。

通過適應(yīng)度函數(shù)（18）。算法的終止條件為達(dá)到最大進(jìn)化代數(shù)，或者用戶滿意。綜上所述，本文所提出基于HMM和IGA的作曲算法流程圖如圖4所示：

圖4 基于HMM-IGA的計(jì)算機(jī)作曲算法

3 實(shí)驗(yàn)設(shè)計(jì)及結(jié)果分析

本文基于MATLAB設(shè)計(jì)了仿真實(shí)驗(yàn)。訓(xùn)練樣本為：《青花瓷》，《美人魚》，《千里之外》和《紅塵客?！?。算法參數(shù)設(shè)計(jì)如下。生成的作品長(zhǎng)度為50個(gè)音符?；谧值錁渌阉魈崛〉男稍L(zhǎng)度為[2,5]。IGA種群大小為 10，最大進(jìn)化代數(shù)為50，交叉概率為0.8，變異概率為0.2，公式（19）中λ為20，β為4，公式（16）中n變化范圍設(shè)為[1,2,3]，公式（17）中k的取值范圍為[0.25,1,1.5,2]。運(yùn)行十次，最優(yōu)片段如圖5所示：

Computer Composing Algorithm Based on Hidden Markov Model and Interactive Genetic Algorithm

Li Dongyang1, Guo Weian2, Zheng Xiaomei3, Kang Qi1, Wang Lei1, Wu Qidi1
(1. College of Electronics and Information Engineering, Tongji University, Shanghai 201804, China；2. Sino-German College Applied Sciences of Tongji University, Shanghai 201804, China；3. The College of Information, Mechanical and Electrical Engineering, Shanghai Normal University, Shanghai 200234, China)

＂Computer music＂ was widespread concerned since it had appeared. Since 1990s, more and more algorithms have been applied to ＂Computer music＂. There are five algorithms used widely for computer composing i.e., Markov chains, genetic algorithm (GA), neural network, stochastic processes and rules-based knowledge base system. This paper proposes a new computer composing algorithm based on Hidden Markov Model (HMM) and interactive GA. The new algorithm not only pays attention to the note information, but also takes the beat information and melody unit into account. Then, the new algorithm produces new music pieces based on HMM and optimizes them using interactive GA (IGA). The simulation results show this new algorithm can produce satisfied music pieces and just needs a small data set.

Computer composing； Hidden Markov Model (HMM)； Interactive Genetic Algorithm (IGA)； Beat； Melody unit

TP393.04

A

1007-757X(2016)011-0001-04

上海市自然科學(xué)基金項(xiàng)目（14ZR1442700）；國(guó)家自然科學(xué)基金（61503287）

李東洋（1992-），男，同濟(jì)大學(xué)電子與信息工程學(xué)院，碩士研究生，研究方向：過程控制，上海 201804

郭為安（1985-），男，同濟(jì)大學(xué)中德工程學(xué)院，講師，研究方向：智能控制，智能計(jì)算，上海 201804

鄭曉妹（1973-），女，上海師范大學(xué)信息與機(jī)電工程學(xué)院，講師，研究方向：算法作曲，上海 200234

康 琦（1980-），男，同濟(jì)大學(xué)電子與信息工程學(xué)院，副教授，研究方向：智能控制，智能計(jì)算等領(lǐng)域，上海 201804

汪 鐳（1970-），男，同濟(jì)大學(xué)電子與信息工程學(xué)院，教授，研究方向：智能控制，智能計(jì)算，CIMS和系統(tǒng)工程方面，上海 201804

吳啟迪（1947-），女，同濟(jì)大學(xué)電子與信息工程學(xué)院，教授，研究方向：智能控制，智能計(jì)算，CIMS和管理科學(xué)方向，上海 201804