Evolutionary Algorithms and Genetic Programming [1]


Introduction

Evolution in general means change and adaptation to the changes by a population and not individuals, changes that are passed on to the next generations. The idea of applying the biological principle of natural evolution to artificial systems, introduced more than three decades ago, has seen impressive growth in the past few years. Usually grouped under the term evolutionary algorithms or evolutionary computation, we find the domains of genetic algorithms, evolution strategies, evolutionary programming, and genetic programming.
Evolutionary algorithms (EAs) are ubiquitous nowadays, having been successfully applied to numerous problems from different domains including optimization, automatic programming, machine learning, economics, operations research, ecology, studies of evolution and learning, and social systems. In this article, we consider genetic algorithms in general and genetic programming to be specific.

Evolutionary Algorithms

Evolutionary algorithm is an overall term used to describe computer-based problem solving systems that use computational models of some of the known mechanisms of evolution as key elements in their design and implementation.

A variety of evolutionary algorithms have been proposed. The major ones are: genetic algorithms, evolutionary programming, evolution strategies, classifier systems and genetic programming. They all share a common conceptual base of simulating the evolution of individual structures via processes of selection, mutation, and reproduction. The topic of discussion in this article concerns genetic programming, but to understand genetic programming it is necessary to first understand the basic concepts of evolutionary algorithms.

EAs maintain a population of structures that evolve according to rules of selection and other operators that are referred to as genetic operators, such as recombination and mutation. Each individual in the population is measured for its fitness in the environment. Reproduction focuses on high fitness individuals and recombination and mutation agitate those individuals, providing general heuristics for exploration.

To understand EAs, it is necessary to have some appreciation of the biological processes on which they are based. In nature, the encoding for genetic information (genome) admits asexual reproduction. Asexual reproduction typically results in offspring that are genetically identical to the parent. (large numbers of organisms reproduce asexually; this includes most bacteria which some biologists hold to be the most successful species known.) Sexual reproduction allows some shuffling of chromosomes, producing offspring that contain a combination of information from each parent.

At the molecular level what occurs (wild oversimplification alert!) is that a pair of almost identical chromosomes bump into one another, exchange chunks of genetic information and drift apart. This is the recombination operation, which is often referred to as crossover because of the way that biologists have observed strands of chromosomes crossing over during the exchange.

Recombination happens in an environment where the selection of who gets to mate is largely a function of the fitness of the individual, i.e. how good the individual is at competing in its environment. Some “luck” (random effect) is usually involved too.

Some EAs use a simple function of the fitness measure to select individuals (probabilistically) to undergo genetic operations such as crossover or asexual reproduction (the propagation of genetic material unaltered). This is fitness-proportionate selection. Other implementations use a model in which certain randomly selected individuals in a subgroup compete and the fittest is selected. This is called tournament selection and is the form of selection we see in nature when stags rut to vie for the privilege of mating with a herd of hinds. Much EA research has assumed that the two processes that most contribute to evolution are crossover and fitness based selection/reproduction.

Evolution, by definition, absolutely requires diversity in order to work. In nature, an important source of diversity is mutation. In an EA, a large amount of diversity is usually introduced at the start of the algorithm, by randomizing the genes in the population. The importance of mutation, which introduces further diversity while the algorithm is running, therefore continues to be a matter of debate. Some refer to it as a background operator, simply replacing some of the original diversity that may have been lost, while others view it as playing the dominant role in the evolutionary process.

It cannot be stressed too strongly that an evolutionary algorithm (as a simulation of a genetic process) is not a random search for a solution to a problem (highly fit individual). EAs use stochastic processes, but the result is distinctly non-random (better than random).

Algorithm EA is

// start with an initial time
t := 0;

// initialize a usually random population of individuals
initpopulation P (t);

// evaluate fitness of all initial individuals in population
evaluate P (t);

// test for termination criterion (time, fitness, etc.)
while not done do

// increase the time counter
t := t + 1;

// select sub-population for offspring production
P' := selectparents P (t);

// recombine the "genes" of selected parents
recombine P' (t);

// perturb the mated population stochastically
mutate P' (t);

// evaluate its new fitness
evaluate P' (t);

// select the survivors from actual fitness
P := survive P,P' (t);
od
end EA.
Advertisements

3 thoughts on “Evolutionary Algorithms and Genetic Programming [1]

  1. Hello,

    if you’re interested in Genetic Algorithms, Genetic Programming or multi-objective, randomized heuristic search algorithms, you would maybe like to have a look at the Distributed Genetic Programming Framework. This LGPL-licensed, open source Java project can be found in the internet at http://dgpf.sourceforge.net/.
    It also allows you to distribute the searches over a network and let different search algorithms (GA, Hill Climbing, …) interact and form a heterogeneous search.

  2. Pingback: Gabriel

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