并行计算在元启发式算法的应用

朱淑娟，孙 颖，胡 沛，2，司明超，潘正祥

(1.山东科技大学 计算机科学与工程学院，山东 青岛 266590；2.南阳理工学院 计算机与软件学院，河南 南阳 473004)

近年来，随着科学研究的不断深入，面临问题的复杂性也在不断增加。寻优问题在其中出现的比重也不断提高。面对这种挑战，人们采用各种各样的优化方法：机器学习方法，元启发式算法，数据挖掘方法等。其中，元启发式算法逐渐成为人们关注的焦点，它受到仿生学的启发，从自然界中获取灵感，跳出局部最优，从而找到全局最优解。而且，元启发式算法被用于解决生活中各种各样的优化问题，并取得了不错的效果。常见的元启发式算法有：遗传算法(GA)[1]模拟达尔文的进化理论和适者生存的遗传机制；粒子群优化算法(PSO)[2]通过粒子模拟鸟群觅食行为，更新粒子的速度和位置，从而找到全局最优值。蚁群优化算法(ACO)[3]的灵感来源于蚂蚁在寻找食物的过程中，根据释放信息素的多少而发现路径的行为。猫群优化算法(CSO)[4]是通过观察猫的两种行为产生的，一种是猫的跟踪模式，另一种是猫的寻找模式。鱼类洄游优化算法(FMO)[5]将鱼类迁徙的行为和运动的模型集成到优化过程中，并利用鱼类生物学中游动的运动方程寻找最优值。拟仿射变换进化算法(QUATRE)[6]是一种基于群体的优化算法，该算法将仿射变换作为一种进化方法，利用粒子间的协同合作进行优化。竹节虫种群进化算法(PPE)[7]灵感来源于自然界，模拟竹节虫的4种生长方式并将其分为4个进化阶段：趋同进化、路径依赖、种群增长、种群竞争。把有利的基因遗传给下一代，使其更好的生存。鲸鱼优化算法(WOA)[8]模拟座头鲸捕猎的行为，将鲸鱼吐泡泡的行为看作开发阶段，将其寻找猎物的行为看作探索阶段，使该算法相比其它传统算法更具有竞争力。基于教学的优化方法(TLBO)[9]，根据教学的过程将算法分为两个阶段：第1个阶段是学生向老师学习成为“教师阶段”；第2个阶段是学习者相互交流称为“学习者阶段”。

元启发式算法在展现出较好性能的同时，也存在一些局限性——不能很好地平衡探索和开发的关系，容易陷入局部最优。为了克服这个缺点，各种元启发式算法的改进版本被提出。改进的主要策略有：并行、二进制、自适应、紧凑、混沌、多目标、混合算法、离散、反向学习。

并行策略是元启发式算法常见的改进方式。与操作系统层面并行(硬件上的并行[10-11])不同的是优化算法的并行属于分群[12]：将一个大种群分为多个小种群，每隔一定的迭代次数，种群间进行信息交流。目前，已有许多研究者使用并行策略对元启发式算法进行改进[13-14]，并将改进后的元启发式算法应用于各个领域。例如，具有3种通信策略的并行粒子群优化算法(PPSO)[12]，并行遗传算法在噪声信道中的应用(PGA)[15]，求解多目标优化问题的并行多群粒子群优化策略(MOPSO)[16]。

目前工作是将互联网中收集的各种并行元启发算法资料进行整理。首先介绍一些常见的元启发式算法，以及变体。第2部分结合具体的文献介绍了两类并行策略。首先是分组的元启发式算法，具体展示了分组的策略和代表性论文。然后对并行元启发式算法的文献按照算法分类进行了总结。最后叙述了真实的并行元启发式算法的分类、交流策略以及相关论文的综述。第3部分介绍了并行策略在元启发式算法的应用。第4部分描述了本文的工作和未来的建议。

1 并行计算和元启发式算法的结合

由于各类优化问题的不断复杂化，研究者们越来越关注并行的元启发式算法。并行策略分为两种：一种是真实的并行(操作系统层面)，使用多处理器实现，可以解决高计算成本的优化问题，提高执行效率。另一种是虚拟并行，将种群分解为多个子种群，各子种群进行种间交流，产生更好的解。

1.1 分组策略

1.1.1 并行的粒子群算法

原始的PSO算法[2]由KENNEDY 和 EBERHART在1995年提出，它是一个基于种群的优化算法。模仿鸟类的捕食行为，将每只鸟赋予位置和速度两个属性。其中vi=[v1，v2，…，vd]，d表示维度，vi代表第i个粒子的速度。xi=[x1，x2，…，xd]，xi代表第i个粒子的位置。并且将每次迭代的个体最优值(pbest)和全局(gbest)最优值保存下来，用于引导个体朝着最优值的方向前进。在PSO中，粒子被随机初始化，更新公式如下：

(1)

(2)

PSO算法的步骤如下：

Step1：初始化N个粒子，并为每个粒子随机初始化一定范围内的位置和速度；

Step2：评估每个粒子的适应度值；

Step4：使用式(1)～(2)更新粒子的速度和位置；

Step5：重复步骤(2)～(4)，直到结束。

并行的粒子群算法(PPSO)[12]将原始PSO算法的种群分为多个子种群，每个子种群使用的更新方式与原始PSO算法一样。在进行一定的迭代次数之后，进行种间交流，文献[12]提出了3种信息交流策略。第1种策略是每隔r1代，对粒子进行变异和更新。首先，计算迭代次数为t时的全局最优值Gt，将其变异；然后，替代每个组中最差的粒子。第2种策略是每隔r2代，将每个组中最好的粒子Gt移到相邻的组中，替换掉相邻组中一些较差的粒子。第3种策略是前两种策略的结合，每隔r1代使用第1种策略，每隔r2代使用第2种策略。

PPSO算法的步骤如下：

Step1：初始化，将N个粒子分为g个组，每个组的个数为ng；

Step2：评估，对每个组中的粒子进行评估，计算其适应度值；

Step3：更新，计算每个组中的全局最优值得到所有粒子的全局最优值，并且计算每个粒子的个体最优值；利用式(1)～(2)进行更新粒子的速度和位置；

Step4：交流，选择交流策略的一种进行信息交换；

Step5：终止，重复步骤(2)～(4)，直到结束。

1.1.2 并行的差分进化算法

原始的DE算法[17]由STORN和PRICE在1997年提出，DE算法使用较少的参数，达到的效果最优，非常适合并行计算。DE算法有以下几个主要的过程：变异、交叉和选择。

变异：从所有个体中随机选择3个个体p1、p2、p3，并利用式(3)对当前个体vi进行更新：

vi=p1+F×(p2-p3)，

(3)

其中F是[0，2]之间的常数，p1、p2、p3属于{1，2，…，N}，N是种群中个体的数量。

交叉：对当前的2个个体vi和xi的某些维度进行交叉，得到新的个体ui更新公式如下：

(4)

其中CR代表交叉概率，它是[0，1]之间的随机数；jrand是[1，D]之间的随机数，其中D是维度。

选择：选择一个实验个体ti，如果f(ti)小于或者等于f(vi)则将ti个体代替当前个体vi。

(5)

DE算法的步骤如下：

step1：初始化种群的数量N；

step2：根据更新公式(3)和(4)，对个体执行变异和交叉操作；

step3：使用式(5)执行贪婪选择过程；

step4：重复步骤(2)～(3)，直到结束。

文献[18]提出了改进的差分进化算法(PaDE)，该算法对原始DE算法进行了3个方面的改进：(1)采用分组策略，并对每个组的参数使用自适应策略，例如每个个体的控制参数F服从柯西分布，交叉概率CR服从正态分布，选择概率P(j)=1/j。(2)提出了抛物线种群方案，每个组中的种群数量动态减少，详细的缩减公式如下：

(6)

式中psmin代表种群规模的最小值；psini代表种群规模的初始值；nfe代表当前个体的适应度值，nfemax代表函数的最大值，对最终的结果进行四舍五入(round)得到第t+1代的个体数量pst+1。(3)在DE算法的3个主要过程中，变异是关键性的步骤，本篇论文提出了基于时间戳的变异方案。

PaDE算法的步骤如下：

Step1：初始化种群的大小和所有个体的位置；

Step2：计算每个个体的适应度大小，并记录全局最优个体的位置和适应度值；

Step3：将所有个体随机分为k个子种群，并根据控制参数F自动生成每个个体的F值；

Step4：为每个子种群生成交叉概率Cr；

Step5：使用策略3进行选择操作；

Step6：使用策略1对参数进行更新，并记录全局最优个体；

Step7：使用策略2调整每个子种群的大小；

Step8：重复执行步骤(3)～(7)，直到终止。

1.1.3 并行的猫群优化算法

