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

戴幸

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

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

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

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

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

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

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

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

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

三、樂(lè)曲編輯的遺傳算法基本步驟

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

上述步驟可以歸納為以下幾個(gè)核心的過(guò)程：

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

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

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

（4）初始化種群；

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

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

四、樂(lè)曲編輯的遺傳操作

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

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

五、結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

[3]曹西征等.基于音高旋律元的柔和樂(lè)曲的自動(dòng)作曲算法[J].自動(dòng)化報(bào)，2012（10）：29-30.