微粒群算法多目标粒子群算法源程序

什么是粒子群算法？

粒子群优化(Partical Swarm Optimization - PSO) 算法是近年来发展起来的一种新的进化算法( Evolu2tionary Algorithm - EA) .PSO 算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质. 但是它比遗传算法规则更为简单,它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作. 它通过追随当前搜索到的最优值来寻找全局最优 .

粒子群算法是怎么用于字符识别的

字符识别可看做属于模式识别范畴，模式识别即对已有的模式进行识别，即分类。

粒子群本身是一个搜索算法或者优化算法，本质说，它不能用于分类。

但是，结合其他的一些分类算法，把分类的问题看成一个问题的优化问题的时候，粒子群就可以用于分类了。

举个粒子，最近邻分类NN，指的是测试集中的样本与训练集中距离最近样本的模式（类别）相同。

现在假定给了训练集A，测试集B。

假设类别已知为C类。

如果训练集A特征大的时候，势必会影响分类时候的速度，那么我们就可以把训练集简化到每类一个样本（共C个样本），那样分类的时候只需要计算B中每个样本到C个中心点中哪个的距离最小就可以了。

如何利用粒子群算法得到这C个中心点呢？？ 一般采用聚类的思想，假设我们想找到C个中心点的每个中心点 是 到A中对应自己类别的样本的距离和最小的C个点，那么适应度函数就出来了。

即训练样本到中心点样本的距离和。

微粒群算法的改进方法

1 多目标优化 相对传统多目标优化方法, PSO在求解多目标问题上具有很大优势。

首先, PSO的高效搜索能力有利于得到多目标意义下的最优解;其次, PSO通过代表整个解集的种群按内在的并行方式同时搜索多个非劣解,因此容易搜索到多个Pareto 最优解; 再则, PSO的通用性使其适合于处理所有类型的目标函数和约束;另外, PSO 很容易与传统方法相结合,进而提出解决特定问题的高效方法。

就PSO 本身而言,为了更好地解决多目标优化问题,必须解决全局最优粒子和个体最优粒子的选择问题。

对于全局最优粒子的选择,一方面要求算法具有较好的收敛速度,另一方面要求所得解在Pareto边界上具有一定的分散性。

对于个体最优粒子的选择,则要求较小的计算复杂性,即仅通过较少的比较次数达到非 劣解的更新。

迄今,基于PSO的多目标优化主要有以下几种 思路: (1)向量法和权重法。

文献[ 20 ]利用固定权重法、适应性权重法和向量评价法,首次将PSO 用于解决MO问题。

然而对于给定的优化问题,权重法通常很难获得一组合适的权重,而向量评价法往往无法给出MO问题的满意解。

(2)基于Pareto的方法。

文献[ 21 ]将Pareto排序机制和PSO相结合来处理多目标优化问题,通过Pareto排序法选择一组精英解,并采用轮盘赌方式从中选择全局最优粒子。

尽管轮盘赌选择机制设计的目的是使所有Pareto个体的选择概率相同,但是实际上只有少数个体得到较大的选择概率,因此不利于维持种群的多样性;文献[ 22 ]通过在PSO中引入Pareto竞争机制和微粒知识库来选择全局最优粒子。

由于非劣解是将候选个体与从种群中随机选出的比较集进行比较来确定的,因此该算法成功与否就取决于比较集规模参数的设定。

如果这个参数太小,该过程从种群中选出的非劣个体可能过少;如果这个参数太大,则可能发生早熟收敛现象。

(3)距离法。

文献[ 23 ]根据个体当前解与Pa2reto解之间的距离来分配其适应值,从而选择全局最优粒子。

由于距离法需要初始化潜在解,如果初始潜在值太大,不同解的适应值的差别则不明显。

这将导致选择压力过小或个体均匀分布,从而导致PSO算法收敛非常缓慢。

(4)邻域法。

文献[ 24 ]提出一种基于动态邻域的选择策略,将一个目标定义为优化目标,而将其它所有目标定义为邻域目标,进而提出了选择全局最优粒子的动态邻域策略,但该方法对优化目标的选择以及邻域目标函数的排序较敏感。

(5)多种群法。

文献[ 25 ]将种群分为多个子种群,每个子种群单独进行PSO 运算,各个子种群之间通过信息交换来搜索Pareto最优解。

但是由于需要增加微粒数目而增加了计算量。

(6)非优势排序法。

文献[ 26 ]利用非优势排序的方法选择全局最优粒子。

