粒子群算法实现

1、西南科技大学计算机学院2015-2016学年第1学期硕士研究生课程智能信息处理考核报告 题目： 粒子群优化算法 专业： 计算机科学与技术 学号： xxxxxxxxxxx 姓名： xxxx 2016年1月粒子群优化算法1.粒子群算法概述：粒子群算法是由Kennedy和Eberhart等于1995年提出的一种基于种群搜索的自适应进化计算技术1，算法最初受到鸟群觅食活动规律性的启发，利用群体智能建立了一个简化模型，用组织社会行为代替了进化算法的自然选择机制，通过种群间的个体协作实现对问题最优解的搜索。Reynolds对鸟群飞行的研究发现，鸟仅仅是追踪它有限数量的邻居但最终的整体结果是整个鸟群好像在一

2、个中心的控制之下，即复杂的全局行为是由简单规则的相互作用引起的。在PSO模型中，每个鸟就是PSO中的粒子，每个优化问题的潜在解都可以想象成d维搜索空间上的一个点，我们称之为“粒子”（Particle），所有的粒子都有一个被目标函数决定的适应值(Fitness Value )，每个粒子还有一个速度决定他们飞行的方向和距离。粒子根据自身和同伴的飞行经验动态进行调整，也就是说通过跟踪两个位置进行更新，一个是粒子自身找到的最优解pbest,即个体最好位置；另一个是整个种群当前找到的最优解gbest,即全局最好位置。速度和粒子位置的更新公式如下：vi = w * vi + c1 * rand() * (

3、pbesti - presenti)+ c2 * rand() * (gbest - presenti)presenti=presenti+vi其中vi代表第i个粒子的速度，w代表惯性权值,c1和c2表示学习参数，rand()表示在0-1之间的随机数,pbesti代表第i个粒子搜索到的最优值,gbest代表整个集群搜索到的最优值,presenti代表第i个粒子的当前位置。对于第一个公式，第一部分为微粒先前行为的惯性，第二部分为“认知（cognition）”部分，表示微粒本身的思考；第三部分为“社会（social）”部分，表示微粒间的信息共享与相互合作。“认知”部分可以由Thorndike的效应

4、法则（law of effect）所解释，即一个得到加强的随机行为在将来更有可能出现。这里的行为即“认知”，并假设获得正确的知识是得到加强的，这样的一个模型假定微粒被激励着去减小误差。“社会”部分可以由Bandura的替代强化（vicarious reinforcement）所解释。根据该理论的预期，当观察者观察到一个模型在加强某一行为时，将增加它实行该行为的几率，即微粒本身的认知将被其它微粒所模仿。这三个部分之间的相互平衡和制约决定了算法的主要性能。惯性因子w代表粒子上一次的速度对本次飞行速度的影响，它主要用于平衡粒子群的全局搜索能力和局部搜索能力。有研究表明，w对优化性能的影响很大，较大的

5、w值有利于跳出局部极小点，而较小的w值有利于算法收敛2。2.粒子群算法的改进途径：目前，学者们对粒子群算法作了各式各样的改进，主要从算法离散化、提高种群多样化、提高收敛速度三个方面进行。2.1算法离散化基于粒子群算法能有效地处理连续优化问题，但在实际工程中存在很多非连续优化类的问题，诸如组合优化问题等。因此，针对离散的优化问题，Kennedy和Eberhart3提出了二进制PSO算法，二进制PSO便于表示本身具有二进制特性的问题。一个典型的例子就是它可以用来表示神经网络的连接情况。例如，1可以代表网络上两个节点相连，而0代表网络上两个节点无连接。因而，一个二进制PSO可以用来优化神经网络结构。

6、此外，H.Yoshida4还提出了混合编码的粒子群算法，并用其求解电压控制问题。为了将粒子群算法应用于组合优化问题，Clerk5提出了有序编码的粒子群算法，并给出了以此种算法解决旅行商问题的具体模型，它的关键在于给出粒子位置和速度的类似定义。2.1提高种群多样化 PSO算法作为一种新的随机搜索算法，仍存在着早熟收敛、收敛速度慢两个难题，并且还有诸如种群多样性随代数增加下降过快、有可能不收敛到全局最优解的缺点。为了解决早熟收敛的问题，一些研究者提出了通过控制种群多样性来提高算法性能的方法。一方面通过解决粒子间的冲突和聚集问题5、分析粒子和种群最优位置的距离6、通过增加环境检测和响应等方法，提出了

