学士学位论文--用于软件测试生成的微粒群优化方法研究.doc

中国矿业大学
本科生毕业设计

设计题目： 用于软件测试生成的微粒群优化方法研究

中国矿业大学徐海学院毕业设计任务书

任务下达日期：
毕业设计日期：

毕业设计题目：用于软件测试生成的微粒群优化方法研究

毕业设计专题题目：

毕业设计主要内容和要求：
结合基本微粒群优化算法的原理，研究该算法在软件测试方面的应用；针对微粒群优化算法的编码特点，运用赫夫曼编码设计出解决问题的步骤；利用C语言编程，仿真验证PSO在软件测试中的可行性。具体设计要求如下：
1、熟悉软件测试的原理和一般方法，重点分析了遗传算法在软件测试方面的应用；
2、熟悉基本粒子群算法的原理和特点，讨论其改进方式，并分析比较算法的优劣性；
3、设计用于软件测试路径覆盖的微粒群优化算法；利用C语言编程仿真，并通过实验论证其有效性。

指导教师签字：

郑 重 声 明
本人所呈交的毕业设计，是在导师的指导下，独立进行研究所取得的成果。所有数据、图片资料真实可靠。尽我所知，除文中已经注明引用的内容外，本毕业设计的研究成果不包含他人享有著作权的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确的方式标明。本论文属于原创。本毕业设计的知识产权归属于培养单位。

本人签名： 日期：

中国矿业大学毕业设计指导教师评阅书

指导教师评语（①基础理论及基本技能的掌握；②独立解决实际问题的能力；③研究内容的理论依据和技术方法；④取得的主要成果及创新点；⑤工作态度及工作量；⑥总体评价及建议成绩；⑦存在问题；⑧是否同意答辩等）：

成 绩： 指导教师签字：
年 月 日
中国矿业大学毕业设计评阅教师评阅书

评阅教师评语（①选题的意义；②基础理论及基本技能的掌握；③综合运用所学知识解决实际问题的能力；③工作量的大小；④取得的主要成果及创新点；⑤写作的规范程度；⑥总体评价及建议成绩；⑦存在问题；⑧是否同意答辩等）：

成 绩： 评阅教师签字：
年 月 日
中国矿业大学毕业设计答辩及综合成绩
答 辩 情 况
提 出 问 题
回 答 问 题
正 确
基本
正确
有一般性错误
有原则性错误
没有
回答

答辩委员会评语及建议成绩：

答辩委员会主任签字：
年 月 日
学院领导小组综合评定成绩：

学院领导小组负责人：
年 月 日

摘 要
作为进化算法的一个重要分支，微粒群优化算法的理论研究一直受到学者们的广泛关注。微粒群优化算法由通过随机初始化一群粒子利用群体迭代使粒子追随自身找到的最好解和群体找到的最好解完成优化。由于其原理简单、调节参数少、执行效率高、易于实现，现已广泛应用于处理交通运输管理、电力系统配置、工业生产调度、工程设计与优化等各类复杂的优化问题。目前，微粒群优化算法成为一种用于软件测试的新型智能优化算法。
本文结合路径覆盖问题的特点，设计用于软件测试的微粒群优化算法。该方法基于赫夫曼编码方式建立微粒群的算法框架，通过不断更新微粒的极值点、速度和位置，找到软件测试问题的最优解。针对其目标函数和微粒群的编码方式，运用了C语言建立仿真平台，通过实验对比验证了微粒群优化算法在软件测试中的优越性。
关键词：软件测试； 微粒群优化算法； 赫夫曼编码； C语言编程

ABSTRACT
As evolutionary algorithm as an important branch of particle swarm optimization algorithm theory research has received extensive attention of scholars. Particle swarm optimization algorithm by through the random initial a group of particle using iterative particle group to follow their own the best solution to find the best solution and groups find complete optimization. Due to its principle is simple, adjust the parameter, less efficient, easy to realize, is widely used in processing transportation management, power system configuration, industrial production scheduling, engineering design and optimization of complex optimization problems. At present, the particle swarm optimization algorithm is used in software testing as a new type of intelligent optimization algorithm.
Based on the characteristics of the path coverage problem, designed for software testing of particle swarm optimization algorithm. Based on the establishment of particles coding way hoffman the algorithm framework, and through the update particle of extreme value point, speed and position, find software testing the optimal solution of the problem. According to the target function and particle swarm the coding method, using C language building simulation platform, through the contrast verify the particle swarm optimization algorithm in software testing the superiority.
Keywords：Software testing; Particle swarm optimization algorithm; Hoffman code; C programming language

