遗传算法聚类设计.pptx

主讲：周润景教授单位：电子信息工程学院,遗传算法聚类设计,目录,遗传算法简介遗传算法原理算法实现总结,一.遗传算法简介,遗传算法是一种模拟自然进化的优化搜索算法。由于它仅依靠适应度函数就可以搜索最优解，不需要有关问题解空间的知识，并且适应度函数不受连续可微等条件的约束，因此在解决多维、高度非线性的复杂优化问题中得到了广泛应用和深入研究。遗传算法在模式识别、神经网络、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。,一.遗传算法简介,本文给出了一种基于遗传算法的聚类分析方法。采用浮点数编码方式对聚类的中心进行编码，并用特征向量与相应聚类中心的欧氏距离的和来判断聚类划分的质量，通过选择、交叉和变异操作对聚类中心的编码进行优化，得到使聚类划分效果最好的聚类中心。,二.遗传算法原理,遗传算法(GeneticAlgorithms，GA)是一种新近发展起来的搜索最优解方法。它模拟生命进化机制，遗传算法对于复杂的优化问题无需建模和复杂运算，只要利用遗传算法的三种算子就能得到最优解。经典遗传算法的一次进化过程示意图如图所示。,二.遗传算法原理,1.遗传算法的基本术语染色体(chromosome)，又称为个体(individual)。编码(coding)。把问题的解表示为位串的过程称为编码，编码后的每个位串就表示一个个体，即问题的一个解。种群(population)。由一定数量的个体组成的群体，也就是问题的一些解的集合。种群中个体的数量称为种群规模。适应度(fitness)。评价群体中个体对环境适应能力的指标，就是解的好坏，由评价函数F计算得到。在遗传算法中，F是求解问题的目标函数，也就是适应度函数。遗传算子(geneticoperator)：(1)选择(selection)(2)交叉(crossover)(3)变异(mutation),二.遗传算法原理,2.遗传算法问题求解过程,二.遗传算法原理,3.遗传算法的基本要素遗传算法包含了如下5个基本要素：问题编码，初始群体的设定，适应度函数的设计，遗传操作设计，控制参数的设定。问题编码(1)二进制编码(2)浮点数编码初始群体的生成最常用的初始方法是无指导的随机初始化。,二.遗传算法原理,适应度函数(FitnessFunction)的确定在遗传算法中，按与个体适应度成正比的概率来决定当前群体中的每个个体遗传到下一代群体中的机会多少，一般希望适应值越大越好，且要求适应值非负。适应度函数是根据目标函数确定的，针对不同种类的问题，目标函数有正有负，因此必须确定由目标函数值到适应度函数之间的映射规则，以适应上述的要求。适应度函数的设计应满足以下条件：(1)单值、连续、非负、最大化。(2)计算量小。适应度函数设计尽可能简单，以减少计算的复杂性。(3)通用性强。适应度对某类问题，应尽可能通用。,二.遗传算法原理,遗传操作遗传算法遗传操作主要包括：选择、交叉、变异三个算子。(1)选择算子采用基于适应度的选择原则，适应度越强被选中概率越大，体现优胜劣汰进化机制。几种常用的选择方法：赌轮选择法最优保存策略锦标赛选择法排序选择法(2)交叉算子交叉算子模拟了自然界生物体的突变、体现了信息交换思想，决定着遗传算法的收敛性和全局搜索能力。目前适合于二进制编码的个体和浮点数编码的个体的交叉算法主要有：单点交叉两点交叉与多点交叉均匀交叉算术交叉,二.遗传算法原理,(3)变异算子变异操作只是对产生的新个体起辅助作用，决定了遗传算法的局部搜索能力。目前适合于二进制编码的个体和浮点数编码的个体的变异算法主要有：基本位变异均匀变异边界变异高斯近似变异,二.遗传算法原理,控制参数控制参数主要有群体规模、迭代次数、交叉概率、变异概率等，对此基本的遗传算法都需要提前设定：N：群体大小，如果群体规模大，可提供大量模式，使遗传算法进行启发式搜索，防止早熟发生，但会降低效率；如果群体规模小，可提高速度，但却会降低效率。一般取为20100。T：遗传运算的终止进化代数，一般取为100500。Pc：交叉概率，它影响着交叉算子的使用频率,一般取为0.40.99。Pm：变异概率，变异率控制着变异算子的使用频率，它的大小将影响群体的多样性及成熟前的收敛性能。一般取为0.00010.1。,三.算法实现,本例使用酒瓶三元色数据，希望将数据按照各自所属的类别归类。取59组数据为对象，确定其所属类别。程序流程如图所示。,三.算法实现,重要程序代码介绍：1.种群初始化遗传聚类算法需要设置的参数有四个，分别是：交叉概率pcross、遗传概率pmutation、进化代数（迭代次数）maxgen和种群规模sizepop，程序如下：%参数初始化maxgen=100;%进化代数，即迭代次数，初始预定值选为100sizepop=100;%种群规模，初始预定值选为100pcross=0.9;%交叉概率选择，0和1之间，一般取0.9pmutation=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个04000的随机数赋给种群中的一条染色体，代表K=4个聚类中心x=individuals.chrom(i,:);%计算每条染色体的适应度individuals.fitness(i)=fitness(x);end%找最好的染色体bestfitnessbestindex=max(individuals.fitness);%找出适应度最大的染色体，并记录其适应度的值(bestfitness)和染色体,三.算法实现,的位置(bestindex)bestchrom=individuals.chrom(bestindex,:);%把最好的染色体赋给变量bestchromavgfitness=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:ndist1=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;%求类中某一点到其聚类中心的距离和，即准则函数endfit=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之间的随机数赋给pickwhilepick=0pick=rand;end%确保pick被赋值fori=1:sizepoppick=pick-sumf(i);%染色体的选择概率越大，pick越容易小于，即染色体越容易被选中ifpickpcrosscontinue;end%当pickpmutationcontinue;end%当pick小于变异概率时，执行变异操作pick=rand;whilepick=0pick=rand;,三.算法实现,endindex=ceil(pick*sizepop);%在种群中，随机选择一条染色体pick=rand;whilepick=0pick=rand;endpos=ceil(pick*3);%在染色体当中，随机选择变异位置chrom(index,pos)=rand*4000;%染色体进行变异endret=chrom;%输出编译后的染色体,三.算法实现,程序运行完以后，初始聚类结果如图1所示，适应度曲线如图2所示。,图1maxgen=100、sizepop=100时的聚类结果,图2maxgen=100、sizepop=100时的适应度函数曲线,三.算法实现,分析聚类结果可知，当进化代数（即迭代次数）maxgen=100，种群规模sizepop=100时，有一类仅有一个数据，聚类结果明显是错误的，并没有按照要求把数据聚为四类。通过分析适应度函数曲线可知，群体的平均适应度在进化到第100左右刚好达到收敛，所以不是迭代次数的问题，也可能是种群规模的问题。所以我们要不断的增加种群规模来比较其聚类效果，这里依次取sizepop=200,300,400,500。当进化代数（即迭代次数）maxgen=100，种群规模sizepop=700时，聚类结果如图3所示，适应度曲线如图4所示。,图3maxgen=100、sizepop=700时的聚类结果,图4maxgen=100、sizepop=700时的适应度函数曲线,三.算法实现,但是当种群规模增加到sizepop=700左右时，聚类效果依然不佳，种群的平均适应度曲线并没有收敛，这时，增加进化代数maxgen。不断的增大种群规模，并找到其合适的进化代数，观察聚类的效果。实验的结果如下表所示,三.算法实现,通过对比表中数据，可以看出随着种群规模和进化代数的增加，准则函数的值得到明显的下降，得出了正确的聚类结果，但是具有很大的随机性，收敛速度也越来越慢。当进化代数（即迭代次数）maxgen=200，种群规模sizepop=1500时，准则函数平均值最小，聚类结果是实验中最好的，聚类结果如图