多核环境下的粒子群算法

吴 海，孙永雄，韩 伟，厉延民

（吉林大学a.长春电信工程股份有限公司;b.计算机科学与技术学院;c.长邮通讯建设有限公司，长春 130012）

0 引 言

1995 年美国电气工程师Eberhart和社会心理学家Kenndy基于鸟群觅食行为提出了粒子群优化算法（PSO：Particle Swarm Optimization），简称粒子群算法[1]。由于该算法概念简明、实现方便、收敛速度快、参数设置少，是一种高效的搜索算法。

PSO是模拟鸟群捕食行为的一种群智能算法。通过假设在搜索食物区域里只有一块食物，所有小鸟都不知道食物在什么地方，小鸟之间通过互相交换信息，估计自身的适应度，判断它们当前的位置离食物的距离，所以搜索目前离食物最近的鸟的周围区域是找到食物的最简单有效的办法，通过鸟之间的集体协作使群体达到最优。PSO就是从这种模型中得到启示并用于解决优化问题的。在PSO中每个优化问题的潜在解都可以想象成搜索空间中的一只鸟，称为“粒子”。粒子主要追随当前的最优粒子在解空间中搜索，PSO初始化为一群随机粒子（随机解），然后通过迭代找到最优解。在每次迭代中，粒子通过跟踪两个“极值”更新自己：1）粒子本身所找到的最优解，称为个体极值pbest;2）整个种群目前找到的最优解，称为全局极值gbest。这两个最优变量使鸟在某种程度上朝着这些方向靠近，此外也可以不用整个种群而只用其中一部分作为粒子的邻居，则所有邻居的极值就是局部极值，粒子始终跟随这两个极值变更自己的位置和速度，直到找到最优解[2，3]。

到目前为止粒子群算法的发展得到越来越多领域学者的关注和研究[4-8]，成为解决许多问题的研究重点。其中对PSO算法的改进也非常多，如增强算法自适应性的改进、增强收敛性的改进、增加多种群多样性的改进、增强局部搜索的改进、与全局优化算法相结合、与确定性的局部优化算法相融合等。

随着多核计算理论和技术的普及，如何在多核计算环境下，高效、并行地实现粒子群算法，对学者们提出了新的挑战。笔者基于多核计算环境，提出一种面向多核计算的改进粒子群算法，并通过实验证实了该改进算法的效果较好。

1 粒子群算法简介

粒子群算法是一个非常简单的算法，且能有效地优化各种函数。从某种程度上说，此算法介于遗传算法和进化规划之间。此算法非常依赖于随机的过程，这也是和进化规划的相似之处，此算法中朝全局最优和局部最优靠近的调整非常类似于遗传算法中的交叉算子。该算法也是用了适应值的概念，也是有进化计算方法共有的特征[5-9]。

在粒子群算法中，每个个体称为一个“粒子”，其实每个粒子代表一个潜在的解。如，在一个D维的目标搜索空间中，可以将每个粒子看成是空间内的一点。设群体由m个粒子构成。m也被称为群体规模，过大的m会影响算法的运算速度和收敛性。

PSO算法通常用数学描述为：设在一个D维空间中，由m个粒子组成的种群X=（x1，…，xi，…，xD），其中第 i个粒子位置为 xi=（xi1，xi2，…，xiD）T，其速度为 Vi=（vi1，vi2，…，vid，…，viD）T。其个体极值为pi=（pi1，pi2，…，piD）T，种群的全局极值为pg=（pg1，pg2，…，pgD）T。按照追随当前最优例子的原理，粒子xi将按式（1），式（2）改变自己的速度和位置。

其中 j=1，2，…，D，i=1，2，…m，m 为种群规模，t为当前进化代数，r1，r2为分布于[0，1]之间的随机数;c1，c2为加速常数。从式（1）可知，每个粒子的速度由3部分组成：1）粒子先前的速度;2）“认知”部分，表示粒子自身的思考;3）“社会”部分，表示粒子间的信息共享与相互合作。

1.1 粒子群算法的特点

粒子群算法是一种新兴的智能优化技术，是群体智能中一个新的分支，也是对简单社会系统的模拟。该算法本质上是一种随机搜索算法，并能以较大的概率收敛于全局最优解。实践证明，它适合在动态、多目标优化环境中寻优，与传统的优化算法相比，具有更快的计算速度和更好的全局搜索能力。具体特点如下。