目 录
第一章 绪论·····································································1
1.1研究背景及意义··························································1
1.2研究内容及目标··························································1
1.3论文框架··································································2
第二章 相关工作综述···························································3
2.1 软件测试问题····························································3
2.1.1软件测试的概念·····················································3
2.1.2软件测试的目的、意义及方法·····································3
2.1.3遗传算法在软件测试中的应用·····································5
2.2 微粒群优化算法·························································6
2.2.1 微粒群优化算法的产生············································6
2.2.2 微粒群优化算法的基本原理·······································7
2.2.3 微粒群优化算法的发展···········································10
2.2.4 微粒群优化算法与其他算法的比较······························11
2.2.5 微粒群优化算法的经典改进······································12
2.2.6 微粒群优化算法的应用···········································16
2.3 本章小结································································16
第三章 用于测试路径覆盖数据生成的微粒群优化算法····················17
3.1 微粒编码································································17
3.1.1 赫夫曼编码························································17
3.1.2目标途径的编码····················································18
3.1.3 被测程序的插桩···················································19
3.2 适应值计算·····························································20
3.3 微粒极值点的更新·····················································22
3.4 粒子位置的更新························································23
3.5 算法步骤································································23
3.6 本章小结································································24
第四章 实验仿真·······························································25
4.1 C 语言的开发环境简介················································25
4.1.1 C语言的发展过程·················································25
4.1.2 C语言的特点·······················································25
4.1.3 C语言版本·························································26
4.1.4 C和C++···························································26
4.1.5 面向对象的程序设计语言········································26
4.1.6 源程序的结构特点················································26
4.2 实验内容································································27
4.2.1 参数设置···························································27
4.2.2 在三角形分类程序中的实验······································28
4.2.3 在其他3个基准测试程序中的实验······························29
4.3 敏感参数实验分析·····················································30
4.4 本章小结································································32
第五章 结论与展望····························································33
参考文献··········································································34
附 录··········································································36
翻译部分··········································································53
英文翻译·······································································53
中文翻译·······································································59
致 谢··········································································65

中国矿业大学2012届本科生毕业设计（论文）
第一章 绪论
1.1研究背景及意义
软件测试是保障软件质量的重要手段[1]，测试的意义在于发现程序中的错误、有效定义和实现软件成分由低级到高级的组装过程、验证软件是否满足任务书和系统定义文档规定的技术要求以及为软件质量模型的建立提供依据。通过软件测试可以确认软件的质量、提供信息还可以测试软件开发的过程。
软件测试问题的基本研究存在很多方向，例如连接测试、文档测试、负载测试、集成测试、单元测试等，本文考虑软件测试中的路径覆盖问题。覆盖问题的普遍性和重要意义。近几年。基于启发式搜索的路径覆盖测试数据生成技术受到学者们的关注。其中，遗传算法( G e n e t i c A l g o r i t h m s,G A) 是用于测试数据的自动生成的有效方法。目前已有许多研究成果 ，如 C h e n 等采用多种群GA生成覆盖路径的测试数据[2]，So f o k l e o u s 等基于GA建立了动态软件测试框架[3]，R a j a p p a 等利用GA并结合图论知识,生成软件的测试用例[4] ，B o u c h a c h i a将免疫GA用于测试数据生成中[4] 等 。
作为一种较新的启发式搜索算法，微粒群优化(Particle Swarm Optimization，PSO)算法是由Eberhart和Kennedy于1995年提出的，其思想来源于对鸟群、鱼群的模拟。PSO通过微粒追随自己找到的最好解和整个群的最好解来完成优化。该算法简单易实现,可调参数少,已得到广泛研究应用。本文将微粒群优化算法用于软件测试问题，设计一种新的测试数据生成方法。所得成果不仅可以拓宽微粒群优化的应用范围，而且可以提高算法的效率，具有重要的参考价格和借鉴意义。
1.2研究内容及目标
本文研究软件测试数据生成的微粒群优化方法，主要研究内容包括：
（1） 路径编码及模型的建立。将被测程序表示成一棵二叉树，对目标路径赫夫曼编码方法表示成二进制串；设计合适的适应度函数评价测试数据的优劣。
（2）用于多路径覆盖测试数据生成的微粒群优化算法设计。采用微粒群优化生成多个测试数据，给出算法的具体执行步骤，以及微粒位置更新、微粒极值的更新等关键问题的解决方法。
（3）基于C语言实现相关算法；将所提方法用于基准程序的路径覆盖测试数据生成，并与已有方法比较，验证所提方法的有效性。
通过上述研究，期望设计一种基于微粒群优化的新型测试数据生成方法，并给出其仿真平台。
1.3论文框架
本文对软件测试的优化求解展开研究，设计一种基于微粒群优化的求解方法，给出微粒位置更新、微粒极值的更新等关键问题的解决方法；在上述方法的基础上，开发基于PSO算法的C语言仿真，进一步完善算法的实用性和可控性。各章内容提要简列如下：
第一章 绪论部分，分析课题的研究背景及意义，简述了论文的研究内容，明确了论文的研究目标。
第二章 详细介绍相关研究工作，首先结合软件测试问题当前的研究热点，对其基本原理以及研究方法作简单介绍，重点介绍遗传算法在该领域的应用，并分析目前研究方法中存在的不足之处。其次,对微粒群优化算法做了详尽的叙述，包括算法的历史来源、发展前景、改进算法、应用领域等，分析了算法的优劣之处，为论文提供了比较系统的理论依据。
第三章给出用于软件测试问题的改进微粒群优化算法，详细介绍了微粒编码和微粒极值点更新等方法，以及算法的步骤。
第四章利用C语言的编程实现微粒群优化算法在软件测试中的应用，并通过程序测试结果验证其可行性。
第五章总结与展望部分，回顾本文完成的主要工作，分析论文完成的目标及存在的不足之处，明确下一步的研究方向，同时对PSO在软件测试领域的应用前景进行了分析。

