29-04-2013, 04:32 PM
GENETIC ALGORITHMS AND THEIR APPLICATIONS: AN OVERVIEW
GENETIC ALGORITHMS.pdf (Size: 151.59 KB / Downloads: 215)
Abstract:
Genetic Algorithm (GA) is a calculus free optimization technique based on
principles of natural selection for reproduction and various evolutionary operations such as
crossover, and mutation. Various steps involved in carrying out optimization through GA
are described. Three applications, viz. finding maximum of a mathematical function,
obtaining estimates for a multiple linear regression model, and fitting a nonlinear statistical
model through GA procedure, are discussed. Finally, results are compared to those
obtained from standard (calculus based) solution techniques.
Introduction
A genetic algorithm (GA) is a search and optimization method which works by mimicking
the evolutionary principles and chromosomal processing in natural genetics. A GA begins
its search with a random set of solutions usually coded in binary strings. Every solution is
assigned a fitness which is directly related to the objective function of the search and
optimization problem. Thereafter, the population of solutions is modified to a new
population by applying three operators similar to to natural genetic operatorsreproduction,
crossover, and mutation. It works iteratively by successively applying these
three operators in each generation till a termination criterion is satisfied. Over the past
decade and more, GAs have been successfully applied to a wide variety of problems,
because of their simplicity, global perspective, and inherent parallel processing.
Classical search and optimization methods demonstrate a number of difficulties when
faced with complex problems. The major difficulty arises when one algorithm is applied to
solve a number of different problems. This is because each classical method is designed to
solve only a particular class of problems efficiently. Thus, these methods do not have the
breadth to solve different types of problems often faced by designers and practitioners.
Moreover, most of the classical methods do not have the global perspective and often get
converged to a locally optimum solution. Another difficulty is their inability to be used in a
parallel computing environment efficiently. Since most classical algorithms are serial in
nature, not much advantage can be achieved with them.
Basics of Genetic Algorithms
The idea of evolutionary computing was introduced in 1960 by Rechenberg in his work
“Evolutionary strategies”. GAs are computerized search and optimization algorithms based
on mechanics of natural genetics and natural selection. Prof. John Holland of University of
Michigan envisaged the concept of these algorithms in the mid-sixties and published
(Holland, 1975).
Basic Concepts
GAs are good at taking larger, potentially huge, search spaces and navigating them looking
for optimal combinations of things and solutions which we might not find in a life time.
GAs are very different from most of the traditional optimization methods. Genetic
algorithms need design space to be converted into genetic space. So, Genetic algorithms
work with a coding of variables. The advantage of working with a coding of variable space
is that coding discretizes the search space even though the function may be continuous. A
more striking difference between GAs and most of the traditional optimization method is
that GA uses a population of points at one time in contrast to the single point approach by
traditional optimization methods. This means that GA processes a number of designs at the
same time.
Working Principle
The GA is an iterative optimization procedure. Instead of working with a single solution in
each iteration, a GA works with a number of solutions (collectively known as population)
in each iteration. A flowchart of the working principle of a simple GA is shown in Figure
In the absence of any knowledge of the problem domain, a GA begins its search from a
random population of solutions. We shall discuss about the detail of coding procedure a
little later. But now notice how a GA processes strings in an iteration. If a termination
criterion is not satisfied, three different operators – reproduction, crossover and mutation –
are applied to update the population of strings. One iteration of these three operators is
known as a generation in the parlance of GAs. Since the representation of a solution in a
GA is similar to a natural chromosome and GA operators are similar to genetic operators,
the above procedure is called a genetic algorithm.
Reproduction
Reproduction (or selection) is usually the first operator applied to a population.
Reproduction selects good strings in a population and forms a mating pool. The essential
idea is that above-average strings are picked from the current population and duplicates of
them are inserted in the mating pool. The commonly used reproduction operator is the
proportionate selection operator, where a string in the current population is selected with
probability proportional to the string’s fitness. Thus, the ith string in the population is
selected with probability proportional to . Since the population size is usually kept fixed
in a simple GA, the cumulative probability for all string in the population must be one.
Software Packages
Whilst there exist many good public-domain genetic algorithm packages, such as
GENESYS and GENITOR, none of these provide an environment that is immediately
compatible with existing tools in the control domain. The MATLAB Genetic Algorithm
Toolbox aims to make GAs easily accessible. This allows the retention of existing
modelling and simulation tools for building objective functions and allows the user to
make direct comparisons between genetic methods and traditional procedures.
Data Structures
The main data structures in the GA Toolbox are chromosomes, phenotypes, objective
function values and fitness values. The chromosome structure stores an entire population in
a single matrix of size Nind × Lind, where Nind is the number of individuals and Lind is
the length of the chromosome structure. Phenotypes are stored in a matrix of dimensions
Nind × Nvar where Nvar is the number of decision variables. An Nind × Nobj matrix
stores the objective function values, where Nobj is the number of objectives. Finally, the
fitness values are stored in a vector of length Nind. In all of these data structures, each row
corresponds to a particular individual.
Toolbox Structure
The GA Toolbox uses MATLAB matrix functions to build a set of versatile routines for
implementing a wide range of genetic algorithm methods. In this section we outline the
major procedures of the GA Toolbox.
Population Representation and Initialization:crtbase, crtbp, crtrp
The GA Toolbox supports binary, integer and floating-point chromosome representations.
Binary and integer populations may be initialised using the Toolbox function to create
binary populations, crtbp. An additional function, crtbase, is provided that builds a vector
describing the integer representation used. Real-valued populations may be initialised
using crtrp. Conversion between binary and real-values is provided by the routine bs2rv
that also supports the use of logarithmic scaling.