Schemata, Building Blocks, and Everything Else

-

Genetic Algorithms (GAs), are a search and optimization method inspired in the way nature works with living entities, using evolutionary-based operators. These operators exchange genetic information through different generations until an ending condition, typically the desired solution, is found. In this entry, the formalism of why GAs work is described as proposed by Holland in the middle seventies and later by Goldberg. To do so, we first need to introduce some key concepts, assuming the classical ternary representation {0, 1, *}, where * is the don't care symbol.


A fundamental concept in GA theory is the one of schema. A schema is a particular subset among the set of all possible binary strings described by a template composed of the ternary alphabet {0, 1, *}. For instance, the schema 01**1 corresponds to the set of strings of length five (that is, strings composed of five symbols from the ternary alphabet) with a 0 in the first position, an 1 in the second position and an 1 in the last position. Every string that fits a template is called an instance of a schema. In our particular example, the strings 01001, 01011 and 01111, among others, are instances of the schema 01**1. It is very common to use the term schema to denote the subset as well as the template defining the subset itself.


Two more concepts are needed in order to understand the intrinsics of GAs: (1) the order of a schema and (2) the length of a schema.


(1) The order of a schema is defined as the number of bits that are non-don't care symbols. For example, the order of the schema 01**1 is 3.

(2) The length of a schema is defined as the distance between the first and the last non-don't care symbols. For example, the length of the schema 01**1 is 4.


With these definitions in mind we can model how different schemas evolve along a GA run using the schema theorem. This theorem states how the frequency of schema instances changes considering the effects of the evolutionary operators of selection, crossover and mutation. Going further, schema theorem states that the frequency of schemata with fitness higher than the average, short length and low-order ones increases in the following generation. One can find the mathematical foundations elsewhere in the bibliography. Anyway, schemata theorem is not enough to comprehend why GAs work; we need another conceptual leap. That is the case of building block hypothesis, which states that the combination of low-order, highly fit schemata (the building blocks) generate higher-order schemata. These new schemata will form high performance solutions. As in Goldberg's own words, the primary idea of GAs in that they work through a mechanism of decomposition and reassembly.


References

O. Corón, F. Herrera, F. Hoffmann, and L. Magdalena. Genetic fuzzy systems: Evolutionary tuning and learning of fuzzy knowledge bases, volume 19 of Advances in Fuzzy Systems— Aplications and Theory. World Scientific, 2001.

D. E. Goldberg. The design of innovation: Lessons from and for competent genetic algorithms. Kluwer Academic Publishers, 1 edition, 2002.

D. E. Goldberg. Genetic algorithms in search, optimization & machine learning. Addison Wesley, 1 edition, 1989.

J. H. Holland. Adaptation in natural and artificial systems. The University of Michigan Press, 1975.

A. Orriols-Puing. New Challenges in Learning Classifier Systems: Mining Rarities and Evolving Fuzzy Models. PhD thesis, Arquitectura i Enginyeria La Salle, Universitat Ramon Llull, Passeig de la Bonanova 8, 08022 - Barcelona, Nov 2008.

Comments

Post a Comment

Popular posts from this blog

A conceptual machine for cloning a human driver

-
Image
If anything else, a Machine Learning practitioner has to get a global view and think on how far our conceptual machines can go. This is a little tale of my recent experience with Deep Learning. To start with, say that I am enrolled in the Udacity’s nanodegree inSelf Driving Car Engineer . Here we are learning the techniques needed for building a car controller capable of driving at the human level. The interesting part of the course (to be read as where one truly learns) is in the so called projects: these are nothing but assignments in which the student has to solve a challenging task, mainly by using Convolutional Neural Networks (convnets), the most well-known Deep Learning models. So far, the most mind-blowing task and the focus of this entry is project 3, were we have to record our driving behavior in a car simulator and let a convnet to clone it and successfully generalize the act of driving. It is remarkable that a convnet learns to control the car from raw color images jointly
Read more

Data Streams and VFML

-
We live in a technological world crowded of information. Every device we can think of can give us a bunch of such data, usually in the form of a flow or stream of information in, more or less, real time . In this particular situation classical knowledge discovery mechanisms (like our loved C4.5, a decision tree developed by Quinlan) are completely unable of extract a correct model of the situation. But, what is so special with flows of data? Following the words of Gama and Rodriques: a data stream is an ordered sequence of instances that can be read only once or a small number of times using limited computing and storage capabilities. These sources of data are characterized by being open-ended, following at high speed, and generated by non-stationary distributions in dynamic environments . So, to properly handle this kind of knowledge the learning algorithm has to learn on line and process massive amounts of data increasing the challenges to be faced. Let's hold one's breath w
Read more

Data Analytics Plus Big Data: A Win-win Strategy

-
We live in a dynamic world where new technologies arise, dominate for a brief blink of an eye and then fall to oblivion rapidly. A part from the academia domain, it is interesting to check what are the current trends in the industry. Or even better: see the whole picture without discriminating. In this regard, a nice analytics tool is found in Google Trends, which allow us to track our terms of interest. The following chart shows the search interest for Machine Learning and Data Analytics . In a similar scale I depicted the search interest for Data Analytics and Big Data . As it is clearly noticeable, knowing both disciplines can open many doors in the industry. Finally, as top and also rising queries, Hadoop is the most popular term.
Read more