第二章 相关工作综述
在第一章中已经阐述了本文研究的方向和主要内容，本章主要详细介绍了软件测试问题和微粒群优化算法的相关研究现状，为后面两章做好铺垫。
2.1软件测试问题
2.1.1软件测试的概念
软件测试(Software testing)是软件生存期(Software life cycle)中的一个重要阶段，是软件质量保证的关键步骤。软件测试就是在软件投入运行前，对软件需求分析、设计规格说明和编码的最终复审，是软件质量保证的关键步骤。软件测试是为了发现错误而执行程序的过程。或者说，软件测试是根据软件开发各阶段的规格说明和程序的内部结构而精心设计一批测试用例(即输人数据及其预测的输出结果)，并利用这些用例去运行程序，以发现程序错误或缺陷的过程。
软件测试与软件开发各阶段的关系。软件开发的过程是一自顶向下，逐步细化的过程，而测试过程则是依相反的顺序安排的自底向上，逐步集成的过程。软件测试在软件生存期中横跨两个阶段：通常在编写出每一个模块之后就对它做必要的测试即单元测试。编码与单元测试属于软件生存期中同一个阶段。在结束这个阶段之后，对软件系统还要进行各种综合测试，这是软件生存期中的另一个独立的阶段，即测试阶段。目前随着软件开发平台及软件设计思想的进步和发展，软件测试已不像传统测试那样，仅存在于程序完成之后，而是跨越了整个软件开发流程，涵盖整个软件生命周期，这样才能确保软件开发过程中的每个阶段禁得起考验。
2.1.2软件测试的目的、意义及方法
软件测试就是在受控制的条件下对系统或应用程序进行操作并评价操作结果的过程，所谓控制条件应包括正常条件与非正常条件。软件测试过程中应该故意地去促使错误的发生，也就是事情在不该出现的时候出现或者在应 该出现的时候没有出现。从本质上说，软件测试是“探测”，在“探测”中发现软件的毛病。软件测试贯穿于软件定义与开发的整个周期，软件的需求规格说明书，结构设计及程序编码，都属于软件测试的对象。
软件测试是保证软件质量的重要活动，它贯穿于整个软件开发生命周期，是软件项目实施的不可缺少的环节。软件测试的目的是为了保证软件产品的最终质量[5]，在软件开发过程中对软件产品进行质量监控。软件测试的主要目的有：(1)为了寻找错误，并尽可能为修正错误提供更多的信息。(2)为了证明软件有错误，而不证明软件没有错误。(3)一个好的测试用例是在于它能发现至今未发现的错误。(4)一个成功的测试是发现了至今未发现的错误的测试[6]。换言之，测试的目的是想以最少的时间和人力，系统地找出软件中潜在的各种错误和缺陷。测试时为了证明程序有错误或缺陷，而不能保证程序没有错误。
软件测试的方法和技术是多种多样的，对于软件测试技术，可以从不同的角度加以分类，可以分为以下几个类别：
(1)黑盒测试。黑盒测试也称功能测试或数据驱动测试，它是在已知产品所应具有的功能情况下，通过测试来检测每个功能是否都能正常使用。在测试时，把程序看作一个不能打开的黑盒子，在完全不考虑程序内部结构和内部特性的情况下，测试者在程序接口进行测试，它只检查程序功能是否按照需求规格说明书的规定正常使用，程序是否能适当地接收输入数据而产生正确的输出信息并且保持外部信息(如：数据库或文件)的完整性。黑盒法着眼于程序外部结构，不考虑内部逻辑结构，只针对软件界面和软件功能进行测试，它主要用于软件验收测试。黑盒法是穷举输入测试，只有把所有可能的输入都作为测试情况使用，才能以这种方法查出程序中所有的错误。测试情况实际上有无穷多个，人们不仅要测试所有合法的输入，而且还要对那些不合法但是可能的输入进行测试。黑河测试时一用户的观点，从输入数据与输出数据的对应关系出发进行测试的，它不涉及到程序的内部结构。黑盒测试注重于测试软件的功能要求，主要试图发现软件中的功能错误、界面错误、数据结构或外部数据库访问错误、性能错误、初始化和终止错误等。
(2)白盒测试。白盒测试也称结构测试或逻辑驱动测试，它是知道产品内部工作过程，可通过测试来检测产品内部动作是否按照规格说明书的规定正常进行，按照程序内部的结构测试程序，检验程序中的每条通路是否都有能按预定要求正确工作，而不涉及它的功能，白盒测试的主要方法有逻辑驱动、基路测试等，主要用于软件验证。白盒测试是基于代码的测试，测试人员通过阅读程序代码或者通过使用开发工具中的单步调试来判断软件的质量。白盒测试需要全面了解程序内部逻辑结构、对所有逻辑路径进行测试。白盒测试是穷举路径测试，在使用这一方案时，测试者必须检查程序的内部结构，从检查程序的逻辑着手，得出测试数据。
(3)一种新的软件测试法——灰盒法。灰盒法是在综合考虑白盒法和黑盒法基础上提出的一种方法，它以程序的主要性能和主要功能为测试依据，测试方法主要根据程序的程序图、功能说明书以及测试者的实践经验来设计，这里所说的主要性能和主要功能凭借测试者的经验来确定，即可把容易发生错误的变量域及程序图(非流程图)作为测试的内容，而把那些不容易发生错误的变量输入和流程图中的不影响或不改变内部逻辑的细节忽略。事实上，许多测试工作是在不完全了解程序的内部逻辑时进行，这也就是“灰色”的由来。
(4)功能测试。功能测试就是检查软件的功能是否正确，其依据是需求文档，如需求规格说明书。由于正确性是软件最重要的质量因素，所以功能测试必不可少。功能测试的基本方法是构造一些合理输入(在需求范围之内)，检查输出是否与期望的相同。如果两者不一致，即表明功能有误。也有例外的情况，如需求规格说明书中的某个功能写错了，而实际上软件的功能却是正确的，这时要更改的是需求规格说明书。功能测试看起来比较简单，只要看得懂需求规格说明书，谁都会做。难点在于如何构造有效的输入。由于输入空间通常是无限的，穷举测试显然行不通。功能测试有两种比较好的测试方法：等价划分法和边界值分析法。功能测试的目标是核实数据的接受、处理和检索是否正确，以及业务规则的实施是否恰当。此类测试基于黑盒技术，该技术通过图形用户界面与应用程序进行交互，并对交互的输出或结果进行分析[7]，以此来核实应用程序及其内部进程。
(5)U 1测试。UI测试是对用户界面的风格、文字、图片、背景的测试。用户界面(UI)测试用于核实用户与软件之间的交互。UI测试的目标是确保用户界面中的每个对象能按照预期的方式运行，并符合公司或行业的标准。包括用户界面友好性，人性化，易操作性等方面的测试。
2.1.3 遗传算法在软件测试中的应用
遗传算法(Genetic Algorithms，GA)是用于测试数据的自动生成的有效方法。目前已有许多研究成果，如Chen等采用多种群GA生成覆盖路径的测试数据，Sofokleous等基于GA建立了动态软件测试框架。Rajappa等利用GA并结合图论知识，生成软件的测试用，Bouchachia将免疫GA用于测试数据生成中等。这些成果极大地丰富了进化测试理论。用GA生成覆盖路径的测试数据，需要将该问题转化为函数优化问题。适应度函数的设计对产生高性能的测试数据非常关键。但是，现有文献适应度函数大多是针对一条目标路径设计的，这将导致GA的一次运行，只能生成穿越一条路径的测试数据。因此，有必要提高生成测试数据的效率。为解决这一问题，Ahmed等首次提出基于GA的多路径测试数据进化生成方法，将测试数据生成问题转化为多目标优化问题，利用GA解决该问题时，分别计算进化个体对不同目标的满足程度，使得一次运行GA，生成分别穿越多条目标路径的多个测试数据[8]，并用实验验证了该方法生成测试数据优于单路径生成方法。Ahmed方法的适应度函数由2部分组成，分别是层接近度和支距离，其中，层接近度指测试数据穿越的路径与每个目标路径不匹配的结点个数之和；支距离反映被穿越的路径与目标路径分支语句的前件还有多少距离，将支距离和层接近度之和作为个体相对于一个目标路径的适应值，将个体针对所有目标路径的适应值平均值作为个体的适应值。但是，当测试数据支距离较大时，层接近度与其相比几乎被忽略不计了，此时其作用得不到很好的体现；更重要的是当分支语句的前件比较复杂时，支距离的计算很复杂，导致测试数据的生成时间较长，效率不高．如果采用合适的方法，针对所有目标路径，设计合适的适应度函数，经过较少的计算能比较不同进化个体的优劣，运行一次GA，生成穿越多条路径的测试数据，将有可能提高生成测试数据的效率。
采用GA生成测试数据的步骤如下：
步骤1 对算法所需的控制参数赋值，对被测试程序的路径编码，插桩被测试的程序；
步骤2 初始化种群；
步骤3 对进化个体解码，执行被测试程序；
步骤4 判断是否有完全匹配的路径，若有，保存与该进化个体对应的测试数据，从目标路径编码中删除该被匹配的路径对应的编码；
步骤5 判断是否满足终止准则，若是，转步骤8；
步骤6 计算进化个体适应值；
步骤7 实施选择、交叉和变异操作，生成子代进化种群，转步骤3；
步骤8 停止进化，解码进化个体，输出测试数据。
2.2微粒群优化算法
2.2.1微粒群优化算法的产生
近年来，社会生产力得到空前的解放，人民生活水平日益提高，科学技术也发展到了一个崭新的高度。随着社会、经济、工业、科学、管理等领域研究的深入，实际问题变得越来越复杂，研究者们迫切需要找到优化这些复杂问题的方法，于是关于优化算法的研究被学者们提上了议程。
研究早期，受大自然运行规律和面向具体问题的经验、规则启发，科学家们提出了启发式优化算法，比较常见的有遗传算法[9]、模拟退火算法[10]和人工神经网络算法[11]。到1995年，美国社会心理学家Kennedy和Eberhart博士等受鸟类和鱼类群体行为的启发，共同提出了微粒群优化算法（Particle Swarm Optimization，PSO）。
微粒群优化算法最初是为了模拟鸟群不可预测的飞行和觅食活动，研究鸟之间的群体合作使群体达到最优的行为[12]。每一只鸟使用简单规则确定自身飞行的方向与速度，同时试图飞行在整个鸟群中而不与其他鸟碰撞。当一只鸟飞离鸟群觅食时，它周围的其他鸟也随之飞向觅食地点，这只鸟一旦发现食物，通过信息传递，将驱使更多的鸟飞到此处，直到整个鸟群都落在觅食点。鸟类寻找食物的过程与特定问题寻找最优解的过程极为相似，已经找到食物的鸟引导其周围的鸟飞向觅食点的方式，增加了整个鸟群找到食物的可能性。
生物社会学家Willson在研究鱼群的觅食活动中发现，群体中的个体在觅食过程中总会得益于其它个体觅食所获得的经验。这些现象表明：群体通过共享信息会得到意想不到的解决问题的优势。对上述生物群体行为的研究和现象的分析，构成了微粒群优化算法理论和思想的源泉。
作为一种新兴的群体智能算法，微粒群优化算法因其算法原理简单、调节参数少、执行效率高、无需梯度信息、易于实现等优点被广泛应用于解决生产生活中各领域的复杂问题。微粒群优化算法最初用于处理连续优化问题，目前已扩展到组合优化[4]问题的处理。实践证明，微粒群优化算法是非线性连续优化问题、组合优化问题以及混合整数非线性优化问题的有效优化工具。
2.2.2微粒群优化算法的基本原理
微粒群优化算法是一种基于群体迭代[12]的随机优化方法，其思想来源于人工生命和演化计算理论。所谓群体迭代，即群体在解空间中追随最优微粒进行搜索，微粒通过追随自己找到的最好解和群体找到的最好解完成优化。
微粒群优化算法主要运用了群体智能的基本概念。通常自然生物个体并非是智能的，但整个生物种群却表现出处理复杂问题的智能。由于自然界各种生物均具有一定的群体行为，从而可以在计算机上建立群体模型。通常，如鱼群、鸟群等群体行为可以根据几条简单的规则进行建模。
在对鸟群集体行为进行仿真时，学者采用了三条简单的规则[13]：
(1)飞离最近的个体，以避免碰撞；
(2)飞向目标；
(3)飞向群体中心。
微粒群优化算法中“群（Swarm）”的概念符合应用于人工生命(Artificial Life)模型时所提的群体智能的5个基本原则[3]：
(1)亲近原则（proximity principle）：微粒群能完成简单的时间和空间计算；
(2)质量原则（quality principle）：微粒群必须能够对周围环境的品质因素做出反应；
(3)多样反应原则（the principle of diverse response）：群体的活动不应该只限于很小的范围；
(4)定性原则（the principle of stability）：微粒群的活动行为不应该随环境变化而发生改变；
(5)自适应原则（the principle of adaptability）：在能够接受的计算量下，微粒群行为模式的改变与计算成本相比代价更低时，微粒群必须能够改变其行为模式。
在微粒群优化算法中，每一个个体被称为一个微粒或主体，每个微粒均代表一个潜在的可能解。每个微粒都有各自当前的位置和速度以及一个由优化函数决定自身位置的适应值。各个微粒在解空间中搜索、追随当前的最优微粒。在每一次迭代中，微粒个体能够记忆自己当前找到的最好位置，称之为个体极值，用表示其位置；微粒同时记住整个种群当前找到的最好位置，称之为全局极值，用表示其位置。
微粒群中微粒的信息可用维矢量表示，位置表示为；速度表示为；微粒迄今为止搜索到的最优位置，即个体极值点，记作；整个微粒群迄今为止搜索得到的最优位置,亦即全局极值点，记作:

