邱千钧，肖玉杰，曹 渊，于邵祯

(1.海军驻航天二院代表室，北京 100854； 2.海军装备研究， 北京 100161)

【基础研究】

基于PSO和SA多子群分层并行的智能分布式算法

邱千钧1，肖玉杰2，曹 渊2，于邵祯2

(1.海军驻航天二院代表室，北京 100854； 2.海军装备研究， 北京 100161)

针对PSO算法全局收敛性差、搜索精度不高，SA算法收敛速度慢，求解时间随着问题规模的增大和复杂急剧增加的问题，提出一种PSO和SA多子群分层并行的智能分布式算法。算法底层是一个采用模拟退火策略搜索全局最优解的子群；上层是一系列粒子子群，采用粒子群优化算法搜索策略，贡献局部最优解。算法从种群个体的组织结构出发，将局部搜索和全局搜索分离，使得PSO算法和SA算法融为一体，解决了算法收敛速度快和全局收敛能力强之间的矛盾。PSO-SAHP算法具有全局收敛性，算法在求解离散型的车间作业调度问题和连续型的Benchmark函数优化问题中，与单一智能优化算法相比，具有良好的可扩展性。这对于求解高度复杂的分布式问题，具有一定的工程意义。

混合算法；PSO算法；SA算法；智能分布式算法

粒子群(Particle Swarm Optimization，简称PSO)算法是Kennedy和Eberhart在1995年提出的一种新型群体智能优化算法[1-4]。粒子群优化算法简单易实现、收敛速度快，在认知无线电参数优化[5]、函数极值寻优[6]、电弧炉供电优化[7]等实际问题中得到了广泛的应用。模拟退火(Simulated Annealing，简称SA)算法是S.Kirkpatrick等人在1982年提出的一种模拟金属退火机理而建立的随机优化方法[8-9]。SA算法接受新模型的方式使其成为一种全局最优算法，并已得到理论和实际应用的验证[10-14]。Information interaction

PSO算法和SA算法都是一种群体智能优化算法，都有自身的特点和优势，同样也都存在一些缺陷和不足。PSO算法简单易实现，但搜索精度不高，且在理论上已经证明了其不是全局最优的[15]；SA算法以概率1收敛于全局最优解，但其收敛速度慢，求解时间随着问题规模的增大和复杂急剧增加[16]。

图1所示为PSO算法和SA算法收敛速度的变化曲线，算法初期，PSO算法以很快的速度收敛到局部最优解，但随着种群的不断进化，算法的收敛速度急剧下降，甚至可能停滞不前，即算法出现“早熟”现象；SA算法虽然收敛速度缓慢，但其不断接近最优解直至最终到达。鉴于PSO算法和SA算法有着几乎互补的优势，很多学者尝试将两者混合，取长补短，设计出很多性能更优的算法[17]。

图1 PSO算法和SA算法收敛速度变化曲线

近年来，混合算法的研究已经成为智能优化算法的主流方向[18-19]。如文献[11,17]等结合PSO优化算法和SA算法各自的优点，提出了SA-DWPSO算法。通过PSO算法局部收敛性和SA算法全局收敛性的融合，有效的避免了PSO算法的早熟现象，加快了其收敛速度。

目前，混合算法主要有为串联[20]和并联[21-22]两种混合形式。但这两种混合方式都是将两种算法以同等地位进行混合，两种算法分工不明确，各自的优势并没有得到充分的发挥。

为了充分发挥PSO算法的快速寻优能力和SA算法的全局收敛特性，本文采用分层混合的思想，提出了一种PSO和SA混合的智能分布式算法。算法底层是一个采用模拟退火策略搜索全局最优解的子群；上层是一系列的粒子子群，采用粒子群优化算法搜索策略，贡献局部最优解。算法从种群个体的组织结构出发，将局部搜索和全局搜索分离，使得PSO算法和SA算法有机的融合为一体，有效的解决了算法收敛速度快和全局收敛能力强之间的矛盾。

1 多子群分层并行的分布式算法

图2所示为粒子群和模拟退火混合的多子群分层混合并行算法(以下简称PSO-SAHP算法)的种群个体组织方式，上层是整个算法的进化主体，在贡献局部最优解的同时也为下层提供SA算法的初始值。由n个相互独立的PSO子群组成，输出局部最优值；下层采用模拟退火策略搜索全局最优解，PSO-SAHP算法可以解耦为如下两个阶段。

图2 PSO-SA混合算法中的种群个体组织方式

阶段1：启动PSO算法搜索局部最优解，同时为底层SA算法提供初值。

首先，随机初始化n个子群，分别记为PSO1、PSO2、、PSOn。每个子群独立的在各自处理机上运行PSO算法，迭代一定代数后，进行信息交互(如将PSO1与PSO2中的某些个体进行交换)，循环迭代一定代数后，取出各自的最优个体，选出最优解作为底层SA算法的初始值。

阶段2：上层PSO子群和下层SA子群协同进化。

在计算过程中，两种算法交替进行迭代，并通过比较目标函数值来判断解的质量和协同进化方向。即如果上层的某个PSO子群搜索到较优的解，则从n个子群中随机选取m个子群中的粒子，用该解替换原粒子的位置，并将其作为SA子群下一次迭代的初始位置；反之如果SA子群搜索到较优解，则随机选取上层m个子群中的粒子，用该解替换原粒子的位置。需要指出的是此阶段为了减少通信，上层PSO子群内部不再进行信息交互操作。

PSO-SAHP 算法的进化流程设计如图3所示。

图3 PSO-SAHP算法的进化流程

2 PSO-SAHP算法的全局收敛性证明

Solis和Wets给出了纯随机优化算法的收敛性判据，为了证明PSO-SAHP算法的全局收敛性，在此不加证明的列出了相关判定定理[23-24]。

(假设1 )对于优化问题〈S,f〉，若fDz,ξ≤fz，并且ξ∈S，则有fDz,ξ≤fξ。其中ξ是D算法在本次迭代过程中曾经搜索过的解。

(定理)PSO-SAHP 算法以概率1收敛于全局最优解。

证明：设PSO-SAHP算法的迭代函数D为

(1)

其中，k是进化代数，Pg,k和Xg,k分别是PSO子群和SA子群第k代更新的全局最好位置，容易证明其满足假设1[17]。

下面证明其满足假设2：

粒子子群的样本空间的并集必须包含解空间S，即

(2)

其中，Mi,k为第k代子群i样本空间的支撑集。

(3)

其中

(4)

即当fYk

Mi,k=Xik-1+ωXik-1-Xik-2+

φ1Pi,k-1-Xik-1+φ2Pg,k-1-Xik-1

(5)

其中，0≤φ1≤c1, 0≤φ2≤c2。

当式(5)成立时，显然有vMi,k∩S

maxc1Pi,j,k-1-xi,j,k-1,c2Pg,j,k-1-xi,j,k-1<

0.5·diamjS

(6)

由引理1、2可知，PSO-SAHP算法以概率1收敛于全局最优解，故定理1成立。证毕。

3 PSO-SAHP 算法的实验测试

为了验证本文所提出的粒子群和模拟退火混合的多子群分层并行算法的有效性，将其应用于求解标准优化函数的测试问题，即离散型的车间作业调度问题和连续型的Benchmark函数优化问题，相关对比试验及结果如下所示。

3.1 车间作业调度问题的对比实验

为了测试算法的可行性，选取典型的测试问题进行对比实验。标准的测试问题主要有FT类、LA类等，分别由Fisher，Thompson和Lawrence等构造[25-26]。

实验环境：基于MPI的并行编程环境，使用 C++编程语言，表1给出了PC机群的详细配置情况。PSO算法中惯性权重线性下降ω=0.9,0.4，加速常数c1=c2=2.0。每个子群的规模为40，SA算法的种群规模为40，初始温度T0=100，比例降温衰减系数K=0.975，马尔科夫链长度Lk=50。阶段1和阶段2的最大迭代均为1 000次，最大保持代数为10(最优值连续10代保持不变即视为收敛)，根据需要PSO算法和SA算法每迭代10次进行一次通信操作，由于算法的随机性和收敛特性等不同，需要增加不同子群之间的等待时间，但这是并行算法不可避免的。

实验对比结果如表2所示，其中第3列为问题已知的最优解y，第4列为使用PSO-SAHP算法求得的最优解y′，误差百分比Err(保留小数点后4位有效数字)计算如式(7)所示，表3列出了求解 FT06型车间作业调度问题的一个最优解。从对比结果可以看出，算法求得的误差控制在2%以内，有效的解决了JSSP调度问题。

