论文部分内容阅读
【摘 要】粒子群优化算法是一种新型的演化算法，概念简单，参数较少，易于实现，但粒子群算法易陷入局部最优导致收敛变慢。寻求解决实际问题的更加有效的粒子群优化算法是论文研究的目标。论文对粒子群算法的算法参数、拓扑结构及混合算法等方面的改进措施进行了概述，并对粒子群算法进行了展望。
【Abstract】Particle swarm optimization is a new evolutionary algorithm. It is simple in concept， and it has few parameters and is easy to implement. The goal of this paper is to find a more effective particle swarm optimization algorithm to solve practical problems. In this paper， the improvement measures of particle swarm optimization are summarized， including the algorithm parameters， topology and hybrid algorithm.
【关键词】粒子群算法;算法参数;拓扑结构;混合算法
【Keywords】particle swarm algorithm; algorithm parameter; topology; hybrid algorithm
【中图分类号】TP301.6 【文献标志码】A 【文章编号】1673-1069（2018）12-0167-02
1 引言
粒子群优化算法由Eberhart博士和Kennedy博士提出[1]，是一种源于对鸟群捕食行为的研究而发明的进化计算技术，后来演化为一种简单有效的优化计算技术，也是EA中一项新发展起来的技术。由于对粒子群优化算法的研究时间较短，尚缺乏理论基础，一些参数也需要根据具体问题依经验而定，更多深入细致的工作还有待进一步展开。
2 粒子群优化算法的改进
粒子群算法计算形式简单，参数设置少且算法收敛性良好，被应用到各个领域。但在应用的过程中，发现粒子群算法易陷入局部，得不到最优解且收敛速度慢[2]，因此，各种改进的粒子群优化算法被相继研究如何提高粒子群的求解性能和速度。
2.1 算法参数的改进
粒子群算法中的参数很多，其中，粒子种群大小M，粒子的最大速度Vmax等可以采用数值实验的方法来确定大致范围，而惯性权重W和加速常数C1、C2粒子运行的轨迹有着直接的影响，因此，算法的效果与这几个参数有着更直接的关系[3]。
2.1.1 改进参数惯性权重W
粒子群优化算法是以种群行为来激励粒子的运动。每个潜在的解与粒子的速度有关，为使粒子朝着更好的方向发展，需要不斷地根据粒子与邻居粒子的经验来调整。
目前对W参数较典型的改进主要有[4]：
2.2 拓扑结构的改进
2.2.1 局部版粒子群
粒子群有全局版和局部版两种。与全局版选择整个种群作为粒子邻居不同的是，局部版选择其中一部分作为粒子的邻居，局部极值是所有邻居中的最好解，每个粒子追随个体极值和局部极值。
2.2.2 空间邻域法
“空间邻域法”由Suganthan提出，是一种基于粒子的空间位置划分的方法。在该方法的迭代中，计算每一个粒子与群中其他粒子的距离，任何2个粒子间的最大距离为dmax。如果要计算粒子a的邻居：对每一粒子b按照||Xa-Xb||/dmax计算一个比值，当b满足||Xa-Xb||/dmax<farc时，则b成为当前粒子a的邻居，所有满足该条件的粒子组成a的邻域，该方法在绝大多数测试中都能获得更优良的性能，但因每一次迭代都需要计算每个粒子的邻域，从而会增加算法的复杂度。
2.2.3 邻域拓扑法
Kennedy等对粒子群的拓扑结构进行了研究，通过分析粒子间的信息流提出了环形、轮形和星形等一系列的改进的拓扑结构。另外还有动态粒子群拓扑结构。
2.2.4 社会趋同法
Kenney提出了社会趋同法，该算法混合了空间邻域和环形拓扑，粒子用聚类中心代替个体极值，能提高算法的性能，但也会增加复杂度。
2.3 混合算法
粒子群优化算法容易早熟收敛、局部寻优能力差，这基本上是所有随机算法都有的弊病，而模拟退火算法、直接搜索法、梯度法、爬山法等一些优化算法却具有很强的局部搜索能力，因此，混合粒子群算法是改进粒子群算法的一个研究方向。
Nocl等人提出了利用梯度信息的混合粒子群算法，使算法搜索到局部最优点，并且节省了比较的计算量，加快了收敛速度。Wachowiak等人提出在粒子群算法中嵌入Powell方法，提高了解的精度。
Shi等人提出将遗传算法与粒子群算法混合，并介绍了两种混合方法：粒子群遗传并行混合进化算法（PGPHEA）和粒子群遗传串行混合进化算法（PGSHEA）。
俞欢军通过对参数进行适当地调节将局部搜索和变异操作同时混合到粒子群算法中，此算法发挥了局部搜索和变异操作的优点。高鹰将模拟退火算法与粒子群算法结合，利用模拟退火较强的跳出局部最优解的能力和粒子群全局寻优能力，实现简单的优点，提高了进化后期算法的收敛速度和精度。
除此，目前还有自适应粒子群算法、带收缩因子的粒子群算法、离散粒子群算法以及协同粒子群、随机粒子群、智能粒子群等改进的粒子群算法。
3 结语
粒子群优化算法是一种新型的演化算法，其概念简单，参数较少，易于实现，自提出以来就被广泛研究与应用。但粒子群算法无论是理论还是实践都尚未成熟，存在随机性强，易陷入局部最优导致收敛慢、精度低等问题。因此，寻求更加有效的粒子群改进算法是很有意义的。近年来，粒子群算法的改进引入了许多新的数学工具，吸收了生物学的最新成果，随着新技术的进步与研究的深入，粒子群算法在操作技术和方法上将更通用、更有效。
【参考文献】
【1】何庆元，韩传久.带有扰动项的改进粒子群算法[J].计算机工程与应用，2007，43（7）：84-86.
【2】张建科.几类改进的粒子群算法[D].西安：西安电子科技大学，2007.
【3】高海兵.粒子群优化算法及其若干工程应用研究[D].武汉：华中科技大学，2007.
【4】Clerc， M.. The Swarm and the Queen： towards a Deterministic and Adaptive Particle Swarm Optimization[P]. Evolutionary Computation， 1999. CEC 99. Proceedings of the 1999 Congress on，1999.
【5】吴启迪，汪镭.智能粒子群算法研究及应用[M].江苏：江苏教育出版社，2005.
【Abstract】Particle swarm optimization is a new evolutionary algorithm. It is simple in concept， and it has few parameters and is easy to implement. The goal of this paper is to find a more effective particle swarm optimization algorithm to solve practical problems. In this paper， the improvement measures of particle swarm optimization are summarized， including the algorithm parameters， topology and hybrid algorithm.
【关键词】粒子群算法;算法参数;拓扑结构;混合算法
【Keywords】particle swarm algorithm; algorithm parameter; topology; hybrid algorithm
【中图分类号】TP301.6 【文献标志码】A 【文章编号】1673-1069（2018）12-0167-02
1 引言
粒子群优化算法由Eberhart博士和Kennedy博士提出[1]，是一种源于对鸟群捕食行为的研究而发明的进化计算技术，后来演化为一种简单有效的优化计算技术，也是EA中一项新发展起来的技术。由于对粒子群优化算法的研究时间较短，尚缺乏理论基础，一些参数也需要根据具体问题依经验而定，更多深入细致的工作还有待进一步展开。
2 粒子群优化算法的改进
粒子群算法计算形式简单，参数设置少且算法收敛性良好，被应用到各个领域。但在应用的过程中，发现粒子群算法易陷入局部，得不到最优解且收敛速度慢[2]，因此，各种改进的粒子群优化算法被相继研究如何提高粒子群的求解性能和速度。
2.1 算法参数的改进
粒子群算法中的参数很多，其中，粒子种群大小M，粒子的最大速度Vmax等可以采用数值实验的方法来确定大致范围，而惯性权重W和加速常数C1、C2粒子运行的轨迹有着直接的影响，因此，算法的效果与这几个参数有着更直接的关系[3]。
2.1.1 改进参数惯性权重W
粒子群优化算法是以种群行为来激励粒子的运动。每个潜在的解与粒子的速度有关，为使粒子朝着更好的方向发展，需要不斷地根据粒子与邻居粒子的经验来调整。
目前对W参数较典型的改进主要有[4]：
2.2 拓扑结构的改进
2.2.1 局部版粒子群
粒子群有全局版和局部版两种。与全局版选择整个种群作为粒子邻居不同的是，局部版选择其中一部分作为粒子的邻居，局部极值是所有邻居中的最好解，每个粒子追随个体极值和局部极值。
2.2.2 空间邻域法
“空间邻域法”由Suganthan提出，是一种基于粒子的空间位置划分的方法。在该方法的迭代中，计算每一个粒子与群中其他粒子的距离，任何2个粒子间的最大距离为dmax。如果要计算粒子a的邻居：对每一粒子b按照||Xa-Xb||/dmax计算一个比值，当b满足||Xa-Xb||/dmax<farc时，则b成为当前粒子a的邻居，所有满足该条件的粒子组成a的邻域，该方法在绝大多数测试中都能获得更优良的性能，但因每一次迭代都需要计算每个粒子的邻域，从而会增加算法的复杂度。
2.2.3 邻域拓扑法
Kennedy等对粒子群的拓扑结构进行了研究，通过分析粒子间的信息流提出了环形、轮形和星形等一系列的改进的拓扑结构。另外还有动态粒子群拓扑结构。
2.2.4 社会趋同法
Kenney提出了社会趋同法，该算法混合了空间邻域和环形拓扑，粒子用聚类中心代替个体极值，能提高算法的性能，但也会增加复杂度。
2.3 混合算法
粒子群优化算法容易早熟收敛、局部寻优能力差，这基本上是所有随机算法都有的弊病，而模拟退火算法、直接搜索法、梯度法、爬山法等一些优化算法却具有很强的局部搜索能力，因此，混合粒子群算法是改进粒子群算法的一个研究方向。
Nocl等人提出了利用梯度信息的混合粒子群算法，使算法搜索到局部最优点，并且节省了比较的计算量，加快了收敛速度。Wachowiak等人提出在粒子群算法中嵌入Powell方法，提高了解的精度。
Shi等人提出将遗传算法与粒子群算法混合，并介绍了两种混合方法：粒子群遗传并行混合进化算法（PGPHEA）和粒子群遗传串行混合进化算法（PGSHEA）。
俞欢军通过对参数进行适当地调节将局部搜索和变异操作同时混合到粒子群算法中，此算法发挥了局部搜索和变异操作的优点。高鹰将模拟退火算法与粒子群算法结合，利用模拟退火较强的跳出局部最优解的能力和粒子群全局寻优能力，实现简单的优点，提高了进化后期算法的收敛速度和精度。
除此，目前还有自适应粒子群算法、带收缩因子的粒子群算法、离散粒子群算法以及协同粒子群、随机粒子群、智能粒子群等改进的粒子群算法。
3 结语
粒子群优化算法是一种新型的演化算法，其概念简单，参数较少，易于实现，自提出以来就被广泛研究与应用。但粒子群算法无论是理论还是实践都尚未成熟，存在随机性强，易陷入局部最优导致收敛慢、精度低等问题。因此，寻求更加有效的粒子群改进算法是很有意义的。近年来，粒子群算法的改进引入了许多新的数学工具，吸收了生物学的最新成果，随着新技术的进步与研究的深入，粒子群算法在操作技术和方法上将更通用、更有效。
【参考文献】
【1】何庆元，韩传久.带有扰动项的改进粒子群算法[J].计算机工程与应用，2007，43（7）：84-86.
【2】张建科.几类改进的粒子群算法[D].西安：西安电子科技大学，2007.
【3】高海兵.粒子群优化算法及其若干工程应用研究[D].武汉：华中科技大学，2007.
【4】Clerc， M.. The Swarm and the Queen： towards a Deterministic and Adaptive Particle Swarm Optimization[P]. Evolutionary Computation， 1999. CEC 99. Proceedings of the 1999 Congress on，1999.
【5】吴启迪，汪镭.智能粒子群算法研究及应用[M].江苏：江苏教育出版社，2005.