1）粒子群优化算法是基于群体智能理论的优化算法，通过群体中粒子间的合作与竞争产生的群体智能指导优化搜索。与进化算法相比，PSO是一种更为高效的并行搜索算法。

2）PSO与GA（Genetic Algorithm）有很多共同之处，两者都是随机初始化种群，使用适应值评价个体的优劣程度和进行一定的随机搜索。但PSO是根据自己的速度决定搜索，没有GA明显的交叉和变异。与进化算法相比，PSO保留了基于种群的全局搜索策略，但其采用的速度-位移模型操作简单，避免了复杂的遗传操作。

3）PSO有良好的机制，能有效地平衡搜索过程的多样性和方向性。

4）GA中由于染色体共享信息，故整个种群较均匀地向最优区域移动。在PSO中gbest将信息传递给其他粒子，是单向的信息流动。多数情况下，所有的粒子可能更快地收敛于最优解。

5）PSO特有的记忆使其可以动态地跟踪当前的搜索情况并调整其搜索策略。

6）由于每个粒子在算法结束时仍保持着其个体极值。因此，若将PSO用于调度和决策问题，可以给出多种有意义的选择方案。而基本遗传算法在结束时，只能得到最后一代个体的信息，前面迭代的信息没有保留。

7）即使同时使用连续变量和离散变量，对位移和速度同时采用连续和离散的坐标轴，在搜索过程中也并不冲突。所以PSO可以很自然、很容易地处理混合整数的非线性规划问题。

8）PSO算法对种群大小不十分敏感，即种群数目下降时性能下降不大。

9）在收敛的情况下，由于所有的粒子都向最优解的方向飞去，所以粒子趋向同一化（失去了多样性）使后期收敛速度明显变慢，以致算法收敛到一定精度时无法继续优化。因此，很多学者都致力于提高PSO算法的性能。

1.2 粒子群算法的应用

粒子群算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的适应性，所以广泛应用于很多学科[10-14]。下面是粒子群算法的一些主要应用领域[15-19]。

1）函数优化。函数优化是粒子群算法的经典应用领域，也是对粒子群算法进行性能评价的常用算例。

2）约束优化。随着问题的增多，约束优化问题的搜索空间也急剧变换，有时在目前的计算机上用枚举法很难甚至不可能求出其精确最优解。粒子群算法是解决这类问题的最佳工具之一。实践证明，粒子群算法对约束优化中的规划，离散空间组合问题的求解非常有效。

3）工程设计问题。工程设计问题在许多情况下所建立的数学模型难以精确求解，即使经过一些简化后可以进行求解，也会因简化得太多而使求解结果与实际相差甚远。现在粒子群算法已成为解决复杂调度问题的有效工具，在电路及滤波器设计、神经网络训练、控制器设计与优化、任务分配等方面粒子群算法都得到了有效的应用。

4）电力系统领域。在其领域中有种类多样的问题，根据目标函数特性和约束类型许多与优化相关的问题需要求解。PSO在电力系统方面的应用主要有：配电网扩展规划、检修计划、机组组合、负荷经济分配、最优潮流计算与无功优化控制、谐波分析与电容配置、配电网状态估计、参数辨识、优化设计。随着粒子群优化理论研究的深入，它还将在电力市场竞价交易、投标策略以及电力市场仿真等领域发挥巨大的应用潜在力。

5）机器人智能控制。机器人是一类复杂的难以精确建模的人工系统，而粒子群算法可用于此类机器人群搜索，如机器人的控制与协调，移动机器人路径规划。所以，机器人智能控制理所当然地成为粒子群算法的一个重要应用领域。

6）交通运输领域。交通方面有车辆路径问题，在物流配送供应领域中要求以最少的车辆数、最小的车辆总行程完成货物的派送任务;交通控制，城市交通问题是困扰城市发展、制约城市经济建设的重要因素。对城市交通运输系统的管理和控制技术进行研究，为缓解交通拥挤发挥巨大作用。其中在其解决方法中应用粒子群算法给解决问题提供了新的有效的计算方式。

7）通信领域。其中包括路由选择及移动通信基站布置优化，在顺序码分多址连接方式通讯系统中使用粒子群算法，可获得可移植的有力算法并提供并行处理能力。比传统的算法具有显著的优越性。可应用于天线阵列控制和偏振模色散补偿等方面。

8）计算机领域。在计算机中处理各种问题都涉及到大量的信息计算方法的选择，以减少程序运行时间，增加系统解决问题的能力，其中包括任务分配问题、数据分类和图像处理等，应用粒子群算法都得到了实际问题解决效率的提高。

