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

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

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

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

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

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

0 引言

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

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

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

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

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

（2）音樂知識的表達問題。

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

（4）音樂作品的評價問題。

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

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

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

（3）設(shè)計仿真實驗，通過對比，驗證算法性能。

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

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

1.1 隱馬爾科夫模型（HMM）

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

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

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

（2）觀察符號集合為式（2）：

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

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

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

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

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

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

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

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

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

1.2 Viterbi 算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（3）單點隨機突變

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

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

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

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

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

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

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

圖4 基于HMM-IGA的計算機作曲算法

3 實驗設(shè)計及結(jié)果分析

本文基于MATLAB設(shè)計了仿真實驗。訓(xùn)練樣本為：《青花瓷》，《美人魚》，《千里之外》和《紅塵客?！贰Ｋ惴▍?shù)設(shè)計如下。生成的作品長度為50個音符。基于字典樹搜索提取的旋律元長度為[2,5]。IGA種群大小為 10，最大進化代數(shù)為50，交叉概率為0.8，變異概率為0.2，公式（19）中λ為20，β為4，公式（16）中n變化范圍設(shè)為[1,2,3]，公式（17）中k的取值范圍為[0.25,1,1.5,2]。運行十次，最優(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é)基金項目（14ZR1442700）；國家自然科學(xué)基金（61503287）

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

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

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

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

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

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