遗传算法聚类设计

主讲：周润景教授单位：电子信息工程学院遗传算法聚类设计目录遗传算法简介遗传算法原理算法实现总结一.遗传算法简介遗传算法是一种模拟自然进化的优化搜索算法。由于它仅依靠适应度函数就可以搜索最优解，不需要有关问题解空间的知识，并且适应度函数不受连续可微等条件的约束，因此在解决多维、高度非线性的复杂优化问题中得到了广泛应用和深入研究。遗传算法在模式识别、神经网络、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。一.遗传算法简介本文给出了一种基于遗传算法的聚类分析方法。采用浮点数编码方式对聚类的中心进行编码，并用特征向量与相应聚类中心的欧氏距离的和来判断聚类划分的质量，通过选择、交叉和变异操作对聚类中心的编码进行优化，得到使聚类划分效果最好的聚类中心。二.遗传算法原理遗传算法(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)变异算子变异操作只是对产生的新个体起辅助作用，决定了遗传算法的局部搜索能力。目前适合于二进制编码的个体和浮点数编码的个体的变异算法主要有：①基本位变异②均匀变异③边界变异④高斯近似变异二.遗传算法原理控制参数控制参数主要有群体规模、迭代次数、交叉概率、变异概率等，对此基本的遗传算法都需要提前设定：N：群体大小，如果群体规模大，可提供大量模式，使遗传算法进行启发式搜索，防止早熟发生，但会降低效率；如果群体规模小，可提高速度，但却会降低效率。一般取为20～100。T：遗传运算的终止进化代数，一般取为100～500。Pc：交叉概率，它影响着交叉算子的使用频率,一般取为0.4～0.99。Pm：变异概率，变异率控制着变异算子的使用频率，它的大小将影响群体的多样性及成熟前的收敛性能。一般取为0.0001～0.1。三.算法实现本例使用酒瓶三元色数据，希望将数据按照各自所属的类别归类。取59组数据为对象，确定其所属类别。程序流程如图所示。开始1、输入最大迭代次数maxgen2、种群大小popsize3、输入交叉概率pcross4、输入变异概率pmutation1、随机生成一个种群2、计算每个个体的适应度3、找出最好的个体，记录最好适应度和平均适应度1、进行选择、交叉和变异操作2、计算每个个体的适应度3、找出适应度最大的个体4、代替上一次适应度最大的个体迭代次数是否小于maxgen迭代次数加一输出适应度最大的个体（最佳聚类中心）进行聚类输出聚类结果结束YesNo三.算法实现重要程序代码介绍：1.种群初始化遗传聚类算法需要设置的参数有四个，分别是：交叉概率pcross、遗传概率pmutation、进化代数（迭代次数）maxgen和种群规模sizepop，程序如下：%%参数初始化maxgen=100;%进化代数，即迭代次数，初始预定值选为100sizepop=100;%种群规模，初始预定值选为100pcross=0.9;%交叉概率选择，0和1之间，一般取0.9pmutation=0.01;%变异概率选择，0和1之间，一般取0.012.适应度函数的设计种群初始化的matlab程序如下：individuals=struct('fitness',zeros(1,sizepop),'chrom',[]);%种群由sizepop条染色体(chrom)及每条染色体的适应度(fitness)组成avgfitness=[];%记录每一代种群的平均适应度，首先赋给一个空数组三.算法实现bestfitness=[];%记录每一代种群的最佳适应度，首先赋给一个空数组bestchrom=[];%记录适应度最好的染色体，首先赋给一个空数组%初始化种群fori=1:sizepop%随机产生一个种群individuals.chrom(i,:)=4000*rand(1,12);%把12个0~4000的随机数赋给种群中的一条染色体，代表K=4个聚类中心x=individuals.chrom(i,:);%计算每条染色体的适应度individuals.fitness(i)=fitness(x);end%%找最好的染色体[bestfitnessbestindex]=max(individuals.fitness);%找出适应度最大的染色体，并记录其适应度的值(bestfitness)和染色体三.算法实现的位置(bestindex)bestchrom=individuals.chrom(bestindex,:);%把最好的染色体赋给变量bestchromavgfitness=sum(individuals.fitness)/sizepop;%计算群体中染色体的平均适应度%记录每一代进化中最好的适应度和平均适应度trace=[avgfitnessbestfitness];适应度函数的matlab程序如下：functionfit=fitness(x)%%计算个体适应度值%xinput个体%fitoutput适应度值data=load[“a.txt”];kernel=[x(1:3);x(4:6);x(7:9);x(10:12)];%对染色体进行编码，其中x(1:3)代表第一个聚类中心，x(4:6)代表第二个聚类中心，x(7:9)代表第三个聚类中心，x(10:12)代表第四个聚类中心三.算法实现Gc=0;%Gc代表聚类的准则函数[n,m]=size(data);%求出待聚类数据的行和列fori=1:ndist1=norm(data(i,1:3)-kernel(1,:));dist2=norm(data(i,1:3)-kernel(2,:));dist3=norm(data(i,1:3)-kernel(3,:));dist4=norm(data(i,1:3)-kernel(4,:));%计算待聚类数据中的某一点到各个聚类中心的距离a=[dist1dist2dist3dist4];mindist=min(a);%取其中的最小值，代表其被划分到某一类Gc=mindist+Gc;%求类中某一点到其聚类中心的距离和，即准则函数endfit=1/Gc;%求出染色体的适应度，即准则函数的倒数，聚类的准则函数越小，染色体的适应度越大，聚类的效果也就越好三.算法实现3.种群初始化选择操作的matlab程序如下：functionret=Select(individuals,sizepop)%本函数对每一代种群中的染色体进行选择，以进行后面的交叉和变异%individualsinput:种群信息%sizepopinput:种群规模%retoutput:经过选择后的种群sumfitness=sum(individuals.fitness);%计算群体的总适应度sumf=(individuals.fitness)./sumfitness;%计算出染色体的选择概率，即染色体的适应度除以总适应度index=[];%用来记录被选中染色体的序号，首先付给一个空数组fori=1:sizepop%转sizepop次轮盘pick=rand;三.算法实现%把一个[0,1]之间的随机数赋给pickwhilepick==0pick=rand;end%确保pick被赋值fori=1:sizepoppick=pick-sumf(i);%染色体的选择概率越大，pick越容易小于，即染色体越容易被选中ifpick0index=[indexi];%把被选择中的染色体的序号赋给indexbreak;endendendindividuals.chrom=individuals.chrom(index,:);三.算法实现%记录选择中的染色体individuals.fitness=individuals.fitness(index);%记录选择中染色体的适应度ret=individuals;%输出经过选择后的染色体4.交叉操作交叉操作的matlab程序：functionret=Cross(pcross,chrom,sizepop)%本函数完成交叉操作%pcorssinput:交叉概率%lenchrominput:染色体的长度%chrominput:染色体群%sizepopinput:种群规模%retoutput:交叉后的染色体fori=1:sizepop三.算法实现%交叉概率决定是否进行交叉pick=rand;whilepick==0pick=rand;end%给pick赋予一个[0,1]之间的随机数ifpickpcrosscontinue;end%当pickpcross时，进行交叉操作index=ceil(rand(1,2).*sizepop);while(index(1)==index(2))|index(1)*index(2)==0index=ceil(rand(1,2).*