粒子群算法实现

西南科技大学计算机学院2015----2016学年第1学期硕士研究生课程《智能信息处理》考核报告题目：粒子群优化算法专业：计算机科学与技术学号：xxxxxxxxxxx姓名：xxxx2016年1月粒子群优化算法1.粒子群算法概述：粒子群算法是由Kennedy和Eberhart等于1995年提出的一种基于种群搜索的自适应进化计算技术[1]，算法最初受到鸟群觅食活动规律性的启发，利用群体智能建立了一个简化模型，用组织社会行为代替了进化算法的自然选择机制，通过种群间的个体协作实现对问题最优解的搜索。Reynolds对鸟群飞行的研究发现，鸟仅仅是追踪它有限数量的邻居但最终的整体结果是整个鸟群好像在一个中心的控制之下，即复杂的全局行为是由简单规则的相互作用引起的。在PSO模型中，每个鸟就是PSO中的粒子，每个优化问题的潜在解都可以想象成d维搜索空间上的一个点，我们称之为“粒子”（Particle），所有的粒子都有一个被目标函数决定的适应值(FitnessValue)，每个粒子还有一个速度决定他们飞行的方向和距离。粒子根据自身和同伴的飞行经验动态进行调整，也就是说通过跟踪两个位置进行更新，一个是粒子自身找到的最优解pbest,即个体最好位置；另一个是整个种群当前找到的最优解gbest,即全局最好位置。速度和粒子位置的更新公式如下：v[i]=w*v[i]+c1*rand()*(pbest[i]-present[i])+c2*rand()*(gbest-present[i])present[i]=present[i]+v[i]其中v[i]代表第i个粒子的速度，w代表惯性权值,c1和c2表示学习参数，rand()表示在0-1之间的随机数,pbest[i]代表第i个粒子搜索到的最优值,gbest代表整个集群搜索到的最优值,present[i]代表第i个粒子的当前位置。对于第一个公式，第一部分为微粒先前行为的惯性，第二部分为“认知（cognition）”部分，表示微粒本身的思考；第三部分为“社会（social）”部分，表示微粒间的信息共享与相互合作。“认知”部分可以由Thorndike的效应法则（lawofeffect）所解释，即一个得到加强的随机行为在将来更有可能出现。这里的行为即“认知”，并假设获得正确的知识是得到加强的，这样的一个模型假定微粒被激励着去减小误差。“社会”部分可以由Bandura的替代强化（vicariousreinforcement）所解释。根据该理论的预期，当观察者观察到一个模型在加强某一行为时，将增加它实行该行为的几率，即微粒本身的认知将被其它微粒所模仿。这三个部分之间的相互平衡和制约决定了算法的主要性能。惯性因子w代表粒子上一次的速度对本次飞行速度的影响，它主要用于平衡粒子群的全局搜索能力和局部搜索能力。有研究表明，w对优化性能的影响很大，较大的w值有利于跳出局部极小点，而较小的w值有利于算法收敛[2]。2.粒子群算法的改进途径：目前，学者们对粒子群算法作了各式各样的改进，主要从算法离散化、提高种群多样化、提高收敛速度三个方面进行。2.1算法离散化基于粒子群算法能有效地处理连续优化问题，但在实际工程中存在很多非连续优化类的问题，诸如组合优化问题等。因此，针对离散的优化问题，Kennedy和Eberhart[3]提出了二进制PSO算法，二进制PSO便于表示本身具有二进制特性的问题。一个典型的例子就是它可以用来表示神经网络的连接情况。例如，1可以代表网络上两个节点相连，而0代表网络上两个节点无连接。因而，一个二进制PSO可以用来优化神经网络结构。此外，H.Yoshida[4]还提出了混合编码的粒子群算法，并用其求解电压控制问题。为了将粒子群算法应用于组合优化问题，Clerk[5]提出了有序编码的粒子群算法，并给出了以此种算法解决旅行商问题的具体模型，它的关键在于给出粒子位置和速度的类似定义。2.1提高种群多样化PSO算法作为一种新的随机搜索算法，仍存在着早熟收敛、收敛速度慢两个难题，并且还有诸如种群多样性随代数增加下降过快、有可能不收敛到全局最优解的缺点。为了解决早熟收敛的问题，一些研究者提出了通过控制种群多样性来提高算法性能的方法。一方面通过解决粒子间的冲突和聚集问题[5]、分析粒子和种群最优位置的距离[6]、通过增加环境检测和响应等方法，提出了不同的策略以增加种群多样性，使算法不至于过早陷入局部极小；另一方面，通过引入遗传算法的“变异”操作来增强全局搜索性能也是一种十分有效的方式。Lovbjger[7]提出了一种改善种群多样性的途径一自组织临界点控制,算法对每个粒子增加了当前临界值属性,如果两个粒子间的距离小于预定闽值则增加彼此的临界值,当个体临界值超过系统全局极限值时,则需重新分配其在搜索空间中的位置,以达到控制种群多样性的目的。值得注意的是，此方法对于pbest的重新初始化给出了两种基本方法:一种是使粒子忘记pbest并重新赋予一个新值;一种是给其一个小的推动力使其偏离pbest。Ratnaweera[8]在自组织算法的基础上给出了一种变异操作随时间变化的自适应层次粒子群算法,并给出了适合变异操作的自适应参数选择方式，但是该算法消除了速度公式中的惯性部分,其发生变异条件是粒子速度为零,使其不能快速、有效地逃出局部极小点。以上这些改进通常阳氏了算法的局部收敛速度,但却能获得了更好的优化结果,这在多模态和较复杂问题的优化中体现的尤为明显。2.1提高种群多样化提高收敛速度的方法主要是修改PSO算法的速度更新方程。这些方法通常会得到较好的局部优化结果,然而对于一些多模态优化问题则会导致性能下降。惯性因子的大小决定着粒子保持原来运动速度的程度,也可以说是粒子对自身运动状态的信任。引入惯性因子,通过调节惯性因子w是早期使用较多的提高收敛速度的办法。Shi和Ebehtart[9]通过研究发现w取值在[0.8,1.2]具有较高的收敛速度,如果w过大(例如l.2)则会导致算法很难收敛。惯性因子与模拟退火算法中的温度参数很相像。模拟退火算法中一个重要过程是使用温度进度表来调节系统温度,温度越高,算法跳出局部极值搜索到其他空间的概率就越大。因此具有自适应特性的惯性因子也可以看作是模拟退火算法中的温度进度表。此外,Angeline[10]借鉴了遗传算法中选择操作用来提高收敛到局部极值的速度,但却损失了大范围搜索能力,从而导致无法搜索到全局最优。Clerc[11]引入了收缩因子K来确保算法的收敛性,从而达到提高局部收敛速度的目的，此方法不单单调节速度更新方程中的某个参数,而是针对w、cl和c2进行整体调节,以此来提高收敛速度。3.粒子群算法实现TSP问题3.1TSP问题TSP问题（TravellingSalesmanProblem）即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。TSP问题可以分为两类，一类是对称TSP问题（SymmetricTSP），另一类是非对称问题（AsymmetricTSP）。所有的TSP问题都可以用一个图（Graph）来描述：V={c1,c2,…,ci,…,cn}，i=1,2,…,n，是所有城市的集合.ci表示第i个城市，n为城市的数目；E={(r,s):r,s∈V}是所有城市之间连接的集合；C={crs:r,s∈V}是所有城市之间连接的成本度量（一般为城市之间的距离）；如果crs=csr,那么该TSP问题为对称的，否则为非对称的。一个TSP问题可以表达为：求解遍历图G=(V,E,C)，所有的节点一次并且回到起始节点，使得连接这些节点的路径成本最低。3.2具体实现代码（java）packagepso_1;importjava.io.BufferedReader;importjava.io.FileInputStream;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.ArrayList;importjava.util.Random;publicclassPSO{privateintbestNum;privatefloatw;privateintMAX_GEN;//迭代次数privateintscale;//种群规模privateintcityNum;//城市数量，编码长度privateintt;//当前代数privateint[][]distance;//距离矩阵privateint[][]oPopulation;//粒子群privateArrayListArrayListSOlistV;//每科粒子的初始交换序列privateint[][]Pd;//一颗粒子历代中出现最好的解，privateint[]vPd;//解的评价值privateint[]Pgd;//整个粒子群经历过的的最好的解，每个粒子都能记住自己搜索到的最好解privateintvPgd;//最好的解的评价值privateintbestT;//最佳出现代数privateint[]fitness;//种群适应度，表示种群中各个个体的适应度privateRandomrandom;publicPSO(){}/***constructorofGA**@paramn*城市数量*@paramg*运行代数*@paramw*权重**/publicPSO(intn,intg,ints,floatw){this.cityNum=n;this.MAX_GEN=g;this.scale=s;this.w=w;}//给编译器一条指令，告诉它对被批注的代码元素内部的某些警告保持静默@SuppressWarnings(resource)/***初始化PSO算法类*@paramfilename数据文件名，该文件存储所有城市节点坐标数据*@throwsIOException*/privatevoidinit(Stringfilename)throwsIOException{//读取数据int[]x;int[]y;Stringstrbuff;BufferedReaderdata=newBufferedReader(newInputStreamReader(newFileInputStream(filename)));distance=newint[cityNum][cityNum];x=newint[cityNum];y=newint[cityNum];for(inti=0;icityNum;i++){//读取一行数据，数据格式167341453strbuff=data.readLine();//字符分割String[]strcol=strbuff.split();x[i]=Integer.valueOf(strcol[1]);//x坐标y[i]=Integer.valueOf(strcol[2]);//y坐标}//计算距离矩阵//，针对具体问题，距离计算方法也不一样，此处用的是att48作为案例，它有48个城市，距离计算方法为伪欧氏距离，最优值为10628for(inti=0;icityNum-1;i++){distance[i][i]=0;//对角线为0for(intj=i+1;jcityNum;j++){doublerij=Math.sqrt(((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))/10.0);//四舍五入，取整inttij=(int)Math.round(rij);if(tijrij){distance[i][j]=tij+1;distance[j][i]=distance[i][j];}else{distance[i][j