该方法在整个种群中,比较微粒的个体最优粒子与其后代,有利于提供合适的选择压力,同时使用小生境技术提高种群多样性。

然而在整个种群中比较所有微粒的个体最优粒子与其后代,其本质不利于种群多样性,容易形成早熟。

另外,文献[ 27 ]将博弈理论中的Maximin策略引入PSO来解决多MO问题。

利用Maximin策略确定微粒的适应值可以很好地确定Pareto最优解而不需要聚类和小生境技术。

2 约束优化 近年来, PSO算法在约束优化方面也取得了一定进展。

基于PSO的约束优化工作主要分为两类: ①罚函数法; ②设计特定的进化操作或约束修正因子。

文献[ 28 ]采用罚函数法,利用非固定多段映射罚函数对约束优化问题进行转化,再利用PSO求解转化后的问题,仿真结果显示PSO相对进化策略和遗传算法有优越性,但其罚函数的设计过于复杂,不利于求解;文献[ 29 ]采用可行解保留策略处理约束,即一方面更新存储区时所有粒子仅保留可行的解,另一方面在初始化阶段所有粒子均从可行解空间取值,然而初始可行解空间对于许多问题是很难确定的;文献[ 30 ]提出了具有多层信息共享策略的微粒群原理来处理约束,根据约束矩阵采用多层Pareto排序机制来产生优良粒子,进而用一些优良的粒子来决定其余个体的搜索方向。

3 离散优化对于离散优化而言,解空间是离散点的集合,而非连续区域,因此利用PSO解决离散优化问题就必须修正速度和位置更新公式,或者是对问题进行变形。

目前,基于PSO的离散优化工作可分为如下三类: (1)将速度作为位置变化的概率。

文献[ 31 ]首次提出了离散二值PSO。

其微粒位置编码采用二进制方式,通过采用Sigmoid函数将速度约束于[ 0, 1 ]区间,来代表微粒位置取1的概率;文献[ 32 ]对文献 [ 31 ]中的方法进行改进,用于解决置换排列问题。

其中微粒用置换排列表示,而速度则根据两个粒子的相似度来定义,决定微粒位置变化的概率,同时还引入变异操作防止最优粒子陷入局部极小。

(2)重新定义PSO操作。

文献[ 33 ]通过重新定义微粒的位置、速度、以及它们之间的加减乘操作,提出一种新的离散PSO,并用于求解旅行商问题。

尽管该算法的效果较差,但是提供了一种解决组合优化问题的新的思路。

(3)直接将连续PSO用于离散情况。

文献[ 34 ]利用连续PSO 解决分布式计算机任务分配问题。

为了将实数转化为正整数,把实数的符号和小数部 分去掉。

结果表明该方法在解的质量和算法速度方面,要优于遗传算法。

4 动态优化 在许多实际工程问题中,优化的环境是不确定的,或者是动态的。

因此,优化算法必须具备随环境动态变化而对最优解作出相应调整的能力,或者是算法具有一定的鲁棒性。

文献[ 35 ]首次提出利用PSO跟踪动态系统;文献[ 36 ]提出用自适应PSO来自动跟踪动态系统的变化,该方法通过对种群中最好微粒的检测和对微粒重新初始化, 有效增强了PSO对系统变化的跟踪能力;文献[ 37 ]为了处理快速变化的动态环境,在微粒速度更新公式中增加了一项变化项,从而无需检测环境的变化就可以跟踪环境。

尽管该方面的研究成果至今较少,但不容质疑这是一项重要的研究内容。

微粒群算法的MATLAB程序实现 初始化粒子群; DO For每个粒子 计算其适应度; If (适应度优于粒子历史最佳值) 用Xi更新历史最佳个体Pi; End 选取当前粒子群中最佳粒子; If (当前最佳粒子优于群历史最佳粒子) 用当前群最佳粒子更新Pg; For每个粒子 按式①更新粒子速度; 按式②更新粒子位置; End While最大迭代数未达到或最小误差未达到。

粒子群算法特征选择

这应该属于粒子的编码问题，给你提供两种。

一种是整数编码，采用连续域的粒子群算法，将得到的粒子值进行取整操作，比如你想选3个特征，取粒子编码长度为3，比如粒子（1.2 5.8 9.8），取整得到（2,6,10）。

还有一个是采用二进制编码（搜索下BPSO），粒子的每一维取值0或1，用来表示该维特征是否被选中，这种可以用来做自适应的特征选择。

粒子群算法属于什么学科

粒子群算法属于计算智能的范畴，如果按照学科分的话当然是计算机学科。

另外粒子群算法是一种进化计算技术(putation)，1995 年由Eberhart 博士和kennedy 博士提出，源于对鸟群捕食的行为研究 。

—————————————————————————— 另外关于计算智能的相关介绍便可以了解 计算智能的主要方法有人工神经网络、遗传算法、遗传程序、演化程序、局部搜索、模拟退火等等。

这些方法具有以下共同的要素：自适应的结构、随机产生的或指定的初始状态、适应度的评测函数、修改结构的操作、系统状态存储器、终止计算的条件、指示结果的方法、控制过程的参数。

计算智能的这些方法具有自学习、自组织、自适应的特征和简单、通用、鲁棒性强、适于并行处理的优点。

在并行搜索、联想记忆、模式识别、知识自动获取等方面得到了广泛的应用。

典型的代表如遗传算法、免疫算法、模拟退火算法、蚁群算法、微粒群算法(也就是粒子群算法，翻译不同罢了)，都是一种仿生算法，基于“从大自然中获取智慧”的理念，通过人们对自然界独特规律的认知，提取出适合获取知识的一套计算工具。

总的来说，通过自适应学习的特性，这些算法达到了全局优化的目的。

多目标粒子群算法源程序

不知道你所说的多目标是指什么，据我的理解，既然有个目标函数，那么多目标可以在目标函数那里表示，我最近也在做这个粒子群算法， 下面是我的vc++6.0代码,改造了一下基本粒子群，求路径的.. #include <math.h> #include <time.h> #include <iostream> using namespace std; double c1=0.7; //?????ò×? double c2=0.2; //?????ò×? double w=1.0; //?????¨?? double Wmax=1.0; //×??ó?????¨?? double Wmin=0.6; //×????????¨?? int Kmax=50; //?ü?ú???? int const Dim=7; //??×????? int const PNum=4; //??×????? int FB=200; //????×????±???? int FC=5; //???????í???? int GBIndex=0; //×?????×??÷?? class PARTICLE; //?ê?÷??×????? void Initial(); //???????à??±??? void Update(int *x,int *v); //????×?v?ü??x void GetDifferent(int *p1,int *p2,int *v); //?ó?·?????ì int GetFit(PARTICLE&); //?????????? void CalculateFit(); //?????????? void BirdsFly(); //??×?·??è void Run(int num); //???????? double GetRandm(); //???ú?????? int A[7][7]={ //??????·??? { 0, 2,1000, 4,1000,1000,1000}, { 2, 0, 3,1000,1000,1000,1000}, {1000, 3, 0,1000, 3, 6,1000}, { 4,1000,1000, 0, 5, 2,1000}, {1000,1000,1000, 5, 0, 1, 2}, {1000,1000, 6, 2, 1, 0, 4}, {1000,1000,1000,1000, 2, 4, 0} }; int B[7][7]={ //?????????± { 0, 2,1000, 4,1000,1000,1000}, { 2, 0, 3,1000,1000,1000,1000}, {1000, 3, 0,1000, 3, 6,1000}, { 4,1000,1000, 0, 5, 2,1000}, {1000,1000,1000, 5, 0, 1, 2}, {1000,1000, 6, 2, 1, 0, 4}, {1000,1000,1000,1000, 2, 4, 0} }; int C[7][7]={ //?????????í {1000, 20,1000, 10,1000,1000,1000}, { 20,1000, 5,1000,1000,1000,1000}, { 1, 7,1000,1000, 7, 36,1000}, { 40,1000, 2,1000, 6, 52,1000}, { 3,1000,1000, 9,1000, 11, 12}, { 20,1000, 6, 6, 8,1000, 14}, {1000,1000,1000,1000, 8, 24,1000} }; int First[7]={0,1,2,3,4,5,6}; int Last[7]={0,1,2,3,4,5,6}; int hp1[7]={0,0,0,0,0,0,0}; int hp2[7]={0,0,0,0,0,0,0}; //?????à class PARTICLE { public: int X[Dim]; //??????×?±ê??×é int XBest[Dim]; //??????×?????????×é int V[Dim]; //??×???????×é double Fit; //?????????? double FitBest; //????×????????????? }; PARTICLE Pt[PNum]; //??×???×é int Inp[4][7]={ {0,6,2,4,1,3,5}, {0,1,2,4,3,5,6}, {0,3,6,5,4,2,1}, {0,3,4,6,5,2,1} }; double GetRandm() { return (double)(rand()/(double)RAND_MAX); } //?????????? void Initial() { GBIndex=0; for(int i=0;i<PNum;i++) { Pt[i].X[0]=Inp[i][0]; //??????X Pt[i].XBest[0]=Pt[i].X[0]; //??????XBest Pt[i].V[0]=0; //???? for(int j=1;j<Dim;j++) { Pt[i].X[j]=Inp[i][j]; //??????X Pt[i].XBest[j]=Pt[i].X[j]; //??????XBest //Pt[i].V[j]=0; Pt[i].V[j]=(int)(10*GetRandm()+1)/1.5;//???? //cout<<Pt[i].V[j]<<ends; } Pt[i].Fit=GetFit(Pt[i]); //?????? Pt[i].FitBest=Pt[i].Fit; //×????????? if (Pt[i].FitBest<=Pt[GBIndex].FitBest) { GBIndex=i; } } cout<<"GBIndex:"<<GBIndex<<endl; } //???????ó?????? int GetFit(PARTICLE &p) { int sum=0; int fb=0; int fc=0; int i=0; do{ sum += A[p.X[i]][p.X[i+1]]; //????·??? fb += B[p.X[i]][p.X[i+1]]; //???????± if(C[p.X[i]][p.X[i+1]]<FC) fc=1000;//???í???? i++; }while(i<6 && p.X[i]!=6); if(fb>FB) { fb=1000; } else fb=0; sum+=(fb+fc); return sum; } //??????×é???÷??×????????? void CalculateFit() { for (int i=0;i<PNum;i++) { Pt[i].Fit=GetFit(Pt[i]); } } //??×?·????°??×????? void BirdsFly() { static int k=0; w=Wmax-k*(Wmax-Wmin)/Kmax; k++; cout<<"??"<<k<<"?????ú??"<<endl; for (int i=0;i<PNum;i++) { if(w>GetRandm()) { Update(Last,Pt[i].V); } for(int j=0;j<Dim;j++) Pt[i].V[j]=0; if(c1>GetRandm()) { GetDifferent(Pt[i].XBest,Pt[i].X,Pt[i].V); Update(Last,Pt[i].V); for(j=0;j<Dim;j++) Pt[i].V[j]=0; } if(c2>GetRandm()) { GetDifferent(Pt[GBIndex].XBest,Pt[i].X,Pt[i].V); Update(Last,Pt[i].V); for(j=0;j<Dim;j++) Pt[i].V[j]=0; } GetDifferent(First,Last,Pt[i].V); //?ü?????? for(j=0;j<Dim;j++) Last[j]=j; Update(Pt[i].X,Pt[i].V); } CalculateFit(); for (i=0;i<PNum;i++) { if (Pt[i].Fit<Pt[i].FitBest) { Pt[i].FitBest=Pt[i].Fit; for (int j=0;j<Dim;j++) { Pt[i].XBest[j]=Pt[i].X[j]; } } } GBIndex=0; for (i=0;i<PNum;i++) { if (Pt[i].FitBest<=Pt[GBIndex].FitBest && i!=GBIndex) { GBIndex=i; } } cout<<"×?????????:"<<Pt[GBIndex].FitBest<<endl; } //?ó?·?????ì void GetDifferent(int *p1,int *p2,int *p) { for(int i=0;i<Dim;i++) { hp1[i]=p1[i]; hp2[i]=p2[i]; } for(i=0;i<Dim;i++) { int sw; if(hp2[i]!=hp1[i]) for(int j=i+1;j<Dim;j++) if(hp2[j]==hp1[i]) { sw=hp2[i]; hp2[i]=hp2[j]; hp2[j]=sw; p[i]=j; } } for(i=0;i<Dim;i++) { hp1[i]=0; hp2[i]=0; } } //?ü???·?? void Update(int* x,int* v) { int s; for(int i=0; i<Dim; i++) if(v[i]!=0) { s=x[i]; x[i]=x[v[i]]; x[v[i]]=s; } } void Run(int num)//????×??????¨????num·??? { for(int i=0;i<num;i++) { BirdsFly(); } for(int j=0;j<Dim;j++) { cout<<Pt[GBIndex].XBest[j]<<ends; if(Pt[GBIndex].XBest[j]==6) return; } } void main() { Initial(); Run(Kmax); }