主讲：周润景教授单位：电子信息工程学院遗传算法聚类设计目录遗传算法简介遗传算法原理算法实现总结一.遗传算法简介遗传算法是一种模拟自然进化的优化搜索算法。由于它仅依靠适应度函数就可以搜索最优解，不需要有关问题解空间的知识，并且适应度函数不受连续可微等条件的约束，因此在解决多维、高度非线性的复杂优化问题中得到了广泛应用和深入研究。遗传算法在模式识别、神经网络、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。一.遗传算法简介本文给出了一种基于遗传算法的聚类分析方法。采用浮点数编码方式对聚类的中心进行编码，并用特征向量与相应聚类中心的欧氏距离的和来判断聚类划分的质量，通过选择、交叉和变异操作对聚类中心的编码进行优化，得到使聚类划分效果最好的聚类中心。二.遗传算法原理遗传算法(GeneticAlgorithms，GA)是一种新近发展起来的搜索最优解方法。它模拟生命进化机制，遗传算法对于复杂的优化问题无需建模和复杂运算，只要利用遗传算法的三种算子就能得到最优解。经典遗传算法的一次进化过程示意图如图所示。父代（n代）个体1个体2个体3个体4个体5个体n个体1个体2个体3个体4个体5个体6子孙1（1×2）子孙2（1×2）子孙3（3×4）个体4（3×4）个体5（5×6）个体6（5×6）新子孙1新子孙2新子孙3新子孙4新子孙5新子孙6新子孙7选择中间群体交叉中间群体变异子代（n+1代）二.遗传算法原理1.遗传算法的基本术语染色体(chromosome)，又称为个体(individual)。编码(coding)。把问题的解表示为位串的过程称为编码，编码后的每个位串就表示一个个体，即问题的一个解。种群(population)。由一定数量的个体组成的群体，也就是问题的一些解的集合。种群中个体的数量称为种群规模。适应度(fitness)。评价群体中个体对环境适应能力的指标，就是解的好坏，由评价函数F计算得到。在遗传算法中，F是求解问题的目标函数，也就是适应度函数。遗传算子(geneticoperator)：(1)选择(selection)(2)交叉(crossover)(3)变异(mutation)二.遗传算法原理2.遗传算法问题求解过程确定实际问题的参数集对参数进行编码初始化群体集评价群体集满足停止？遗传操作得到新群体结束位串解码得到参数计算目标函数值计算适应度值选择交叉变异YesNo二.遗传算法原理3.遗传算法的基本要素遗传算法包含了如下5个基本要素：问题编码，初始群体的设定，适应度函数的设计，遗传操作设计，控制参数的设定。问题编码(1)二进制编码(2)浮点数编码初始群体的生成最常用的初始方法是无指导的随机初始化。二.遗传算法原理适应度函数(FitnessFunction)的确定在遗传算法中，按与个体适应度成正比的概率来决定当前群体中的每个个体遗传到下一代群体中的机会多少，一般希望适应值越大越好，且要求适应值非负。适应度函数是根据目标函数确定的，针对不同种类的问题，目标函数有正有负，因此必须确定由目标函数值到适应度函数之间的映射规则，以适应上述的要求。适应度函数的设计应满足以下条件：(1)单值、连续、非负、最大化。(2)计算量小。适应度函数设计尽可能简单，以减少计算的复杂性。(3)通用性强。适应度对某类问题，应尽可能通用。二.遗传算法原理遗传操作遗传算法遗传操作主要包括：选择、交叉、变异三个算子。(1)选择算子采用基于适应度的选择原则，适应度越强被选中概率越大，体现优胜劣汰进化机制。几种常用的选择方法：①赌轮选择法②最优保存策略③锦标赛选择法④排序选择法(2)交叉算子交叉算子模拟了自然界生物体的突变、体现了信息交换思想，决定着遗传算法的收敛性和全局搜索能力。目前适合于二进制编码的个体和浮点数编码的个体的交叉算法主要有：①单点交叉②两点交叉与多点交叉③均匀交叉④算术交叉二.遗传算法原理(3)变异算子变异操作只是对产生的新个体起辅助作用，决定了遗传算法的局部搜索能力。目前适合于二进制编码的个体和浮点数编码的个体的变异算法主要有：①基本位变异②均匀变异③边界变异④高斯近似变异二.遗传算法原理控制参数控制参数主要有群体规模、迭代次数、交叉概率、变异概率等，对此基本的...
