一種宋詞自動生成的遺傳算法-文章學習匯報

1、一種宋詞自動生成的遺傳算法匯報人：XXX日期：2016年11月2日匯報提綱 研究背景 遺傳算法 構(gòu)造宋詞生成遺傳算法 系統(tǒng)的實現(xiàn)與結(jié)果分析一、研究背景 漢語古典詩詞的計算化研究始于 20 世紀90 年代中期，到目前為止，已在語料庫建立、詞匯語義分析、創(chuàng)作風格辨析、聯(lián)語應對等方面取得了一些初步的成果，但在詩歌的自動生成方面，尚無系統(tǒng)性的學術(shù)性研究。相比而言，國外有關(guān)機器詩歌自動生成的研究起步較早，目前已嘗試了許多方法并積累了一定的經(jīng)驗。 較為成熟的詩歌生成系統(tǒng)主要是Levy 開發(fā)的原型系統(tǒng)POEVOLVE，能夠生成Limerick(一種起源于歐洲的五行打油詩)。在該系統(tǒng)中將詩歌生成問題看成一個狀

2、態(tài)空間搜索問題，并提出了語義(meaningfulness), 語法(grammaticality) 和詩性(poeticness)3 個詩歌必須滿足的條件。一、研究背景 借鑒上述的遺傳算法詩歌生成系統(tǒng)的主要原理，在我們自己建立的全宋詞熟語料庫(包括切分、詞性、音韻、情感、典故、格律、詞牌、句法等內(nèi)容)的基礎(chǔ)上，針對宋詞自身的特點，按照遺傳算法的構(gòu)造原理，具體給出了一種宋詞自動生成的遺傳算法，并進行了機器實現(xiàn)。一、研究背景系統(tǒng)整體框架二、遺傳算法 遺傳算法（GA）由 Holland 教授于六十年代提出。它是仿真生物遺傳學和自然選擇機理，通過人工方式所構(gòu)造的一類智能優(yōu)化搜索算法。 早期的應用研究

3、主要圍繞組合優(yōu)化問題以及復雜的函數(shù)優(yōu)化問題求解，如今應用研究的領(lǐng)域：NP完全問題機器學習并行處理神經(jīng)網(wǎng)絡(luò)權(quán)值知識發(fā)現(xiàn)1、概述概述二、遺傳算法 染色體 基因2、基本概念基本概念二、遺傳算法 適應度:基本概念各個個體對環(huán)境的適應程度叫做適應度。為了體現(xiàn)染色體的適應能力，引入了對問題中的每一個染色體都能進行度量的函數(shù)，叫適應度函數(shù). 這個函數(shù)是計算個體在群體中被使用的概率。二、遺傳算法 選擇(selection) 交叉(crossover) 變異(mutation)操作算法簡單遺傳算法的遺傳操作主要有以下三種：二、遺傳算法操作算法1選擇(selection)選擇操作也叫復制操作，從群體中按個體的適應

4、度函數(shù)值選擇出較適應環(huán)境的個體。一般地說，選擇將使適應度高的個體繁殖下一代的數(shù)目較多，而適應度較小的個體，繁殖下一代的數(shù)目較少,甚至被淘汰。最通常的實現(xiàn)方法是輪盤賭(roulette wheel)模型。群體中每一染色體指定餅圖中一個小塊。塊的大小與染色體的適應性分數(shù)成比例，適應性分數(shù)愈高，它在餅圖中對應的小塊所占面積也愈大。為了選取一個染色體，要做的就是旋轉(zhuǎn)這個輪子，直到輪盤停止時，看指針停止在哪一塊上，就選中與它對應的那個染色體。若產(chǎn)生隨機數(shù)為0.81，則6號個體被選中。二、遺傳算法操作算法2交叉(Crossover)交叉算子將被選中的兩個個體的基因鏈按一定概率pc進行交叉，從而生成兩個新的

5、個體，交叉位置pc是隨機的。其中Pc是一個系統(tǒng)參數(shù)。根據(jù)問題的不同，交叉又為了單點交叉算子（Single Point Crossover）、雙點交叉算子（Two Point Crossover）、均勻交叉算子 (Uniform Crossover)，在此我們只討論單點交叉的情況。單點交叉操作的簡單方式是將被選擇出的兩個個體S1和S2作為父母個體，將兩者的部分基因碼值進行交換。假設(shè)如下兩個8位的個體：產(chǎn)生一個在1到7之間的隨機數(shù)c，假如現(xiàn)在產(chǎn)生的是2，將S1和S2的低二位交換，后代P1為1100 1111，P2為10101100。二、遺傳算法操作算法3變異(Mutation)這是在選中的個體中，