9）生物医学领域。许多菌体的生长模型即为非线性模型，为此，提出用粒子群算法解决非线性模型的参数估计问题。还在分子力场的参数设定和蛋白质图形的发现方面有所使用。根据粒子群算法提出的自适应多峰生物测定融合算法，提高了解决问题的准确性。在医学方面，如医学成像上得到推广应用等。

1.3 多核计算环境下的粒子群算法

1.3.1 粒子群算法的形式化定义和构成要素

基本粒子群算法可定义为的元素：fmax为最大的惯性权值;fmin为最小的惯性权值;pg为初始群体值;

算法调用的求解函数为： [x，dd]=judge（x，M）。

粒子群算法的构成要素如下。

1）粒子群编码方法。基本粒子群算法使用固定长度的二进制符号串表示群体中的个体，其等位基因由二值符号集{0，1}所组成。初始群体中每个个体的基因值可用均匀分布的随机数生成。

2）个体适应度评价。通过确定局部最优迭代达到全局最优收敛，得出结果。

3）基本粒子群算法的运行参数。基本粒子群算法有下述7个运行参数需要提前设定。

①r为粒子群算法的种子数，对粒子群算法其中种子数值可随机生成，也可固定为一个初始的数值，要求能涵盖目标函数的范围。

②M为粒子群群体大小，即群体中所含个体的数量，一般取20～100。在变量较多时可取100以上的数。

③max_d一般为最大迭代次数，以满足最小误差的要求。粒子群算法的最大迭代次数，也是终止条件数。

④ r1，r2是两个在[0，1]之间变化随机数。

⑤ c1，c2为加速度数，取[0，1]之内的随机数。

⑥ww为惯性权重。

⑦vk，xk为一个粒子的速度和位移数值，用粒子群算法迭代出每组数值。

1.3.2 多核计算环境下的粒子群算法描述

2 实 验

在以上算法分析设计的基础上，用C++语言分别实现了原始粒子群算法（PSO）和笔者提出的多核计算环境下的改进粒子群算法。通过运行实际的算法程序，对运行结果进行统计分析，比较两种算法各自的优越性。

程序运行的硬件环境是：2 GByte内存，AMD 4800+处理器。软件环境是：Windows XP SP2操作系统，C++集成开发环境。

该实验采用了函数Griewank对算法进行测试，并将改进算法与其经典算法进行比较。其结果如图1所示。由图1可知，基于多核计算环境的粒子群算法的计算时间，有了大幅度的提高。

图1 时间消耗对比图Fig.1 Time lost contrast

3 结 语

随着多核计算理论和技术的普及，如何在多核计算环境下，高效、并行地实现粒子群算法，对学者们提出了新的挑战。笔者基于多核计算环境，提出一种面向多核计算的改进粒子群算法，其计算时间有了大幅度提高。通过实验显示了该改进算法的优良效果。

：

[1]KENNEDY J，EBERHART R C.Particle Swarm Optimization[C]∥Proceedings of the Fourth IEEE International Conference on Neural Networks.Perth，Australia： [s.n.]，1995：1942-1948.

[2]WAYNEL L WINSTON.运筹学应用范例与解法[M].北京：清华大学出版社，2004：681-779.WAYNEL L WINSTON.Operations Research Application and Algorithms[M].Beijing：Tsinghua University Press，2004：681-779.

[3]赵瑞安，吴方.非线性最优化理论和方法[M].杭州：浙江科学技术出版社，1992：1-41.

ZHAO Rui-an，WU Fang.Theory and Methods for Nonlinear Optimization[M].Hangzhou：Zhejiang Science and Technology Press，1992：1-41.

[4]刘国平，曾强.多目标最优化的粒子群算法[J].杭州师范学院学报：自然科学版，2005，4（1）：30-33.

LIU Guo-ping，ZENG Qiang.PSO Based on Multiple Target Optimization[J].Journal of Hangzhou Teachers College：Natural Science Edition，2005，4（1）：30-33.

[5]汪定伟，王俊伟，王洪峰，等.智能优化方法[M].北京：高等教育出版社，2007：4-75.

WANG Ding-wei，WANG Jun-wei，WANG Hong-feng，et al.Intelligent Optimization Method[M].Beijing：Higher Education Press，2007：4-75.

[6]王凌，刘波.微粒子群优化与调度算法[M].北京：清华大学出版社，2008：20-120.

