GENETIC ALGORITHMS

• The problem addressed by GAs is to search a

space of candidate hypotheses to identify the
best hypothesis.
• In GAs the "best hypothesis" is defined as the
one that optimizes a predefined numerical
measure for the problem at hand, called the
hypothesis fitness.
• The algorithm operates by iteratively updating a
pool of hypotheses, called the population. On
each iteration, all members of the population are
evaluated according to the fitness function.
• A new population is then generated by
probabilistically selecting the most fit individuals
from the current population.
• Some of these selected individuals are carried
forward into the next generation population intact.
Others are used as the basis for creating new
offspring individuals by applying genetic
operations such as crossover and mutation.
• REFER TABLE 9.1 for “A prototypical genetic
algorithm” (PAGE no 251, Tom Mitchell book)
 Genetic Algorithm Example
Example: Maximizing a Function
• Consider the problem of maximizing the function, f(x)
= x^2
where x is permitted to vary between 0 to 31. The steps
involved in solving this problem are as follows:
• Step 1: For using genetic algorithms approach, one
must first code the decision variable ‘x’ into a finite
length string. Using a five bit (binary integer)
unsigned integer, numbers between 0(00000) and
31(11111) can be obtained. The objective function here
is f(x) = x^2 which is to be maximized.
• To start with, select initial population at
random. Here initial population of size 4 is
chosen, but any number of populations can be
elected based on the requirement and
application.
• Table 1. shows an initial population randomly
selected.
• The population average fitness has improved
from 288.75 to 636.5 in one generation. The
maximum fitness has increased from 625 to
841 during same period.
• Although random processes make this best
solution, its improvement can also be seen
successively.
GENETIC PROGRAMMING
 Genetic programming (GP)
• Genetic programming (GP) is a form of
evolutionary computation in which the
individuals in the evolving population are
computer programs rather than bit strings.
• Koza (1992) describes the basic genetic
programming approach and presents a broad
range of simple programs that can be
successfully learned by GP.
 Representing Programs
• Programs manipulated by a GP are typically
represented by trees.
• Each function call is represented by a node in
the tree, and the arguments to the function
are given by its descendant nodes.
• For example, Figure 9.1 illustrates this tree
representation for the function
• To apply genetic programming to a particular
domain, the user must define the primitive
functions to be considered as well as the
terminals (e.g., x, y, constants such as 2).
• As in a genetic algorithm, the prototypical
genetic programming algorithm maintains a
population of individuals (in this case,
program trees). On each iteration, it produces
a new generation of individuals using
selection, crossover, and mutation.
• . Crossover operations are performed by
replacing a randomly chosen subtree of one
parent program by a subtree from the other
parent program.
 MODELS OF EVOLUTION AND
LEARNING
• In many natural systems, individual organisms
learn to adapt significantly during their
lifetime.
• At the same time, biological and social
processes allow their species to adapt over a
time frame of many generations.
 Lamarckian Evolution
• Larmarck was a scientist who, in the late
nineteenth century, proposed that evolution
over many generations was directly
influenced by the experiences of individual
organisms during their lifetime.
• In particular, he proposed that experiences of a
single organism directly affected the genetic
makeup of their offspring:
• Example: If an individual learned during its
lifetime to avoid some toxic food, it could pass
this trait on genetically to its offspring, which
therefore would not need to learn the trait.
• It would presumably allow for more efficient
evolutionary progress than a
generate-and-test process (like that of GAS
and GPs) that ignores the experience gained
during an individual's lifetime.
 Baldwin Effect
