Introduction on Evolutionary Algorithms

Evolutionary Algorithms

Among the set of search and optimization techniques, the development of Evolutionary Algorithms (EA) has been very important in the last decade. EAs are a set of modern met heuristics used successfully in many applications with great complexity. It success on solving difficult problems has been the engine of a field known as Evolutionary Computation (EC).

    Benefits using EC techniques mostly come from flexibility gains and their fitness to the objective target in combination with a robust behavior. Now days, EC is consider as a adaptable concept for problems solution, specially complex optimization problems. This vision is the alternative to some old descriptions that shows EC as a collection of similar algorithms ready to be used in any problem.

    Most of the present implementations of EA come from any of these three basic types (strongly related although independently developed): Genetic Algorithms (GA), Evolutionary Programming (EP) and Evolutionary Strategies (ES). Two groups of EA have became very important, Genetic Programming (GP) with a lot of real problems and Classifier Systems (CS) used for machine learning and for discovering rules in rules based systems (RBS)

Figure 1. Location of the different families of evolutionary algorithms.

Genetic Algorithms

    A Genetic Algorithm (GA) is an heuristic used to find a vector x ^* (a string) of free parameters with associated values in an admissible region for which an arbitrary quality criterion is optimized:

    A sequential genetic algorithm proceeds in an iterative manner by generating new populations of string from the old ones. Every string is the encoded version of a tentative solution. An evaluation function associates a fitness measure to every string indicating its suitability to the problem. The algorithm applies stochastic operators such as selection, crossover and mutation on an initially random population in order to compute a whole generation of new strings.

    Since GAs apply operations drawn from nature, the nomenclature used in this field is closely related to the terms we can find in biology. The next table summarizes the meaning of these special terms in the aim of helping novel researchers

Table 1. Nomenclature in EA.

    Unlike most other optimization techniques, GAs maintain a population of tentative solution that are manipulated competitively by applying some variation operators to find a global optimum. This characteristic although is very useful to escape from local optimum, requires high computational resources (large memory and search times, for example), and thus a variety of are being studied to design efficient GAs. With this goal numerous advances are continuously being achieved by designing new operators, hybrid algorithms, and more. One very important of such improvements consists in using parallel models of GAs (PGAs).

    PGAs are not only parallel versions of sequential GAs. In fact they actually reach the ideal goal of having a parallel algorithm whose behavior is better than the sum of separate behaviors of its component sub-algorithms.

Sequential Genetic Algorithms

    The sequential genetic algorithm operates on a population of strings or, in general, structures of arbitrary complexity representing tentative solutions. In textbook versions of GAs, every string is called an individual and it is composed of one or more chromosomes and a fitness value. Normally, an individual contains just one chromosome that represents the set of parameters called genes. Every gene is in turn encoded in (usually) binary by using a given number of alleles(0,1).

Figure 2. Some details on the genotype.

Sequential evolutionary algorithm

Algorithm 1. Pseudo-code for a sequential evolutionary algorithm.

Parallel Genetic Algorithms

    As we said above, PGAs are not only parallel versions of sequential GAs. PGAs has the same advantages as a serial GA, consisting in using representations of the problem parameters (and not parameters themselves), robustness, easy customization for a new problem, and multiple-solution capabilities. These are the characteristics that led GAs and other EAs to be worth of study and use. In addition, a PGA is usually faster, less prone to finding only sub-optimal solutions, and able of cooperating with other search techniques in parallel. Summarizing advantages of using PGA are:

Advantages of using PGA:

• Works on a coding of the problem (least restrictive)
• Basically independent of the problem (robustness)
• Can yield alternative solutions to the problem
• Parallel search from multiple points in the space
• Easy parallelization as islands or neighborhoods
• Better search, even if no parallel hardware is used
• Higher efficiency and efficacy than sequential GAs
• Easy cooperation with other search procedures

    PGAs are a class of guided random evolutionary algorithms. If we take a deeper look at them we can distinguish among 4 different types of parallelization. Types 1 and2 proceed in the same way as a sequential GA, but in a faster manner. This is achieved by either profiting from a code parallelizer embedded in a compiler, or else by the explicit parallelization (master-slave global parallelization) of the genetic operators and/or evaluations. However, only for problems with a time-consuming function evaluation do they represent a viable choice; otherwise the communication overhead is higher than the benefits of their parallel execution.

    Many different models have been proposed for the rest of PGAs (types 3 y 4). However, all these existing models can fit into two more general classes depending on their grain of parallelism, called coarse or fine grained parallel GAs (cgpGAs and fgpGAs). This classification relies on the computation/communication ratio. If this ratio is high we call the PGA a coarse grain algorithm, and if low then we call a fine grain parallel GA.

    As a stochastic technique, in a PGA, we can distinguish three major steps, namely initial sampling, optimization and checking the stopping criterion. Therefore, it begins (t=0) by randomly creating a population P(t =0) of m structures, each one encoding the p problem variables on some alphabet.

    Each structure is usually a vector over IB={0,1} (I=IB ^p·xl)or IR (I=IR ^p). Consequently, each problem variable is encoded in l_x bits or in a floating-point number. However, as mentioned before, other non-string representations are possible.

Parallel Evolutionary Algorithm

Home | Introduction on EAs | xxGA | Problems | Links | Articles DB