啟發(fā)式搜索算法進行樂曲編輯的基本原理分析

戴幸

摘 要：該論文通過對啟發(fā)式搜索算法進行樂曲編輯的基本原理進行分析，并對該算法實施樂曲編輯的主要步驟進行明確，最后，基于啟發(fā)式搜索算法背景，對交互式計算機樂曲編輯系統(tǒng)進行樂曲編輯展開具體的實驗與分析，重點解決的問題是搜索空間的限制、樂曲編碼方法、確定評價函數(shù)。

關(guān)鍵詞：樂曲編輯；啟發(fā)式搜索算法；遺傳算法；適應(yīng)度；進化

一、啟發(fā)式搜索的提出

啟發(fā)式搜索算法是在狀態(tài)空間搜索概念的基礎(chǔ)上提出的。所謂狀態(tài)空間搜索即針對某一個問題的求解的過程可以歸納為由問題初始的狀態(tài)向目標(biāo)狀態(tài)轉(zhuǎn)移并尋求路徑的過程。歸根到底，狀態(tài)空間搜索即是兩個不同狀態(tài)中間的路徑求解，其中不同點表現(xiàn)出來的為結(jié)果，路徑所體現(xiàn)的則是過程；在很多情況下，一個問題的路徑求解可能面臨較大的分支，即部分求解條件存在一定的不確定性，這就使得求解的路徑并非只有一條，從而構(gòu)成了一副狀態(tài)空間圖，那么從狀態(tài)空間圖中尋找一個從初始到最終目標(biāo)的路徑過程便叫做狀態(tài)空間搜索。

在絕大多數(shù)的狀態(tài)空間搜索中，屬于廣度優(yōu)先搜索或深度優(yōu)先搜索，廣度優(yōu)先搜索是根據(jù)一定的順序進行某一分支的搜索，該分支搜索完成之后再進行后續(xù)分支的搜索，最終以搜索到目標(biāo)為結(jié)束標(biāo)志。深度優(yōu)先搜索則是按照層次從初始的狀態(tài)逐層搜索，最終以搜索到目標(biāo)為結(jié)束標(biāo)志。

二、啟發(fā)式搜索算法的基本原理

啟發(fā)式搜索算法同樣是以狀態(tài)空間為基礎(chǔ)的搜索方式之一，它的典型特征是預(yù)先對需要搜索的任何一個空間位置進行評估，從中篩選出最好的空間位置，然后按照這個位置作為搜索點展開新的搜索，直到尋找到最終的目標(biāo)。利用啟發(fā)式搜索算法能夠有效避免無效的空間路徑搜索，從而提升了搜索的效率。很明顯，在啟發(fā)式搜索算法中，對于空間位置的評估是非常重要的。當(dāng)使用不同的評估策略時，獲得的評估結(jié)果也是完全不同的。

一般情況下，啟發(fā)式搜索算法的評估采取評估函數(shù)來表示，典型的如f（n） = g（n） + h（n），上述評估函數(shù)中，f（n）代表每一個位置n的評估函數(shù)，g（n）則代表了整個狀態(tài)空間中從初始狀態(tài)位置到n位置的真實代價，h（n）則代表了從位置n到目標(biāo)位置的最優(yōu)路徑的代價。在評估函數(shù)中，h（n）是整個算法啟發(fā)特征的表現(xiàn)，而g（n）函數(shù)是已知的，它主要表征了狀態(tài)搜索的廣度優(yōu)先優(yōu)勢，當(dāng)h（n） >> g（n）成立時，g（n）完全能夠省略，從而有效提升了搜索效率。

當(dāng)前，常見的啟發(fā)式搜索算法包括有模擬退火算法、蟻群算法、人工神經(jīng)網(wǎng)絡(luò)和遺傳算法。其中遺傳算法作為來源于生物學(xué)領(lǐng)域進化論觀點的一種算法，在搜索過程中可實現(xiàn)一定的并行性，整個搜索過程較為簡單，可擴展性較強，具有良好的適應(yīng)性，從而成為了啟發(fā)式搜索算法中影響和應(yīng)用最為廣泛的算法。

三、樂曲編輯的遺傳算法基本步驟

從遺傳算法的本質(zhì)來看，它具有典型的迭代特點。結(jié)合遺傳算法的基本操作流程，可以獲得樂曲編輯的遺傳算法步驟。利用活動圖，得到如圖1所示的步驟：

上述步驟可以歸納為以下幾個核心的過程：

（1）進行編碼策略的選擇，需要將域與樂曲的集合進行轉(zhuǎn)換，結(jié)果為狀態(tài)空間S；

（2）構(gòu)建種群適應(yīng)度評價函數(shù)；

（3）設(shè)置遺傳策略，核心的操作主要包括有種群大小的確定，遺傳操作（選擇、交叉與變異）的具體方法，同時對遺傳操作方法的各類概率參數(shù)進行確定；

（4）初始化種群；

（5）進行種群各位串解碼后的適應(yīng)度計算；

（6）根據(jù)遺傳策略，多次重復(fù)進行遺傳操作，判斷新種群的性能是否達到既定的指標(biāo)或者是否進行了足夠的迭代次數(shù)。

四、樂曲編輯的遺傳操作

在遺傳算法中，進行樂曲編輯的遺傳操作是在初始種群確定以及編碼策略選擇的基礎(chǔ)上展開的，主要的遺傳操作包含兩種，一為交叉操作，二為變異操作。

交叉操作主要是以一定的交叉算子為基礎(chǔ)進行，其根本的目標(biāo)是在已經(jīng)選擇的種群個體中，通過兩個不同位置個體的相同位置基因?qū)嵤┙粨Q，以此來產(chǎn)生新的個體。在本次遺傳算法的樂曲編輯中，交叉操作主要以單點交叉與兩點交叉兩種方式來展開。交叉操作執(zhí)行之后 ，樂曲種群中將會產(chǎn)生更為優(yōu)秀的種群個體，并進入到新的種群中。

五、結(jié)語

通過對啟發(fā)式搜索算法進行樂曲編輯的基本原理分析，發(fā)現(xiàn)到目前為止，發(fā)達國家的一些研究人員針對計算機算法的樂曲編輯方式取得了不錯的進展，一些基于算法的樂曲編輯系統(tǒng)也已經(jīng)出現(xiàn)，典型的如Cybernetic Composer系統(tǒng)、CHORAL系統(tǒng)、EMI系統(tǒng)、ERNN系統(tǒng)、GenJam系統(tǒng)等，這些系統(tǒng)在一定程度上提升了樂曲制作過程中的人機交互能力。在國內(nèi)，計算機算法樂曲編輯方面的研究絕大多數(shù)是基于理論的，具體的實踐系統(tǒng)方面較少，這和國外相比具有較大的差距，需要在未來的研究過程中繼續(xù)深入和完善。

參考文獻：

[1]馮寅，周昌樂.算法作曲的研究進展[J].軟件學(xué)報，2006，（02）：52-53.

[2]肖武雄.頻譜音樂的曲式原則[J].星海音樂學(xué)院學(xué)報，2012，（04）：77-78.

[3]曹西征等.基于音高旋律元的柔和樂曲的自動作曲算法[J].自動化報，2012（10）：29-30.