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

戴幸

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

關鍵詞：樂曲編輯；啟發式搜索算法；遺傳算法；適應度；進化

一、啟發式搜索的提出

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

在絕大多數的狀態空間搜索中，屬于廣度優先搜索或深度優先搜索，廣度優先搜索是根據一定的順序進行某一分支的搜索，該分支搜索完成之后再進行后續分支的搜索，最終以搜索到目標為結束標志。深度優先搜索則是按照層次從初始的狀態逐層搜索，最終以搜索到目標為結束標志。

二、啟發式搜索算法的基本原理

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

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

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

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

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

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

（1）進行編碼策略的選擇，需要將域與樂曲的集合進行轉換，結果為狀態空間S；

（2）構建種群適應度評價函數；

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

（4）初始化種群；

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

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

四、樂曲編輯的遺傳操作

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

交叉操作主要是以一定的交叉算子為基礎進行，其根本的目標是在已經選擇的種群個體中，通過兩個不同位置個體的相同位置基因實施交換，以此來產生新的個體。在本次遺傳算法的樂曲編輯中，交叉操作主要以單點交叉與兩點交叉兩種方式來展開。交叉操作執行之后 ，樂曲種群中將會產生更為優秀的種群個體，并進入到新的種群中。

五、結語

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

參考文獻：

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

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

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