Evolutionary Algorithms (EAs) Overview

Evolutionary Algorithms (EAs) are optimization techniques designed for searching optimal values in complex spaces. 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 of 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:

• Single population or Panmixia: Where there are no group structures or mating restrictions. In this kind of population any individual may be mated with any other one of the population.
• Structured populations: Where the population is decentralized. Decentralizing the EA by structuring the population has many advantages, like getting greater performance, algorithmic improving (in diversity, convergence, dynamic environments, ...), or making possible to face more complex problems. But using structured algorithms may have some disadvantages too, like the greater complexity on the implementation and analysis, added to the fact that decentralizing the algorithm is not always better. There are two important models of decentralized populations:
• Coarse-grained or Distributed Evolutionary Algorithms (dEAs): The population is partitioned in several subpopulations (islands). Each island runs independently, and there are individual exchanges among the islands with a given frecuency.
• Fine-grained or Cellular Evolutionary Algorithms (cEAs): In cEAs, individuals are placed on a toroidal d-dimensional grid (where d = 1,2, or 3 is used in practice), one individual per grid location (this location is often refereed as a cell, and hence this fine-grained approach is also known as cellular). Every individual have a neighborhood, and an individual only can be mated for reproduction with other individual of its neighborhood. The main difference of a cellular EA with respect to a panmictic one is its decentralized selection, since the reproductive loop is performed inside each of the numerous individual pools. In a cEA, one given individual has its own pool defined by neighboring individuals, and at the same time, one individual belongs to many pools. This 2D structure with overlapped neighborhoods is used to provide a smooth diffusion of good solutions along the grid.

In Figure 1 we can see the difference of the behavior (success %) among a structured cGA, a panmictic genGA (generational) and a panmictic 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 a cEA. As we can see, when a cEA begins, it creates a random initial population, evaluates it, and then the variation operators are applied to all the individuals of the population in each generation. After that, the algorithm replaces the old population with the new one, evaluates this new population, and then checks the stooping conditions. The algorithm makes 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

back to home