|
Unit-05/Lecture-01 |
||||||||||||
|
GENETIC ALGORITHM;(Jun-2012,14) Genetic Algorithms are stochastic search techniques
based on themechanism of natural selection and
natural genetics to imitate living beings for solving those difficult
problems With high complexity and or undesirable
structure. Basic Concepts Genetic Algorithms
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
below 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. Genetic Algorithm vs Conventional Approach
|
|
Unit-05/Lecture-02 |
|
Working Principle of Genetic Algorithms (GAs) The workability of
genetic algorithms (GAs) is based on Darwinian’s theory of survival of the
fittest. Genetic algorithms (GAs) may contain a chromosome, a gene, set of
population, fitness, fitness function, breeding, mutation and selection.
Genetic algorithms (GAs) begin with a set of solutions represented by chromosomes,called population.
Solutions from one population are taken and used to form a new population,
which is motivated by the possibility that the new population will be better
than the old one. Further, solutions are selected according to their fitness
to form new solutions, that is, offsprings. The
above process is repeated until some condition is satisfied. Algorithmically,
the basic genetic algorithm (GAs) is outlined as below: Step I [Start] Generate random population of chromosomes, that is,
suitable solutions for the problem. Step II [Fitness] Evaluate the fitness of each chromosome in the
population. Step III [New population] Create a new population by repeating
following steps until the new population is complete. a) [Selection] Select two parent chromosomes from a population
according to their
fitness. Better the fitness, the bigger chance to be
selected to be the parent. b) [Crossover] With a crossover probability, cross over the
parents to form new offspring, that is, children. If no crossover was
performed, offspring is the exact copy of parents. c) [Mutation] With a mutation probability, mutate new offspring
at each locus. d) [Accepting] Place new offspring in the new population. Step IV
[Replace] Use new generated population for a further run of the algorithm. Step V [Test] If the end condition is satisfied, stop, and return
the best solution in current population. Step VI
[Loop] Go to step 2. The genetic
algorithms performance is largely influenced by crossover and mutation
operators. |
|
Unit-05/Lecture-03 |
||||||||||||
|
Fitness Function;(Jun-2012) A fitness function is a particular type of objective function that is used to
summarise, as a single figure of merit,
how close a given design solution is to achieving the set aims. In particular,the
fields ofgenetic programming and genetic algorithms, each design solution is
represented as a string of numbers (referred to as a chromosome). After each round of
testing, or simulation, the idea is to delete the 'n' worst design solutions,
and to breed 'n' new ones from the best
design solutions. Each design solution, therefore, needs to be awarded a
figure of merit, to indicate how close it came to meeting the overall
specification, and this is generated by applying the fitness function to the
test, or simulation, results obtained from that solution. The reason that genetic algorithms
cannot be considered to be a lazy way of performing design work is precisely
because of the effort involved in designing a workable fitness function. Even
though it is no longer the human designer, but the computer, that comes up
with the final design, it is the human designer who has to design the fitness
function. If this is designed badly, the algorithm will either converge on an
inappropriate solution, or will have difficulty converging at all. Moreover, the fitness function must
not only correlate closely with the designer's goal, it must also be computed
quickly. Speed of execution is very important, as a typical genetic algorithm
must be iterated many times in order to produce a usable result for a
non-trivial problem. Fitness approximation may be
appropriate, especially in the following cases:
Two main classes of fitness functions
exist: one where the fitness function does not change, as in optimizing a
fixed function or testing with a fixed set of test cases; and one where the
fitness function is mutable, as in niche differentiation or co-evolving the
set of test cases. Another way of looking at fitness
functions is in terms of a fitness landscape, which shows the fitness
for each possible chromosome. Definition of the fitness function is
not straightforward in many cases and often is performed iteratively if the
fittest solutions produced by GA are not what is desired. In some cases, it
is very hard or impossible to come up even with a guess of what fitness
function definition might be. Interactive genetic algorithms address
this difficulty by outsourcing evaluation to external agents (normally
humans).
|
|
Unit-05/Lecture-04 |
||||||||||||
|
Basic Genetic Algorithm Operations;
(Jun-2014) There are three
basic operators found in every genetic algorithm: reproduction, crossover and
mutation. There are some optimization algorithms that do not employ the
crossover operator. These algorithms will be referred to as evolutionary
algorithms rather than genetic algorithms. Reproduction The reproduction operator allows individual
strings to be copied for possible inclusion in the next generation. The
chance that a string will be copied is based on the string’s fitness value, calculated
from a fitness function. For each generation, the reproduction operator
chooses strings that are placed into a mating pool, which is used as the
basis for creating the next generation.
There are many
different types of reproduction operators. One always selects the fittest and
discards the worst, statistically selecting the rest of the mating pool from
the remainder of the population. There are hundreds of variants of this
scheme. None are right or wrong. In fact, some will perform better than others
depending on the problem domain being explored. For a detailed, mathematical comparison
of reproduction/selection strategies for genetic algorithms, see the work of Blickle. For the moment, we shall look at the most
commonly used reproduction method in GAs. The Roulette Wheel Method simply
chooses the strings in a statistical fashion based solely upon their relative
(ie. percentage) fitness values. This method can be
implemented for example by using a roulette wheel. The roulette wheel is
nothing but an implementation of the inverse function method for generating
discrete random deviates.
When selecting the
three strings that will be placed in the mating pool, the roulette wheel is
spun three times, with the results indicating the string to be placed in the
pool. It is obvious from the above wheel that there’s a good chance that
string 10000 will be selected more than once. This is fine. Multiple copies
of the same string can exist in the mating pool. This is even desirable,
since the stronger strings will begin to dominate, eradicating the weaker
ones from the population. There are difficulties with this, as it can lead to
premature convergence on a local optimum.
|
|
Unit-05/Lecture-05 |
||||||||
|
Crossover;(Jun-2013) Once the mating pool is created, the next
operator in the GA’s arsenal comes into play. Remember that crossover in
biological terms refers to the blending of chromosomes from the parents to
produce new chromosomes for the offspring. The analogy carries over to
crossover in GAs. The GA selects two strings at random from the mating pool.
The strings selected may be different or identical, it does not matter. The
GA then calculates whether crossover should take place using a parameter
called the crossover probability. This is simply a probability value p and is
calculated by flipping a weighted coin. The value of p is set by the user,
and the suggested value is p=0.6, although this value can be domain
dependant. If the GA decides not to perform crossover, the two selected
strings are simply copied to the new population (they are not deleted from
the mating pool. They may be used multiple times during crossover). If
crossover does take place, then a random splicing point is chosen in a
string, the two strings are spliced and the spliced regions are mixed to
create two (potentially) new strings. These child strings are then placed in
the new population. As an example, suppose that the strings 10000 and 01110
are selected for crossover and the GA decides to mate them. The GA then
randomly selects a splicing point, say 3. Then the following crossover will
then occur: 100|00
10010 ⇒ 011|10 01100 The newly created
strings are 10010 and 01100. Crossover is performed until the new population
is created. Then the cycle starts again with selection. This iterative
process continues until any user specified criteria are met (for example,
fifty generations, or a string is found to have a fitness exceeding a certain
threshold). • Mutation Selection and crossover alone can obviously
generate a staggering amount of differing strings. However, depending on the
initial population chosen, there may not be enough variety of strings to
ensure the GA sees the entire problem space. Or the GA may find itself
converging on strings that are not quite close to the optimum it seeks due to
a bad initial population. Some of these problems are overcome by introducing
a mutation operator into the GA. The GA has a mutation probability, m, which
dictates the frequency at which mutation occurs. Mutation can be performed
either during selection or crossover (though crossover is more usual). For
each string element in each string in the mating pool, the GA checks to see
if it should perform a mutation. If it should, it randomly changes the
element value to a new one. In our binary strings, 1s are changed to 0s and
0s to 1s. For example, the GA decides to mutate bit position 4 in the string 10000: 10000 ⇒ 10010 The resulting string is 10010 as the fourth
bit in the string is flipped. The mutation probability should be kept very
low (usually about 0.001%) as a high mutation rate will destroy fit strings
and degenerate the GA algorithm into a random walk, with all the associated
problems. But mutation will help prevent the population from stagnating, adding ”fresh blood”, as it were, to a population.
Remember that much of the power of a GA comes from the fact that it contains
a rich set of strings of great diversity. Mutation helps to maintain that
diversity throughout the GA’s iterations. GA Example: Optimization Problem We illustrate how GA
can be applied to solve an optimization problem. Specifically we want to find
the integer x in the interval [0, 31] that maximizes the function f(x) = x 2 . Clearly the answer is given by x = 31. Our goal here is to see how
GA can be used to find this answer. The first thing we need to do is to
convert the problem in such a way that we can apply GA ideas. In the context
of GA, it is obvious that the fitness function is f(x) = x 2 , and
the parameter of interest is x. The least obvious decision is how parameter x
should be coded. There are clearly many ways to accomplish that. In this
example we will code x by its binary representation. Since the maximum value
of x is 31, we code x using a finite string of 5 bits. The next choice is the
size of the population. We choose a very small population of only 4 so that
we can go through by hand one generation to see how GA actually works. We
randomly choose 4 strings, each consisting of a random sequence of 5 bits, to
represent the genes of the 4 individuals in that population. For example, we
obtain the strings as shown in the first column of the following table. Their
corresponding value of x (their phenotypes) are given by the decimal values
of the strings, as shown in column 2. Their fitnesses
as determined by the fitness function are shown in column 3. The total
fitness of the population is 1170, with a maximum fitness of 576 and an
average fitness of 293. The fitness of each individual as a fraction of the
total fitness is displayed in column 4. Notice that individual 2 is the
fittest and individual 3 is the least fit
To mimic the process
of reproduction, each string is copied with a probability given by its
relative fitness to the next generation. Suppose we get 1 copy of individual
1, 2 copies of individual 2, 0 copy of individual 3, and 1 copy of
individual 4. These strings then go into the mating pool. 01101 11000 11000
10011 Next these strings are paired up randomly and their genetic material is
switched at a randomly chosen site. For example, we pair up string 1 and 2
and pick a cross-over point at 4. String 3 and 4 are paired up and their
strings are swapped at site 2. The genes of the off-springs are then given by
the following strings. 011|01 01100 ⇒ 110|00 11001 11|000 11011 ⇒ 10|011 10000 Suppose we use a
mutation rate of 0.001 and perform bit changes on a bit-by-bit fashion. We
have a total of 20 bits here, and therefore the average number of bit changes
per generation is 20×0.001 = 0.02. We assume there is no mutation for this
generation. Therefore the new generation has the
following genetic makeup.
Notice that the
fitness of the fittest individual increases from 576 to 729. Furthermore the average fitness of the entire population
increases from 293 to 429. Also notice that the best string of the first
generation got 2 copies due to its fitness. The first copy 1100|0− >
1100|1 increases its fitness, and the second copy 11|000− > 11|011
does even better. There are many different ways in which one can carry out
the cross-over process. However there is one problem
with the cross-over process that we have just considered. With an initial
population of the following strings, we will never be able to find the
maximum of the function. Why? 01001 11000 11000 10011 The most optimal
solution is given by x = 31, which has a binary representation of 11111. However if we use the above cross-over procedure then we
can never obtain a 1 at the third position of the string. In this case we
will have to rely on mutation to create a 1 at that position.
|
|
Unit-05/Lecture-06 |
||||||||||||||||||||||||||||||||||||
Operators
of GA (Jun-2012,13,14)
The
crossover and mutation are the most important part of the genetic algorithm.
The performance is influenced mainly by these two operators. Before we can
explain more about crossover and mutation, some information about chromosomes
will be given. Encoding of a Chromosome
The
chromosome should in some way contain information about solution which it
represents. The most used way of encoding is a binary string. The chromosome
then could look like this:
Each
chromosome has one binary string. Each bit in this string can represent some
characteristic of the solution. Or the whole string can represent a number -
this has been used in the basic GA applet. Of course, there are many other ways of encoding. This depends
mainly on the solved problem. For example, one can encode directly integer or
real numbers, sometimes it is useful to encode some permutations and so on. Crossover
After
we have decided what encoding we will use, we can make a step to crossover.
Crossover selects genes from parent chromosomes and creates a new offspring.
The simplest way how to do this is to choose randomly some crossover point
and everything before this point point copy from a
first parent and then everything after a crossover point copy from the second
parent. Crossover can then look like this ( | is the crossover point):
There
are other ways how to make crossover, for example we can choose more
crossover points. Crossover can be rather complicated and very depends on
encoding of the encoding of chromosome. Specific crossover made for a
specific problem can improve performance of the genetic algorithm. Mutation After
a crossover is performed, mutation take place. This is to prevent falling all
solutions in population into a local optimum of solved problem. Mutation
changes randomly the new offspring. For binary encoding we can switch a few
randomly chosen bits from 1 to 0 or from 0 to 1. Mutation can then be
following:
The mutation depends on the encoding as well as the crossover
|
|
Unit-05/Lecture-07 |
|
Problem Solving
steps: ¨
When predicting the
expected gametes from an individual that is heterozygous or homozygous for
one of the chromosomal rearrangements you MUST diagram the pairing of the
homologous chromosomes at meiosis! This will ensure that you are very clear
about the chromosome composition going into and out of meiosis ¨
Remember to trace
out meiotic products beginning from the centromere! ¨
Pay attention to
whether the meiotic products are balanced (have one of everything – one
allele of each gene and one centromere). If the gametes are balanced then
they will give rise to viable progeny. If they are imbalanced (deleted or
duplicated for large regions of a chromosome) then the progeny are usually inviable. ¨
Deletions,
inversions, and translocations change the linkage of genes that surround or
are within the rearrangement. ¨
Deletion: ·
If the deletion of a
gene on one homolog uncovers a mutation in the gene on the other homolog then
the individual will show pseudodominance for the recessive mutant phenotype.
If you see pseudodominance in a cross it indicates the presence of a
deletion. ·
Deletions of DNA can
be analyzed using restriction analysis. In a diploid organism, a deletion on
one chromosome will mean that a restriction fragment that comes from within
the deleted region of the genome will be at half the concentration of that
found in a normal cell that has the DNA on both chromosomes. ¨
Inversion: Single
crossovers within the inversion loop lead to recombinant gametes that are
imbalanced for genetic material OUTSIDE the loop. One recombinant product is
duplicated for the region at outside the loop at one end of the chromosome
and simultaneously deleted for the material outside the loop at the other end
of the chromosome. The reciprocal recombinant gamete has the reciprocal
imbalance. All gametes have the expected amount of DNA for everything within
the inversion loop. If the centromere is in the inversion (pericentric) then
each meiotic product has a centromere. If the centromere is outside of the
inversion loop then the meiotic products that result from a single cross over
with in the loop are imbalanced for the centromere as well as the surrounding
genes – one recombinant product will be dicentric and the other will be acentric . ¨
Therefore, severe
reduction of recombination between genes within a rearrangement indicates the
presence of a deletion (heterozygous or homozygous) or an inversion
(heterozygous). ¨
Translocation: ·
More than half of
the gametes formed at meiosis are imbalanced – the products of adjacent 1 and
adjacent 2 segregations. Therefore the translocation
heterozygote is semisterile. This can be detected
in organisms such as corn where each kernel of corn on the ear is the result
of an independent fertilization event. Because the alternate segregation is
the only one that gives balanced gametes genes on the nonhomologous
chromosomes involved in the translocation act as if they are linked. Imagine
the genotype A N1/a T1; B N2/b T2. The only
balanced gametes are AB and ab (the products of alternate segregation in the
cruciform structure shown above). This is the result you would see from a
double heterozygote (A/a; B/b) if the A and B genes were
closely linked.
|
|
Unit-05/Lecture-08 |
||||||||||||||||
|
Applications of GA;(Jun-2013)
An effective GA representation and
meaningful fitness evaluation are the keys of the success in GA applications.
The appeal of GAs comes from their simplicity and elegance as robust search
algorithms as well as from their power to discover good solutions rapidly for
difficult high-dimensional problems. GAs are useful
and efficient when
The advantage of the GA approach is
the ease with which it can handle arbitrary kinds of constraints and
objectives; all such things can be handled as weighted components of the
fitness function, making it easy to adapt the GA scheduler to the particular
requirements of a very wide range of possible overall objectives. GAs have been used for
problem-solving and for modeling. Gas are applied
to many scientific, engineering problems, in business and entertainment,
including:
Differences Between GAs and Traditional
Methods Genetic algorithms
deal with a coded form of the function values (parameter set), rather than
with the actual values themselves. So, for example, if we want to find the
maximum of a function f(x1, x2) of two variables,
the GA would not deal directly with x1 or x2 values, but with strings that
encode these values. For example strings
representing the binary values of the variables can be used. Genetic algorithms
use a set, or population, of points to conduct a search, not just a single
point on the problem space. This gives GAs the power to search noisy spaces
littered with local optimum points. Instead of relying on a single point to
search through the space, the GAs looks at many different areas of the
problem space at once, and uses all of this information to guide it. Genetic
algorithms use only payoff information to guide themselves through the
problem space. Many search techniques need a variety of information to guide
themselves. Hill climbing methods require derivatives, for example. The only
information a GA needs is some measure of fitness about a point in the space
(sometimes known as an objective function value). Once the GA knows the
current measure of ”goodness” about a point, it can
use this to continue searching for the
optimum. GAs are probabilistic in nature, not deterministic.
This is a direct result of the randomization techniques used by GAs. GAs are inherently parallel. Here lies one of the most
powerful features of genetic algorithms. GAs, by their nature, are very
parallel, dealing with a large number of points (strings) simultaneously.
Holland has estimated that a GA processing n strings at each generation, the
GA in reality processes n3 useful substrings. This becomes clearer
later on when schemata are discussed.
|
