Evolutionary Algorithms and Genetic Programming [2]


Genetic Algorithm

Genetic algorithms are a variation of evolutionary algorithms. Genetic algorithms model of machine learning that derives its behavior from a metaphor of the processes of evolution in nature. This is done by the creation within a machine of a population of individuals represented by chromosomes, in essence a set of character strings that are analogous to the base-4 chromosomes that we see in our own DNA.

The individuals in the population then go through a process of evolution. The processes of nature boil down to different individuals competing for resources in the environment. Some are better than others. Those that are better are more likely to survive and propagate their genetic material.

Genetic algorithms are used for a number of different application areas. An example of this would be multidimensional optimization problems in which the character string of the chromosome can be used to encode the values for the different parameters being optimized. In practice, therefore, we can implement this genetic model of computation by having arrays of bits or characters to represent the chromosomes. Simple bit manipulation operations allow the implementation of crossover, mutation and other operations.

Although a substantial amount of research has been performed on variable-length strings and other structures, the majority of work with genetic algorithms is focused on fixed-length character strings. We should focus on both this aspect of fixed-lengthness and the need to encode the representation of the solution being sought as a character string, since these are crucial aspects that distinguish genetic programming, which does not have a fixed length representation and there is typically no encoding of the problem.

When the genetic algorithm is implemented it is usually done in a manner that involves the following cycle:
1.    Evaluate the fitness of all of the individuals in the population.
2.    Create a new population by performing operations such as crossover, fitness-proportionate reproduction and mutation on the individuals whose fitness has just been measured.
3.    Discard the old population and iterate using the new population.

One iteration of this loop is referred to as a generation. There is no theoretical reason for this as an implementation model. Indeed, we do not see this punctuated behavior in populations in nature as a whole, but it is a convenient implementation model. The first generation (generation 0) of this process operates on a population of randomly generated individuals. From there on, the genetic operations, in concert with the fitness measure, operate to improve the population.

Genetic Programming

Genetic programming is a branch of genetic algorithms. The main difference between genetic programming and genetic algorithms is the representation of the solution – genetic algorithms create a string of numbers that represent the solution while genetic programming creates computer programs as the solution.

The objects in genetic programming that constitute the population are not fixed-length character strings that encode possible solutions to the problem at hand, they are programs that, when executed, “are” the candidate solutions to the problem. These programs are expressed in genetic programming as program trees, rather than as lines of code. Thus, for example, the simple program “a + b * c” would be represented as:

Or, to be precise, as suitable data structures linked together to achieve this effect. Because this is a very simple thing to do in the programming language LISP, many GP programmers tend to use LISP. However, this is simply an implementation detail. There are straightforward methods to implement GP using a non-LISP programming environment. The programs in the population are composed of elements from the function set and the terminal set, which are typically fixed sets of symbols selected to be appropriate to the solution of problems in the domain of interest. In GP the crossover operation is implemented by taking randomly selected subtrees in the individuals (selected according to fitness) and exchanging them.   It should be pointed out that GP usually does not use any mutation as a genetic operator.

Further explanation of how genetic programming works is given in the section below.

Advertisements

2 thoughts on “Evolutionary Algorithms and Genetic Programming [2]

  1. Hi! I am currently writing a (free and open) e-book called “Global Optimization – Theory and Application””. It is about genetic algorithms, evolutionary algorithms, evolution strategy, leaning classifier systems, simulated annealing, and so on. I hope that I can make this topic more interesting for students and fellow researchers and help people to get started with it. Of course, it is still very incomplete and probably has also errors, but I try to improve it very much. You can find it at http://www.it-weise.de/projects/book.pdf, I will update it regularly. Constructive criticism is always welcom, as well as new suggestions on what to include in the book.
    Kind regards,
    Thomas.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s