694 Modern Methods of Optimization
13.2 Genetic Algorithms
13.2.1 Introduction
Many practical optimum design problems are characterized by mixed continuous–
discrete variables, and discontinuous and nonconvex design spaces. If standard nonlin-
ear programming techniques are used for this type of problem they will be inefficient,
computationally expensive, and, in most cases, find a relative optimum that is closest to
the starting point. Genetic algorithms (GAs) are well suited for solving such problems,
and in most cases they can find the global optimum solution with a high probability.
Although GAs were first presented systematically by Holland [13.1], the basic ideas
of analysis and design based on the concepts of biological evolution can be found in
the work of Rechenberg [13.2]. Philosophically, GAs are based on Darwin’s theory of
survival of the fittest.
Genetic algorithms are based on the principles of natural genetics and natural
selection. The basic elements of natural genetics—reproduction, crossover, and
mutation—are used in the genetic search procedure. GAs differ from the traditional
methods of optimization in the following respects:
1.A population of points (trial design vectors) is used for starting the procedure
instead of a single design point. If the number of design variables isn, usually
the size of the population is taken as 2nto 4n. Since several points are used as
candidate solutions, GAs are less likely to get trapped at a local optimum.
2.GAs use only the values of the objective function. The derivatives are not used
in the search procedure.
3.In GAs the design variables are represented as strings of binary variables that
correspond to the chromosomes in natural genetics. Thus the search method
is naturally applicable for solving discrete and integer programming problems.
For continuous design variables, the string length can be varied to achieve any
desired resolution.
4.The objective function value corresponding to a design vector plays the role of
fitness in natural genetics.
5.In every new generation, a new set of strings is produced by using randomized
parents selection and crossover from the old generation (old set of strings).
Although randomized, GAs are not simple random search techniques. They
efficiently explore the new combinations with the available knowledge to find
a new generation with better fitness or objective function value.13.2.2 Representation of Design Variables
In GAs, the design variables are represented as strings of binary numbers, 0 and 1. For
example, if a design variablexiis denoted by a string of length four (or a four-bit string)
as 0 1 0 1, its integer (decimal equivalent) value will be( 1 ) 20 +( 0 ) 21 +( 1 ) 22 +
( 0 ) 23 = 1 + 0 + 4 + 0 = 5. If each design variablexi, i = 1 , 2 ,... , nis coded in
a string of lengthq, a design vector is represented using a string of total lengthnq.
For example, if a string of length 5 is used to represent each variable, a total string
of length 20 describes a design vector withn=4. The following string of 20 binary
digits denote the vector (x 1 = 81 , x 2 = 3 , x 3 = 1 ,x 4 = ): 4