自适应遗传算法在聚类分析中的应用

《自适应遗传算法在聚类分析中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、科科I技I论I坛自适应遗传算法在聚类分析中的应用朱永宽谷涓涓：f1、河南职业技术学院，河南郑州4500462、河南省工业设计学校，河南郑州450002)摘要：针对k一均值聚类方法可能受初始选定的聚类中心的影响而过早收敛于次优解的不足，给出了一种基于自适应遗传算法的聚类分析方法fAGAC)。对该自适应遗传算法的构成要素及用其解决聚类问题的一般步骤给出了阐述。用VS2008编写了该算法的程序用来对数字进行聚类取得了较好的聚类结果。关键词：自适应遗传算法；聚类分析；k一均值；适应度函数Abstract：Thetraditionalk-meanclusteringmethodist

2、oosensitivetotheinitialclusteringcenter．Toovercomethisproblemaclusteringanal—ysismethodsbasedonadaptivegeneticalgorithm(AGAC)ispresented．Theconstituentelementsofgeneticalgorithmanditsgeneralstepstosolveproblemshavedemonstrated．Ithasagoodconclusionusingthisclusteringanalysismethodtoclustern

3、umber．Keywords：Adaptivegeneticalgorithm；clusteringanalysis；K—means；fitnessfunction引言1．1标准遗传算法遗传算法(GA)起源于对生物系统所进行1．I．I编码的计算机模拟研究。它是由美国的J．Holland教编码是将问题的解空间转换成遗传算法授1975年首先提出的，其主要特点是直接对结所能处理的搜索空间，以使待解决问题能够被构对象进行操作，不存在求导和函数连续性的遗传算法的算子进行操作。常用的编码方法有限定；具有内在的隐并行性和更好的全局寻优二进制编码、符号编码、浮点数编码。能力；采用概率化的寻

4、优方法，能自动获取和指1．1．2适应度函数导优化的搜索空间，自适应地调整搜索方向，不在遗传算法中，模拟自然选择的过程主要需要确定的规则。GA的这些性质，已被人们广是通过评估函数和适应度函数来实现的。前者泛地应用于组合优化、机器学习、信号处理、自计算每个个体优劣的绝对值，后者计算每个个适应控制和人工生命等领域。然而标准的遗传体相对于整个群体的相对适应度。个体适应度算法尚存在如下不足：早熟收敛问题；局部搜索的大小决定了它继续繁衍还是消亡。能力不足；遗传算子具有的无方向性会减慢遗1．13遗传算子传算法的进化速度。针对这一问题本文引入一a．选择算子种自适应遗传算法(AGA)t‘嘘用

5、于聚类分析。选择算子建立在对个体适应度进行评价1uQJ￡、●u聚类分析是一种新兴的多元统计方法，是的基础上，目的是避免基因损失，提高全局收当代分类学与多元分析的结合。聚类分析是将敛性和计算效率。常用选择算子的操作方法有03O54分类对象置于一个多维空间中，按照它们空间赌轮选择法、排序选择法、最优保存策略。92866关系的亲疏程度进行分类。通俗地讲，聚类分析b．交叉算子oo口JUo0oo就是根据事物彼此不同的属性进行辨认，将具遗传算法交叉算子模仿自然界有性繁殖64409图1自适应遗传算法流程图有相似属性的事物聚为一类，使得同一类的事的基因重组过程，以使优良基因遗传给下一代c’

6、Dq厶c、nu物具有高度的相似性。聚类分析正在蓬勃发展，个体。通常使用的交叉算子有一点交叉、两点47q厶U有贡献的研究领域包括数据挖掘，统计学，机器交叉、多点交叉和一致交叉等。学习，空问数据库技术，生物学，以及市场营销c．变异算子k¨仁等。变异操作模拟自然界生物进化中，染色体．。目前已有很多种聚类算法，如k一均值算上某位基因发生的突变现象，从而改变染色体8．法是一种简单常用的方法，该方法首先选定某的结构和物理形状。变异是遗传算法中保持物种距离度量作为模式问相似性度量，然后确定种多样性的一个重要途径。它以一定的概率选4某个评价聚类划分结果质量的准则函数，在给择个体染色体中的某

7、一位或几位，随机地改变出初始聚类中心点后，用迭代法找出使准则函该位基因值，以达到变异的目的。图2聚类前的数字4图3聚类后的数字数取极值的最好划分结果。该方法的缺点是可1．1．4控制参数的选择率按下式进行调节：能受初始选定的聚类中心的影响而过早收敛于在遗传算法的运行过程中，存在着对其性次优解。最大似然估计法首先假设待分类数据能产生重大影响的一组参数，主要有染色体位l唧册???唧慨唧r㈣符合某种先验概率分布，然后根据计算出的后串长度L，群体规模n，交叉概率P和变异概率验概率进行数据的分类。基于图论的方法首先P。其中位串