一种基于遗传算法改进的蚁群聚类算法

各种聚类算法及改进算法的研究

论文关键词：数据挖掘；聚类算法；聚类分析论文摘要：该文详细阐述了数据挖掘领域的常用聚类算法及改进算法，并比较分析了其优缺点，提出了数据挖掘对聚类的典型要求，指出各自的特点，以便于人们更快、更容易地选择一种聚类算法解决特定问题和对聚类算法作进一步的研究。并给出了相应的算法评价标准、改进建议和聚类分析研究的热点、难点。上述工作将为聚类分析和数据挖掘等研究提供有益的参考。 1 引言随着经济社会和科学技术的高速发展，各行各业积累的数据量急剧增长，如何从海量的数据中提取有用的信息成为当务之急。聚类是将数据划分成群组的过程，即把数据对象分成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。它对未知数据的划分和分析起着非常有效的作用。通过聚类，能够识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相互关系等。为了找到效率高、通用性强的聚类方法人们从不同角度提出了许多种聚类算法，一般可分为基于层次的，基于划分的，基于密度的，基于网格的和基于模型的五大类。 2 数据挖掘对聚类算法的要求(1)可兼容性：要求聚类算法能够适应并处理属性不同类型的数据。(2)可伸缩性：要求聚类算法对大型数据集和小数据集都适用。(3)对用户专业知识要求最小化。(4)对数据类别簇的包容性：即聚类算法不仅能在用基本几何形式表达的数据上运行得很好，还要在以其他更高维度形式表现的数据上同样也能实现。(5)能有效识别并处理数据库的大量数据中普遍包含的异常值，空缺值或错误的不符合现实的数据。(6)聚类结果既要满足特定约束条件，又要具有良好聚类特性，且不丢失数据的真实信息。(7)可读性和可视性：能利用各种属性如颜色等以直观形式向用户显示数据挖掘的结果。(8)处理噪声数据的能力。(9)算法能否与输入顺序无关。 3 各种聚类算法介绍随着人们对数据挖掘的深入研究和了解，各种聚类算法的改进算法也相继提出，很多新算法在前人提出的算法中做了某些方面的提高和改进，且很多算法是有针对性地为特定的领域而设计。某些算法可能对某类数据在可行性、效率、精度或简单性上具有一定的优越性，但对其它类型的数据或在其他领域应用中则不一定还有优势。所以，我们必须清楚地了解各种算法的优缺点和应用范围，根据实际问题选择合适的算法。 3.1 基于层次的聚类算法基于层次的聚类算法对给定数据对象进行层次上的分解，可分为凝聚算法和分裂算法。 (1)自底向上的凝聚聚类方法。这种策略是以数据对象作为原子类，然后将这些原子类进行聚合。逐步聚合成越来越大的类，直到满足终止条件。凝聚算法的过程为：在初始时，每一个成员都组成一个单独的簇，在以后的迭代过程中，再把那些相互邻近的簇合并成一个簇，直到所有的成员组成一个簇为止。其时间和空间复杂性均为O(n2)。通过凝聚式的方法将两簇合并后，无法再将其分离到之前的状态。在凝聚聚类时，选择合适的类的个数和画出原始数据的图像很重要。 [!--empirenews.page--] (2)自顶向下分裂聚类方法。与凝聚法相反，该法先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件。其主要思想是将那些成员之间不是非常紧密的簇进行分裂。跟凝聚式方法的方向相反，从一个簇出发，一步一步细化。它的优点在于研究者可以把注意力集中在数据的结构上面。一般情况下不使用分裂型方法，因为在较高的层很难进行正确的拆分。 3.2 基于密度的聚类算法很多算法都使用距离来描述数据之间的相似性，但对于非凸数据集，只用距离来描述是不够的。此时可用密度来取代距离描述相似性，即基于密度的聚类算法。它不是基于各种各样的距离，所以能克服基于距离的算法只能发现“类圆形”的聚类的缺点。其指导思想是：只要一个区域中的点的密度（对象或数据点的数目）大过某个阈值，就把它加到与之相近的聚类中去。该法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可发现任意形状的簇，并可用来过滤“噪声”数据。常见算法有DBSCAN，DENCLUE 等。[1][2][3]下一页 3.3 基于划分的聚类算法给定一个N个对象的元组或数据库，根据给定要创建的划分的数目k，将数据划分为k个组，每个组表示一个簇类（<=N）时满足如下两点：(1)每个组至少包含一个对象；(2)每个对

