Article

Extracted global structure makes local building block processing effective in XCS

Authors:

Martin V. Butz,

Martin Pelikan,

David E. GoldbergAuthors Info & Claims

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

Pages 655 - 662

https://doi.org/10.1145/1068009.1068121

Published: 25 June 2005 Publication History

Abstract

Michigan-style learning classifier systems (LCSs), such as the accuracy-based XCS system, evolve distributed problem solutions represented by a population of rules. Recently, it was shown that decomposable problems may require effective processing of subsets of problem attributes, which cannot be generally assured with standard crossover operators. A number of competent crossover operators capable of effective identification and processing of arbitrary subsets of variables or string positions were proposed for genetic and evolutionary algorithms. This paper effectively introduces two competent crossover operators to XCS by incorporating techniques from competent genetic algorithms (GAs): the extended compact GA (ECGA) and the Bayesian optimization algorithm (BOA). Instead of applying standard crossover operators, here a probabilistic model of the global population is built and sampled to generate offspring classifiers locally. Various offspring generation methods are introduced and evaluated. Results indicate that the performance of the proposed learning classifier systems XCS/ECGA and XCS/BOA is similar to that of XCS with informed crossover operators that is given all information about problem structure on input and exploits this knowledge using problem-specific crossover operators.

References

[1]

C. W. Ahn, R. S. Ramakrishna, and G. Goldberg. Real-coded Bayesian optimization algorithm: Bringing the strength of BOA into the continuous world. Genetic and Evolutionary Computation Conference (GECCO-2004), 3102:840--851, 2004.]]

[2]

L. B. Booker, D. E. Goldberg, and J. H. Holland. Classifier systems and genetic algorithms. Artificial Intelligence, 40:235--282, 1989.]]

Digital Library

[3]

P. A. Bosman and D. Thierens. Mixed IDEAs. Utrecht University Technical Report UU-CS-2000-45, Utrecht University, Utrecht, Netherlands, 2000.]]

[4]

M. V. Butz. Rule-based evolutionary online learning systems: Learning bounds, classification, and prediction. PhD thesis, University of Illinois at Urbana-Champaign, Urbana, IL, 2004.]]

Digital Library

[5]

M. V. Butz, D. E. Goldberg, and P. L. Lanzi. Bounding learning time in XCS. Proceedings of the Sixth Genetic and Evolutionary Computation Conference (GECCO-2004): Part II, pages 739--750, 2004.]]

[6]

M. V. Butz, D. E. Goldberg, and K. Tharakunnel. Analysis and improvement of fitness exploitation in XCS: Bounding models, tournament selection, and bilateral accuracy. Evolutionary Computation, 11:239--277, 2003.]]

Digital Library

[7]

M. V. Butz, T. Kovacs, P. L. Lanzi, and S. W. Wilson. Toward a theory of generalization and learning in XCS. IEEE Transactions on Evolutionary Computation, 8:28--46, 2004.]]

Digital Library

[8]

M. V. Butz, K. Sastry, and D. E. Goldberg. Tournament selection in XCS. Proceedings of the Fifth Genetic and Evolutionary Computation Conference (GECCO-2003), pages 1857--1869, 2003.]]

Digital Library

[9]

G. F. Cooper and E. H. Herskovits. A Bayesian method for the induction of probabilistic networks from data. Machine Learning, 9:309--347, 1992.]]

Digital Library

[10]

K. A. De Jong and W. M. Spears. Learning concept classification rules using genetic algorithms. IJCAI-91 Proceedings of the Twelfth International Conference on Artificial Intelligence, pages 651--656, 1991.]]

[11]

J. J. Gibson. The Ecological Approach to Visual Perception. Lawrence Erlbaum Associates, 1979.]]

[12]

D. E. Goldberg. The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Kluwer Academic Publishers, Boston, MA, 2002.]]

Digital Library

[13]

G. Harik. Linkage learning via probabilistic modeling in the ECGA. IlliGAL report 99010, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, 1999.]]

[14]

D. Heckerman, D. Geiger, and D. M. Chickering. Learning Bayesian networks: The combination of knowledge and statistical data. Technical Report MSR-TR-94-09, Microsoft Research, Redmond, WA, 1994.]]

Digital Library

[15]

M. Henrion. Propagating uncertainty in Bayesian networks by probabilistic logic sampling. In J. F. Lemmer and L. N. Kanal, editors, Uncertainty in Artificial Intelligence, pages 149--163. Elsevier, Amsterdam, London, New York, 1988.]]

[16]

J. H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI, 1975. second edition, 1992.]]

Digital Library

[17]

J. H. Holland and J. S. Reitman. Cognitive systems based on adaptive algorithms. In D. A. Waterman and F. Hayes-Roth, editors, Pattern directed inference systems, pages 313--329. Academic Press, New York, 1978.]]

[18]

T. Kovacs. Deletion schemes for classifier systems. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99), pages 329--336, 1999.]]

[19]

P. Larrañaga. A review on estimation of distribution algorithms. In P. Larrañaga and J. A. Lozano, editors, Estimation of Distribution Algorithms, chapter 3, pages 57--100. Kluwer Academic Publishers, Boston, MA, 2002.]]

[20]

P. Larrañaga, R. Etxeberria, J. A. Lozano, and J. M. Pena. Optimization in continuous domains by learning and simulation of Gaussian networks. In A. Wu, editor, Workshop Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000), pages 201--204, San Fransisco, CA, 2000. Morgan Kaufmann.]]

[21]

P. Larrañaga and J. A. Lozano, editors. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer, Boston, MA, 2002.]]

[22]

F. Lobo and G. Harik. Extended compact genetic algorithm in C++. IlliGAL report 99016, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, 1999.]]

[23]

T. M. Mitchell. Machine Learning. McGraw-Hill, Boston, MA, 1997.]]

Digital Library

[24]

H. Mühlenbein and G. Paaβ. From recombination of genes to the estimation of distributions I. Binary parameters. Parallel Problem Solving from Nature, pages 178--187, 1996.]]

Digital Library

[25]

R. M. Neal. Probabilistic inference using Markov chain Monte Carlo methods. Technical Report CRG-TR-93-1, Dept. of Computer Science, University of Toronto, 1993.]]

[26]

J. Pearl. Probabilistic reasoning in intelligent systems: Networks of plausible inference. Morgan Kaufmann, San Mateo, CA, 1988.]]

Digital Library

[27]

M. Pelikan. Bayesian optimization algorithm, decision graphs, and Occam's razor. Proceedings of the Third Genetic and Evolutionary Computation Conference (GECCO-2001), pages 511--518, 2001.]]

[28]

M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer-Verlag, 2005.]]

[29]

M. Pelikan, D. E. Goldberg, and E. Cantu-Paz. BOA: The Bayesian optimization algorithm. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99), pages 525--532, 1999.]]

[30]

M. Pelikan, D. E. Goldberg, and F. Lobo. A survey of optimization by building and using probabilistic models. Computational Optimization and Applications, 21(1):5--20, 2002.]]

Digital Library

[31]

M. Pelikan, D. E. Goldberg, and S. Tsutsui. Getting the best of both worlds: Discrete and continuous genetic and evolutionary algorithms in concert. Information Sciences, 156(3--4):36--45, 2003.]]

Digital Library

[32]

J. P. Rivera and R. Santana. Improving the discovery component of classifier systems by the application of estimation of distribution algorithms. In Proceedings of the students sessions, ACAI'99, pages 43--44, Chania, Greece, 1999.]]

[33]

K. Sastry and D. E. Goldberg. On extended compact genetic algorithm. IlliGAL report 2000026, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, 2000.]]

[34]

G. Schwarz. Estimating the dimension of a model. The Annals of Statistics, 6:461--464, 1978.]]

[35]

H. A. Simon. Sciences of the Artificial. MIT Press, Cambridge, MA, 1969.]]

Digital Library

[36]

R. A. Watson, G. S. Hornby, and J. B. Pollack. Modeling building-block interdependency. Parallel Problem Solving from Nature, pages 97--106, 1998.]]

Digital Library

[37]

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

Digital Library

[38]

S. W. Wilson. Generalization in the XCS classifier system. Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 665--674, 1998.]]

[39]

S. W. Wilson. Get real! XCS with continuous-valued inputs. In P. L. Lanzi, W. Stolzmann, and S. W. Wilson, editors, Learning classifier systems: From foundations to applications (LNAI 1813), pages 209--219. Springer-Verlag, Berlin Heidelberg, 2000.]]

Digital Library

Cited By

Nakata MBrowne W(2021)Learning Optimality Theory for Accuracy-Based Learning Classifier SystemsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2020.299431425:1(61-74)Online publication date: Feb-2021
https://doi.org/10.1109/TEVC.2020.2994314
Kovacs T(2012)Genetics-Based Machine LearningHandbook of Natural Computing10.1007/978-3-540-92910-9_30(937-986)Online publication date: 2012
https://doi.org/10.1007/978-3-540-92910-9_30
Urbanowicz RMoore J(2009)Learning classifier systemsJournal of Artificial Evolution and Applications10.5555/1644490.16444912009(1-25)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.5555/1644490.1644491
Show More Cited By

Index Terms

Extracted global structure makes local building block processing effective in XCS

Recommendations

Automated global structure extraction for effective local building block processing in XCS

Learning Classifier Systems (LCSs), such as the accuracy-based XCS, evolve distributed problem solutions represented by a population of rules. During evolution, features are specialized, propagated, and recombined to provide increasingly accurate ...
Network crossover performance on NK landscapes and deceptive problems
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

Practitioners often have some information about the problem being solved, which may be represented as a graph of dependencies or correlations between problem variables. Similar information can also be obtained automatically, for example by mining the ...
Bayesian Immigrant Diploid Genetic Algorithm for Dynamic Environments
Artificial Evolution
Abstract
In dynamic environments, the main aim of an optimization algorithm is to track the changes and to adapt the search process. In this paper, we propose an approach called the Bayesian Immigrant Diploid Genetic Algorithm (BIDGA). BIDGA uses implicit ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

June 2005

2272 pages

ISBN:1595930108

DOI:10.1145/1068009

Editor:
Hans-Georg Beyer
Vorarlberg University of Applied Sciences, Austria
,
General Chair:
Una-May O'Reilly
CSAIL, MIT

Copyright © 2005 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: 25 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO05

Sponsor:

GECCO05: Genetic and Evolutionary Computation Conference

June 25 - 29, 2005

Washington DC, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
246
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nakata MBrowne W(2021)Learning Optimality Theory for Accuracy-Based Learning Classifier SystemsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2020.299431425:1(61-74)Online publication date: Feb-2021
https://doi.org/10.1109/TEVC.2020.2994314
Kovacs T(2012)Genetics-Based Machine LearningHandbook of Natural Computing10.1007/978-3-540-92910-9_30(937-986)Online publication date: 2012
https://doi.org/10.1007/978-3-540-92910-9_30
Urbanowicz RMoore J(2009)Learning classifier systemsJournal of Artificial Evolution and Applications10.5555/1644490.16444912009(1-25)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.5555/1644490.1644491
Kurahashi S(2008)Technology extraction from time series data reflecting expert operator skills and knowledgeInternational Journal of Computer Applications in Technology10.1504/IJCAT.2008.02193833:2/3(157-163)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.1504/IJCAT.2008.021938
Lanzi P(2008)Learning classifier systems: then and nowEvolutionary Intelligence10.1007/s12065-007-0003-31:1(63-82)Online publication date: 8-Feb-2008
https://doi.org/10.1007/s12065-007-0003-3
Kurahashi STerano T(2008)Technology Extraction of Expert Operator Skills from Process Time Series DataLearning Classifier Systems10.1007/978-3-540-88138-4_16(269-285)Online publication date: 17-Oct-2008
https://dl.acm.org/doi/10.1007/978-3-540-88138-4_16
Llorà XSastry KLima CLobo FGoldberg D(2008)Linkage Learning, Rule Representation, and the Χ-Ary Extended Compact Classifier SystemLearning Classifier Systems10.1007/978-3-540-88138-4_11(189-205)Online publication date: 17-Oct-2008
https://dl.acm.org/doi/10.1007/978-3-540-88138-4_11
Kurahashi S(2008)Real-Valued LCS Using UNDX for Technology ExtractionProceedings of the 12th international conference on Knowledge-Based Intelligent Information and Engineering Systems, Part II10.1007/978-3-540-85565-1_128(1026-1033)Online publication date: 3-Sep-2008
https://dl.acm.org/doi/10.1007/978-3-540-85565-1_128
Butz MGoldberg DLanzi P(2007)Effect of pure error-based fitness in XCSProceedings of the 2003-2005 international conference on Learning classifier systems10.5555/1761381.1761391(104-114)Online publication date: 1-Jan-2007
https://dl.acm.org/doi/10.5555/1761381.1761391
Llorà XSastry KYu TGoldberg DLipson H(2007)Do not match, inheritProceedings of the 9th annual conference on Genetic and evolutionary computation10.1145/1276958.1277319(1798-1805)Online publication date: 7-Jul-2007
https://dl.acm.org/doi/10.1145/1276958.1277319
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.

Media

Figures

Other

Tables

View Table of Contents