WANG Ling，LIU Bo.Particle Swarm Optimization and Scheduling Algorithms[M].Beijing：Tsinghua University Press，2008：20-120.

[7]孙志胜，曹爱增，梁永涛.基于遗传算法的聚类分析及其应用[J].济南大学学报，2004，18（2）：127-129.

SUN Zhi-sheng，CAO Ai-zeng，LIANG Yong-tao.Cluster Analysis Based on Genetic Algorithm and Its Application[J].Journal of Jinan University，2004，18（2）：127-129.

[8]刘文远，王宝文.基于遗传算法的模糊聚类分析[J].计算机工程，2004，30（19）：116-118.

LIU Wen-yuan，WANG Bao-wen.Fuzzy Clustering Analysis Based on Genetic Algoritnms[J].The Computer Engineering，2004，30（19）：116-118.

[9]安良，胡勇，胡良梅，等.一种改进的模糊C-均值（FCM）聚类算法[J].合肥工业大学学报，2003，26（3）：354-358.

AN Liang，HU Yong，HU Liang-mei，et al.A Modified Fuzzy C-Means（MFCM）Clustering Algorithm[J].Journal of Hefei University of Technology，2003，26（3）：354-358.

[10]GAING Z L.A Particle Swarm Optimization Approach for Optimum Design of PID Controller in AVR System [J].IEEETransactions on Energy Conversion，2004，19（2）：384-391.

[11]KROHLING R A，LDOS SANTOS COELLO.Coevolutionary Particle Swarm Optimization Using Gaussian Distribution for Solving Constrned Optimization Problems[J].IEEE Trans Syst Man Cybern B：Cybern，2006，36（6）：1407-1416.

[12]HSIEH S，SUN T，LIU C，et al.Efficient Population Utilization Strategy for Particle Swarm Optimizer[J].IEEE Trans Syst Man Cybern B：Cybern，2009，39（2）：444-456.

[13]SUGANTHAN P N，HANSEN N，LIANG J J，et al.Problem Definitions and Evaluation Criteria for the CEC2005 Special Session on Real-Parameter Optimization[C]∥Proc IEEE Congr Evol Comput.[S.l.]：Nanyang Technological University，2005：1-50.

[14]WANG Z，HO D W C，LIU X.Variance-Constrained Filtering for Uncertain Stochastic Systems with Missing Measurements[J].IEEE Trans Automatic Control，2003，48（7）：1254-1258.

[15]刘海波，侯国华，马健，等.湿蒸汽中水粒子群激光散射的相函数计算[J].吉林大学学报：信息科学版，2007，25（4）：398-405.

LIU Hai-bo，HOU Guo-hua，MA Jian，et al.Calculation on Laser Scattering Phase Function of Water PSO in Wer Steam[J].Journal of Jilin University：Information Science Edition，2007，25（4）：398-405.

[16]张利彪，周春光，刘小华，等.粒子群算法在求解优化问题中的应用[J].吉林大学学报：信息科学版，2005，23（4）：385-389.

ZHANG Li-biao， ZHOU Chun-guang，LIU Xiao-hua， et al.Application of Particle Swarm Optimization for Solving Optimization Problems[J].Journal of Jilin University：Information Science Edition，2005，23（4）：385-389.

[17]陈永刚，杨凤杰，孙吉贵.新的粒子群优化算法[J].吉林大学学报：信息科学版，2006，24（2）：181-184.

CHEN Yong-gang，YANG Feng-jie，SUN Ji-gui.New Particle-Swarm-Optimization Algorithm[J].Journal of Jilin University：Information Science Edition，2006，24（2）：181-184.

[18]闵克学，葛宏伟，张毅，等.基于蚁群和粒子群优化的混合算法求解TSP问题[J].吉林大学学报：信息科学版，2006，24（4）：402-405.

MIN Ke-xue，GE Hong-wei，ZHANG Yi，et al.Solving Traveling Salesman Problems by an ACO-and-PSO-Based Hybrid Algorithm[J].Journal of Jilin University：Information Science Edition，2006，24（4）：402-405.

[19]陈养平，王来雄，黄士坦.基于粒子群优化的多处理器任务调度算法[J].吉林大学学报：信息科学版，2007，25（3）：277-285.

CHEN Yang-ping，WANG Lai-xiong，HUANG Shi-tan.Task Scheduling Algorithm for Multiprocessor Based on Particle Swarm Optimization[J].Journal of Jilin University：Information Science Edition，2007，25（3）：277-285.