research-article

Managing team-based problem solving with symbiotic bid-based genetic programming

Authors:

Peter Lichodzijewski,

Malcolm I. HeywoodAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 363 - 370

https://doi.org/10.1145/1389095.1389162

Published: 12 July 2008 Publication History

Abstract

Bid-based Genetic Programming (GP) provides an elegant mechanism for facilitating cooperative problem decomposition without an a priori specification of the number of team members. This is in contrast to existing teaming approaches where individuals learn a direct input-output map (e.g., from exemplars to class labels), allowing the approach to scale to problems with multiple outcomes (classes), while at the same time providing a mechanism for choosing an outcome from those suggested by team members. This paper proposes a symbiotic relationship that continues to support the cooperative bid-based process for problem decomposition while making the credit assignment process much clearer. Specifically, team membership is defined by a team population indexing combinations of GP individuals in a separate team member population. A Pareto-based competitive coevolutionary component enables the approach to scale to large problems by evolving informative test points in a third population. The ensuing Symbiotic Bid-Based (SBB) model is evaluated on three large classification problems and compared to the XCS learning classifier system (LCS) formulation and to the support vector machine (SVM) implementation LIBSVM. On two of the three problems investigated the overall accuracy of the SBB classifiers was found to be competitive with the XCS and SVM results. At the same time, on all problems, the SBB classifiers were able to detect instances of all classes whereas the XCS and SVM models often ignored exemplars of minor classes. Moreover, this was achieved with a level of model complexity significantly lower than that identified by the SVM and XCS solutions.

References

[1]

M. Brameier and W. Banzhaf. Evolving teams of predictors with linear genetic programming. Genetic Programming and Evolvable Machines, 2(4):381--407, 2001.]]

Digital Library

[2]

M. Brameier and W. Banzhaf. Linear Genetic Programming. Springer, Genetic and Evolutionary Computation Series, 2007.]]

Digital Library

[3]

A. Chandra, H. Chen, and X. Yao. Trade-off between diversity and accuracy in ensemble generation, volume 16 of Studies in Computational Intelligence, chapter 19 in Multi-Objective Machine Learning, pages 429--464. Springer-Verlag, 2006.]]

[4]

C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/$\sim$cjlin/libsvm.]]

[5]

E. D. de Jong. A monotonic archive for Pareto-coevolution. Evolutionary Computation, 15(1):61--93, 2007.]]

Digital Library

[6]

R.-E. Fan, P.-H. Chen, and C.-J. Lin. Working set selection using second order information for training support vector machines. Journal of Machine Learning Research, 6:1889--1918, 2005.]]

Digital Library

[7]

S. G. Ficici and J. B. Pollack. Pareto optimality in coevolutionary learning. In Proceedings of the 6th European Conference on Advances in Artificial Life, pages 316--325, 2001.]]

Digital Library

[8]

J. B. J. M. Garrell. Bloat control and generalization pressure using the minimum description length principle for a Pittsburgh approach learning classifier system. Learning Classifier Systems, 4399:59--79, 2007.]]

Digital Library

[9]

S. Hettich and S. D. Bay. The UCI KDD Archive {http://kdd/ics/uci/edu}. Irvine, CA: University of California, Dept. of Information and Comp. Science, 1999.]]

[10]

K. Imamura, T. Soule, R. B. Heckendorn, and J. A. Foster. Behavioral diversity and a probabilistically optimal GP ensemble. Genetic Programming and Evolvable Machines, 4(3):235--253, 2003.]]

Digital Library

[11]

P. Lichodzijewski and M. I. Heywood. Coevolutionary bid-based genetic programming for problem decomposition in classification. Genetic Programming and Evolvable Machines. Submitted.]]

Digital Library

[12]

P. Lichodzijewski and M. I. Heywood. GP classifier problem decomposition using first-price and second-price auctions. In Proceedings of the European Conference on Genetic Programming, pages 137--147, 2007.]]

Digital Library

[13]

P. Lichodzijewski and M. I. Heywood. Pareto-coevolutionary genetic programming for problem decomposition in multi-class classification. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 464--471, 2007.]]

Digital Library

[14]

A. R. McIntyre and M. I. Heywood. MOGE: GP classification problem decomposition using multi-objective optimization. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 863--870, 2006.]]

Digital Library

[15]

A. R. McIntyre and M. I. Heywood. Cooperative problem decomposition in Pareto competitive classifier models of coevolution. In Proceedings of the European Conference on Genetic Programming (to appear), 2008.]]

Digital Library

[16]

D. E. Moriarty and R. Miikkulainen. Forming neural networks through efficient and adaptive coevolution. Evolutionary Computation, 5(4):373--399, 1998.]]

Digital Library

[17]

D. J. Newman, S. Hettich, C. L. Blake, and C. J. Merz. UCI Repository of Machine Learning Databases {http://www.ics.uci.edu/$\sim$mlearn/mlrepository.html}. Irvine, CA: University of California, Dept. of Information and Comp. Science, 1998.]]

[18]

J. Noble and R. A. Watson. Pareto coevolution: Using performance against coevolved opponents in a game as dimensions for Pareto selection. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 493--500, 2001.]]

[19]

J. Paredis. The symbiotic evolution of solutions and their representations. In Proceedings of the 6th International Conference on Genetic Algorithms, pages 359--365, 1995.]]

