基于遗传算法的聚类分析

基于遗传算法的聚类分析ClusterAnalysisWhichBasedonGeneticAlgorithm学院：电子信息工程学院专业：控制工程姓名：苏良碧学号：30956059指导老师：周润景聚类分析聚类分析是模式识别中的一个重要问题，是非监督学习的重要方法。聚类分析的目的是将若干特征模式按照它们之间的“相似度”划分为若干个集合，每个集合中的特征模式之间按照某种度量来说“相似”，而不同集合中的特征模式之间按相同的度量来说“不相似”。准则函数用来判断聚类质量cjnijjjiWjnicjmxJ112)(...2,1,...12,||||遗传算法遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律演化而来的随机化搜索方法。适者生存，优胜劣汰很多年以后···第一代：第二代：第N代：基于遗传算法的聚类开始1、输入最大迭代次数maxgen2、种群大小popsize3、输入交叉概率pcross4、输入变异概率pmutation1、随机生成一个种群2、计算每个个体的适应度3、找出最好的个体，记录最好适应度和平均适应度1、进行选择、交叉和变异操作2、计算每个个体的适应度3、找出适应度最大的个体4、代替上一次适应度最大的个体迭代次数是否小于maxgen迭代次数加一输出适应度最大的个体（最佳聚类中心）进行聚类输出聚类结果结束第一步：参数初始化%%参数初始化maxgen=100;%进化代数，即迭代次数sizepop=100;%种群规模pcross=0.9;%交叉概率选择，0和1之间pmutation=0.01;%变异概率选择，0和1之间第二步：生成种群、计算适应度、找出最好个体individuals=struct('fitness',zeros(1,sizepop),'chrom',[]);%种群avgfitness=[];%每一代种群的平均适应度bestfitness=[];%每一代种群的最佳适应度bestchrom=[];%适应度最好的染色体%初始化种群fori=1:sizepop%随机产生一个种群individuals.chrom(i,:)=4000*rand(1,12);x=individuals.chrom(i,:);%计算适应度individuals.fitness(i)=fitness(x);end%%找最好的染色体[bestfitnessbestindex]=max(individuals.fitness);bestchrom=individuals.chrom(bestindex,:);%最好的染色体avgfitness=sum(individuals.fitness)/sizepop;%染色体的平均适应度%记录每一代进化中最好的适应度和平均适应度trace=[avgfitnessbestfitness];计算适应度functionfit=fitness(x)%%计算个体适应度值%xinput个体%fitoutput适应度值data=[2232.433077.871298.871580.11752.072463.041962.41594.971835.951495.181957.443498.021125.171594.392937.7324.223447.312145.011269.071910.722701.971802.071725.811966.351817.361927.42328.791860.451782.881875.131237.912055.133405.09688.942104.723198.511675.651747.231580.391806.021810.192191.1274.563288.022433.87307.353363.842021.611988.271657.512069.22173.922608.551803.57372.163077.442163.46576.62140.9833201724.131704.491798.752501.212652.65984.561656.941913.342459.07362.513150.032472565.742284.973024.581978.061536.132375.641661.061552.42005.05790.292419.983051.161557.271746.271879.132793.363009.261073.551766.081803.141895.181207.881600.623123.07245.753373.672248.452785.363052.811035.65315.423088.292187.121243.282451.723111.99829.841555.913139.211347.072364.313096.881926.981507.341626.471808.571608.781565.951124.11840.982819.4126613302.391710.321805.551899.092400.61130.181902.422753.71355.191566.162927.811651.141774.031725.562110.633308.04702.062788.113395.231684.451807.611680.562356.651363.581729.442749.551992.421526.91581.42];kernel=[x(1:3);x(4:6);x(7:9);x(10:12)];Gc=0;[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;第三步：进化过程%%进化开始fori=1:maxgeni%选择individuals=Select(individuals,sizepop);avgfitness=sum(individuals.fitness)/sizepop;%交叉individuals.chrom=Cross(pcross,individuals.chrom,sizepop);%变异individuals.chrom=Mutation(pmutation,individuals.chrom,sizepop);%计算适应度forj=1:sizepopx=individuals.chrom(j,:);%解码[individuals.fitness(j)]=fitness(x);end%找到最小和最大适应度的染色体及它们在种群中的位置[newbestfitness,newbestindex]=max(individuals.fitness);[worestfitness,worestindex]=min(individuals.fitness);%代替上一次进化中最好的染色体ifbestfitnessnewbestfitnessbestfitness=newbestfitness;bestchrom=individuals.chrom(newbestindex,:);endindividuals.chrom(worestindex,:)=bestchrom;individuals.fitness(worestindex)=bestfitness;avgfitness=sum(individuals.fitness)/sizepop;trace=[trace;avgfitnessbestfitness];%记录每一代进化中最好的适应度和平均适应度选择函数functionret=Select(individuals,sizepop)%本函数对每一代种群中的染色体进行选择，以进行后面的交叉和变异%individualsinput:种群信息%sizepopinput:种群规模%retoutput:经过选择后的种群sumfitness=sum(individuals.fitness);sumf=(individuals.fitness)./sumfitness;index=[];fori=1:sizepop%转sizepop次轮盘pick=rand;whilepick==0pick=rand;endfori=1:sizepoppick=pick-sumf(i);ifpick0index=[indexi];break;endendendindividuals.chrom=individuals.chrom(index,:);individuals.fitness=individuals.fitness(index);ret=individuals;交叉函数functionret=Cross(pcross,chrom,sizepop)%本函数完成交叉操作%pcorssinput:交叉概率%lenchrominput:染色体的长度%chrominput:染色体群%sizepopinput:种群规模%retoutput:交叉后的染色体fori=1:sizepop%交叉概率决定是否进行交叉pick=rand;whilepick==0pick=rand;endifpickpcrosscontinue;end%随机选择交叉个体index=ceil(rand(1,2).*sizepop);while(index(1)==index(2))|index(1)*index(2)==0index=ceil(rand(1,2).*sizepop);end%随机选择交叉位置pos=ceil(rand*3);whilepos==0pos=ceil(rand*3);endtemp=chrom(index(1),pos);chrom(index(1),pos)=chrom(index(2),pos);chrom(index(2),pos)=temp;endret=chrom;变异函数functionret=Mutation(pmutation,chrom,sizepop)%本函数完成变异操作%pcorssinput:变异概率%lenchrominput:染色体长度%chrominput:染色体群%sizepopinput:种群规模%boundinput:每个个体的上届和下届%retoutput:变异后的染色体fori=1:sizepop%变异概率决定该轮循环是否进行变异pick=rand;ifpickpmutationcontinue;endpick=rand;whilepick==0pick=rand;endindex=ceil(pick*sizepop);%变异位置pick=rand;whilepick==0pick=rand;endpos=ceil(pick*3);chrom(index,pos)=rand*4000;endret=chrom;第四步：进行聚类kernal=[bestchrom(1:3);bestchrom(4:6);bestchrom(7:9);bestchrom(10