Err=×100% (7)

表2 车间作业调度问题对比实验结果

3.2 Benchmark函数优化问题的对比实验

从文献[27]中选取3个基准函数进行对比分析，表4列出了这些Benchmark函数的定义，搜索空间、初始化空间、已知的最优解等基本信息。实验软硬件环境：为了和文献[27]中(其唯一的参数α设置为从1.2到0.5线性减少)的结果对比，PC机群的计算节点分别取2、4个，当计算节点分别为2和4时，上层每个粒子的规模分别是为40和20， 其他设置同上。

对于每一个标准Benchmark函数，为了排除随机性，运行50次并记录最优解的平均值，即最优均值以及平均耗时，其结果如表5、6、7所示。

从表5、6、7可以看出，对于求解三个标准函数，PSO-SAHP算法运行50次的最佳均值和平均耗时明显小于文献[27]中的算法，这说明PSO-SAHP算法具有良好的可扩展性，优势较明显。

表3 FT06车间作业调度的一个最优解

表4 标准Benchmark函数

表5 Rosenbrock函数的对比实验

表6 Griewank函数的对比实验

表7 Rastrigrin函数的对比实验

4 结论

PSO和SA多子群分层并行的智能分布式算法底层是一个采用模拟退火策略搜索全局最优解的子群；上层是一系列的粒子子群，采用粒子群优化算法搜索策略，贡献局部最优解。算法从种群个体的组织结构出发，将局部搜索和全局搜索分离，使得PSO算法和SA算法有机的融合为一体，有效的解决了算法收敛速度快和全局收敛能力强之间的矛盾。

相关试验表明，PSO-SAHP算法在离散型问题和连续型问题的求解中，具有良好的可扩展性，优势较明显。需要进一步验证PSO-SAHP算法在解决多无人机编队协同航路规划、电力系统仿真计算等工程领域问题中的有效性。

[1] Tao Q, CHANG H Y, YANG Y.A rotary chaotic PSO algorithm for trustworthy scheduling of a grid workflow [J].Computer & Operations Research,2011,38(5):824-836.

[2] WANG G L, ZHAO G Q, LI H P.Research on optimization design of the heating/cooling channels for rapid heat cycle molding based on response surface methodology and constrained particle swarm optimization [J].Expert Systems with Applications, 2011, 38(6): 6705-6719.

[3] GORAI A, GHOSH A.Hue-preserving color image enhancement using particle swarm optimization [C].2011 IEEE Recent Advances in Intelligent Computational Systems, Piscataway: IEEE, 2011:563-568.

[4] 方伟，孙俊，谢振平，等.量子粒子群优化算法的收敛性分析及控制参数研究[J].物理学报，2010,59(6)：3686-3694.

[5] 赵知劲，徐世宇，郑仕链，等.基于二进制粒子群算法的认知无线电决策引擎[J].物理学报，2009,58(7)：5118-5125.

[6] 高维尚，邵诚，高琴.群体智能优化中的虚拟碰撞：雨林算法[J].物理学报，2013,62(19)：1-16.

[7] 冯琳，毛志忠，袁平.改进多目标粒子群算法及其在电弧炉供电优化中的应用[J].控制理论与应用，2011,28(10)：1455-1460.

[8] MIAO H, TIAN Y C.Robot path planning in dynamic environments using a simulated annealing based on approach [C].Proceeding of 10th International Conference on Control， Automation， Robotics and Vision.Hanoi Vietnam， 2008:1253-1258.

[9] 王丽芳，曾建潮.基于微粒群算法和模拟退火算法的协同进化方法[J].自动化学报，2006，32(4)：630-635.

[10] 蒲荣富，肖思和，许多.模拟退火算法优化分析与应用研究[D].成都：成都理工大学，2013.

[11] 林令娟，刘希玉.模拟退火微粒群混合算法的研究及应用[D].济南：山东师范大学，2010.

[12] 任子晖, 王坚, 高岳林.马尔科夫链的粒子群优化算法全局收敛性分析[J].控制理论与应用，2011,28(4)：462-466.

[13] 金欣磊, 马龙华, 吴铁军, 等.基于随机过程的PSO收敛性分析[J].自动化学报, 2007, 33(12): 1263 - 1268.

[14] VAN DEN BERGH F, ENGELBRECHT A P.A study of particle swarm optimization particle trajectories [J].Information Sciences, 2006, 178(8): 937 - 971.

[15] 金 敏,鲁华祥.一种遗传算法与粒子群优化的多子群分层混合算法[J].控制理论与应用，2013,30(10)：1231-1238.

[16] 周 杰，俎云霄.一种用于认知无线电资源分配的并行免疫遗传算法[J].物理学报，2010,59(10)：7508-7515.

[17] 赵知劲，郑仕链，尚俊娜，等.基于量子遗传算法的认知无线电决策引擎研究[J].物理学报，2007,56(11)：6760-6706.

[18] 俎云霄，周杰.基于组合混沌遗传算法的认知无线电资源分配[J].物理学报，2011,60(7)：7950-7957.

[19] LI S T, WU X X, TAN M K.Gene selection using hybrid particle swarm optimization and genetic algorithm [J].Soft Computing, 2008, 12(11): 1039-1048.

[20] MARINAKIS Y, MARINAKI M.A hybrid genetic—particle swarm optimization algorithm for the vehicle routing problem [J].Expert Systems with Applications, 2010, 37(2): 1446-1455.

[21] KUO R J, SYU Y J, CHEN Z Y.Integration of particle swarm opti-mization and genetic algorithm for dynamic clustering [J].Information Sciences, 2012, 195: 124-140.

[22] KAO Y T, ZAHARA E.A hybrid genetic algorithm and particle swarm optimization for multimodal functions [J].Applied Soft Computting, 2008, 8(2): 849-857.

[23] SOLIS F，WETS R.Minimization by random search techniques [J].Mathematics of Operations Research, 1981,6(5)：19-30.

[24] 李宁，孙德宝.粒子群优化算法的理论分析与应用研究[D].武汉：华中科技大学，2006.

[25] GAO J,GEN M,SUN L,et al.The particle swarm optimization algorithm convergence analysis and parameter selection[J].Information Processing Letters, 2003, 85(6): 317-325.

[26] ZHANG Jing，WANG Wannian，XUN Xinli.Improved particle swarm algorithm for batch splitting flexible job shop scheduling [J].Control and Decision，2012，27(4)：513-518.

[27] 王小根，奚茂龙，须文波.具有量子行为粒子群优化算法的并行化研究[J].计算机工程与应用，2009,45(11)：45-45.

AnIntelligentDistributedAlgorithmofMulti-SubgroupHierarchicalHybridofSimulatedAnnealingAlgorithmandParticleSwarmOptimization

QIU Qianjun1， XIAO Yujie2， CAO Yuan2， YU Shaozhen2

(1.Navy Representative office in the Second Academy of CASC， Beijing 100854, China；2.Naval Academy of Armament， Beijing 100161, China)

To make use of the strong global search ability of the simulated annealing algorithm and the high convergence rate of the particle swarm optimization, we combine these two algorithms and propose an intelligent distributed algorithm of multi-subgroup hierarchical hybrid of simulated annealing algorithm and particle swarm optimization (PSO-SAHP).This hybrid algorithm adopts a hierarchical structure; the base level is composed of a series of subgroups of simulated annealing algorithm, which provides the global search ability of the entire algorithm. The top level comprises all elite subgroups consisting of the best individual of each subgroup, which performs the accurate local search by using the particle swarm algorithm with cramped initial velocity. The global convergence analysis of PSO-SAHP is given in this paper, algorithm for solving discrete job shop scheduling continuous optimization problem of Benchmark functions，compared with single algorithm，has good scalability and obvious advantages. It has some engineering significance for solving highly complex distributed computing problems.

compound arithmetic; PSO-SAHP; SA algorithms; intelligent distributed algorithm

2017-09-13；

2017-09-30

邱千钧(1990—)，男，硕士，主要从事舰载武器研究。

10.11809/scbgxb2017.12.057

本文引用格式：邱千钧，肖玉杰，曹渊，等.基于PSO和SA多子群分层并行的智能分布式算法[J].兵器装备工程学报，2017(12):261-266.

formatQIU Qianjun， XIAO Yujie， CAO Yuan, et al.An Intelligent Distributed Algorithm of Multi-Subgroup Hierarchical Hybrid of Simulated Annealing Algorithm and Particle Swarm Optimization[J].Journal of Ordnance Equipment Engineering,2017(12):261-266.

TP301.6

A

2096-2304(2017)12-0261-06

(责任编辑杨继森)