原始的CSO算法是由CHU等人在2006年提出的[4]，其灵感来源于猫的行为。CSO将猫在休息时的状态看作算法的搜寻模式，一旦猫发现目标算法就会进入另一个阶段即跟踪模式。同时，通过一定的概率控制两种模式的执行比例。值得注意的是：在搜寻模式中，利用一定概率从记忆池中选择位置进行移动。概率公式如下：

(7)

其中，记忆池中有j只猫，Pi代表选中当前解的概率，Fi代表猫的适应度值，Fmax和Fmin.代表适应度值的最大和最小。Fb由目标函数确定，如果是最大化问题Fb=Fmin，相反则Fb=Fmax。在跟踪模式中，使用式(3)～(4)更新猫的速度和位置。

vi=vi+r1×c1×(xbest-xi)，

(8)

xi=vi+xi，

(9)

式中vi和xi代表第i只猫的速度和位置；xbest代表适应度值最好的猫的位置，c1为常数，r1是[0，1]之间的随机数。

CSO算法的步骤如下：

Step1：创建N只猫，随机初始化每只猫的位置、速度和标志；

Step2：评估每只猫的适应度值并记录全局最优个体；

Step3：根据标志判断执行跟踪过程或者搜寻过程；

Step4：根据一定的比例重新选取一定的个体执行搜寻模式，剩余的执行跟踪模式；

Step5：重复步骤(2)～(3)，直到结束。

文献[19]提出了CSO的并行化，称为并行的猫群优化算法(PCSO)。PCSO在跟踪过程中执行并行策略，满足交流条件时，对分组的个体执行组间交流。本文中具体的并行策略如下：

首先，随机选择一组个体，并对该组个体按照适应度值大小进行排序，适应度值最小的为个体L；

其次，在剩余组中随机选择一组个体，并记录局部最优解P；

最后，使用局部最优解P替换适应度值最差的个体L。

PCSO算法的步骤如下：

Step1：创建N只猫，同时将其分为g组，随机初始化每只猫的位置、速度和标志；

Step2：评估每只猫的适应度值并记录全局最优个体；

Step3：根据标志判断执行跟踪过程或者搜寻过程，如果是跟踪模式，则并行执行；

Step4：根据一定的比例选取一定的个体执行搜寻模式，剩余的执行跟踪模式；

Step5：判断是否满足信息交换的迭代次数，如果满足，则执行并行策略；

Step6：重复步骤(2)～(5)，直到结束。

1.1.4 其它并行的元启发式优化算法

表1整理了常见的并行元启发式算法。下面将按照算法进行分类，详细介绍这些常见算法的分组策略。

并行的共生生物搜索算法(SOS)：在文献[20]中，考虑到共生生物搜索算法的局限性，提出了多组思想和基于量子行为的组间交流策略(MQSOS)。对每个组中最好的5个个体根据式(10)更新，同时对每个组中较差的5个个体根据式(11)更新：

(10)

(11)

式中xnew为更新后的个体向量；xi为当前个体的位置；avei代表第i个个体历史最优位置的平均值；Pi是量子力学中的吸引点，个体在运动过程中，向Pi靠近；α和u分别为收敛系数和随机变量。

并行的狼群优化算法(GWO)：文献[21]提出了具有交流策略的分组的狼群优化算法(PGWO)。经过一定的迭代次数，将第i个组的m个最佳个体，替换第i+1组中较差的m个个体。文献[22]提出了多组GWO算法，将狼群按照适应度值分为多组，适应度值由大到小，最优的第1只狼分到第1组，第2只狼分到第2组，依次类推，循环分组。每隔一定的迭代次数，重新分组。

并行的差分进化算法(DE)：文献[23]动态地将种群分为3组，每个组中的个体按照由适应度值大小进行排序。然后将每个组中的前3个个体，随机替换其他组中后3个解。在下一次迭代的时候，再重新合并为一个大的群体，然后分为3个子种群。文献[24]提出了具有两种交流策略的并行紧凑差分进化算法(pcDE)。第1种是精英策略，该策略将所有组中的最优解替换为全局最优解。第2种是均值精英策略，对所有组中的最优解求平均值替换全局最优解。

并行的猫群优化算法(CSO)：文献[25]对PCSO算法进行的改进版本，提出了改进的并行猫群优化算法(EPCSO)。组间交流策略与PCSO中的交流策略一样，但是，使用了田口正交方法对PSCO进行改进。文献[26]对改进的PCSO进行了研究。与之前一样的是都在跟踪模式采用了并行策略，并进行信息交换。这篇论文主要对应用方面做出了突出的贡献。文献[27]将具有3种策略的PCSO算法与紧凑方案结合，应用到无线传感器网络定位问题上。策略1：平均替换，将每个组的局部最优解取平均代替每个组中最差的解。策略2：最佳替换，随机选择一组的最优值代替每个组的最差解。策略3：权重替换，将每个组的最优值，用不同的权重对应相乘之和代替每个组的随机解。