一种改进的遗传算法

第17卷第3期 辽阳石油化工高等专科学校学报Vol.17No.3 2001年9月 Journal of Liaoyang Petrochemical College September2001 一种改进的遗传算法 王亮申　王文友　吴克勤　江远鹏　谢　荣 (辽阳石油化工高等专科学校机械系,辽阳111003) 摘　要　给出的适应值标定公式能够解决对个体选择压力和标定后适应值非负问题. 对多极值函数的遗传算法所提出的改进措施可以增加群体的多样性,避免算法“早熟”,过早 陷入局部最优. 关键词　遗传算法;适应值标定;早熟 中图分类号　O224 由美国密执安(Michrgan)大学的Holland教授等人在1975年创立的遗传算法(G enetic Algo2 rithms简称G A),是建立在达尔文(Darwin)的生物进化论和孟德尔(Mendel)的遗传学说基础上的算法.经过后人的不断改进使得遗传算法更加完善.由于遗传算法求解复杂优化问题的巨大潜力及其在各个领域(如布局优化问题、交通问题、图像处理与识别、结构设计、电力系统设计、可靠性计算等)的成功应用,这种算法越来越被人们所接受. 遗传算法是一种基于生物进化原理构想出来的搜索最优解的仿生算法,它模拟基因重组与进化的自然过程,把待解决问题的参数编成二进制码或十进制码(也可编成其它进制码)即基因(gene),若干基因组成一个染色体(个体),许多染色体进行类似于自然选择、配对交叉和变异运算,经过多次重复迭代(即世代遗传)直至得到最后的优化结果.习惯上,适应度值越大,表示解的质量越好.对于求解最小值问题可通过变换转为求解最大值问题.遗传算法是一种高度并行、随机、自适应搜索算法. 尽管遗传算法有许多优点,也有许多专家学者对遗传算法进行不断研究,但目前存在的问题依然很多.如(1)适应值标定方式多种多样,没有一个简洁、通用方法,不利于对遗传算法的使用; (2)遗传算法的“早熟”现象即很快收敛到局部最 收稿日期:2001-06-27优解而不是全局最优解是迄今为止最难处理的关键问题;(3)快要接近最优解时在最优解附近左右摆动,收敛较慢. 1　改进方法 1.1　适应值标定 初始种群中可能存在特殊个体的适应值超常(如很大).为了防止其统治整个群体并误导群体的发展方向而使算法收敛于局部最优解需限制其繁殖;在计算临近结束,遗传算法逐渐收敛,由于群体中个体适应值比较接近,继续优化选择困难,造成在最优解附近左右摇摆,此时应将个体适应值适当加以放大,以提高选择能力,这就是适应值的标定.文献[1]提出的标定方法有两个计算公式,不利于使用;文献[2]的标定方式虽然限制了适应值范围但将最大最小值颠倒.此外象幂律标定、对数标定等亦有应用.本文针对适应值标定问题提出以下计算公式. f’= 1 f max-f min+δ (f+|f min|) f′—为标定后的适应值;f—为原适应值;δ—为在(0,1)内的一个正实数,目的是防止分母为零和增加遗传算法的随机性;|f min|—是为了保证定标后的适应值不出现负值。

蚁群聚类算法综述

