基于共享存储的并行狭义遗传算法

晏妮

（陕西安康职业技术学院 陕西 安康725000）

基于共享存储的并行狭义遗传算法

晏妮

（陕西安康职业技术学院 陕西 安康725000）

遗传算法具有简单、易算且方便分布并行处理等特点，基于这种优势，遗传算法被广泛应用于众多领域范围内，比如机器学习、工业控制等。为解决高难度的非线性及其相关问题，采用基于共享存储的并行狭义遗传算法，可以有效实现对数据级的并行操作，具有较强的并行度，其只需较少的通讯开销就能获得比原先更高的运行效率，至少提高至50%以上。文中详细阐述了基于共享存储的并行狭义遗传算法，仿真实验验证了其正确性和高效性。

共享存储；并行狭义遗传算法；非线性；探究

遗传算法拥有广泛的发展前景，且应用范围极广，是一种全局优化的搜索算法，常常应用于解决许多复杂的问题中，究其本质，遗传算法就是一种模式的运算，具有简单、易算且方便分布并行处理等特点。而基于共享存储的并行狭义遗传算法更是将这些优势得到了进一步提高，使其被广泛应用于工业控制、作曲等诸多方面，实现了高效率运行。

1 并行狭义算法的简要概述

狭义遗传算法具有一定的局部收敛性，属于遗传算法的一种，但这种方法的搜索并不是一个Markov过程。所谓Markov过程，通常用以下方式表达：设{X(t),t∈T}，对任意n个不同的t1＜t2＜…＜tn-1＜tn,则有 P(X(tn)≤xn|X(tn-1)=xn-1,… X(t1)= x1=P(X(tn)≤xn|X(tn-1)=xn-1），则称 X(t)为马尔可夫（Markov）过程，简称马氏过程。但这种狭义的遗传算法的搜索率十分高，且收敛过程的稳定性也十分高，同时在搜索过程中具有较强的可控制性。但无论是粗粒度还是细粒度的并行遗传算法，都具有很低的运行效率。究其原因，这主要是因为并行遗传算法的运行效率都不太高，且他们在实现并行方面，都只能实现控制并行的功能，却不能实现对数据的并行。而狭义遗传算法却能够实现对数据的并行且具有很小的通讯开销，同时还具有较高的运行效率。

2 基于共享存储的并行狭义遗传算法的模型分析

通常情况下，并行狭义遗传算法的模型需要满足以下条件，第一，需要进行一次利用基于个体进化的狭义遗传算法，对一个给定的区域[G,K]进行搜索，且搜索的是一个并行任务，在搜索的过程中，每一个并行任务都会产生一个并行进程进而完成搜索任务。第二，每一个并行进程都需要一个处理器资源，这个处理器资源通过申请就可以得到，如果处理器资源的申请通过就可以在有限的时间内完成任务。第三，一个并行进程最多只能允许在一个处理器资源上运行。第四，每一个并行进程在申请处理器资源时，如果资源能够满足既可以在限制的时间内完成任务。第五，处理器资源都具有一定的有限性。第六，利用个体进化的狭义遗传算法所得到的求解，可将其归纳为有限个子任务，也可以说是有限个并行进程。所以，针对以上条件，就需要设置一个等待队列的进程，也可以说是公共存储区，该共享队列主要用来保存局部最优解。一般情况下，共享队列应存放在处理器上面，并且要求是一个被激活的处理器。如图1所示。

由于一个并行进程最多只能允许在一个处理器资源上运行，当一个资源处理器产生了两个新的搜索任务时，其中有一个搜所任务在处理器上运行，那么另一个搜索任务就必须申请其他处理器之后，再在相应的处理器上运行，这样才能确保运行的顺利进行。所以，系统中的每一个处理器都会产生一定的任务，并将其传递到其他系统中的处理器，进而产生局部最优解，而这些最优解会迅速传递到第一个被激活的处理器资源上，因此，这样才能得到全局最优解。

图1 系统处理器之间通讯示意图Fig.1 Communication between the system processor schematic

3 基于共享存储的并行狭义遗传算法的实现

当在任意一个处理器上设立一个公共队列Q的过程中，其目的就是为了存储搜索的局部最优结果，那么，基于共享存储的并行狭义遗传算法是如何实现的呢？具体分析如下。

3.1 并行狭义遗传算法的探索进程和开发进程之间的关系

如图2所示，由于并行狭义遗传算法主要是用于探索空间的，一旦算法开始，就会启动n个并行进程算法进行探索空间，这一过程就被称为探索进程。因此，每一个并行进程都有一个相对应的群体进行操作，设置一个模式变量，其主要就是用来存放模式，并确保它们能够初始化为不同的群体。这时，就要求距离函数满足下述条件：h(P)＜h(P)时，其中11i0i代表的是探索进程的符号，且1≤i≤n。如果随机选取一个探索进程并将其模式变量取出，如果为空，则并行探索进程处于刚启动的状态，因为只有刚启动时，并行进程才会出现这种可能。这时，将提取的模式直接加入到本地模式变量中，这样在和远程读取的模式进行空间交配，最终产生两个新模式，并随机存入本地和远程模式变量中，然后继续执行进程，直至出现最优解，然后将其提交给开发进程，并读取本地模式变量，并用它来将本地群体进行初化，继续上述步骤，直至收到终止信号，结束本进程。基于空间交配的特殊性，各探索进程分别对不同的子空间进行搜索，所以，采用过大的变异和交叉概率是不适宜的，只有采用适宜的变异和交叉概率，才能有效实现搜索的可达性。

图2 探索进程和开发进程之间的关系Fig.2 Explore the relationship between the process and the development process

通常情况下，开发进程的操作群体空间在刚开始的时候，确保相应的个体，而这些个体都是由n个探索进程所提供。一旦群体满了之后，这时就要采用最小的淘汰法对探索进程中提交的个体进行相应的接收。更重要的一点是，由于n个探索进程分别在n个不同的模式空间之中进行搜索功能，这在一定程度上就已经保证了所提交的个体分别是不同子空间中的最优个体，这样才能使开发进程对具有多样性的个体进行操作，使其得到有效保障。所以，这样的开发进程适宜采用小变异概率和交叉概率进行运算，从而避免群体中已积累有用信息的多样性较优个体遭到破坏。

3.2 基于共享存储的并行狭义遗传算法的操作步骤

对一个给定的区域[G,K]内进行搜索操作，便会产生一个进程，而这些进程便会执行以下操作：

1)一旦给定的区域[G,K]进行搜索任务时，产生一个进程，而每个进程会相应产生一个初始群体M,M满足{a1,a2,a3…,am}.

2)对所产的初始群体M中的a1,a2,a3…,am都要进行适应度的评估。

