摘要：

　　基因编程（GP）算法具有天然的并行性，因此出现了并行分布式GP模型，如主从模型、岛屿模型和网格模型等。但是实现这些分布式模型的算法过程复杂，不具有可重用性，很难依据不同拓扑结构来快速实现大规模的GP计算。针对这些缺点，提出了基于图的并行分布式GP模型，形式化地描述了图中的各种GP操作，使其能够支持不同拓扑结构的GP分布式并行计算。经过实验测试，该模型能够实现上述三种GP模型，并具有稳定、高效、易实现的特点。

　　关键词：

　　分布式并行基因编程；图模型；主从模型；岛屿模型；网格模型

　　0引言

　　基因编程（Genetic Programming，GP）是基于生物进化理论，由计算机程序自动实现用户定义任务的一种进化算法。GP是由Koza率先完整介绍[1]，现在已经广泛地应用于各个领域。随着GP问题越来越复杂，计算量也呈指数级增长，对GP的进化效率也提出了越来越高的要求，随之出现了并行分布式基因编程（Parallel Distributed Genetic Programming，PDGP）。

　　PDGP模型主要可以分为主从模型、岛屿模型和网格模型，以及这三种模型搭配的混合模型。几种模型的实现语言很多，如MPI、Java、C++语言[2-5]，实现的软件系统有DEAP、OpenBeagle、ECJ、GPLab等。

　　为了提升PDGP模型的计算性能，de Vega等[6]对PDGP模型内子群的个数，每个子群内个体的数量，以及拓扑结构都进行了深入的研究，认为如果要得到最优的进化效率，子群的个数、每个子群内个体的数量在具体问题中的配置都不一样。Tongchim等[7]则对同步与异步模型进行比较，他们在一个完全连接的拓扑结构中发现，进化过程中异步迁移比同步迁移效率更优。

　　负载均衡理论也被用于提升PDGP模型的计算性能，Oussaidène等[8]用贪婪启发式方法尽量把评估个体的工作量均匀地分配到不同的计算机中完成。直到2011年，de Vega等[9]才详细研究负载均衡在GP算法中的应用，认为增加负载均衡技术的主从模型比传统的主从模型效率高，对于计算时间短的GP问题不适宜用网格模型。

　　随着显卡技术的进步，图形处理器（Graphic Processing Unit，GPU）也被用来提升PDGP模型的计算性能。Harding等[10]用统一计算架构

　　（Compute Unified Device Architecture，CUDA）技术实现了基于GPU的PDGP模型，Cano等[11]则利用GPU在PDGP模型的评估阶段进行加速，在大数据计算加速方面取得了良好的效果。

　　但是，随着大数据量计算和存储资源需求的增长，特别是对大规模集群技术的利用，现有的PDGP模型和应用技术存在低效、不稳定、无法支持大数据量计算的问题，需要新模型来解决。这种新模型需要拥有稀疏的数据依赖、同步和异步迭代计算能力，还能让使用者不必关心模型内部复杂的数据存储、数据同步和数据死锁。新模型可以让使用者将更多的精力放在GP问题的研究上，而不用将大量的精力用来处理数据并发和模型检测。现今已知的软件，ECJ[4]或OpenBeagle[5]等，都支持单节点的GP算法，但是在实现PDGP模型的技术上却显现不足，需要用户自定义节点间的连接关系，不能自动支持数据并发，设计的模型无法保证正确性，无法满足新的需求。本文通过分析PDGP模型中三种模型的特点及共性，定义了基于图的PDGP（Graphbased PDGP，GPDGP）模型，并在此基础上实现了相关算法，完全可以满足GP的新需求。

　　1PDGP模型

　　1.1GP算法

　　GP算法和遗传算法（Genetic Algorithm，GA）[12]都是进化算法。两者都有基本的基因操作，如复制、选择、交叉和变异等，使用范围也都很广泛，但是GP算法使用计算机程序表示个体（Individual），GA算法却是用二进制代码表示个体。GP算法一般是以GP语义树表示个体，每个个体都是一种计算机程序，代表问题的一种求解方法。很多个体组成一个群体，一个群体可以分成若干个子群体。GP语义树由操作符集P={+，-，*，sin，…}和终端集T={x，y，z，…}组成，图1为一棵GP语义树f（x，y）=xy+sinx。GP算法通过基本的基因操作产生符合要求的个体，该组基因操作可以用基因操作集合BaseOperation={Reproduce， Selection， Crossover， Mutation}来表示。

