一种集成遗传算法与模糊推理的粗糙集数据分析算法

收稿日期:2004205230.作者简介:许松荣(19792),男,硕士研究生;厦门,厦门大学计算机与信息工程学院(361005).E 2mail:xsr abc@基于遗传算法的模糊聚类方法许松荣(厦门大学计算机与信息工程学院,福建厦门361005)摘要:针对模糊c 2均值算法容易收敛于局部极小点的缺陷,将遗传算法应用于模糊c 2均值算法的优化计算中.算法采用实数编码,提高了试验精度.实验证明基于遗传算法的模糊聚类方法能够在一定程度上克服初值的影响,跳出局部极小点,在大样本的聚类方面有较大的优势.关 键 词:聚类;模糊c 2均值算法;遗传算法中图分类号:TP391 文献标识码:A 文章编号:167124512(2004)S120217203The fuzzy clustering method based on genetic arithmeticXu SongrongAbstr act:This paper applies genetic arithmetic to optimization of the fuzzy c 2mean arithmetic since the fuzzy c 2mean arithmetic has the limitation of converging to the local infinitesimal point.The arithmetic adopts the real code and thus increases the precision of the experiments.The experiments prove that the fuzzy c 2means arithmetic based on genetic arithmetic can overcome the influence of initial values and possess the predominance in the clustering of huge samples.Key words:clustering;fuzzy c 2mean arithmetic;genetic arithmeticXu Songr ong Postgraduate;Computer &Information Engineering College,Xiamen U niversity.Fujian,Xiamen 361005,China. 聚类[1]是根据数据的不同特征,将其划分为不同的数据类.聚类的目的是使得属于同一类别的个体之间的距离尽可能地小,而不同类别上的个体间的距离尽可能地大.聚类方法包括统计方法、机器学习方法、神经网络方法等.模糊聚类方法具有简便易行,聚类效果较好的优点,在实际应用中获得广泛的运用.但是普通的模糊聚类易于陷入局部极小点而不能搜索到全局的聚类中心.而遗传算法作为一种新型的进化优化算法,可以概率地在状态空间搜索最佳点,特别适合于非线性多峰值的函数优化问题.1 普通的模糊聚类方法模糊聚类是将样本空间X ={x 1,x 2,,,x n }的样本点分成c 类,任意一个样本点x i I X 几乎不可能被严格地划分给某一类,定义样本点x i 属于第j (1[j [c)类的程度w ij (0[w i j [1).样本空间X 的模糊聚类用模糊矩阵W =(w ij )描述,元素w ij 是矩阵W 的第i 行第j 列元素,代表第i 个样本点隶属于第j 类的隶属度.W 具有以下性质:w ij I [0,1];(1)E c j=1w ij =1;(2)0<E n i =1w ij <n.(3)为了计算各个样本点相对于聚类中心的隶属度,一般采用FCM 算法.定义目标函数:J m (W ,Z )=E ni =1E cj =1w ij d 2ij (x i ,z j ),Z =(z 1,z 2,,,z c ),其中z j 表示第j 类的聚类中心,d 2ij (x i ,z j )=+x i -z j +是样本点x i 到聚类中心z j 的欧氏距离.聚类即是求目标函数在式(1)~(3)约束下的第32卷增刊 华 中 科 技 大 学 学 报(自然科学版) Vol.32 Sup.2004年 10月J.Huazhong Univ.of Sci.&Tech.(Nature Science Edition)Oct.2004最小值.FCM 算法通过对目标函数的迭代优化来取得对样本集的模糊分类.具体算法参见文献[2].该算法对初值敏感,很大程度上依赖初始聚类中心的选择,当初始聚类中心严重偏离全局最优聚类中心时,用FCM 很可能陷入局部极小值.当聚类数目较大时,该缺点更为明显.2 基于遗传算法的模糊聚类方法遗传算法[3]是基于/优胜劣汰、适者生存0的一种高度并行、随机和自适应的全局优化算法.它从某一随机种群出发,按照一定的操作规则,根据每一个个体的适应度,存优去劣,引导搜索过程向最优解逼近.遗传算法不要求连续、可微等条件,具有较强的鲁棒性.对于所定义的目标函数,聚类问题即是求满足式(1)~(3)的W 和Z ,使得目标函数值最小,这实际上是一个优化的问题.用遗传算法求解,主要考虑以下因素[4]:染色体编码、个体适应度评价、遗传算子(选择算子、交叉算子、变异算子)以及遗传参数设置等.2.1 染色体编码方法设n 个样本被分成c 类:Z 1,Z 2,,,Z c ,模糊分类矩阵W =(w ij )共有n @c 个元素.这里采用实数编码方案[5,6].一个染色体可以被编码成为:[z 1z 2,z c w 11w 12,w 1c w 21w 22,w 2c ,w n 1w n 2,w nc ].2.2 始化群体的生成当聚类个数c 给定时,随机选取聚类中心并随机生成w ij 组成模糊矩阵W .2.3 适应度函数用适应度函数模拟自然选择,评价染色体的相对优劣程度,由此决定各种遗传操作.个体以J m (W ,Z )为目标函数值,J m (W ,Z )越小,个体的适应度就越高.取f i =1/J m (W ,Z )作为第i个个体的适应度,总的适应度为F =E cj =1f i ,平均适应度为 f =f i /F.2.4 选择选择操作建立在对个体的适应度评价的基础上,用来将父代中的优秀个体保存到下一代.常用的选择操作有轮赌盘选择、余数选择法、保留最佳个体等.这里采用期望值选择法.a .计算群体中每个个体在下一代生存的期望数目N i =f i / f .b .若某个个体被选中并要参与配对和交叉,则它在下一代的期望数目减去0.5;若不参与配对和交叉,则该个体的生存期望数目减去1.c .在上面两种情况中,若一个个体的期望值小于0,则该个体不参与选择.2.5 交叉交叉用于组合新个体,使子代继承父代优秀基因.a .对每个个体产生[0,1]的随机数r ,若r <p c ,则该个体参加交叉操作,选出交叉操作的一组染色体后进行随机配对.b .对每一对染色体X 、Y,产生(0,1)之间的随机数e.c .做如下交叉运算:X z e X +(1-e )Y,Y z e Y +(1-e)X.2.6 变异变异用来保持种群的多样性.这里变异操作分为两个部分.首先对染色体的前c 位基因进行变异操作.a .产生随机数r ,若p m <r ,则进行变异操作.b .产生随机正整数h (1[h [c/2).c .产生h 个随机正整数t 1,t 2,,,t h ,对第t i 位基因产生随机数,代替原来的基因.d .若前c 位发生重复,则对重复的基因再进行变异.然后对染色体第c 位后的基因(记做Z )进行变异操作.a .产生(0,1)之间的随机数A .b .产生nc 维随机向量V =[v 1v 2,v nc ],v i I [0,1].c .做变异Z z Z +A V.2.7 合法性检查遗传操作可能产生非法的个体,要对产生的非法个体进行修正.修正的规则如下:a .如果w ij >1或w ij <0,则w ij =0.5.b .如果E cj =1w ij >1,且所有w ij 都相同,则令w ij =1/c,j =1,2,,,c;否则,令w ik =max (w i 1,w i 2,,,w i c ),于是w ik =1-E c j =1,j X kw ij ,j =1,2,,,c.c .如果E cj =1w ij <1,且所有w ij 都相同,则令w ij =1/c,j =1,2,,,c;否则,令w ik =min (w i 1,w i 2,,,w ic ,于是w ik =1-E cj =1,j X kw ij ,218 华 中 科 技 大 学 学 报(自然科学版) 第32卷j =1,2,,,c.d .如果E ni =1w ij \n,则w ij z 0.5,i =1,2,,,n.3 实例应用基于遗传算法的模糊c 2均值算法对二维数据集进行聚类.图1(a)为聚类样本.初始种图1 聚类样本和聚类结果群300,最大进化世代数500,p c =0.2,p m =0.05.运算结果为J =2.619.聚类中心为(0.749,0.218)和(0.234,0.238).图1(b)为聚类结果.参考文献[1]张红云,刘向东,段晓东等.数据挖掘中聚类算法比较研究.计算机应用与软件,2003(2):5~6[2]李洪兴,汪培庄.模糊数学.北京:国防工业出版社,1994.[3]褚蕾蕾,陈绥阳,周 梦.计算智能的数学基础.北京:科学出版社,2002.[4]史忠植.知识发现.北京.清华大学出版社,2002.[5]张 维,潘福铮.一种基于遗传算法的模糊聚类.湖北大学学报,2002(2):101~104[6]王 敞,陈增强,袁著祉.基于遗传算法的K 均值分析.计算机科学,2003(2):162~164219增刊 许松荣:基于遗传算法的模糊聚类方法。

遗传模糊算法在短期负荷预测中的应用提出了一种基于模糊逻辑原理的负荷预测方法，使用遗传算法对系统参数进行训练。

在以往的模糊逻辑系统建立过程中,其主要参数（如模糊推理规则和隶属函数等）需要依靠运行人员经验或专家知识来确定，而本文利用遗传算法，通过对样本数据的自学习过程来获取系统参数。

在遗传算法中，将推理规则与隶属函数参数的确定结合在一起，从而确定系统参数的最优组合，由此建立起一个较合理的模糊负荷预测系统。

仿真实验结果表明，该方法能够达到满意的预测精度，具有良好的实用前景。

关键词：短期负荷预测；模糊逻辑系统；遗传算法APPLICATION OF GENETIC-FUZZY ALGORITHM FOR SHORT TERM LOADFORECASTING OF POWER SYSTEMXiong Hao ；Luo Ri-cheng(Electrical Engineering School ,Wuhan University, WuHan 430072, China)ABSTRACT: A novel approach based on fuzzy logic system (FLS) is introduce d to short term load forecasting (STLF).Traditional methods to choose membership functions and fuzzy control rules used to be done by means of integrating experien ce from experts in professional fields and technologic faculty. In this paper, howeve r, a genetic algorithm based approach is developed to optimize parameters of membership functions and fuzzy control rules, simultaneously. And thus, the difficulties i n building forecasting system, to some extent, can be disposed. At last, this new s ystem is tested in an actual environment and produces superior results to traditiona l fuzzy logic short term load forecasting.KEYWORDS: short term load forecasting; fuzzy logic system; genetic algorith m;0 引言短期负荷预测是能量管理系统（EMS）的重要组成部分，也是确定机组组合、地区间功率输送方案和负荷调度方案不可或缺的重要一环。

收稿日期:2004-08-03基金项目:安徽省教育厅自然科学基金资助项目(2003KJ007)作者简介:张 媛(1981 ),女,安徽贵池人,硕士研究生,研究方向为人工智能及其应用。

粗糙集算法及其应用张 媛,张 铃,张燕平(安徽大学人工智能研究所,安徽合肥230039)摘 要:粗糙集理论正被广泛运用于不确定环境下的信息处理中。

当要从大量复杂的数据中发现知识时,属性约简是一个关键问题,因此文中提出了一种特殊的属性约简算法。

它是一种简单化数据的分析法,利用了一种新的用于粗糙集中的属性约简算法,即一种生成对称矩阵的约简算法,并结合了一个具体的例子来说明。

将此算法运用于复杂的实验数据中,对其进行约简,发现效果明显。

由此可看出此算法是相当有效的。

关键词:粗糙集;数据挖掘;决策表;约简;核中图分类号:T P301.6 文献标识码:A 文章编号:1005-3751(2005)04-0017-02Algorithm of Roughsets and Its ApplicationZHANG Yuan,ZHANG Ling,ZHANG Yan ping(Ar tificial Intelligence Institute,Anhui U niv ersity,Hefei 230039,China)Abstract:Roughsets is w idely applied to deal w ith the information under uncertainty.When w e w ant to deal w ith huge amounts of data,reduction of attribute is an important i ssue.S o the paper uses a new algorithm for reduction of attribute.It is an analysis method of simpli fyi ng data.It uses a new algorithm for reducti on of attribute in roughsets,which is an algorithm of building s ymmetry matri x.T he algo rithm to complicated data is applied,then reduct it.The effect is obvious.It shows the validity of the algorithm.Key words:roughsets;data mining;decision mak i ng table;reduction;core0 引 言粗糙集理论是波兰数学家Z.Pa w lak 于1982年提出的一种分析数据的数学理论,该理论在分类意义下定义了模糊性和不确定性的概念[1],是一种处理不确定、不相容数据和不精确问题的新型数学工具,其主要思想就是在保持分类能力不变的前提下,通过知识约简,导出问题的决策和分类规则。

基于粗糙集的模糊决策算法
粗糙集是一种高效的认知模型，可用于建立根据不同情况和状态来进行决策的模糊决策算法。

它通过联合不同的决策准则来构建评估函数，从而实现动态环境下可变的决策。

粗糙集的组成有两部分：粗糙规则和粗糙度度量，其中粗糙规则是以简短的英语语言条件式表示的准则，描述了决策的前提和结果，而粗糙度度量是用来分析粗糙规则的强度的度量。

通过计算粗糙规则的强度，可以给定不同的权重并通过比较权重来影响决策。

基于粗糙集的模糊决策算法首先需要搜集所有可能的粗糙规则，然后对所有粗糙规则计算粗糙度度量，以评估其强度。

接下来，将每一条粗糙规则的权重汇总成整体评估函数，根据该函数的输出做出最终决定。

这种方法不仅有限度考虑了不确定性因素，而且可以及时处理临时决策情况。

基于遗传算法的交通信息模糊融合方法针对智能运输系统及其事件检测子系统研究开发的特点，提出了基于遗传算法的交通信息模糊融合方法。

交通事件是导致交通流质量变化的主要因素，应用遗传算法优化交通事件检测的模糊控制模型参数，对模糊控制器所做出的决策进行动态调整仿真实验结果表明该算法具有更高的检测率和更低的误报率，能提高事件的检测效率。

标签：交通流；模糊控制；遗传算法；信息融合；模式识别1模糊控制和遗传算法人工智能技术可划分为传统人工智能技术（即专家系统）和处理数值计算的新人工智能技术，例如模糊逻辑，遗传算法和人工神经网络等。

1.1模糊控制原理(1)模糊集合的运算。

模糊集合理论的基本思想是把普通集合中的绝对隶属关系灵活化, 使元素对集合的隶属度从原来只能取{0,1}（正确或错误）中的值扩充到［0,1］区间中的任一数值。

模糊集合是由隶属函数来刻画的。

论域中的模糊子集是以隶属函数表征的集合。

即由映射μA∶U→［0，1］u→μA(u)确定论域的一个模糊子集A。

μA称为模糊子集A的隶属函数，隶属度μA(u)说明u隶属于A的程度。

常用的模糊集合运算主要有并、交以及补运算。

(2)模糊化，模糊推理及解模糊化。

模糊控制系统主要包括三个过程:输入的模糊化、模糊推理和输出解模糊化。

①模糊化(fuzzification)。

模糊化是将模糊控制器输入量的确定值转换为相应模糊语言变量值的过程，此相应语言变量值均由对应的隶属度来定义。

本文选择三角形隶属函数，其曲线如图1所示。

图1三角形隶属函数曲线其对应表达式为：μx=1,如果x=B(x-A)/(B-A),如果B>x>A（C-x）/(C-B),如果C>x>B0,如果x≥C或者x≤A（1）其中A、B和C为三角形隶属函数参数。

②模糊推理(fuzzy inference)。

模糊推理是根据事先制定好的一组模糊条件语句构成的模糊控制规则，运用模糊数学理论对模糊控制规则进行计算推理，即根据模糊规则对输入的一系列条件进行综合评估，以得到一个定性的语言表示量。

一种基于遗传算法的粗糙集属性约简算法
曹俊琴;冯家鹏
【期刊名称】《机械工程与自动化》
【年(卷),期】2011(000)005
【摘要】属性约简是粗糙集的核心内容之一,它是一个NP完全问题,这使得粗糙集很难在实际中应用.根据已知决策表系统的二进制可辨别矩阵,利用遗传算法快速寻优的特点,提出了一种基于遗传算法的属性约简算法.实验结果显示,该方法简单、有效.
【总页数】3页(P28-30)
【作者】曹俊琴;冯家鹏
【作者单位】太原科技大学,山西太原 030024;煤炭科学研究总院太原研究院,山西太原 030006
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.一种启发信息遗传算法的粗糙集属性约简算法 [J], 孙宇航;常晋义;谢从华
2.一种基于并行遗传算法的粗糙集属性约简 [J], 吕跃进;刘南星;陈磊
3.一种基于改进遗传算法的粗糙集属性约简算法磁 [J], 李玉龙;张亚光;毕聪聪
4.一种基于遗传算法的粗糙集属性约简算法 [J], 邹瑞芝
5.一种基于量子遗传算法与粗糙集理论的属性约简法 [J], 冯林
因版权原因，仅展示原文概要，查看原文内容请购买。

粗糙集理论及其应用发展一、粗糙集的产生与发展粗糙集(Roughsets)理论是由波兰数学家Z. Pawlak在1982年提出的，该理论是一种刻画不完整性和不确定性的数学工具，能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在的规律。

1992年至今，每年都召开以RS为主题的国际会议，推动了RS理论的拓展和应用。

国际上成立了粗糙集学术研究会，参加的成员来自波兰、美国、加拿大、日本、挪威、俄罗斯、乌克兰和印度等国家。

目前，粗糙集这一新的数学理论已经成为信息科学领域的研究热点之一，它在机器学习、知识获取、决策分析、过程控制等许多领域得到了广泛的应用。

粗糙集首先从新的视角对知识进行了定义。

把知识看作是关于论域的划分，从而认为知识是具有粒度〔granularity〕的。

认为知识的不精确性是由知识粒度太大引起的。

为处理数据〔特别是带噪声、不精确或不完全数据〕分类问题提供了一套严密的数学工具，使得对知识能够进行严密的分析和操作。

又由于数据挖掘的深入研究和一些成功的商业运作，使得粗糙集理论和数据挖掘有了天然的联系，粗糙集在知识上的定义、属性约简、规则提取等理论，使得数据库上的数据挖掘有了深刻理论基础，从而为数据挖掘提供了一种崭新的工具。

粗糙集不仅自己可以独特的挖掘知识，而且可以和其他的数据挖掘算法结合起来，从而产生了学多混合数据挖掘算法，大大开拓了数据挖掘的算法和技术，丰富了数据挖掘的工具。

除了研究，人们也在积极寻找粗糙集在数据挖掘中的应用，如RSES系统，该系统是基于粗糙集理论上研制的数据挖掘系统，里面提供了粗糙集的属性约简算法和规则提取，可以找到最佳约简集和近似约简集，并可以提出规则。

另外，还有，Regina大学开发的KDD-R系统，被广泛用于医疗诊断、电信业等领域。

还有美国Kansas大学开发的LERS(Learningfrom Examples based on RS)系统，在医疗诊断、社区规划、全球气象研究等方面都有应用。