• Although Lamarckian evolution is not an
accepted model of biological evolution, other
mechanisms have been suggested by which
individual learning can alter the course of
evolution.
• One such mechanism is called the Baldwin
effect, after J. M. Baldwin (1896), who first
suggested the idea.
• Baldwin proposed that individual learning can
explain evolutionary phenomena. The ability
of individuals to learn can guide the
evolutionary process.
• In effect, learning smooths the fitness
landscape, thus facilitating evolution.
• Example: Imagine some new change in the
environment of some species, such as a new
predator. Such a change will selectively favor
individuals capable of learning to avoid the
predator.
• As the proportion of such self-improving
individuals in the population grows, the
population will be able to support a more diverse
gene pool, allowing evolutionary processes to
adapt more rapidly.
• Thus. the Baldwin effect provides an indirect
mechanism for individual learning to positively
impact the rate of evolutionary progress.
• By increasing survivability and genetic diversity
of the species, individual learning supports more
rapid evolutionary progress, thereby increasing
the chance that the species will evolve genetic,
nonlearned traits that better fit the new
environment
• There have been several attempts to develop
computational models to study the Baldwin effect.
• For example, Hinton and Nowlan (1987)
experimented with evolving a population of simple
neural networks, in which some network weights
were fixed during the individual network
"lifetime," while others were trainable.
• Additional computational studies of the Baldwin
effect have been reported by Belew (1990), Harvey
(1993), and French and Messinger (1994).
PARALLELIZING GENETIC ALGORITHMS
• GAs are naturally suited to parallel
implementation, and a number of approaches
to parallelization have been explored.
1. Coarse grain approaches to parallelization
subdivide the population into somewhat
distinct groups of individuals, called demes.
▪ Each deme is assigned to a different computational
node, and a standard GA search is performed at
each node
• These models are characterised by the
relatively long time they require for
processing a generation within each
(“sequential”) deme, and by their occasional
communication for exchanging individuals.
• Sometimes coarse grained parallel GAs are
known as distributed GAs because they are
usually implemented on distributed memory
MIMD computers. This approach is also well
suited for heterogeneous network.
• Transfer between demes occurs by a migration
process, in which individuals from one deme are
copied or transferred to other demes.
• This process is modeled after the kind of
cross-fertilization that might occur between
physically separated subpopulations of biological
species.
• One benefit of such approaches is that it reduces
the crowding problem often encountered in
nonparallel GAs, in which the system falls into a
local optimum due to the early appearance of a
genotype that comes to dominate the entire
population.
• What Is the “Crowding Problem”?
– In non-parallel Genetic Algorithms where there’s
only one large population, sometimes an early
good solution (genotype) appears.
That genotype starts reproducing a lot because it
gives higher fitness and soon, almost everyone
becomes similar to it. So the GA stops exploring
new possibilities and gets stuck in a local best.
– This is called crowding or premature convergence.
2. Fine grained algorithms are the opposite.
▪ They require a large number of processors
because the population is divided into a large
number of small demes.
▪ Inter-deme communication is realised either by
using a migration operator, or by using
overlapping demes.
▪ fine-grained implementations typically assign one
processor per individual in the population.
Recombination then takes place among
neighboring individuals.
 Applications of GAs
• Optimization − Genetic Algorithms are most
commonly used in optimization problems wherein we
have to maximize or minimize a given objective
function value under a given set of constraints. The
approach to solve Optimization problems has been
highlighted throughout the tutorial.
• Economics − GAs are also used to characterize various
economic models like the cobweb model, game theory
equilibrium resolution, asset pricing, etc.
• Neural Networks − GAs are also used to train neural
networks, particularly recurrent neural networks.
• Parallelization − GAs also have very good parallel
capabilities, and prove to be very effective means in
solving certain problems, and also provide a good area
for research.
• Image Processing − GAs are used for various digital
image processing (DIP) tasks as well like dense pixel
matching.
• Vehicle routing problems − With multiple soft time
windows, multiple depots and a heterogeneous fleet.
• Scheduling applications − GAs are used to solve
various scheduling problems as well, particularly the
time tabling problem.
• Machine Learning − as already discussed, genetics
based machine learning (GBML) is a niche area in
machine learning.
• Robot Trajectory Generation − GAs have been
used to plan the path which a robot arm takes by
moving from one point to another.
• Parametric Design of Aircraft − GAs have been
used to design aircrafts by varying the parameters
and evolving better solutions.
• DNA Analysis − GAs have been used to determine
the structure of DNA using spectrometric data
about the sample.
• Multimodal Optimization − GAs are obviously
very good approaches for multimodal optimization
in which we have to find multiple optimum
solutions.