Evolutionary Algorithms (EAs) Overview

Evolutionary Algorithms (EAs) are optimization techniques for searching complex spaces for an optimum. They are based on some biological processes that can be appreciated in nature. These processes of nature seem to boil down to a haphazard generation of biologically diverse organisms. Some of evolution is determined by natural selection or 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.

Sexual reproduction allows some shuffling of chromosomes, producing offspring that contain a combination of information from each parent. 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. 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 which may have been lost, while others view it as playing the dominant role in the evolutionary process.

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

Every Evolutionary Algorithm works over a set of individuals which evolve along the time to find a solution. This set of individuals is usually called population. Among all the types of representation for the population that have been proposed the most popular are:

In Figure 1 we can see the difference of the behavior (success %) among a structured cGA and the panmistic genGA (generational) and ssGA (steady state) when solving the Rosenbrock problem with some different instances.

Figure 1. The cGA versus genGA and ssGA (success %)

 

Among the major of the evolutionary algorithms proposed we can stand out:

They all share a common conceptual base of simulating the evolution of individual structures via processes of selection, mutation, and reproduction. The processes depend on the perceived performance of the individual structures as defined by an environment.

In Figure 2 we show the typical structure of an cEA. As we can see, when an EA begins it creates a random initial population, evaluates it, and then we can see how they are applied the variation operators for all the individuals of the population in each generation. Once made that, the algorithm replace the old population with the new one, evaluate this new population, and checks the stooping condition. The algorithm make this loop until the stopping condition is satisfied. For an explained pseudocode of a Cellular EA click here.

Figure 2. Structure of a Cellular Evolutionary Algorithm