article

Parallel linear genetic programming for multi-class classification

Authors:

Carlton Downey,

Jing LiuAuthors Info & Claims

Genetic Programming and Evolvable Machines, Volume 13, Issue 3

Pages 275 - 304

https://doi.org/10.1007/s10710-012-9162-9

Published: 01 September 2012 Publication History

Abstract

Motivated by biological inspiration and the issue of instruction disruption, we develop a new form of Linear Genetic Programming (LGP) called Parallel LGP (PLGP) for classification problems. PLGP programs consist of multiple lists of instructions. These lists are executed in parallel after which the resulting vectors are combined to produce the classification result. PLGP limits the disruptive effects of crossover and mutation, which allows PLGP to significantly outperform regular LGP. Furthermore, PLGP programs are naturally suited to caching due to their parallel architecture. Although caching techniques have been used in tree based GP, to our knowledge, there are no caching techniques specifically developed for LGP. Thus, a novel caching technique is also developed with the intrinsic properties of PLGP in mind, which can decrease fitness evaluation time by almost an order of magnitude for the classification problems.

References

[1]

P.J. Angeline, Subtree crossover: Building block engine or macromutation? In: Genetic Programming 1997: Proceedings of the Second Annual Conference, ed. by J.R. Koza, K. Deb, M. Dorigo, D.B. Fogel, M. Garzon, H. Iba, R.L. Riolo (Morgan Kaufmann, Stanford University, CA, USA, 1997), pp. 9-17.

[2]

W. Banzhaf, P. Nordin, R.E. Keller, F.D. Francone, Genetic Programming: An Introduction on the Automatic Evolution of Computer Programs and Its Applications (Morgan Kaufmann Publishers, San Francisco, CA, 1998).

[3]

M. Brameier, W. Banzhaf, Evolving teams of predictors with linear genetic programming. Genet. Program. Evolvable Mach. 2(4), 381-407 (2001).

[4]

D.M. Chitty, A data parallel approach to genetic programming using programmable graphics hardware, in Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, 2007, pp. 1566-1573.

[5]

J. de Freitas, G.L. Pappa, A.S. da Silva, M.A. Goncalves, E. Moura, A. Veloso, A.H.F. Laender, M.G. de Carvalho, Active learning genetic programming for record deduplication, in IEEE Congress on Evolutionary Computation (CEC 2010) (IEEE Press, Barcelona, Spain, 18-23 Jul 2010).

[6]

M. Defoin Platel, M. Clergue, P. Collard, Maximum homologous crossover for linear genetic programming, ed. by C. Ryan, T. Soule, M. Keijzer, E. Tsang, R. Poli, E. Costa, in Genetic Programming, Proceedings of EuroGP'2003. LNCS, vol. 2610 (Springer, Essex, 14-16 Apr 2003), pp. 194-203.

[7]

P. D'haeseleer, Context preserving crossover in genetic programming, Evolutionary Computation, 1994, in IEEE World Congress on Computational Intelligence, Proceedings of the First IEEE Conference, vol. 1 (27-29 Jun 1994), pp. 256-261.

[8]

C. Downey, M. Zhang, Parallel linear genetic programming, in European Conference on Genetic Programming, pp. 178-189 (2011).

[9]

P.G. Espejo, S. Ventura, F. Herrera, A survey on the application of genetic programming to classification. IEEE Trans. Syst. Man Cybern. C Appl. Rev. 40(2), 121-144 (2010).

Digital Library

[10]

C. Fogelberg, M. Zhang, Linear genetic programming for multi-class object classification. In: Proceedings of the 18th Australian Joint Conference on Artificial Intelligence, 2005, vol. 3809, pp. 369-379.

[11]

F.D. Francone, M. Conrads, W. Banzhaf, P. Nordin, Homologous crossover in genetic programming, ed. by W. Banzhaf, J. Daida, A.E. Eiben, M.H. Garzon, V. Honavar, M. Jakiela, R.E. Smith, in Proceedings of the Genetic and Evolutionary Computation Conference, vol. 2 (Morgan Kaufmann, Orlando, FL, USA, 13-17 Jul 1999), pp. 1021-1026.

[12]

C. Gathercole, P. Ross, Dynamic training subset selection for supervised learning in genetic programming, in Proceedings of the 3rd International Conference on Parallel Problem Solving from Nature, 1994, PPSN III, pp. 312-321.

[13]

M. Giacobini, M. Tomassini, L. Vanneschi, Limiting the number of fitness cases in genetic programming using statistics, in Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, PPSN VII, 2002, pp. 371-380.

Digital Library

[14]

F.J. Gomez, Robust Non-Linear Control Through Neuroevolution. Ph.D. thesis, Technical Report AITR- 03-303, PhD Thesis (Department of Computer Science, The University of Texas at Austin, 2003).

[15]

F.J. Gomez, R. Mikkulainen, Incremental evolution of complex general behavior. Adapt. Behav. 5(3-4), 317-342 (1997).

Digital Library

[16]

F.J. Gomez, J. Schmidhuber, R. Miikkulainen, Accelerated neural evolution through cooperatively coevolved synapses. J. Mach. Learn. Res. 9, 937-965 (2008).

Digital Library

[17]

F. Gomez, R. Miikkulainen, 2-d pole balancing with recurrent evolutionary networks, in Proceeding of the International Conference on Artificial Neural Networks (Springer, Berlin, 1998), pp. 425-430.

[18]

S. Handley, On the use of directed acyclic graph to represent a population of computer programs, in Proceedings of the International Conference on Evolutionary Computation, 1994, pp. 154-159.

[19]

S. Hettich, C.B. Merz, UCI repository of machine learning databases (1998), http://www.ics.uci. edu/~mlearn/MLRepository.html.

[20]

M.I. Heywood, A.N. Zincir-Heywood, Dynamic page based crossover in linear genetic programming. IEEE Trans. Syst. Man Cybern. B Cybern. 32(3), 380-388 (2002).

Digital Library

[21]

J.H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. (University of Michigan Press/MIT Press, Ann Arbor/Cambridge, MA, 1975).

[22]

M. Keijzer, Alternatives in subtree caching for genetic programming, in European Conference on Genetic Programming, 2004, pp. 328-337.

[23]

J.R. Koza, Genetic Programming: on the Programming of Computers by Means of Natural Selection (MIT Press, London, 1992).

[24]

K. Krawiec, B. Bhanu, Visual learning by evolutionary and coevolutionary feature synthesis. IEEE Trans. Evol. Comput. 11(5), 635-650 (2007).

[25]

W.B. Langdon, Pareto, population partitioning, price and genetic programming. Research Note, RN/95/29, University College London, London, UK (1995).

[26]

W.B. Langdon, Long random linear programs do not generalize. Genet. Program. Evolvable Mach. 2(2), 95-100 (2001).

Digital Library

[27]

P. Lichodzijewski, M.I. Heywood, Coevolutionary bid-based genetic programming for problem decomposition in classification. Genet. Program. Evolvable Mach. 9(4), 331-365 (2008).

Digital Library

[28]

A.R. McIntyre, M.I. Heywood, Classification as clustering: a pareto cooperative-competitive GP approach. Evol. Comput. 19(1), 137-166 (2011).

Digital Library

[29]

R.I.B. McKay, in Industrial Electronics Society, 2000. IECON 2000. 26th Annual Confjerence of the IEEE Third Asia-Pacific Conference on Simulated Evolution and Learning (IEEE Press, Nagoya, Japan, Oct. 22-28, 2000), pp. 2861-2866.

[30]

G. Olague Caballero, E. Romero, L. Trujillo, B. Bhanu, Multiclass object recognition based on texture linear genetic programming. Appl. Evol. Comput. 4448, 291-300 (2007).

[31]

G. Olague, S. Cagnoni, E. Lutton, Introduction to the special issue on evolutionary computer vision and image understanding--Editorial. Pattern Recogn. Lett. 27(11), 1161-1163 (2006).

Digital Library

[32]

M. Oltean, C. Grosan, A comparison of several linear genetic programming techniques. Complex Syst. 14(4), 285-313 (2004).

[33]

R. Poli, W.B. Langdon, S. Dignum, On the limiting distribution of program sizes in tree-based genetic programming, ed. by M. Ebner, M. O'Neill, A. Ekárt, L. Vanneschi, A.I. Esparcia-Alcázar, in Proceedings of the 10th European Conference on Genetic Programming. Lecture Notes in Computer Science, vol. 4445 (Springer, Valencia, Spain, Apr 11-13, 2007), pp. 193-204.

[34]

M.E. Roberts, The effectiveness of cost based subtree caching mechanisms in typed genetic programming for image segmentation, in Proceedings of the 2003 International Conference on Applications of Evolutionary Computing (Springer, Berlin, 2003), pp. 444-454.

Digital Library

[35]

D. Robilliard, V. Marion-Poty, C. Fonlupt, Genetic programming on graphics processing units. Genet. Program. Evolvable Mach. 10, 447-471 (2009).

Digital Library

[36]

G.C. Wilson, W. Banzhaf, A comparison of cartesian genetic programming and linear genetic programming, ed. by M. O'Neill, L. Vanneschi, S. Gustafson, A.I. Esparcia Alcazar, I. De Falco, A. Della Cioppa, E. Tarantino, in Proceedings of the 11th European Conference on Genetic Programming. Lecture Notes in Computer Science, vol. 4971 (Springer, Naples, Mar 26-28 2008), pp. 182-193.

[37]

P. Wong, Removing Redundancy and Reducing Fitness Evaluation Costs in Genetic Programming. Master's thesis (School of Engineering and Computer Science, Victoria University of Wellington, 2008).

[38]

P. Wong, M. Zhang, Scheme: caching subtrees in genetic programming, in IEEE Congress on Evolutionary Computation, pp. 2678-2685 (2008).