并行的蝙蝠算法(BA)：文献[28]提出了PBA算法并将其应用于车间调度问题。采用的交流策略是将第i组中k个最佳个体替换第i+1组较差的个体，第i+1组替换第i+2组，依次循环。文献[29]将并行与压缩策略结合，提出了一种改进的BA算法(pcBA)。该算法使用3种策略：所有组中最优值替换每个组中最差的；一个组中最优个体移动到相邻组中替换较差的个体；随机选择两个组进行交换。通过动态参数控制3种策略的执行。文献[30]提出了混合的并行蝙蝠算法(HPBA)，将变异操作嵌入到PBA中，克服了原始算法的不足。

并行的拟仿射变换进化算法(QUATRE)：文献[31]将并行策略引入到原始的QUATRE算法中，使用的策略是将每个组中最优的个体移动到相邻组中，替换相邻组较差的粒子。文献[32]将自适应、分组和QUATRE算法结合，使用3个组，每个组采用不同的策略更新迭代。文献[33]采用3种交流策略，每次随机选择一种对每个组中最差的个体进行更新。策略1：使用随机一组的最优个体与当前最差的粒子作差，再加上最差个体的位置偏移量，来替换最差的粒子。策略2：使用随机两组的最优个体平均值与当前最差的粒子作差，再加上最差个体的位置偏移量，替换最差的粒子。策略3，与之前的流程一样，不同的是选用3个组的最优个体平均值作差。

当然，还有一些其它的并行元启发式算法(见表1)。例如，多分组蜂群算法(MCBA)[34]，多组萤火虫算法(IMGFA)[35]，基于DE和花授粉算法(FPA)的并行优化算法(FDA)[36]，分布式并行萤火虫算法(DPFA)[37]，一个新的异构元启发式算法(PGWO)[38]，改进的花授粉算法(pcFPA)[39]，多分组花朵授粉算法(MFPA)[40]，并行多宇宙优化算法(PMVO)[41]，并行鲸鱼优化算法(PWOA)[42]，并行自适应布谷鸟搜索算法(pcCS)[43]，并行紧凑差分进化算法(pcDE)[24]，多组正余弦算法(MMSCA)[44]，并行正余弦算法(PSCA)[45]，自适应并行阿基米德优化算法(APAOA)[46]，多组协同进化的多目标蚱蜢优化算法(MOGOW)[47]，多组蜻蜓算法(MDA)[48]，自适应分组樽海鞘群算法(AMSSA)[49]等。

表1 多分组的并行元启发式算法总结

续表1

1.2 真实的并行

在本节中，对表2整理的文献进行分类，并简要的概述。并行元启发式算法的效率比较突出，有效的降低了运算成本，提高了运算时间，在复杂的全局优化问题上有突出效果。表2中，整理了真实的并行文章。

表2 真实的并行元启发式算法总结

1.2.1 并行化模型

并行化模型主要分为以下4种：主从模型、岛屿模型(粗粒度)、细胞元模型(细粒度)和混合模型[65，66，70，72，73，79]。

(1)主从模型：主从模式有一个主处理器，多个从处理器，所有的操作并行的在从处理器工作，并由主处理器控制。如图1所示，主从模式结构类似于星型。

(2)粗粒度模型：粗粒度模型也称岛屿模型，将一个种群分为多个子种群，每个子种群代表一个处理器单元。如图2所示，每个子种群之间通过交流策略进行沟通，从而交换部分个体。

(3)细粒度模型：细粒度模型也称细胞元模型，将一个种群划分为多个小的子种群，并将子种群映射到二维网格中。通常，每个子种群包含4个领域个体。然而，当与领域个体交换信息时，速度较快，与其他个体沟通时会出现延迟。如图3所示。

(4)混合模型：由上面两个或两个以上模型组合的并行化模型称为混合模型。如图4所示。

图1 主从模式 图2 粗粒度模式

图3 细粒度模式 图4 混合模式

1.2.2 并行元启发式算法的研究

ASADZADEH使用3种模型实现了并行ABC算法(pABC)[74]：主从模型，细粒度模型和粗粒度模型。在粗粒度模型中，pABC在每个处理器上设置了一个殖民地，共有n个，每个殖民地使用的领域拓扑结构是立方体，并且每两个殖民地之间动态地进行信息沟通。

