论文部分内容阅读
摘 要： 分析了传统粗粒度并行遗传算法的局限性，针对其迁移固定不变及无效迁移造成的通信开销大等缺点，将公共池与自适应迁移策略相结合，提出了一种适合在多核计算机上运行的基于公共池自适应迁移策略的并行遗传算法。该算法根据当前的进化状态自适应地进行迁移，并利用公共池淡化了子种群间交换个体时的拓扑结构。对复杂非线性函数求极值的仿真结果表明，该算法与传统并行遗传算法相比，收敛速度快，求解精度高，得到最优解的进化代数提前，并行效率明显提升。
关键词： 粗粒度； 并行遗传算法； 公共池； 自适应迁移策略； 函数优化
中图分类号：TP391 文献标志码：A 文章编号：1006-8228（2016）10-43-04
Parallel genetic algorithm based on adaptive migration strategy of sharing pool
Jiang Ran
（Faculty of Information Engineering， Yangzhou Ploytechnic College， Yangzhou， Jiangsu 225000， China）
Abstract： The limitations of traditional coarse grained parallel genetic algorithm are analyzed. Aiming at the disadvantages of high communication overhead caused by fixed or invalid migration， a parallel genetic algorithm is proposed， which is suitable for running on multi-core computers and based on the adaptive migration strategy of sharing pool. According to the current state of evolution， the proposed algorithm can adapt to the migration， and the sharing pool is used to dilute the topological structure of the individual exchange between the sub populations. Simulation results for extreme value of complex nonlinear function show that， compared with the traditional parallel genetic algorithm， the algorithm is fast convergence， high precision， early to obtain the evolutionary generation of optimal solution， and significantly improves the parallel efficiency.
Key words： coarse grained； parallel genetic algorithm； sharing pool； adaptive migration strategy； function optimization
0 引言
并行遗传算法（Parallel Genetic Algorithms，PGA）是将并行计算机的高速并行性和遗传算法的天然并行性相结合的一种算法。目前并行遗传算法模型分为主从式模型、粗粒度模型、细粒度模型和混合模型[1]。其中粗粒度模型是应用最广且适应性最强的并行遗传算法模型。
1 研究现状
国内外学者对粗粒度模型的研究，主要集中在迁移拓扑、迁移规模和迁移策略等问题上[2]。近几年相关的研究包括：蔡明頔、胡振兴等人提到的通过对交叉算子的修正，以及多个小规模种群并行优化求解的方案[3-4]；刘晋胜等人提出的采用八个不同策略为并行遗传算法的分支遗传操作进行群体寻优等[5-6]。
根据这些研究分析可知，一方面，如果粗粒度模型中各子种群之间迁移间隔小，则有利于提高解的精度和收敛速度，但会明显地增大通信及同步开销，如果迁移间隔较大，虽然降低了通信及同步开销，但不利于提高解的精度和收敛速度。针对这个问题，本文提出一种自适应迁移策略，即各个子种群中执行个体迁移时，并不是固定不变地移迁，而是根据当前的进化状态动态、有条件地迁移；此外，本文提出公共池的概念，应用公共池的方式来代替各子种群间个体迁移时的拓扑结构。因此，将本文算法称为基于公共池自适应迁移策略的并行遗传算法（Parallel Genetic Algorithm Based on Adaptive Migration Strategy of Sharing Pool，简称AMSPPGA算法）。
2 AMSPPGA算法
2.1 AMSPPGA算法的选择算子
AMSPPGA算法的选择算子总共选出k个个体，其过程描述为：首先计算种群中每一个个体的适应值，然后按适应值从大到小排序，从中选取前s（s 2.2 AMSPPGA算法的交叉淘汰算子
在AMSPPGA算法中，交叉淘汰算子采用文献[7]提出的多父体杂交算子的思想。多父体杂交算子的思想如下[7]：考虑函数优化问题，其中，，记D中的M个点为，记所生成的子空间为，其中aj满足条件：。 在AMSPPGA算法中，借鉴多父体杂交算子的思路，结合算法特点，交叉淘汰算子设计过程如下[8]：
Step1：；
Step2：如果则转到Step8；
Step3：随机生成，并使aj满足：，并且；
Step4：对选择算子选择出来的k个个体：生成一个新个体：即；
Step5：令为种群P（t）中最差的个体，如果优于，则用替换；
Step6：；
Step7：转到Step2；
Step8：交叉淘汰算子结束。
在交叉淘汰算子中，RI为替换、淘汰个体的数量，其值大小决定了算法替换、淘汰压力的大小。
2.3 AMSPPGA算法的迁移算子
种群间个体的迁移算子决定着各子种群以什么样的方式与其他种群中的个体交换。本文对迁移算子进行改进，用公共池的方式来代替各子种群间个体迁移时的拓扑结构。
首先对迁移算子的初始条件作说明：设粗粒度并行遗传算法的子种群数为m，每个种群中的个体总数都为n，第i个子种群在进化代数为j时的最佳个体为，该个体的适应度值为[9]。
算法设置一个公共池，用来接收各子种群的最佳和最差适应度个体，在公共池中维护两个数组。一个数组存储各子种群传来的最佳适应度个体，其数据元素为结构体形式，q为子种群号，也对应着数组的下标，其中，存储第q个种群的最佳个体值；另一个数组存储各子种群传来的最差适应度个体，数据元素为结构体形式，其他含义同上。
设当前的子种群号为s，进化代数为gen，具体的迁移算子步骤为：选择当前子种群中适应度值最佳（最差）的个体（），并将该个体的适应度值（）与公共池中最佳（最差）个体数组中相应种群号的（）比较，如果大于（小于），就表示本次得到了比上次与公共池交互时更好（更差）的个体，此时分别用（）和（）替换种群s在公共池中的（）和（）的值；否则不替换。
利用公共池方式可以先存储所有子种群的迁移个体，然后再进行比较、处理操作。相比于按拓扑结构指定的次序来进行传递两个子种群中的最优及最差个体，这样做更有利于最优个体向各个子种群扩散，并且减少了因为无效迁移造成的通信及同步开销，同时在公共池中用两个数组分别来存放各子种群中的最优及最差个体，可以使得公共池的维护更方便。
2.4 AMSPPGA算法的迁移准则
在AMSPPGA算法中，各个子种群中执行个体迁移时，并不是固定不变地移迁，而是根据当前的进化状态动态、有条件地迁移。为了便于描述AMSPPGA算法的迁移准则，给出以下定义。
在公式1中，n为种群大小，为适应值函数，为种群P的所有个体偏离中心点的距离平方之和，相似度能够体现出在当前代时种群中各个个体的之间的差异程度。从公式⑴可知：当较大时，表明种群中个体差异程度较大，即表明种群中个体呈现多样性；当较小时，表明种群中个体差异程度较小，即表明种群中个体即将收敛[10]。
AMSPPGA算法的迁移准则如下，首先利用公式⑴计算出当前种群个体的相似度，当种群个体相似度小于时，表明个体差异较小，此时从公共池中接受一个使本子种群的个体相似度达到最大的个体，随机替换一个个体，以增大种群个体的多样性。当种群个体相似度大于时，表明个体差异较大，此时从公共池中接受一个最优的个体，以便发挥优良个体的导向作用，加快收敛。
2.5 AMSPPGA算法具体描述
AMSPPGA算法具体描述如下。
Step 1：初始化子种群数目m，子种群中的个体数目n等算法的运行参数。
Step 2：创建m个子线程，让m个子线程并行地对各个子种群执行初始化，利用本文2.1中的思路进行选择算子操作，利用本文2.2中的思路进行交叉淘汰算子操作。
Step 3：每一个子种群计算本代中个体的适应值，利用本文2.3小节的思想和步骤生成迁移算子。
Step 4：利用本文2.4小节的迁移思想和迁移准则执行迁移操作。
Step 5：判断接受来的新个体是否存在于本子种群中，以及是否比最差个体好来决定是否淘汰最差个体。
Step 6：令为种群q中最差的个体，为种群q中最优的个体。如果等于，则转到Step 7，否则转到 Step 3。
Step 7：算法结束。
3 仿真及结果分析
采用较为复杂的非线性函数求极值问题对AMSPPGA算法进行验证，并与传统PGA算法进行对比。
Schaffer函数为：
设公式⑵各自变量x1，x2的取值都在[-100，100]之间，Schaffer函数为在（0，0）处存在全局极大值点1。AMSPPGA算法采用实数编码，参数设定如下：种群规模为100，子种群数为2，最小和最大个体相似度分别为0.1和10.0，最大进化代数为100，CPU类型为Intel双核处理器T6570，按照AMSPPGA算法连续执行程序10次，得到表1实验结果。结果表明每次执行都能找到问题的全局最优解。
将传统PGA算法与AMSPPGA算法分别在1，2，4核CPU计算机上连续执行程序10次，根据实验结果，两种算法的并行加速比曲线如图1所示。
从图1中可以看出，由于AMSPPGA算法根据当前的进化状态动态、有条件地迁移，有效地提高了个体迁移的效率，求解问题时AMSPPGA算法的并行加速比明显高于传统PGA算法，具有较好的性能。
Schaffer函数求极值时最优解变化情况
从图2中可以看出，传统PGA算法当进化到60代时得到最优解，AMSPPGA算法在进化25时就得到最优解，并且最优解的质量比传统PGA算法要高，这是由于本文算法使用了公共池方式，减少了因为无效迁移造成的通信及同步开销，同时又保证了各子种群之间的优良个体有效迅速地传播，充分发挥了优良个体的导向作用，避免了传统PGA算法迁移时的盲目性、固定性，提高了传统PGA算法的全局寻优能力，以及求解精度和收敛速度。 4 结束语
本文针对并行遗传算法的粗粒度模型这个主要研究热点，从模型的迁移策略入手进行研究，探讨迁移算子作用机制的本质，提出了一种基于公共池自适应迁移策略的并行遗传算法。算法根据当前的进化状态，动态、有条件地迁移，并利用公共池淡化了子种群间的拓扑结构。实验结果表明，本文算法确实有效地提高了个体迁移的效率和算法的收敛速度，减少了因无效迁移造成的通信及同步开销，得到了更好质量的解，并且出现最优解的代数也缩短，算法的并行效率比传统PGA算法明显更高。
参考文献（References）：
[1] 冯小丹，娄自婷，王文元.并行遗传算法的研究及应用进展[J].
电脑知识与技术，2014.10（10）：2347-2350
[2] 高家全，何桂霞.并行遗传算法研究综述[J].浙江工业大学学
报，2007.35（1）：56-59
[3] 蔡明頔，么焕民.基于小种群策略的并行遗传算法[J].哈尔滨
师范大学自然科学学报，2013.29（3）：13-15
[4] 胡振兴，李汪根.基于小种群策略的并行遗传算法[J].软件导
刊，2013.12（2）：33-35
[5] 刘晋胜，彭志平，周靖.一种多策略并行遗传算法研究[J].计算
机测量与控制，2011.19（2）：1188-1190
[6] 刘晋胜，彭志平，周靖.一种多策略并行遗传算法研究及其收
敛性分析[J].计算机测量与控制，2011.19（8）：2022-2025
[7] 郭涛，康立山，李艳.一种求解不等式约束下函数优化问题的
新算法[J].武汉大学学报（自然科学版），1999.45（5）：771-775
[8] 郭肇禄.一种基于自适应迁移策略的并行遗传算法[D].江西
理工大学，2009
[9] 严晓明.粗粒度并行遗传算法迁移算子的一种改进[J].福建
师范大学学报（自然科学版），2013.29（1）：42-47
[10] 李伟，黄颖，李康顺.一种基于自适应迁移策略的并行遗传
算法[J].武汉理工大学学报，2011.33（7）：138-142
关键词： 粗粒度； 并行遗传算法； 公共池； 自适应迁移策略； 函数优化
中图分类号：TP391 文献标志码：A 文章编号：1006-8228（2016）10-43-04
Parallel genetic algorithm based on adaptive migration strategy of sharing pool
Jiang Ran
（Faculty of Information Engineering， Yangzhou Ploytechnic College， Yangzhou， Jiangsu 225000， China）
Abstract： The limitations of traditional coarse grained parallel genetic algorithm are analyzed. Aiming at the disadvantages of high communication overhead caused by fixed or invalid migration， a parallel genetic algorithm is proposed， which is suitable for running on multi-core computers and based on the adaptive migration strategy of sharing pool. According to the current state of evolution， the proposed algorithm can adapt to the migration， and the sharing pool is used to dilute the topological structure of the individual exchange between the sub populations. Simulation results for extreme value of complex nonlinear function show that， compared with the traditional parallel genetic algorithm， the algorithm is fast convergence， high precision， early to obtain the evolutionary generation of optimal solution， and significantly improves the parallel efficiency.
Key words： coarse grained； parallel genetic algorithm； sharing pool； adaptive migration strategy； function optimization
0 引言
并行遗传算法（Parallel Genetic Algorithms，PGA）是将并行计算机的高速并行性和遗传算法的天然并行性相结合的一种算法。目前并行遗传算法模型分为主从式模型、粗粒度模型、细粒度模型和混合模型[1]。其中粗粒度模型是应用最广且适应性最强的并行遗传算法模型。
1 研究现状
国内外学者对粗粒度模型的研究，主要集中在迁移拓扑、迁移规模和迁移策略等问题上[2]。近几年相关的研究包括：蔡明頔、胡振兴等人提到的通过对交叉算子的修正，以及多个小规模种群并行优化求解的方案[3-4]；刘晋胜等人提出的采用八个不同策略为并行遗传算法的分支遗传操作进行群体寻优等[5-6]。
根据这些研究分析可知，一方面，如果粗粒度模型中各子种群之间迁移间隔小，则有利于提高解的精度和收敛速度，但会明显地增大通信及同步开销，如果迁移间隔较大，虽然降低了通信及同步开销，但不利于提高解的精度和收敛速度。针对这个问题，本文提出一种自适应迁移策略，即各个子种群中执行个体迁移时，并不是固定不变地移迁，而是根据当前的进化状态动态、有条件地迁移；此外，本文提出公共池的概念，应用公共池的方式来代替各子种群间个体迁移时的拓扑结构。因此，将本文算法称为基于公共池自适应迁移策略的并行遗传算法（Parallel Genetic Algorithm Based on Adaptive Migration Strategy of Sharing Pool，简称AMSPPGA算法）。
2 AMSPPGA算法
2.1 AMSPPGA算法的选择算子
AMSPPGA算法的选择算子总共选出k个个体，其过程描述为：首先计算种群中每一个个体的适应值，然后按适应值从大到小排序，从中选取前s（s
在AMSPPGA算法中，交叉淘汰算子采用文献[7]提出的多父体杂交算子的思想。多父体杂交算子的思想如下[7]：考虑函数优化问题，其中，，记D中的M个点为，记所生成的子空间为，其中aj满足条件：。 在AMSPPGA算法中，借鉴多父体杂交算子的思路，结合算法特点，交叉淘汰算子设计过程如下[8]：
Step1：；
Step2：如果则转到Step8；
Step3：随机生成，并使aj满足：，并且；
Step4：对选择算子选择出来的k个个体：生成一个新个体：即；
Step5：令为种群P（t）中最差的个体，如果优于，则用替换；
Step6：；
Step7：转到Step2；
Step8：交叉淘汰算子结束。
在交叉淘汰算子中，RI为替换、淘汰个体的数量，其值大小决定了算法替换、淘汰压力的大小。
2.3 AMSPPGA算法的迁移算子
种群间个体的迁移算子决定着各子种群以什么样的方式与其他种群中的个体交换。本文对迁移算子进行改进，用公共池的方式来代替各子种群间个体迁移时的拓扑结构。
首先对迁移算子的初始条件作说明：设粗粒度并行遗传算法的子种群数为m，每个种群中的个体总数都为n，第i个子种群在进化代数为j时的最佳个体为，该个体的适应度值为[9]。
算法设置一个公共池，用来接收各子种群的最佳和最差适应度个体，在公共池中维护两个数组。一个数组存储各子种群传来的最佳适应度个体，其数据元素为结构体形式，q为子种群号，也对应着数组的下标，其中，存储第q个种群的最佳个体值；另一个数组存储各子种群传来的最差适应度个体，数据元素为结构体形式，其他含义同上。
设当前的子种群号为s，进化代数为gen，具体的迁移算子步骤为：选择当前子种群中适应度值最佳（最差）的个体（），并将该个体的适应度值（）与公共池中最佳（最差）个体数组中相应种群号的（）比较，如果大于（小于），就表示本次得到了比上次与公共池交互时更好（更差）的个体，此时分别用（）和（）替换种群s在公共池中的（）和（）的值；否则不替换。
利用公共池方式可以先存储所有子种群的迁移个体，然后再进行比较、处理操作。相比于按拓扑结构指定的次序来进行传递两个子种群中的最优及最差个体，这样做更有利于最优个体向各个子种群扩散，并且减少了因为无效迁移造成的通信及同步开销，同时在公共池中用两个数组分别来存放各子种群中的最优及最差个体，可以使得公共池的维护更方便。
2.4 AMSPPGA算法的迁移准则
在AMSPPGA算法中，各个子种群中执行个体迁移时，并不是固定不变地移迁，而是根据当前的进化状态动态、有条件地迁移。为了便于描述AMSPPGA算法的迁移准则，给出以下定义。
在公式1中，n为种群大小，为适应值函数，为种群P的所有个体偏离中心点的距离平方之和，相似度能够体现出在当前代时种群中各个个体的之间的差异程度。从公式⑴可知：当较大时，表明种群中个体差异程度较大，即表明种群中个体呈现多样性；当较小时，表明种群中个体差异程度较小，即表明种群中个体即将收敛[10]。
AMSPPGA算法的迁移准则如下，首先利用公式⑴计算出当前种群个体的相似度，当种群个体相似度小于时，表明个体差异较小，此时从公共池中接受一个使本子种群的个体相似度达到最大的个体，随机替换一个个体，以增大种群个体的多样性。当种群个体相似度大于时，表明个体差异较大，此时从公共池中接受一个最优的个体，以便发挥优良个体的导向作用，加快收敛。
2.5 AMSPPGA算法具体描述
AMSPPGA算法具体描述如下。
Step 1：初始化子种群数目m，子种群中的个体数目n等算法的运行参数。
Step 2：创建m个子线程，让m个子线程并行地对各个子种群执行初始化，利用本文2.1中的思路进行选择算子操作，利用本文2.2中的思路进行交叉淘汰算子操作。
Step 3：每一个子种群计算本代中个体的适应值，利用本文2.3小节的思想和步骤生成迁移算子。
Step 4：利用本文2.4小节的迁移思想和迁移准则执行迁移操作。
Step 5：判断接受来的新个体是否存在于本子种群中，以及是否比最差个体好来决定是否淘汰最差个体。
Step 6：令为种群q中最差的个体，为种群q中最优的个体。如果等于，则转到Step 7，否则转到 Step 3。
Step 7：算法结束。
3 仿真及结果分析
采用较为复杂的非线性函数求极值问题对AMSPPGA算法进行验证，并与传统PGA算法进行对比。
Schaffer函数为：
设公式⑵各自变量x1，x2的取值都在[-100，100]之间，Schaffer函数为在（0，0）处存在全局极大值点1。AMSPPGA算法采用实数编码，参数设定如下：种群规模为100，子种群数为2，最小和最大个体相似度分别为0.1和10.0，最大进化代数为100，CPU类型为Intel双核处理器T6570，按照AMSPPGA算法连续执行程序10次，得到表1实验结果。结果表明每次执行都能找到问题的全局最优解。
将传统PGA算法与AMSPPGA算法分别在1，2，4核CPU计算机上连续执行程序10次，根据实验结果，两种算法的并行加速比曲线如图1所示。
从图1中可以看出，由于AMSPPGA算法根据当前的进化状态动态、有条件地迁移，有效地提高了个体迁移的效率，求解问题时AMSPPGA算法的并行加速比明显高于传统PGA算法，具有较好的性能。
Schaffer函数求极值时最优解变化情况
从图2中可以看出，传统PGA算法当进化到60代时得到最优解，AMSPPGA算法在进化25时就得到最优解，并且最优解的质量比传统PGA算法要高，这是由于本文算法使用了公共池方式，减少了因为无效迁移造成的通信及同步开销，同时又保证了各子种群之间的优良个体有效迅速地传播，充分发挥了优良个体的导向作用，避免了传统PGA算法迁移时的盲目性、固定性，提高了传统PGA算法的全局寻优能力，以及求解精度和收敛速度。 4 结束语
本文针对并行遗传算法的粗粒度模型这个主要研究热点，从模型的迁移策略入手进行研究，探讨迁移算子作用机制的本质，提出了一种基于公共池自适应迁移策略的并行遗传算法。算法根据当前的进化状态，动态、有条件地迁移，并利用公共池淡化了子种群间的拓扑结构。实验结果表明，本文算法确实有效地提高了个体迁移的效率和算法的收敛速度，减少了因无效迁移造成的通信及同步开销，得到了更好质量的解，并且出现最优解的代数也缩短，算法的并行效率比传统PGA算法明显更高。
参考文献（References）：
[1] 冯小丹，娄自婷，王文元.并行遗传算法的研究及应用进展[J].
电脑知识与技术，2014.10（10）：2347-2350
[2] 高家全，何桂霞.并行遗传算法研究综述[J].浙江工业大学学
报，2007.35（1）：56-59
[3] 蔡明頔，么焕民.基于小种群策略的并行遗传算法[J].哈尔滨
师范大学自然科学学报，2013.29（3）：13-15
[4] 胡振兴，李汪根.基于小种群策略的并行遗传算法[J].软件导
刊，2013.12（2）：33-35
[5] 刘晋胜，彭志平，周靖.一种多策略并行遗传算法研究[J].计算
机测量与控制，2011.19（2）：1188-1190
[6] 刘晋胜，彭志平，周靖.一种多策略并行遗传算法研究及其收
敛性分析[J].计算机测量与控制，2011.19（8）：2022-2025
[7] 郭涛，康立山，李艳.一种求解不等式约束下函数优化问题的
新算法[J].武汉大学学报（自然科学版），1999.45（5）：771-775
[8] 郭肇禄.一种基于自适应迁移策略的并行遗传算法[D].江西
理工大学，2009
[9] 严晓明.粗粒度并行遗传算法迁移算子的一种改进[J].福建
师范大学学报（自然科学版），2013.29（1）：42-47
[10] 李伟，黄颖，李康顺.一种基于自适应迁移策略的并行遗传
算法[J].武汉理工大学学报，2011.33（7）：138-142