Abstract
Much previous works deal with the functions that cause a genetic algorithm (GA) to diverge from the global optimum. It is now a fact: Walsh analysis allows the identification of GA-hard problems. But what about genetics-based machine learning? Do we know what makes a problem hard for a classifier system (CS)? In order to try to answer these questions, we describe the relation between CS performance and the structure of a given boolean function when it is expressed as a Walsh polynomial. The analysis of the relative magnitude of Walsh coefficients allows us to set up a typology of boolean functions according to their hardness for a CS. Thus, each function can be placed in a specific class of difficulty. Using the converse process, we can start from well chosen Walsh coefficients in order to build boolean functions hard for a CS to learn.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. D. Bethke. Genetic algorithms as function optimizers. PhD thesis, University of Michigan, 1980.
D. E. Goldberg. Genetic algorithms and walsh functions. Complex Systems, 3:pp 129–171, 1989.
D. E. Goldberg. Construction of high-order deceptive functions using low-order walsh coefficients. Annals of Mathematics and Artificial Intelligence, 5:pp 35–48, 1992.
J. H. Holland. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press, 1975.
J. R. Koza. Genetic programming: On the programming of computers by means of natural selection. MIT Press, Cambridge, MA, 1993.
S. W. Wilson. Classifier systems and the animat problem. Machine Learning, 2 (3): 199–218, 1987.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 1995 Springer-Verlag/Wien
About this paper
Cite this paper
Escazut, C., Collard, P. (1995). Typology of Boolean Functions Using Walsh Analysis. In: Artificial Neural Nets and Genetic Algorithms. Springer, Vienna. https://doi.org/10.1007/978-3-7091-7535-4_43
Download citation
DOI: https://doi.org/10.1007/978-3-7091-7535-4_43
Publisher Name: Springer, Vienna
Print ISBN: 978-3-211-82692-8
Online ISBN: 978-3-7091-7535-4
eBook Packages: Springer Book Archive