7、不同的策略以增加种群多样性，使算法不至于过早陷入局部极小；另一方面，通过引入遗传算法的“变异”操作来增强全局搜索性能也是一种十分有效的方式。Lovbjger7提出了一种改善种群多样性的途径一自组织临界点控制,算法对每个粒子增加了当前临界值属性,如果两个粒子间的距离小于预定闽值则增加彼此的临界值,当个体临界值超过系统全局极限值时,则需重新分配其在搜索空间中的位置,以达到控制种群多样性的目的。值得注意的是，此方法对于pbest的重新初始化给出了两种基本方法:一种是使粒子忘记pbest并重新赋予一个新值;一种是给其一个小的推动力使其偏离pbest。Ratnaweera8在自组织算法的基础上给出了一种

8、变异操作随时间变化的自适应层次粒子群算法,并给出了适合变异操作的自适应参数选择方式，但是该算法消除了速度公式中的惯性部分,其发生变异条件是粒子速度为零,使其不能快速、有效地逃出局部极小点。以上这些改进通常阳氏了算法的局部收敛速度,但却能获得了更好的优化结果,这在多模态和较复杂问题的优化中体现的尤为明显。2.1提高种群多样化提高收敛速度的方法主要是修改PSO算法的速度更新方程。这些方法通常会得到较好的局部优化结果,然而对于一些多模态优化问题则会导致性能下降。惯性因子的大小决定着粒子保持原来运动速度的程度,也可以说是粒子对自身运动状态的信任。引入惯性因子,通过调节惯性因子w是早期使用较多的提高收敛

9、速度的办法。Shi和Ebehtart9通过研究发现w取值在 0.8,1.2具有较高的收敛速度,如果w过大(例如l.2)则会导致算法很难收敛。惯性因子与模拟退火算法中的温度参数很相像。模拟退火算法中一个重要过程是使用温度进度表来调节系统温度,温度越高,算法跳出局部极值搜索到其他空间的概率就越大。因此具有自适应特性的惯性因子也可以看作是模拟退火算法中的温度进度表。此外, Angeline10借鉴了遗传算法中选择操作用来提高收敛到局部极值的速度,但却损失了大范围搜索能力,从而导致无法搜索到全局最优。Clerc11引入了收缩因子K来确保算法的收敛性,从而达到提高局部收敛速度的目的，此方法不单单调节速度

10、更新方程中的某个参数,而是针对w、cl和c2进行整体调节,以此来提高收敛速度。3. 粒子群算法实现TSP问题 3.1 TSP问题TSP问题（Travelling Salesman Problem）即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路 径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。TSP问题可以分为两类，一类是对称TSP问题（Symmetric TSP），另一类

11、是非对称问题（Asymmetric TSP）。所有的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）package

12、 pso_1;import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Random; public class PSO private int bestNum; private float w; private int MAX_GEN;/ 迭代次数 private int scale;/ 种群规模 private

13、int cityNum; / 城市数量，编码长度 private int t;/ 当前代数 private int distance; / 距离矩阵 private int oPopulation;/ 粒子群 private ArrayListArrayList listV;/ 每科粒子的初始交换序列 private int Pd;/ 一颗粒子历代中出现最好的解， private int vPd;/ 解的评价值 private int Pgd;/ 整个粒子群经历过的的最好的解，每个粒子都能记住自己搜索到的最好解 private int vPgd;/ 最好的解的评价值 private int b

14、estT;/ 最佳出现代数 private int fitness;/ 种群适应度，表示种群中各个个体的适应度 private Random random; public PSO() /* * constructor of GA * * param n * 城市数量 * param g * 运行代数 * param w * 权重 */ public PSO(int n, int g, int s, float w) this.cityNum = n; this.MAX_GEN = g; this.scale = s; this.w = w; / 给编译器一条指令，告诉它对被批注的代码元素内部的