3)一旦对群体M执行操作后，群体M已焕然一新，成为被更新后的种群M。

4)做出准确的判断，即群体M是否达到稳定的状态。如果已经达到稳定的状态，就会得到局部最优个体R，其作用主要有3项，首先，主要是为了调用基于个体化的狭义遗传算法，进而得到子区域[R1,R2];其次，是将当前局部最优解及其对应的子区域[R1,R2]，将其加入到共享队列Q中，最后重新确定搜索区域，同时执行并行遗传操作。完成下文第6个步骤。如果群体M没有进化达到稳定的状态，则进行交叉操作，按照第5个步骤进行。

5)执行交叉操作，并转入第2个操作，即对所产的初始群体M中的每一个个体都要进行适应度的评估。

6)重新确定搜索区域，同时执行并行遗传操作。其中，并行遗传操作主要可分为四种情况进行，第一种情况是，当G= R1时，则将原来的分区[G,K]转变为新的区域[R2,K]，这样就可以在搜索过程中产生一个在当前处理器上运行的新进程。第二情况是，当K=R2时，就可以将原来的分区[G,K]转变为新的区域[G,R1]，这样就可以在新区域搜索任务中产生新的进程，并在处理器资源上运行。第三种情况是，当G=R1且K=R2时，则证明区域[G,K]已经完成搜索任务。第四种情况是，当G≠R1且K≠R2，则原来的区域[G,K]已经边变为新的[G,R1]和[R2,K]，这样就可以在新区域搜索任务中产生新的进程，这样就可以申请处理器资源，如果能够得到满足通过就可以在处理器资源上运行，进而执行并行遗传搜索，如果没有得到满足，则该进程就会处于等待队列状态，另外，对于新区域[G,R1]的搜索也会产生一个进程，并让该进程在当前处理器上运行。

7)当全部分区域被搜索后就会将队列Q中的内容输出，这样就能够得到公共队列中的最有个体，也就是全局的最优解。

3.3 并行狭义遗传算法具有较高的运行效率

通常情况下，基于共享存储的并行狭义遗传算法一般会根据实际情况，采用自动区域划分的方法,这样就可以让不同区域的遗传寻优过程分布到不同的处理器上进行并行执行过程。因此，在进行区域划分之后，各个子区域之间应满足下述内容：

1)Di∩Dj=Φ，∀i，j{1,2，…，m}，且i≠j；这主要是考虑到具体实现时的可操作性，则算法存在着边界相交。

3)每个分区上都只有一个极值点，即每个子区域都是单峰值区域，其中{D1，D2，…Dm}为D的一个划分。因此，时间顺序来说，各个区域之间的依赖关系属于一种二叉树结构。如图3所示。

图3 自动区域划分和各个区域之间的关系Fig.3 Automatic zoning and relationship between the various regions

所以，对各个子区域之间的遗传搜索可以并行地完成，这种并行操作是数据级的并行。另外，并行算法中唯一的通讯开销是在各进程之间传递一次初始值和返回搜索后的局部最优解，因此通讯开销小。而利用CGA或GGA实现的并行算法需要不断地交换不同子群体或邻域之间的个体或最优个体，或者需要不断地分配初始遗传子群体并收集遗传搜索结果。显然，CGA或GGA的并行算法的通讯开销比RGA的并行算法的通讯开销大得多。综上所述，基于共享存储的并行狭义遗传算法具有较高的运行效率。

4 结束语

综上所述，正是基于共享存储的并行狭义遗传算法具有较高的并行度，以及高运行效率，不仅使数据级的并行操作成为现实，同时还使得它被广泛应用于各个行业，为电子科技领域做出了重要贡献。

[1]王竹荣,巨涛,马凡.多核集群系统下的混合并行遗传算法研究[J].计算机科学,2011(7):194-199. WANG Zhu-rong,JU Tao,MA Fan.Genetic algorithm hybrid multi-core parallel cluster system under[J].Computer Science,2011(7):194-199.

[2]肖海林,王鹏,聂在平.基于遗传算法的多基站协作通信功率分配方案[J].电子科技大学学报,2014(1):26-30,41. XIAO Hai-lin,WANG Peng,NIE Zai-ping.Based on genetic algorithm base collaborative communication power allocation scheme[J].University of Electronic Science and Technology, 2014(1):26-30,41.

[3]苗乾坤.面向共享存储系统的计算模型及性能优化[J].中国科学技术大学,2010(5):15-21. MIAO Qian-kun.Model and performance optimization for shared storage system [J].University of Science and Technology of China,2010(5):15-21.

[4]郑金华,蔡自兴.基于共享存储的并行RGA的设计与实现[J].高技术通讯,2000(3):23-27. ZHENG Jin-hua,CAI Zi-xing.Design and implementation of shared memory parallelism based on RGA [J].High-tech Communications,2000(3):23-27.

[5]马利平,葛海波，欧阳磊.基于共享存储器的多处理机并行快速通信[J].电子设计工程，2011（7）：65-67. MA Li-ping,GE Hai-bo,OUYANG Lei.Based on shared memory multiprocessor parallel fast communication[J]. Electronic Design Engineering，2011（7）：65-67.

[6]白东玲，郭绍永.一种改进的混合遗传算法求解0_1背包问题[J].电子设计工程，2013(14)：9-11. BAI Dong-ling,GUO Shao-yong.An improved hybrid genetic algorithm 0_1 knapsack problem [J].Electronic Design Engineering，2013(14)：9-11.

Narrow parallel genetic algorithm based on shared storage

YAN Ni
（Shaanxi Ankang Vocational and Technical College,Ankang 725000,China）

The genetic algorithm is simple,easy to calculate and easy distribution of parallel processing,etc.,based on this advantage,genetic algorithms are widely used in many fields within the range,such as machine learning,industrial control.In order to solve difficult nonlinear and related issues,narrow parallel genetic algorithm based on shared storage,you can effectively achieve data-level parallelism,with a strong degree of parallelism,which requires less communication overhead can be obtained higher efficiency than the original,at least to more than 50%increase.This paper elaborates on shared memory parallel narrow genetic algorithms,simulation results verify the correctness and efficiency.

Shared memory;parallel narrow genetic algorithm;nonlinear;inquiry

TN99

A

1674－6236（2015）07-0074-03

2014-06-10 稿件编号：201406070

晏 妮(1983—)，女，陕西安康人，硕士，高级讲师。研究方向：计算机教学。