每次迭代中，微粒个体根据下式进行当前位置和速度的更新，得到下一次微粒的速度和位置：
（2.1）

（2.2）
其中，=1,2,…,m; =1,2,…,; 为迭代次数。表示微粒在第次迭代中第维的速度。
,是学习因子，也称加速系数，分别调节向个体最好微粒和全局最好微粒飞行的最大步长，合适的,可以加快收敛速度且不易陷入局部最优，若太小，则搜索空间不足，微粒远离目标区域；若太大，会导致微粒跳过最好解，一般取。，是[0，1]之间的随机数，用来保持群体的多样性。
公式（2.1）的第二部分，即微粒当前位置与个体极值点之间的距离，称作微粒的“自身认知”部分，表示微粒自身的经验和对自身的学习；而公式（2.1）的第三部分，即微粒当前位置与全局最优位置的距离，称作微粒的“社会认知”部分，表示微粒的动作来源于群体中其他微粒的经验，代表微粒间信息的共享与合作[14]。微粒正是根据上一代的速度、自身当前位置与自身最好经验和群体最好经验的距离来更新速度。
由于微粒群优化算法中没有实际的机制来控制微粒的速度，所以有必要对微粒速度的最大值作出限制，令其最大速度为，则速度在[-，+]之间，大小应适中，若太大会导致微粒跳过最好解，若太小则会陷入局部最优，同样地，我们也规定位置在[-，+]之间。
标准PSO的算法流程可以描述为：
Step 1 初始化。在允许的范围内随机产生初始搜索点的位置和速度，每个微粒的pbest设置为当前位置，计算出每个微粒的个体极值，将个体极值中最好的记作全局极值，将gbest设置为当前最好微粒的位置；
Step 2 评价微粒。根据适应度函数计算每个微粒的适应值，若计算所得的适应值好于该微粒当前的个体极值，则将设置为该微粒当前的位置，且更新个体极值；