基于遺傳算法的針灸處方尋優設計

高 燕, 任玉蘭, 周小平, 梁繁榮,

（1.成都信息工程學院,四川成都 610225;2.成都中醫藥大學,四川成都 611137）

0 引言

幾千年來針灸處方數據的積累,為現代醫務工作者提供了豐富的針灸臨床經驗,但是,海量針灸處方數據的存儲及對隱藏于其中的規律分析卻成為針灸學發展的一個重要瓶頸,而計算機科學的發展,尤其是數據倉庫及數據挖掘算法近幾年在各行各業的研究及應用中獲得的巨大成功,使從海量針灸處方數據中尋找有用的規律已成為可能。課題研究的主要內容是基于海量結構化后的針灸處方數據,從中尋找其最優的針灸處方,以指導針灸臨床醫療中穴位及療法療程的選擇,為醫生提供臨床輔助決策功能。

針灸處方涉及的年代為先秦至今。每一朝代都有對于每種疾病的選穴方案,而且朝代的變遷,也使選穴規律有一定的改變,這一改變也符合遺傳理論的思想,因此,對于針灸處方可以采用遺傳算法從古今中外的針灸處方數據中獲得最優方案。

1 算法設計思路

遺傳算法擬解決的問題重點有以下兩點:基因編碼及適應度函數。

1.1 基因編碼

由于本次處方尋優涉及的內容有4點:主穴（5個）、配穴（3個）、療法及療程,因此,可以確定該基因由以上10個基因片段組成,采用二進制編碼,具體編碼如下[1-3]:

基因1～5:主穴 目前腧穴表中有361個穴位和989個經外奇穴,共1350個穴位,可以對1350個穴位進行二進制編碼,如果按編號編碼,則可以用11位表示,要注意的是,11位能表示的數字為0～2047,因此要規定編碼不能超過1350。

基因6～8:配穴 同主穴編碼原理。

基因9:療法 取值為“刺灸方法表”中刺灸方法字段下的值,即中醫針灸中所采用諸如“十二刺”、“人中針”、“日光灸”等方法。取值種類為369種,同樣,也是369種的任意組合。因此編碼也可以采用同主穴編碼一樣的原理。即采用ID號進行編碼,可用9位表示,9位二進制能表示的數字范圍為0～511,因此,必須限制編碼時超過369的二進制組合。

基因10:療程 分析療程的文字描述,可知關鍵有4個數字,即每幾天1次這個幾,多少次1個療程的多少,治療多少個療程的多少,療程間隔時間中的這個時間,因此可以組合這4個數字,第1個數字可用3位二進制,第2個數字用4位二進制,第3個數字用3位二進制,第4個數字也用3位二進制。

各基因的二進制碼組合在一起就形成了代表個體遺傳特性的基因碼鏈。采用隨機數生成,可以生成若干個此形式的初始解的祖先群體。遺傳算法就從這些原始祖先群體開始。

關于穴位基因的限定:（1）因為1～8個基因都是基于穴位,因此必須限制1～8個基因不能重復;

（2）為了限制穴位基因的無效選擇,即對于某些病縱觀其歷代處方數據會得出一個總基因的子集,因此為了加速穴位基因的正確選擇,可以從穴位子集中獲得,即1～8的基因的初始化及今后的迭代均需在特定年代的所有穴位中選擇,而不需從腧穴表的1350個腧穴中去獲得。

1.2 適應度函數的確定

每一朝代均有自己特定的處方選擇方案,而這些方案也會在下一個年代遺傳下去然后再進化形成新的處方規律,表1為針灸處方治療方案推薦級別,推薦級別由針灸界專家給定,它將成為后續針灸處方集合選定的標準。

表1 針灸處方治療方案推薦等級

可以看出,每一個最優處方其實是在各處方集中獲得一個均衡的最大值,因此,適應度函數可以分兩步獲得,第一步先獲得每一個朝代或其余分類方式獲得的每一處方集合的處方規律,即適應度函數,然后再通過推薦級別組合適應度函數,最終得到總的適應度函數值。由于處方是一群定性文字集合,因此,可以通過聚類算法找到每一個朝代的核心群,這個核心群也許會有N個（N＞1）。當每次迭代產生新的處方就和推薦級別中所給定的特定核心群中所有處方進行對比分析,從而得到一個適應度函數值,然后再加權組合該適應度函數值,最終得到總的適應度函數值,通過該值找到這代的所有處方中最優的處方,然后進行再次迭代遺傳。下面給出特定年代的適應度函數計算公式[4]

式（1）表示新一代種群中某個體和核心群中每一處方進行距離比較,然后求距離的平均值。表示新一代物種群中某個體主穴與核心群中第i個處方的主穴相同的概率。、x同理,需要注意的是,x取值只能3i3i為0或1。因此,以上的適應度函數也可以看作是距離公式。

總的適應度函數計算公式[5]

M代表推薦級別中所涉及到的年代分類個數,fM代表該分類在總適應度函數中的權重,比如對推薦級別中涉及到經典著作記載、歷代醫家長期沿用、現代高質量隨機對照試驗的驗證等種類,因此在這里 fM就分別代表這些種類的權重,而總的適應度函數也會在相應的推薦級別涉及的種類上進行加權運算。在這里要注意的是,適應度函數取值越小,表明適應度越高,取值越高表明適應度越低,這主要是因為適應度函數是基于距離公式得來,所以具有距離公式的特點。

1.3 核心群的定義

核心群主要采用聚類算法獲得,聚類算法會根據處方群中各處方的相似性找到哪些處方會成為一個群,而哪些處方又會成為一個群,最后對形成的子群（聚類分析中稱為簇）進行個數的確定,當簇中個體數目占總個體的百分比大于某個數時,或同時比較簇中個體在所有簇中個體的排名和百分比,滿足某種條件的就稱其為核心群,因此核心群的個數可以不止一個。

聚類分析中數據的初始化,為了比較特定年代數據處方集合的相似度,必須先對處方數據進行重建然后再進行聚類分析,在此采用聚類分析中的相異獨矩陣類型[6]。

相異矩陣存儲n個對象間的相異性或相似性,表現形式是一個n*n維的矩陣,其中的每一個元素d（i,j）表示對象i和對象j間的相異度[7]。分析處方數據,由于其屬性均為文字類型,必須將之轉換為數量關系,根據上述對f（x）函數的分析,同理也可以將處方之間的比較轉換為每一字段的概率公式,見公式（3）

聚類方法采用層次聚類中的凝聚方法,即自底向上,開始將每個對象作為單獨的一個類,然后相繼地合并相近的對象或組,將較小的數據對象子集合依據相似程度進行合并,這些小的數據對象子集合逐漸合并成較大的數據對象子集合,直到達到一個終止條件,從而構成一個類的層次。

Ci和Cj是兩個聚類,其最短距離定義公式為

其中,pi∈Ci,pj∈Cj,dpi,pj表示樣本pi和pj間的距離,D（Ci,Cj）表示Ci類中的所有樣本與Cj類中的所有樣本之間的最短距離。

2 設計思路的實現

實驗采用的開發平臺是Visual Studio 2005,開發語言為C#,樣本數據存儲在Access2003數據庫中。表2為一面癱病人針灸處方尋優后的結果,根據其需要,只顯示3個適應度函數值較高的推薦治療方案。

表2中的推薦治療方案來自于表1針灸處方治療方案推薦等級中所選定的等級,比如當選定I級Ia等級時,將會根據:高質量古籍載錄證據+高質量隨機對照試驗證據和高質量專家經驗證據+高質量隨機對照試驗證據分別準備相應的處方集合,然后對處方集合分別求集合適應度,即上文所述的特定年代的適應度,最后再對4個集合進行總的適應度計算。于是就得到表2的綜合推薦治療方案。

表2中的推薦指數即為適應度函數值。如果不采用尋優方式,比較某一處方是否更優則完全憑個人經驗,由于個人片面的知識及經驗,就會形成仁者見仁,智者見智的景象,而根據遺傳算法去尋找最優處方,客觀性較強,同時根據上述算法的描述,可以看出每一處方中均包含了特定年代的優秀思想,以至于最后所得結果是各個年代的最優基因。從臨床實踐中看,眾多醫生都認可尋優后推薦的處方方案,即在眾多醫生間尋找到一個平衡點。

表2 尋優后的推薦方案

3 結束語

從實驗運行速度看,優化時間過久,三百條左右的處方,基本要運行2分鐘左右,因此下一步工作是提高編碼和解碼,可引入遺傳編程或基因表達式編程;實驗處方格式僅僅是針對主穴、配穴、療法及療程4項內容,其實對于原始處方信息還包含很多內容,因此下一步研究可擴大處方涉及的信息量,盡可能從更深、更廣角度進行算法設計研究。

致謝:感謝成都信息工程學院科研基金（CRF201040）對本文的資助

[1] 劉挺,秦兵,張宇,等.信息檢索系統導論[M].北京:機械工業出版社,2008:20-50.

[2] 黃建春,鄒漢斌,李曉峰.基于文本聚類的映射聚類算法研究[J].計算機工程與設計,2007,（6）:1264-1266.

[3] 楊麗麗,袁道華,李曉娟.一種新型IP網絡拓撲分級構造算法及實現[J].計算機工程與設計,2003,（6）:93-96.

[4] M.Halkidi,Y.Batistakis,M.Vazirgiannis Clustering algorithms and validity measures[J].IEEE,2001:3-22.

[5] 彭京,唐常杰,曾濤.基于神經網絡和屬性距離矩陣的中藥方劑功效歸約算法[J].四川大學學報（工程科學版）,2006,38（1）:92-97.

[6] Jiawei Han and Micheline Kamber.Data Mining:Concepts and Techniques[M].Morgan Kaufmann Publishers,Inc.2001:223-259.

[7] 張云濤,龔玲.數據挖掘原理與技術[M].北京:電子工業出版社,2004:41-45.

[8] 湯效琴,戴汝源.數據挖掘中聚類分析的技術方法[J].微計算機信息,2003,（1）:3-4.