15、某些警告保持静默 SuppressWarnings(resource) /* * 初始化PSO算法类 * param filename 数据文件名，该文件存储所有城市节点坐标数据 * throws IOException */ private void init(String filename) throws IOException / 读取数据 int x; int y; String strbuff; BufferedReader data = new BufferedReader(new InputStreamReader( new FileInputStream(filename);

16、distance = new intcityNumcityNum; x = new intcityNum; y = new intcityNum; for (int i = 0; i cityNum; i+) / 读取一行数据，数据格式1 6734 1453 strbuff = data.readLine(); / 字符分割 String strcol = strbuff.split( ); xi = Integer.valueOf(strcol1);/ x坐标 yi = Integer.valueOf(strcol2);/ y坐标 / 计算距离矩阵 / ，针对具体问题，距离计算方法也不一样，

17、此处用的是att48作为案例，它有48个城市，距离计算方法为伪欧氏距离，最优值为10628 for (int i = 0; i cityNum - 1; i+) distanceii = 0; / 对角线为0 for (int j = i + 1; j cityNum; j+) double rij = Math .sqrt(xi - xj) * (xi - xj) + (yi - yj) * (yi - yj) / 10.0); / 四舍五入，取整 int tij = (int) Math.round(rij); if (tij rij) distanceij = tij + 1; dist

18、anceji = distanceij; else distanceij = tij; distanceji = distanceij; distancecityNum - 1cityNum - 1 = 0; oPopulation = new intscalecityNum; fitness = new intscale; Pd = new intscalecityNum; vPd = new intscale; Pgd = new intcityNum; vPgd = Integer.MAX_VALUE; / nPopulation = new intscalecityNum; bestT

19、 = 0; t = 0; random = new Random(System.currentTimeMillis(); / 初始化种群，多种随机生成办法 void initGroup() int i, j, k; for (k = 0; k scale; k+)/ 种群数 oPopulationk0 = random.nextInt(65535) % cityNum; for (i = 1; i cityNum;)/ 粒子个数 oPopulationki = random.nextInt(65535) % cityNum; for (j = 0; j i; j+) if (oPopulati

20、onki = oPopulationkj) break; if (j = i) i+; void initListV() int ra; int raA; int raB; listV = new ArrayListArrayList(); for (int i = 0; i scale; i+) ArrayList list = new ArrayList(); ra = random.nextInt(65535) % cityNum; for (int j = 0; j ra; j+) raA = random.nextInt(65535) % cityNum; raB = random.

21、nextInt(65535) % cityNum; while (raA = raB) raB = random.nextInt(65535) % cityNum; / raA与raB不一样 SO s = new SO(raA, raB); list.add(s); listV.add(list); public int evaluate(int chr) / 0123 int len = 0; / 编码，起始城市,城市1,城市2.城市n for (int i = 1; i cityNum; i+) len += distancechri - 1chri; / 城市n,起始城市 len +=

22、distancechrcityNum - 1chr0; return len; / 求一个基本交换序列作用于编码arr后的编码 public void add(int arr, ArrayList list) int temp = -1; SO s; for (int i = 0; i list.size(); i+) s = list.get(i); temp = arrs.getX(); arrs.getX() = arrs.getY(); arrs.getY() = temp; / 求两个编码的基本交换序列，如A-B=SS public ArrayList minus(int a, in

23、t b) int temp = b.clone(); int index; / 交换子 SO s; / 交换序列 ArrayList list = new ArrayList(); for (int i = 0; i cityNum; i+) if (ai != tempi) / 在temp中找出与ai相同数值的下标index index = findNum(temp, ai); / 在temp中交换下标i与下标index的值 changeIndex(temp, i, index); / 记住交换子 s = new SO(i, index); / 保存交换子 list.add(s); retu

24、rn list; / 在arr数组中查找num，返回num的下标 public int findNum(int arr, int num) int index = -1; for (int i = 0; i cityNum; i+) if (arri = num) index = i; break; return index; / 将数组arr下标index1与下标index2的值交换 public void changeIndex(int arr, int index1, int index2) int temp = arrindex1; arrindex1 = arrindex2; arr

25、index2 = temp; / 二维数组拷贝 public void copyarray(int from, int to) for (int i = 0; i scale; i+) for (int j = 0; j cityNum; j+) toij = fromij; / 一维数组拷贝 public void copyarrayNum(int from, int to) for (int i = 0; i cityNum; i+) toi = fromi; public void evolution() int i, j, k; int len = 0; float ra = 0f;

26、ArrayList Vi; / 迭代一次 for (t = 0; t MAX_GEN; t+) / 对于每颗粒子 for (i = 0; i scale; i+) if(i=bestNum) continue; ArrayList Vii = new ArrayList(); /System.out.println(-); / 更新速度 / Vii=wVi+ra(Pid-Xid)+rb(Pgd-Xid) Vi = listV.get(i); / wVi+表示获取Vi中size*w取整个交换序列 len = (int) (Vi.size() * w); /越界判断 /if(lencityNum)

27、 len=cityNum; /System.out.println(w:+w+ len:+len+ Vi.size():+Vi.size(); for (j = 0; j len; j+) Vii.add(Vi.get(j); / Pid-Xid ArrayList a = minus(Pdi, oPopulationi); ra = random.nextFloat(); / ra(Pid-Xid)+ len = (int) (a.size() * ra); /越界判断 /if(lencityNum) len=cityNum; /System.out.println(ra:+ra+ len:

28、+len+ a.size():+a.size(); for (j = 0; j len; j+) Vii.add(a.get(j); / Pid-Xid ArrayList b = minus(Pgd, oPopulationi); ra = random.nextFloat(); / ra(Pid-Xid)+ len = (int) (b.size() * ra); /越界判断 /if(lencityNum) len=cityNum; /System.out.println(ra:+ra+ len:+len+ b.size():+b.size(); for (j = 0; j len; j+

29、) SO tt= b.get(j); Vii.add(tt); / 保存新Vii listV.add(i, Vii); / 更新位置 / Xid=Xid+Vid add(oPopulationi, Vii); / 计算新粒子群适应度，Fitnessmax,选出最好的解 for (k = 0; k fitnessk) vPdk = fitnessk; copyarrayNum(oPopulationk, Pdk); bestNum=k; if (vPgd vPdk) System.out.println(最佳长度+vPgd+ 代数：+bestT); bestT = t; vPgd = vPdk;

30、 copyarrayNum(Pdk, Pgd); public void solve() int i; int k; initGroup(); initListV(); / 每颗粒子记住自己最好的解 copyarray(oPopulation, Pd); / 计算初始化种群适应度，Fitnessmax,选出最好的解 for (k = 0; k vPdk) vPgd = vPdk; copyarrayNum(Pdk, Pgd); bestNum=k; / 打印 System.out.println(初始粒子群.); for (k = 0; k scale; k+) for (i = 0; i c

31、ityNum; i+) System.out.print(oPopulationki + ,); System.out.println(); System.out.println(- + fitnessk); / 进化 evolution(); / 打印 System.out.println(最后粒子群.); for (k = 0; k scale; k+) for (i = 0; i cityNum; i+) System.out.print(oPopulationki + ,); System.out.println(); System.out.println(- + fitnessk);

32、 System.out.println(最佳长度出现代数：); System.out.println(bestT); System.out.println(最佳长度); System.out.println(vPgd); System.out.println(最佳路径：); for (i = 0; i cityNum; i+) System.out.print(Pgdi + ,); /* * param args * throws IOException */ public static void main(String args) throws IOException System.out.

33、println(Start.); PSO pso = new PSO(48, 5000, 30, 0.5f); pso.init(c:/data.txt); pso.solve(); 3.3 运行结果截图4.总结通过对这个实验报告的书写，让我对粒子群算法从一无所知到有所了解，尽管对改进算法没有什么思路，但是至少可以让自己学习这个基本的算法，然后用自己熟悉的编程语言实现出来，学以致用。在以后学习的每一个算法，都应该抱以这样的学习态度，亲自编写，而不是纯看理论知识，让晦涩难懂的算法使自己打退堂鼓。对于该算法的学习还应该更加深入，让自己能提出自己独特的见解最好。参考文献：1J Kennedy,R C

34、 Eberthart.Swarm Intelligence.Morgan Kaufmann Publishers,SanFrancisico,CA,2001.2Y Shi, R C Eberthart.A modified particle swarm optimizer.Proceedings of the International Joint Conference on Evolutionary Computation,1998:69-73.3 J Kennedy,R C Eberthart. A discrete binary version of the particle swarm

35、 optimization algorithm.Proceeding of International Conference on System,Man and Cybemetics,1997:4104-4109.4Yoshida H,Fukuama Y,Takayama S A.A Particle Swarm Optimization for Reactive Power and Voltage Control in Electric Power System Considering Voltage Security Assessment.IEEE International Conference on System,Man and Cybemetics,1999,6(497):502.5 T Krink,J S Vesterstrom,J Riget. Parti