在文献[64]使用主从模式对原始GA进行改进，共享多处理器，并将其应用于学校时间表问题。文献[67]分析了同步和并行式GA的响应力，还涉及了岛屿模型和细胞元模型。文献[68]中提出了并行GA，并将其应用于带时间窗的车辆路径规划。该算法将种群分为两个组(G1和G2)，每个组负责一个目标：G1负责最小化移动距离，G2负责最小化约束冲突，并且两个种群协同进化。

文献[16]使用了广播的交流策略，研究了同步和异步的并行多分组PSO算法，并将其用于解决多目标问题。文献[71]中，使用3种模型实现PPSO算法：岛屿模型、细胞元模型和领域岛屿模型。岛屿-PPSO使用环形结构实现每个子种群的演化，在进化过程中，通过迁移实现信息交流。迁移策略是将每个岛的最佳粒子替换相邻岛中随机选择的粒子。细胞-PPSO将粒子分布到处理单元中，全局最优解不可见，故交流策略使用局部粒子中最佳的粒子更新。领域岛屿-PPSO与岛屿-PPSO不同，将迁移的概念取消，使用环形拓扑结构和二维网络拓扑结合。

文献[14]提出了并行蚁群算法(PACS)，该算法使用3种通信方式，有效的解决了旅行商问题。文献[69]提出了并行蚁群优化算法(PACS)，采用7种交流策略。策略1，将最优个体分为一组，将剩余的个体随机分为多组，每隔一定的迭代次数，用最好的组去优化其他组的个体。策略2，每隔一定的迭代次数，随机找一对组进行交流。策略3，组与组构成环结构进行信息素的更新。策略4，向相邻组更新信息素。策略5、策略6和策略7是策略1分别和策略2、策略3、策略4的组合。

2 基于并行优化算法的应用

近年来，越来越多的论文使用并行元启发式算法解决各样格式的复杂问题，主要包括以下几个方面：无线传感器网(WSN)、旅行商问题(TSP)、图像分割、调度问题、路径规划等问题。在本节中，主要回顾并行元启发式算法的应用问题。同时，在表1和表2中列举了相关文章的应用。

(1)无线传感器网络是一种很有前途的新兴技术，它由传感器节点组成，节点用于获取周围的信息。例如，文献[26]使用EPCSO对无线传感器节点的部署进行了优化，延长了无线传感器网络的使用寿命，同时降低了传感器网络节点的损耗。文献[32]将改进的拟仿射变换算法(AMG-QUATRE)应用于WSN的定位，实验结果表明，AMG-QUATRE与其他算法相比，定位更准确。文献[29]使用pcBA对WSN的能量平衡问题进行优化。文献[42]使用PWOA算法准确预测WSN节点的位置，提前预防各种灾害的发生。

(2)旅行商问题是组合优化中常见的问题，目标是如何找到最短的路径。例如，文献[30]将并行的蝙蝠算法对TSP进行建模，有效地解决了旅行商问题。由于原始的蚁群算法求解TSP时，会出现陷入局部最优的现象。所以文献[63]对原始的算法进行改进，使用奖励机制，使得更快更准的找到了各个城市之间的最短路径。文献[69]使用3种交流策略，将PACO算法应用于TSP，并使用了大量的数据进行检验。总体而言，所提出的算法可以获得很好的性能。

(3)调度问题被广泛应用于工业、交通和医疗保健等各个领域。例如，文献[55]解决了经济负荷调度问题；文献[56]解决了云计算调度问题；文献[28，74]有效解决了车间调度问题；文献[77]解决了经济排放负荷调度问题。

3 结论

近年来，关于元启发式算法的研究越来越多。本文对并行元启发式算法进行了总结，将并行策略分为两大类：第1类是虚拟的并行，也称分群。详细介绍了分群的概念，然后根据所调查的文献对并行元启发式算法进行展开；第2类是真实的并行，将种群分为多组，每个组在不同的处理器上面执行。本文首先详细介绍了4种常见的并行化模型(主从模式、粗粒度模型、细粒度模型和混合模型)和一些代表性的研究成果。由于并行元启发式算法广泛应用于各个领域，论文中最后对所调查文献中的应用进行了整理，主要介绍了3类常见的应用问题。在未来，可以采用各种并行化模型与元启发式发进行结合，应用于多目标问题上，有效的提高效率和性能。