计算机工程与应用2006.16 引言 聚类分析是数据挖掘领域中的一个重要分支[1],是人们认 和探索事物之间内在联系的有效手段,它既可以用作独立的 据挖掘工具,来发现数据库中数据分布的一些深入信息,也 以作为其他数据挖掘算法的预处理步骤。所谓聚类(clus- ring)就是将数据对象分组成为多个类或簇(cluster),在同一 簇中的对象之间具有较高的相似度,而不同簇中的对象差别大。传统的聚类算法主要分为四类[2,3]:划分方法,层次方法, 于密度方法和基于网格方法。 受生物进化机理的启发,科学家提出许多用以解决复杂优 问题的新方法,如遗传算法、进化策略等。1991年意大利学A.Dorigo等提出蚁群算法,它是一种新型的优化方法[4]。该算不依赖于具体问题的数学描述,具有全局优化能力。随后他 其他学者[5～7]提出一系列有关蚁群的算法并应用于复杂的组优化问题的求解中,如旅行商问题(TSP)、调度问题等,取得 著的成效。后来其他科学家根据自然界真实蚂蚁群堆积尸体分工行为,提出基于蚂蚁的聚类算法[8,9],利用简单的智能体 仿蚂蚁在给定的环境中随意移动。这些算法的基本原理简单懂[10],已经应用到电路设计、文本挖掘等领域。本文详细地讨现有蚁群聚类算法的基本原理与性能,在归纳总结的基础上 出需要完善的地方,以推动蚁群聚类算法在更广阔的领域内 到应用。 2聚类概念及蚁群聚类算法 一个簇是一组数据对象的集合,在同一个簇中的对象彼此 类似,而不同簇中的对象彼此相异。将一组物理或抽象对象分组为类似对象组成的多个簇的过程被称为聚类。它根据数据的内在特性将数据对象划分到不同组(或簇)中。聚类的质量是基于对象相异度来评估的,相异度是根据描述对象的属性值来计算的,距离是经常采用的度量方式。聚类可用数学形式化描述为:设给定数据集X={x 1 ,x 2 ,…,x n },!i∈{1,2,…,n},x i ={x i1 ,x i2 , …,x

遗传算法基本原理及改进

遗传算法基本原理及改进 编码方法： 1、二进制编码方法 2、格雷码编码方法 3、浮点数编码方法。个体长度等于决策变量长度 4、多参数级联编码。一般常见的优化问题中往往含有多个决策变量，对这种还有多个变量的个体进行编码的方法就成为多参数编码方法。多参数编码的一种最常用和最基本的方法是：将各个参数分别以某种方式进行编码，然后再将它们的编码按照一定顺序连接在一起就组成了标识全部参数的个体编码。 5、多参数交叉编码：思想是将各个参数中起主要作用的码位集中在一起，这样他们就不易于被遗传算子破坏掉。在进行多参数交叉编码时，可先对各个参数进行编码；然后去各个参数编码串的最高位连接在一起，以他们作为个体编码串前N位编码，同上依次排列之。

改进遗传算法的方法： （1）改进遗传算法的组成成分或实用技术，如选用优化控制参数、适合问题的编码技术等。 （2）采用动态自适应技术，在进化过程中调整算法控制参数和编码精度。 （3）采用混合遗传算法 （4）采用并行算法 （5）采用非标准的遗传操作算子 改进的遗传算法： （1）分层遗传算法 （2）CHC算法 （3）messy遗传算法； （4）自实用遗传算法（Adaptive Genetic Algorithm） （5）基于小生境技术的遗传算法（Niched Genetic Algorithm，简称NGA）。 （6）并行遗传算法（Parallel Genetic Algorithm） （7）混合遗传算法：遗传算法与最速下降法相结合的混合遗传算法；遗传算法与模拟退火算法相结合的混合遗传算法。 解决标准遗传算法早熟收敛和后期搜索迟钝的方案 （1）变异和交叉算子的改进和协调采用 将进化过程划分为渐进和突变两个不同阶段 采用动态变异 运用正交设计或均匀设计方法设计新的交叉和变异算子 （2）采用局部搜索算法解决局部搜索能力差的问题 （3）采用有条件的替代父代的方法，解决单一的群体更新方式难以兼顾多样性和收敛性的问题 （4）收敛速度慢的解决方法； 产生好的初始群体 利用小生境技术 使用移民技术 采用自适应算子 采用与局部搜索算法相结合的混合遗传算法 对算法的参数编码采用动态模糊控制 进行未成熟收敛判断

比较专家系统、模糊方法、遗传算法、神经网络、蚁群算法的特点及其适合解决的实际问题

比较专家系统、模糊方法、遗传算法、神经网络、蚁群算法的特点及其适合解决的实际问题 一、专家系统(Expert System) 1，什么是专家系统？ 在日常生活中大家所认知的“专家”一般都拥有某一特定领域的大量专业知识，以及丰富的实际经验。在解决问题时，专家们通常拥有一套独特的思维方式，能较圆满地解决一类困难问题，或向用户提出一些建设性的建议等。 专家系统一般定义为一个具有智能特点的计算机程序。 它的智能化主要表现为能够在特定的领域内模仿人类专家思维来求解复杂问题。因此，专家系统必须包含领域专家的大量知识，拥有类似人类专家思维的推理能力，并能用这些知识来解决实际问题。 专家系统的基本结构如图1所示，其中箭头方向为数据流动的方向。 图1 专家系统的基本组成 专家系统通常由知识库和推理机两个主要组成要素。 知识库存放着作为专家经验的判断性知识,例如表达建议、 推断、 命令、 策略的产生式规则等, 用于某种结论的推理、 问题的求解,以及对于推理、 求解知识的各种控制知识。 知识库中还包括另一类叙述性知识, 也称作数据,用于说明问题的状态,有关的事实和概念,当前的条件以及常识等。

专家系统的问题求解过程是通过知识库中的知识来模拟专家的思维方式的，因此，知识库是专家系统质量是否优越的关键所在，即知识库中知识的质量和数量决定着专家系统的质量水平。一般来说，专家系统中的知识库与专家系统程序是相互独立的，用户可以通过改变、完善知识库中的知识内容来提高专家系统的性能。 推理机实际上是一个运用知识库中提供的两类知识,基于木某种通用的问题求解模型,进行自动推理、 求解问题的计算机软件系统。 它包括一个解释程序, 用于决定如何使用判断性知识推导新的知识, 还包括一个调度程序, 用于决定判断性知识的使用次序。 推理机的具体构造取决于问题领域的特点,及专家系统中知识表示和组织的方法。 推理机针对当前问题的条件或已知信息，反复匹配知识库中的规则，获得新的结论，以得到问题求解结果。在这里，推理方式可以有正向和反向推理两种。正向推理是从前件匹配到结论，反向推理则先假设一个结论成立，看它的条件有没有得到满足。由此可见，推理机就如同专家解决问题的思维方式，知识库就是通过推理机来实现其价值的。 人机界面是系统与用户进行交流时的界面。通过该界面，用户输入基本信息、回答系统提出的相关问题，并输出推理结果及相关的解释等。 综合数据库专门用于存储推理过程中所需的原始数据、中间结果和最终结论，往往是作为暂时的存储区。解释器能够根据用户的提问，对结论、求解过程做出说明，因而使专家系统更具有人情味。 知识获取是专家系统知识库是否优越的关键，也是专家系统设计的“瓶颈”问题，通过知识获取，可以扩充和修改知识库中的内容，也可以实现自动学习功能。 2，专家系统的特点 在功能上, 专家系统是一种知识信息处理系统, 而不是数值信息计算系统。在结构上, 专家系统的两个主要组成部分 – 知识库和推理机是独立构造、分离组织, 但又相互作用的。在性能上, 专家系统具有启发性, 它能够运用专家的经验知识对不确定的或不精确的问题进行启发式推理, 运用排除多余步骤或减少不必要计算的思维捷径和策略；专家系统具有透明性, 它能够向用户显示为得出某一结论而形成的推理链, 运用有关推理的知识(元知识)检查导出结论的精度、一致性和合理性, 甚至提出一些证据来解释或证明它的推理；专家系统具有灵活性, 它能够通过知识库的扩充和更新提高求解专门问题的水平或适应环境对象的某些变化,通过与系统用户的交互使自身的性能得到评价和监护。 3，专家系统适合解决的实际问题 专家系统是人工智能的一个应用，但由于其重要性及相关应用系统之迅速发展，它已是信息系统的一种特定类型。专家系统一词系由以知识为基础的专家系统(knowledge-based expert system)而来，此种系统应用计算机中储存的人类知识，解决一般需要用到专家才能处理的问题，它能模仿人类专家解决特定问题时的推理过程，因而可供非专家们用来增进问题解决的能力，同时专家们也可把它视为具备专业知识的助理。由于在人类社会中，专家资源确实相当稀少，有了专家系统，则可使此珍贵的专家知识获得普遍的应用。 专家系统技术广泛应用在工程、科学、医药、军事、商业等方面，而且成果相当丰硕，甚至在某些应用领域，还超过人类专家的智能与判断。其功能应用领

智能优化算法(蚁群算法和粒子群算法)

7.1 蚁群优化算法概述 ?7.1.1 起源 ?7.1.2 应用领域 ?7.1.3 研究背景 ?7.1.4 研究现状 ?7.1.5 应用现状

7.1.1 蚁群优化算法起源 20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。

20世纪90年代意大利学者M．Dorigo，V．Maniezzo，A．Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法——蚁群算法，是群智能理论研究领域的一种主要算法。

背景：人工生命 ?“人工生命”是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容。 ?研究如何利用计算技术研究生物现象。?研究如何利用生物技术研究计算问题。

?现在关注的是第二部分的内容，现在已经有很多源于生物现象的计算技巧。例如，人工神经网络是简化的大脑模型，遗传算法是模拟基因进化过程的。 ?现在我们讨论另一种生物系统－社会系统。更确切的是，在由简单个体组成的群落与环境以及个体之间的互动行为，也可称做“群智能”(swarm intelligence)。这些模拟系统利用局部信息从而可能产生不可预测的群体行为（如鱼群和鸟群的运动规律），主要用于计算机视觉和计算机辅助设计。

?在计算智能(computational intelligence)领域有两种基于群智能的算法。蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization)。前者是对蚂蚁群落食物采集过程的模拟，已经成功运用在很多离散优化问题上。