　　支持独立的不同任务集并行执行的一个经典方法是给图染色，即相邻节点间没有相同颜色[16]。首先给数据图中的节点染色，然后只允许相同颜色的节点并发同步执行，执行完后再换另一种颜色的节点并发同步执行，这种执行方式满足边并发模型。全并发模型满足二阶节点染色，例如相隔两种不同颜色以上的两个节点可以全并发执行。节点并发模型则只需要数据图中的节点被染成一种颜色即可。虽然图染色是一种NP难题，但是使用启发式的贪婪染色法仍然很容易实现图染色。PDGP模型有很多最终只被染成两种颜色的模型，可以使用染色模板很方便地将模型中的节点染色[17]。

　　计算引擎的全局操作分为同步和异步两种。在同步全局操作中，首先要给数据图染色，然后启动数据图。启动数据图的过程是依据全局节点集V，先启动数量最多的同种颜色节点，等待这些节点并发同步初始化完成后再换数量更小的另一种颜色的节点同步并发初始化，直到所有的节点都完成这一阶段的任务。

　　程序前

　　由上可知，实现GPDGP模型很便捷，只需要替换每个节点的Apply阶段的代码即可，这极大地方便了使用GPDGP模型解决GP问题，提高了代码的可重用性，实现了GPDGP模型的稳定性和高效性。 　　3实验设计

　　GPDGP模型实现了PDGP模型中的主从模型、岛屿模型和网格模型。GPDGP模型自动进行节点同步或异步迭代的计算，使用者仅需关注如何实现节点上的GP程序。本实验使用两个开源的框架GraphLab和OpenBeagle Puppy，对基于岛屿模型的符号回归问题[18]进行性能测试，以验证GPDGP模型的正确性。

　　岛屿模型需要通过迁移来实现若干个体在岛屿之间的交换。岛屿模型中每个岛屿的基因操作是独立、并行的，各自所花费的时间也可能是不一样的。迁移分为同步和异步两种情况，同步必须等待所有的岛屿都完成自己的基因操作，然后才进行迁移；异步则是每个岛屿完成自己的基因操作，然后立即进行迁移操作。本实验仅讨论同步迁移的符号回归问题对迁移率优化的问题，使同步岛屿模型进化效率更优。

　　实验硬件环境为三台配置相同的计算机，同时，设置每个节点上的实验参数均相同，因此可以认为实验网络结构是同质的。使用最经典的公式f（x）=x4+x3+x2+x进行符号回归实验，来探讨子群体内个体数量对迁移率的影响，主要参数配置如表1所示。

　　本文中GPDGP模型依次实现了主从模型、岛屿模型和网格模型。为了验证模型的稳定性、实用性和高效性，分别对岛屿模型中不同迁移率的效率进行探讨，并与ECJ岛屿模型的进化效率进行了对比。在对岛屿模型中不同迁移率的效率进行探讨时，验证了迁移率不受岛屿内个体数量、每次岛屿迁移前的进化迭代次数影响，大约在5%～10%左右为宜[19]。迁移率过小，对岛屿内的进化没有任何影响；迁移率过大，则破坏每个岛屿内生态平衡，使每个岛屿在交叉、变异过程中需要的适应度小的个体材料较少，进而影响岛屿内的进化效率。

　　由于混合模型由前述三种模型混合形成，比如在岛屿模型中每个岛屿再实现主从模型，或者在岛屿模型中每个岛屿再实现网格模型。因此，混合模型的拓扑结构复杂多变，GPDGP模型在实现混合模型过程中要处理更加复杂的数据并发管理。未来，将进一步研究用GPDGP模型实现混合模型，探索混合模型的复杂拓扑结构和数据并发管理；同时，在基于GPDGP模型实现的符号回归问题中，将研究样本数量与子群体数量、子群体内个体数量、迭代次数等其他参数的关系，尽可能在这些参数之间建立数学模型，提高GPDGP模型的进化效率。

　　参考文献：

　　[1]

　　KOZA J. Genetic programming[M]. Cambridge： MIT Press，1992.

　　[2]

　　FEMNANDEZ F， TOMASSINI M， VANNESCHI L，et al. A distributed computing environment for genetic programming using MPI[C]// Recent Advances in Parallel Virtual Machine and Message Passing Interface. Berlin：Springer，2000.1908：322-329.

　　[3]

　　KUROSE S， YAMAMORI K， AIKAWA M. Asynchronous migration for parallel genetic programming on a computer cluster with multicore processors[J]. Artificial Life Robotics，2012，16（4）：533-536.

　　[4]

　　WHITE D R. Software review： the ECJ toolkit[J]. Genetic Programming and Evolvable Machines，2012，13（1）：65-67.

　　[5]

　　BATENKOV D. Open BEAGLE： a generic framework for evolutionary computations[J]. Genetic Programming and Evolvable Machines，2011，12：329-331.

　　[6]

　　de VEGA F F， TOMASSINI M， PUNCHⅢ W F，et al. Experimental study of multipopulation parallel genetic programming[J]. Genetic Programming， LNCS 1802.Berlin：Springer，2000.1802：283-293.

　　[7]

　　TONGCHIM S， CHONGSTITVATANA P. Asynchronous migration in parallel genetic programming [C]// Proceedings of Asian Computing Science Conference， LNCS 1742.Heidelberg：Springer，1999.1742：388-389.

　　[8]

　　OUSSAIDNE M， CHOPARD B， PICTET O V. Parallel genetic programming： an application to trading models evolution[J]. Parallel Computing，1997，23（8）：1183-1198.

　　[9]

　　de VEGA F F， ABENGZAR SNCHEZ J G， COTTA C. A preliminary analysis and simulation of load balancing techniques applied to parallel genetic programming[C]// IWANN11： Proceedings of the 11th International Conference on Artificial Neural Networks Conference on Advances in Computational Intelligence： Volume Part Ⅱ， LNCS 6692. Berlin： Springer， 2011： 308-315. 　　[10]

　　HARDING S， BANZHAF W. Distributed genetic programming on GPUs using CUDA[R/OL]. （2009） [2012-11-01]. http：//www.evolutioninmaterio.com/.

　　[11]

　　CANO A， ZAFRA A， VENTURA S. Speeding up the evaluation phase of GP classification algorithms[J]. Soft Computing，2011，16（2）：187-202.

　　[12]

　　吉根林。基因算法研究综述[J].计算机应用与软件，2004，21（2）：69-73.

　　[13]

　　FOLINO G， PIZZUTI C， SPEZZANOG. A scalable cellular implementation of parallel genetic programming[J]. IEEE Transactions on Evolutionary Computation，2003，7（1）： 37-53.

　　[14]

　　GONZALEZ J E， LOW Y C， GU H J，et al. PowerGraph： distributed graphparallel computation on natural graphs[C]//

　　OSDI12：Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation. Berkeley：USENIX Association，2012：17-30.

　　[15]

　　LOW Y， BICKSON D， GONZALEZ J， et al. Distributed graphLab： a framework for machine learning and data mining in the cloud [J]. Proceedings of the VLDB Endowment， 2012， 5（8）：716-727.

　　[16]

　　BERTSEKAS D P，TSITSIKLIS J N. Parallel and distributed computation： numerical methods[M]. Belmont： Athena Scientific， 1989.

　　[17]

　　GONZALEZ J E， LOW Y， GRETTON A，et al. Parallel Gibbs sampling： from colored fields to thin junction trees[J]. Journal of Machine Learning Research-Proceedings Track，2011，15： 324-332.

　　14th International Conference on Artificial Intelligence and Statistics

　　[18]

　　SALHI A， GLASER H， de ROURE D. Parallel implementation of a geneticprogramming based tool for symbolic regression[J]. Information Processing Letters，1998，66（6）：299-307.

　　[19]

　　FEMNANDEZ F， TOMASSINI M， VANNESCHI L. Studying the influence of communication topology and migration on distributed genetic programming[C]// Genetic Programming Proceedings，LNCS 2038. Berlin：Springer，2001：51-63.