6、將新個體的基因鏈的各位按概率pm進行異向轉(zhuǎn)化，最簡單方式是改變串上某個位置數(shù)值。對二進制編碼來說將0與1互換：0變異為1，1變異為0。如下8位二進制編碼：隨機產(chǎn)生一個1至8之間的數(shù)i，假如現(xiàn)在k=6，對從左往右的第6位進行變異操作，將原來的1變?yōu)?，得到如下串：三、構(gòu)造宋詞生成遺傳算法東風/夜/放/花/千/樹。更/吹落，星/如/雨。寶馬/雕車/香/滿/路。鳳簫/聲動，玉壺/光轉(zhuǎn)，一夜/魚龍舞。蛾兒/雪柳/黃金縷，笑語/盈盈/暗香/去。眾里/尋/他/千百/度，驀然/回首，那人/卻/在/燈火/闌珊/處。在詞庫里查找這些詞的頻率，發(fā)現(xiàn)每個詞的頻率都大于2。這說明，除這首詞外其它詞的分詞結(jié)果已經(jīng)完全涵

7、蓋了這首詞中使用的每一個詞語。也就是說，這首詞實質(zhì)上是詞庫中某些詞的一種排列組合形式。因此，我們可以認為詩詞生成問題在本質(zhì)上是一個解空間中尋求最優(yōu)化的問題。青玉案元夕三、構(gòu)造宋詞生成遺傳算法 因此，可以將遺傳算法的優(yōu)化機制引入到宋詞的自動生成模型中。下面將從以下4 個方面給出宋詞生成遺傳算法的構(gòu)造方法：1、求解問題編碼2、初始種群生成3、適應度函數(shù)設(shè)計4、遺傳操作（選擇，交叉，變異）三、構(gòu)造宋詞生成遺傳算法編碼方案文章提出了將“平、仄”與“0、1”編碼相對應的編碼方案。1、編碼方案比如詞牌清平樂平仄分布如下:平仄,仄平平仄.仄平平仄仄,仄平仄.平仄平平,平仄平平.仄平仄,平仄平平.其中表示可平

8、可仄.根據(jù)我們的編碼方案可得如下編碼串:*0*1,*1001.*1*0011,*1*0*1.*0 *100,*0*100.*1*0*1,*0*100.三、構(gòu)造宋詞生成遺傳算法編碼方案在實際操作中，為縮小問題的解空間，我們將分詞模式固定為出現(xiàn)概率最大一種模式：*0/*1，*1/0/01。*1 /*0 /0 /11，*1/*0/*1。*0/*1/00，*0/*1/00。*1/*0/*1，*0/*1/00。相應地，我們對詞庫中的單字詞和雙字詞進行分類：單字詞分為平、仄兩類，對應編碼 0、1；雙字詞分為平平、平仄、仄平、仄仄 4 類，對應編碼 00、01、10、11。染色體基因三、構(gòu)造宋詞生成遺傳算法

9、初始種群生成2、初始種群的生成考慮到宋詞嚴格的格律要求，在求解該優(yōu)化問題過程中，我們始終將格律要求作為必須滿足的約束條件。種群初始化的操作主要有以下步驟:1）根據(jù)給定的主題詞，從詞庫中挑選和主題詞相關(guān)度大于k1 的詞，構(gòu)成一級候選詞空間。再從一級候選詞中挑選相關(guān)度高的一部分詞，組成二級候選詞空間。以此遞歸至候選詞空間的詞數(shù)量大于 n1。2）從候選詞空間隨機選擇滿足押韻要求的詞，首先填充每個需要押韻的位置，然后在滿足平仄要求的基礎(chǔ)上，隨機選詞填充剩余的位置。同此操作，生成含 N 個個體的的初始種群。三、構(gòu)造宋詞生成遺傳算法適應度函數(shù)3、適應度函數(shù)的構(gòu)造 針對宋詞生成問題，個體適應性的評判主要依據(jù)

10、以下4個指標：（1）句法合法性（2）主題相關(guān)性（3）詞句搭配的適當性（4）風格和情感統(tǒng)一性三、構(gòu)造宋詞生成遺傳算法（1）句法合法性適應度函數(shù) 詩詞的句子不同于普通自然語言文本的句子。對于普通自然語言文本，句子的有效性通常是由嚴格的句法分析保證的。但由于詩詞語言具有高度凝練的特點，其句法成分往往并不完整。 但通過對大量詩詞語句構(gòu)成的分析，組成句子的有效模式的數(shù)目是有限的，并且呈現(xiàn)出了層次化的結(jié)構(gòu)。分詞模式為“2212”的七字詞句的 DFA判斷圖三、構(gòu)造宋詞生成遺傳算法適應度函數(shù)三、構(gòu)造宋詞生成遺傳算法適應度函數(shù)（2）主題相關(guān)性 所有詞語和主題詞的相關(guān)度之和（3）詞句搭配的適當性 所有兩個連續(xù)詞語

11、的相關(guān)度之和三、構(gòu)造宋詞生成遺傳算法適應度函數(shù)利用互信息計算詞義相關(guān)度首先先構(gòu)造頻率矩陣，我們將所有的待測詞（t 個）都用 在待測文獻（d 句）中的出現(xiàn)頻率表示出來，形成 td 的矩陣。如果 s 為文獻（實驗時為句子），三、構(gòu)造宋詞生成遺傳算法適應度函數(shù)三、構(gòu)造宋詞生成遺傳算法適應度函數(shù)（4）風格和情感的統(tǒng)一性 詞中出現(xiàn)的詞匯的風格和情感得分都趨于一致。三、構(gòu)造宋詞生成遺傳算法適應度函數(shù)適應度函數(shù)F定義為以上4個量歸一化的加權(quán)和，即F=1G+2 R+3P+4S。其中,句法合法性簡寫為G，主題相關(guān)性簡寫為R，詞句搭配的適當性簡寫為P，風格和情感統(tǒng)一性簡寫為S。G,R,P 與S 均已歸一化,1,2

12、,3,4為相應的加權(quán)系數(shù)。三、構(gòu)造宋詞生成遺傳算法遺傳操作4、遺傳操作選擇操作就是從群體中按個體的適應度函數(shù)值選擇出較適應環(huán)境的個體.考慮到宋詞作品的優(yōu)化是一個主觀性較強的問題,目前尚無固定、量化的標準可以借鑒,我們采用精英主義和輪盤賭算法相結(jié)合的模型作為選擇個體的依據(jù).精英主義方法在每一次產(chǎn)生新的一代時,首先把當前最優(yōu)解原封不動地復制到新的一代中,其他選擇步驟不變.這樣任何時刻產(chǎn)生的一個最優(yōu)解都可以存活到遺傳算法結(jié)束.在保留了當前最優(yōu)解后,采用輪盤賭算法完成對剩余個體的選擇,即按照個體適應度值所占全部個體適應值總和的比例作為被選概率來選擇個體.(1)選擇操作:三、構(gòu)造宋詞生成遺傳算法遺傳操作

13、交叉操作是遺傳算法中最重要的操作,是決定算法收斂性能的關(guān)鍵,因此必須慎重選擇交叉算子的策略.通過對宋詞編碼特點的分析與實驗,我們采用包括可以跨句進行的部分映射和啟發(fā)式兩種交叉操作.這里,部分映射交叉可看作二進制串的兩點或多點交叉在換位表達中的擴展,用特別的修復程序來解決簡單的兩點或多點交叉引起的非法性.可以跨句部分映射交叉方法雖然操作簡單快速,且由于交叉點可以在整首宋詞范圍內(nèi)隨機選取,因而產(chǎn)生的子代與父代有較大的相異性,能夠有效避免種群單一化的過早出現(xiàn);但是由于可能破壞句子的句法有效性的問題,因此必須通過啟發(fā)式交叉策略加以補救。(2)交叉算子:三、構(gòu)造宋詞生成遺傳算法遺傳操作變異操作是按一定概率,對個體編碼串上的某個或某些基因位的值進行改變.針對宋詞生成,我們采用啟發(fā)式變異操作.步驟如下:(3)變異算子:步驟1:對于要進行變異的個體,比較每句的適應度,選出適應度值最小的句子。步驟2:若所選句不符合句法規(guī)范,找出與原句句法組合最接近的一種合法組合,利用詞義相關(guān),替換原句某個或某些基因位。步驟3:否則,隨機選取句中一個基因位Wn,獲取其鄰位基因Wn1 的詞性P,查找與Wn 相關(guān)度最大且詞性為P的詞,替換Wn1(若n=1,改對Wn+1 進行操作)。四、系統(tǒng)的實現(xiàn)與結(jié)果分析四、系統(tǒng)的實現(xiàn)與結(jié)