Digital Library

[20]

G. Paris, D. Robiliard, and C. Ronlupt. Applying boosting techniques to genetic programming. In Proceedings of the International Conference on Artificial Evolution, pages 267--278, 2001.]]

Digital Library

[21]

C. D. Rosin and R. K. Belew. New methods for competitive coevolution. Evolutionary Compuatation, 5:1--29, 1997.]]

Digital Library

[22]

T. Soule. Cooperative evolution on the intertwined spirals problem. In Proceedings of the European Conference on Genetic Programming, pages 434--442, 2003.]]

Digital Library

[23]

R. Thomason and T. Soule. Novel ways of improving cooperation and performance in ensemble classifiers. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1708--1715, 2007.]]

Digital Library

[24]

S. Wilson. Classifier fitness based on accuracy. Evolutionary Computation, 3(2):149--175, 1995.]]

Digital Library

Cited By

Zhou ZZincir-Heywood NHeywood M(2024)Simple Efficient Evolutionary Ensemble Learning on Network Intrusion Detection BenchmarksApplications of Evolutionary Computation10.1007/978-3-031-56852-7_23(361-376)Online publication date: 21-Mar-2024
https://doi.org/10.1007/978-3-031-56852-7_23
Mei YChen QLensen AXue BZhang M(2023)Explainable Artificial Intelligence by Genetic Programming: A SurveyIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.322550927:3(621-641)Online publication date: Jun-2023
https://doi.org/10.1109/TEVC.2022.3225509
Heywood M(2023)W. B. Langdon “Jaws 30”Genetic Programming and Evolvable Machines10.1007/s10710-023-09473-z24:2Online publication date: 22-Nov-2023
https://doi.org/10.1007/s10710-023-09473-z
Show More Cited By

Index Terms

Managing team-based problem solving with symbiotic bid-based genetic programming
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
        Supervised learning by classification
    2. Machine learning approaches
      1. Classification and regression trees
      2. Markov decision processes
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Markov decision processes

Recommendations

Coevolutionary bid-based genetic programming for problem decomposition in classification

In this work a cooperative, bid-based, model for problem decomposition is proposed with application to discrete action domains such as classification. This represents a significant departure from models where each individual constructs a direct input-...
Pareto-coevolutionary genetic programming for problem decomposition in multi-class classification
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

A bid-based approach for coevolving Genetic Programming classifiers is presented. The approach coevolves a population of learners thatdecompose the instance space by way of their aggregate bidding behaviour. To reduce computation overhead, a small, ...
Symbiotic coevolutionary genetic programming: a benchmarking study under large attribute spaces

Classification under large attribute spaces represents a dual learning problem in which attribute subspaces need to be identified at the same time as the classifier design is established. Embedded as opposed to filter or wrapper methodologies address ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
Total Citations
View Citations
290
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)2

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhou ZZincir-Heywood NHeywood M(2024)Simple Efficient Evolutionary Ensemble Learning on Network Intrusion Detection BenchmarksApplications of Evolutionary Computation10.1007/978-3-031-56852-7_23(361-376)Online publication date: 21-Mar-2024
https://doi.org/10.1007/978-3-031-56852-7_23
Mei YChen QLensen AXue BZhang M(2023)Explainable Artificial Intelligence by Genetic Programming: A SurveyIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.322550927:3(621-641)Online publication date: Jun-2023
https://doi.org/10.1109/TEVC.2022.3225509
Heywood M(2023)W. B. Langdon “Jaws 30”Genetic Programming and Evolvable Machines10.1007/s10710-023-09473-z24:2Online publication date: 22-Nov-2023
https://doi.org/10.1007/s10710-023-09473-z
Heywood M(2023)Evolutionary Ensemble LearningHandbook of Evolutionary Machine Learning10.1007/978-981-99-3814-8_8(205-243)Online publication date: 2-Nov-2023
https://doi.org/10.1007/978-981-99-3814-8_8
Zhou ZQiu ZNiblett BJohnston ASchwartzentruber JZincir-Heywood NHeywood M(2023)A Boosting Approach to Constructing an Ensemble StackGenetic Programming10.1007/978-3-031-29573-7_9(133-148)Online publication date: 29-Mar-2023
https://doi.org/10.1007/978-3-031-29573-7_9
Rebuli KVanneschi L(2022)An Empirical Study of Progressive Insular Cooperative GPSN Computer Science10.1007/s42979-021-00998-73:2Online publication date: 7-Jan-2022
https://doi.org/10.1007/s42979-021-00998-7
Brotto Rebuli KVanneschi L(2021)Progressive Insular Cooperative GPGenetic Programming10.1007/978-3-030-72812-0_2(19-35)Online publication date: 25-Mar-2021
https://doi.org/10.1007/978-3-030-72812-0_2
Krawiec KHeywood MAuger AStützle T(2019)Solving complex problems with coevolutionary algorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323384(975-1001)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3323384
Ma XLi XZhang QTang KLiang ZXie WZhu Z(2019)A Survey on Cooperative Co-Evolutionary AlgorithmsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2018.286877023:3(421-441)Online publication date: Jun-2019
https://doi.org/10.1109/TEVC.2018.2868770
Krawiec KHeywood MTakadama K(2018)Solving complex problems with coevolutionary algorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3207888(880-906)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3207888
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten