基于遗传算法的针灸处方寻优设计

高 燕, 任玉兰, 周小平, 梁繁荣,

（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.