遗传算法聚类设计.pptx

《遗传算法聚类设计.pptx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、主讲：周润景教授单位：电子信息工程学院遗传算法聚类设计目录遗传算法简介遗传算法原理算法实现总结一.遗传算法简介遗传算法是一种模拟自然进化的优化搜索算法。由于它仅依靠适应度函数就可以搜索最优解，不需要有关问题解空间的知识，并且适应度函数不受连续可微等条件的约束，因此在解决多维、高度非线性的复杂优化问题中得到了广泛应用和深入研究。遗传算法在模式识别、神经网络、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。一.遗传算法简介本文给出了一种基于遗传算法的聚类分析方法。采用浮点数编码方式对聚类的中心进行编码，并用特征向量与相应聚类中心的欧氏距离的和来判断聚类划分的质量

2、，通过选择、交叉和变异操作对聚类中心的编码进行优化，得到使聚类划分效果最好的聚类中心。二.遗传算法原理遗传算法(GeneticAlgorithms，GA)是一种新近发展起来的搜索最优解方法。它模拟生命进化机制，遗传算法对于复杂的优化问题无需建模和复杂运算，只要利用遗传算法的三种算子就能得到最优解。经典遗传算法的一次进化过程示意图如图所示。二.遗传算法原理1.遗传算法的基本术语染色体(chromosome)，又称为个体(individual)。编码(coding)。把问题的解表示为位串的过程称为编码，编码后的每个位串就表示一个个体，即问题的一个解。种群(population)。由一定

3、数量的个体组成的群体，也就是问题的一些解的集合。种群中个体的数量称为种群规模。适应度(fitness)。评价群体中个体对环境适应能力的指标，就是解的好坏，由评价函数F计算得到。在遗传算法中，F是求解问题的目标函数，也就是适应度函数。遗传算子(geneticoperator)：(1)选择(selection)(2)交叉(crossover)(3)变异(mutation)二.遗传算法原理2.遗传算法问题求解过程二.遗传算法原理3.遗传算法的基本要素遗传算法包含了如下5个基本要素：问题编码，初始群体的设定，适应度函数的设计，遗传操作设计，控制参数的设定。问题编码(1)二进制编码(2)浮点

4、数编码初始群体的生成最常用的初始方法是无指导的随机初始化。二.遗传算法原理适应度函数(FitnessFunction)的确定在遗传算法中，按与个体适应度成正比的概率来决定当前群体中的每个个体遗传到下一代群体中的机会多少，一般希望适应值越大越好，且要求适应值非负。适应度函数是根据目标函数确定的，针对不同种类的问题，目标函数有正有负，因此必须确定由目标函数值到适应度函数之间的映射规则，以适应上述的要求。适应度函数的设计应满足以下条件：(1)单值、连续、非负、最大化。(2)计算量小。适应度函数设计尽可能简单，以减少计算的复杂性。(3)通用性强。适应度对某类问题，应尽可能通用。二.遗传算法

5、原理遗传操作遗传算法遗传操作主要包括：选择、交叉、变异三个算子。(1)选择算子采用基于适应度的选择原则，适应度越强被选中概率越大，体现优胜劣汰进化机制。几种常用的选择方法：①赌轮选择法②最优保存策略③锦标赛选择法④排序选择法(2)交叉算子交叉算子模拟了自然界生物体的突变、体现了信息交换思想，决定着遗传算法的收敛性和全局搜索能力。目前适合于二进制编码的个体和浮点数编码的个体的交叉算法主要有：①单点交叉②两点交叉与多点交叉③均匀交叉④算术交叉二.遗传算法原理(3)变异算子变异操作只是对产生的新个体起辅助作用，决定了遗传算法的局部搜索能力。目前适合于二进制编码的个体和浮点数编码的个体的变

6、异算法主要有：①基本位变异②均匀变异③边界变异④高斯近似变异二.遗传算法原理控制参数控制参数主要有群体规模、迭代次数、交叉概率、变异概率等，对此基本的遗传算法都需要提前设定：N：群体大小，如果群体规模大，可提供大量模式，使遗传算法进行启发式搜索，防止早熟发生，但会降低效率；如果群体规模小，可提高速度，但却会降低效率。一般取为20～100。T：遗传运算的终止进化代数，一般取为100～500。Pc：交叉概率，它影响着交叉算子的使用频率,一般取为0.4～0.99。Pm：变异概率，变异率控制着变异算子的使用频率，它的大小将影响群体的多样性及成熟前的收敛性能。一般取为0.0001～0.1。三

7、.算法实现本例使用酒瓶三元色数据，希望将数据按照各自所属的类别归类。取59组数据为对象，确定其所属类别。程序流程如图所示。三.算法实现重要程序代码介绍：1.种群初始化遗传聚类算法需要设置的参数有四个，分别是：交叉概率pcross、遗传概率pmutation、进化代数（迭代次数）maxgen和种群规模sizepop，程序如下：%%参数初始化maxgen=100;%进化代数，即迭代次数，初始预定值选为100sizepop=100;%种群规模，初始预定值选为100pcros