蚁群算法

社会性动物的群集活动往往能产生惊人的自组织行为，如个体行为显得盲目的蚂蚁在组成蚁群后能够发现从蚁巢到食物源的最短路径。生物学家经过仔细研究发现蚂蚁之间通过一种称之为“外激素”的物质进行间接通讯、相互协作来发现最短路径。受其启发，1991年由意大利学者 M. Dorigo，V. Maniezzo 和 A. Colorni 通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群优化。本文阐述了算法的基本原理及特性以及一些优化的蚁群算法，阐述了蚁群算法在数据挖掘中的应用,最后总结了蚁群算法在数据挖掘应用中尚待解决的问题。 关键词: 蚁群算法; 蚁群优化; 数据挖掘 正文文字大小：大中小 1 蚁群算法原理 自1991年由意大利学者 M. Dorigo，V. Maniezzo 和 A. Colorni 通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群优化。该算法的出现引起了学者们的极大关注，蚁群算法的特点： ①其原理是一种正反馈机制或称增强型学习系统; 它通过【最优路径上蚂蚁数量的增加→信息素强度增加→后来蚂蚁选择概率增大→最优路径上蚂蚁数量更大增加】达到最终收敛于最优路径上L ②它是一种通用型随机优化方法, 它吸收了蚂蚁的行为特(内在搜索机制) , 它是使用人工蚂蚁仿真(也称蚂蚁系统) 来求解问题L但人工蚂蚁决不是对实际蚂蚁的一种简单模拟, 它融进了人类的智能L人工蚂蚁有一定的记忆; 人工蚂蚁不完全是瞎的; 人工蚂蚁生活的时空是离散的L ③它是一种分布式的优化方法, 不仅适合目前的串行计算机, 而且适合未来的并行计算机L ④它是一种全局优化的方法, 不仅可用于求解单目标优化问题, 而且可用于求解多目标优化问题L ⑤它是一种启发式算法, 计算复杂性为o (Nc*n2*m) , 其中Nc 是迭代次数, m 是蚂蚁数目, n 是目的节点数目L 蚁群发现最短路径的原理和机制[1] 下面用图 1解释蚁群发现最短路径的原理和机制。 如图 1(a)所示，在蚁巢和食物源之间有两条道路 Nest-A-B-D-Food 和Nest-A-C-D-Food，其长度分别为 4 和 6。单位时间内蚂蚁可移动一个单位长度的距离。开始时所有路径上都没有外激素。 如图 1(b)，在 t=0 时刻，20 只蚂蚁从蚁巢出发移动到 A。由于路径上没有外激素，它们以

蚁群算法聚类分析

蚁群算法聚类分析 摘要： 蚁群算法是今年来才提出的一种基于种群寻优的启发式搜索算法，由意大利学者M.Dorigo等于1991年首先提出。该算法受到自然界中真实蚁群集体行为的启发，利用真实蚁群通过个体间的信息传递、搜索从蚁穴到食物间的最短路径的集体寻优特征，来解决一些离散系统中优化的困难问题。本文就蚁群算法的基本原理、模型特征、聚类分析展开论述。 关键字： 蚁群算法原理模型聚类分析

引言 蚁群算法是最近几年才提出的一种新型的模拟进化算法。蚂蚁是大家司空见惯的一种昆虫，而他们的群体合作的精神令人钦佩。他们的寻食、御敌、筑巢(蚂蚁的筑窝、蜜蜂建巢)之精巧令人惊叹。蚂蚁是自然界中常见的一种生物，人们对蚂蚁的关注大都是因为“蚂蚁搬家，天要下雨”之类的民谚。然而随着近代仿生学的发展，这种似乎微不足道的小东西越来越多地受到学者们的关注。1991年M．DIorigo，V.MaIliezzo等人首先提出了蚁群算法 (Ant Colony Algorithms)，人们开始了对蚁群的研究：相对弱小，功能并不强大的个体是如何完成复杂的工作的(如寻找到食物的最佳路径并返回等)。在此基础上一种很好的优化算法逐渐发展起来。 基本蚁群算法的机制原理 模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式引入的，该算法基于如下基本假设： (1)蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境做出反应，也只对其周围的局部环境产生影响； (2)蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行为实际上是其基因的适应性表现，即蚂蚁是反应型适应性主体； (3)在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为； 由上述假设和分析可见，基本蚁群算法的寻优机制包含两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息量越大，则该路径越容易被选择；时间越长，信息量会越小；在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解，类似于学习自动机的学习机制。 蚁群算法实际上是一类智能多主体系统，其自组织机制使得蚁群算法不需要对所求问题的每一方面都有详尽的认识。自组织本质上是蚁群算法机制在没有外界作用下使系统熵增加的动态过程，体现了从无序到有序的动态演化，其逻辑结构如图1所示。

改进的混沌遗传算法

改进的混沌遗传算法 李辉 (计算机学院2004级研究生 04720746) 摘要：混沌遗传算法(chaos genetic algorithm, CGA)是基于混沌优化的遗传操作,将使子代个体均匀地分布于定义空间,从而可避免早熟,以较大的概率实现全局最优搜索.与传统的遗传算法相比较, CGA 的在线和离线性能都有较大的改进。而遗传算法作为一种智能算法，是解决非线性复杂优化问题的有利工具，但它在搜索过程中易陷入局部最优，收敛速度慢的缺陷又限制了它的寻优效能。混沌遗传算法具有两者的优点，大大提高了优化的效率。 关键词：遗传算法混沌混沌优化 Abstract：Chaos genetic algorithm (CGA)is a genetic operation,which based on chaos optimization,makes the individuals of subgeneration distribute uniformly in the defined space and avoids the premature of subgeneration.To compare the performances of the CGA with those of the traditional GA,The results demonstrated that the CGA’s on-line and off–line performance was all superior to that of the traditional GA.As an inteliengence algorithm,GA is a effectual toos to resolve the problem of the liner-optimization,but the slower convergence and the premature restrict its efficiency.And CGA which has the two strongpoint has promoted is efficiency in optimization. Key words: genetic algorithm chaos chaos optimization 1 引言： 遗传算法(GA)最早由美国Michigan大学的John Holland教授提出，通过模拟自然界中的生命进化过程，有指导地而不是盲目地进行随机搜索，适用于在人工系统中解决复杂特定目标的非线性反演问题。De Jong首先将遗传算法应用于函数优化问题的研究，他的工作表明在求解数学规划时，GA是一种有效的方法。但对于大型复杂系统，尤其是非线性系统优化问题的求解，GA仍有许多缺陷，如无法保证收敛到全局最优解，群体中最好的染色体的丢失，进化过程的过早收敛等。 混沌是自然界中一种较为普遍的现象，具有“随机性”、“遍历性”及“规律性”等特点，在一定范围内能按其自身的“规律”不重复地遍历所有状态的。在搜索空间小时混沌优化方法效果显著，但搜索空间大时几乎无能为力。 混沌遗传算法(CGA)的基本思想是将混沌状态引入到优化变量中，并把混沌运动的遍历范围“放大”到优化变量的取值范围，然后把得到的混沌变量进行编码，进行遗传算子操作。再给混沌变量附加—混沌小扰动，通过一代代地不断进化，最后收敛到一个最适合环境的个体上，求得问题的最优解。 2 传统遗传算法 传统遗传算法： population old_pop,new_pop;/*current and next population*/ int pop_size,generation; float p_cross,p_mutation; /*prob. Of crossover & mutation*/ 1 old_pop=initial random population={ind1,ind2,….indpopsize} 2 while(generation

蚁群聚类算法研究及应用

－5009－ 0引言 俗话说“物以类聚，人以群分”，人们在不知不觉中进行着 聚类活动，它是人们认识和探索事物之间内在联系的有效手段。聚类在数据挖掘中有着重要的地位，它既可以用作独立的数据挖掘工具，来发现数据库中数据分布的一些深入信息，也可以作为其它数据挖掘算法的预处理步骤。因此，聚类算法的研究具有很重要的现实意义。 蚁群算法不依赖于具体问题，具有全局优化能力，因此受 到了广大学者的注意。此后蚁群算法不断被改进并应用于不同领域。在聚类分析方面，Deneubourg等人受蚂蚁堆积尸体和分类它们的幼体启发，最早将蚁群算法用于聚类分析，从此开始了蚁群聚类算法的研究。 本文详细地讨论了现有的蚁群聚类算法的基本原理与性 能，在归纳总结的基础上提出需要完善的地方，以推动蚁群聚类算法的进一步研究及在更广阔的领域内得到应用。 1聚类概念及数学模型 聚类就是把一组个体按照相似性归为若干类或簇，使得 属于同一类或簇的个体之间的差别尽可能的小，而不同类或簇的个体间的差别尽可能大。聚类质量是用对象的相异度来评估，而不同类型变量的相异度的计算方法是不同的，常用的度量方法是区间标度变量中的欧几里得距离。 聚类的数学描述：设样本集={,=1,2,…,}，其中为 维模式向量，其聚类问题就是找到一个划分={ 1 , 2 ,…, }，满足= =1 ，≠，=，,=1,2,…,，≠，且使 得总的类内离散度和= =1 ,最小，其中为的 聚类中心，=1,2,…,；,为样本到其聚类中心的距 离，即,=‖‖。聚类目标函数为各样本到对应 聚类中心的距离总和，聚类中心=1 ，||为的样 本数目。 2蚁群聚类算法分类及应用 由于现实的蚁群运动过程接近于实际的聚类问题，所以 近年来涌现出大量的蚁群聚类算法。这些算法不仅思想、原理不同，而且算法的特性也根据解决问题的不同而不同，如初始参数及待聚类数据的要求、聚类形状等。