[39]

W. Yan, C.D. Clack, Evolving robust GP solutions for hedge fund stock selection in emerging markets. Soft Comput. Fusion Found. Methodol. Appl. 15(1), 37-50 (2011).

Digital Library

[40]

T. Yu, J.F. Miller, The role of neutral and adaptive mutation in an evolutionary search on the onemax problem, ed. by E. Cantú-Paz, in Late Breaking Papers at the Genetic and Evolutionary Computation Conference (GECCO-2002) (AAAI, New York, NY, Jul 2002), pp. 512-519.

[41]

T. Yu, J.F. Miller, Through the interaction of neutral and adaptive mutations, evolutionary search finds a way. Artif. Life 12(4), 525-551 (2006).

Digital Library

[42]

B.T. Zhang, D.Y. Cho, Genetic programming with active data selection, in Selected Papers from the Second Asia-Pacific Conference on Simulated Evolution and Learning, SEAL'98, vol. 1585, ed. by R.I. Bob McKay, X. Yao, C.S. Newton, J.-H. Kim, T. Furuhashi (Australian Defence Force Academy, Canberra, Australia, 1998; Springer, 1999), pp. 146-153.

[43]

M. Zhang, V.B. Ciesielski, P. Andreae, A domain-independent window approach to multiclass object detection using genetic programming. EURASIP J. Appl. Signal Process. (8), 841-859 (2003) (special Issue on Genetic and Evolutionary Computation for Signal Processing and Image Analysis).

[44]

M. Zhang, X. Gao, W. Lou, A new crossover operator in genetic programming for object classification. IEEE Trans. Syst. Man. Cybern. B 37(5), 1332-1343 (2007).

[45]

M. Zhang, W. Smart, Using gaussian distribution to construct fitness functions in genetic programming for multiclass object classification. Pattern Recogn. Lett. 27(11), 1266-1274 (2006).

Digital Library

Cited By

Huang ZMei YZhang FZhang MWagner M(2022)Graph-based linear genetic programmingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528730(955-963)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528730
Huang ZZhang FMei YZhang M(2022)An Investigation of Multitask Linear Genetic Programming for Dynamic Job Shop SchedulingGenetic Programming10.1007/978-3-031-02056-8_11(162-178)Online publication date: 20-Apr-2022
https://dl.acm.org/doi/10.1007/978-3-031-02056-8_11
Hart ESim K(2016)A hyper-heuristic ensemble method for static job-shop schedulingEvolutionary Computation10.1162/EVCO_a_0018324:4(609-635)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1162/EVCO_a_00183
Show More Cited By

Parallel linear genetic programming for multi-class classification
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

Caching for parallel linear genetic programming
GECCO '11: Proceedings of the 13th annual conference companion on Genetic and evolutionary computation

Parallel Linear Genetic Programming (PLGP) is an exciting new approach to Linear Genetic Programming (LGP) which decreases building block disruption and significantly improves performance by the introduction of a parallel architecture. We introduce a ...
New crossover operators in linear genetic programming for multiclass object classification
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

Genetic programming (GP) has been successfully applied to solving multiclass classification problems, but the performance of GP classifiers still lags behind that of alternative techniques. This paper investigates an alternative form of GP, Linear GP (...
A comparison of Cartesian genetic programming and linear genetic programming
EuroGP'08: Proceedings of the 11th European conference on Genetic programming

Two prominent genetic programming approaches are the graph-based Cartesian Genetic Programming (CGP) and Linear Genetic Programming (LGP). Recently, a formal algorithm for constructing a directed acyclic graph (DAG) from a classical LGP instruction ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Genetic Programming and Evolvable Machines

Genetic Programming and Evolvable Machines Volume 13, Issue 3

September 2012

135 pages

ISSN:1389-2576

Issue’s Table of Contents

Copyright © Copyright © 2012 Springer Science+Business Media, LLC.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 September 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang ZMei YZhang FZhang MWagner M(2022)Graph-based linear genetic programmingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528730(955-963)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528730
Huang ZZhang FMei YZhang M(2022)An Investigation of Multitask Linear Genetic Programming for Dynamic Job Shop SchedulingGenetic Programming10.1007/978-3-031-02056-8_11(162-178)Online publication date: 20-Apr-2022
https://dl.acm.org/doi/10.1007/978-3-031-02056-8_11
Hart ESim K(2016)A hyper-heuristic ensemble method for static job-shop schedulingEvolutionary Computation10.1162/EVCO_a_0018324:4(609-635)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1162/EVCO_a_00183
Scoble AJohnston MZhang M(2012)Local search in parallel linear genetic programming for multiclass classificationProceedings of the 25th Australasian joint conference on Advances in Artificial Intelligence10.1007/978-3-642-35101-3_32(373-384)Online publication date: 4-Dec-2012
https://dl.acm.org/doi/10.1007/978-3-642-35101-3_32

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents