基于图的分布式并行基因编程模型

doi:10.3724/SP.J.1087.2013.01260

计算机应用 ›› 2013, Vol. 33 ›› Issue (05): 1260-1266.DOI: 10.3724/SP.J.1087.2013.01260

基于图的分布式并行基因编程模型

鲁强¹,²,钟伟²,王智广²

1. 中国石油大学(北京) 北京市地球探测与信息技术重点实验室，北京102249
2. 中国石油大学(北京) 地球物理与信息工程学院，北京102249

收稿日期:2012-11-22 修回日期:2013-01-14 出版日期:2013-05-01 发布日期:2013-05-08
通讯作者: 钟伟
作者简介:鲁强(1977-)，男，河北唐山人，副教授，博士，CCF会员，主要研究方向：分布式系统、软件工程、知识工程；钟伟(1987-)，男，江西赣州人，硕士研究生，主要研究方向：分布式计算；王智广(1964-)，男，内蒙古通辽人，教授，CCF会员，主要研究方向：分布式计算。
基金资助:
国家自然科学基金资助项目(61275185);国家863计划项目(2009AA063403);中国石油大学(北京)基金资助项目(KYJJ2012-05-19)

Graph-based parallel distributed genetic programming model

LU Qiang¹,²,ZHONG Wei²,WANG Zhiguang²

1. Beijing Key Laboratory of Earth Prospecting and Information Technology, China University of Petroleum, Beijing 102249, China
2. College of Geophysics and Information Engineering, China University of Petroleum, Beijing 102249, China

Received:2012-11-22 Revised:2013-01-14 Online:2013-05-08 Published:2013-05-01
Contact: ZHONG Wei

摘要/Abstract

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

关键词: 分布式并行基因编程, 图模型, 主从模型, 岛屿模型, 网格模型

Abstract: Since Genetic Programming (GP) is of natural parallelism, the parallel and distributed GP model was developed, including master-slave model, island model and grid model. However, the realizing algorithm of these distributed models is complex and they cannot be reused. It is difficult to achieve the scale computation of GP quickly based on different topologies. Due to these shortcomings, the authors presented the graph-based parallel distributed GP model which realizes formal description of the various operations of GP, and could support the distributed parallel computation of GP for different topologies. It is easy to achieve the master-slave model, island model and grid model of GP through experimental test. The new model is stable, efficient and easy to realize.

Key words: Parallel Distributed Genetic Programming (PDGP), graph model, master-slave model, island model, grid model

中图分类号:

TP311.5

鲁强钟伟王智广. 基于图的分布式并行基因编程模型[J]. 计算机应用, 2013, 33(05): 1260-1266.

LU Qiang ZHONG Wei WANG Zhiguang. Graph-based parallel distributed genetic programming model[J]. Journal of Computer Applications, 2013, 33(05): 1260-1266.

参考文献

［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 multi-core 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］OUSSAIDNE 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, ABENGZAR SNCHEZ J G, COTTA C. A preliminary analysis and simulation of load balancing techniques applied to parallel genetic programming［C］// IWANN'11: 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 graph-parallel computation on natural graphs［C］//

OSDI'12: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.

［18］SALHI A, GLASER H, de ROURE D. Parallel implementation of a genetic-programming 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.

[1]	周震, 袁正道. 面向物联网环境的高效通信接收机设计[J]. 计算机应用, 2020, 40(1): 202-206.
[2]	王泽宇, 吴艳霞, 张国印, 布树辉. 面向RGB-D场景解析的三维空间结构化编码深度网络[J]. 计算机应用, 2017, 37(12): 3458-3466.
[3]	娄自婷, 张亚萍. 基于贪心优化策略的网格排布算法[J]. 计算机应用, 2016, 36(7): 1954-1958.
[4]	范家兵, 王鹏, 周渭博, 燕京京. 在推荐系统中利用时间因素的方法[J]. 计算机应用, 2015, 35(5): 1324-1327.
[5]	杨陟卓. 基于上下文语境的词义消歧方法[J]. 计算机应用, 2015, 35(4): 1006-1008.
[6]	盛洪波汪西莉. 基于局部聚类的自适应线性近邻传递分类算法[J]. 计算机应用, 2014, 34(1): 255-259.
[7]	任梅詹永照潘道远孙佳瑶. 基于概率超图的视频事件语义检测[J]. 计算机应用, 2012, 32(11): 3014-3017.
[8]	常晓龙张晖. 融合语素特征的中文褒贬词典构建[J]. 计算机应用, 2012, 32(07): 2033-2037.
[9]	陈学工杨兰黄伟季兴. 三维网格模型的布尔运算方法[J]. 计算机应用, 2011, 31(06): 1543-1545.
[10]	陈学工马金金邱华付金华肖克炎. 三维网格模型的稳定布尔运算算法[J]. 计算机应用, 2011, 31(05): 1198-1201.
[11]	郭文强高晓光高晓光. 复杂系统的图模型多智能体协同故障诊断[J]. 计算机应用, 2010, 30(11): 2906-2909.
[12]	侯宝明崔红霞刘雪娜. 三维网格模型的快速拓扑重建算法[J]. 计算机应用, 2010, 30(11): 3002-3004.
[13]	彭昂王如龙陈泉泉张锦. 基于复杂属性相似度的聚类算法及其应用研究[J]. 计算机应用, 2010, 30(07): 1930-1932.
[14]	张少丽王毅刚陈小雕. 基于空间分解的三角网格模型求交方法[J]. 计算机应用, 2009, 29(10): 2671-2673.
[15]	李环周帅锋. 基于多不动点约束的网格模型局部编辑[J]. 计算机应用, 2009, 29(06): 1687-1689.

基于图的分布式并行基因编程模型

Graph-based parallel distributed genetic programming model

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics