gbar for the chloride and calcium channels and the time constant and middle point of the
potassium channel parameters, Ninf and tauN. The simulations have a time step of 20
micro seconds and are responses of the single compartmental model to current injections
of .1 nanoampere to 1.0 nano ampere.
Genetic algorithms is a biomimetic science, its origin comes from a computational study
of natural evolution. Much of the terminology is borrowed from the field of genetics.
We first introduce some of the terminology. All biological organisms consist of cells,
these cells contain DNA or genetic information in one or more chromosomes. These
chromosomes consist of genes. Each gene encodes a trait. The different settings for a trait
are called 'allels'. Each genome is located at a particular locus or position in the gene.
The complete collection of all the genes, that is the chromosomes of an organism is
called the genome.
The term genotype refers to a set of genes in the genome. Two organisms with the same
genes are said to have the same genotype. The genotype gives rise to the phenotype on
development. Organisms whose chromosomes are in pairs are called diploid, a single set
of chromosomes is haploid. During sexual reproduction, recombination or crossover of
genes occurs to create the gamete. The gametes from the two parents combine to form a
diploid offspring chromosome.
In haploid organisms, genes are exchanged from single strands of parent chromosome.
The offspring genetic material is subject to random mutations owing to copying errors
and other factors. The fitness of an individual organism is the probability the organism
will live to reproduce(viability) or as a function of the number of offspring that organism
In genetic algorithms, a chromosome is usually a bit string and denotes a candidate
solution to a problem. An allele is usually a bit one or zero at each locus and in more
complicated encodings , it can be more complicated. Cross over consists of exchange of
genetic material between two haploid parents and mutation consists of inverting a single
bit at some locus. Often there is no phenotype but problems like neural networks have
both a phenotype and genotype.
A simple genetic algorithm
A genetic algorithm works as follows, given a clearly defined problem and a bit string
representation for a candidate solution.
1. start with a randomly generated population of n l-bit chromosomes.
2. Calculate the fitness f(x) of each chromosome x in the population.
3. Repeat the following steps until n offspring have been created.
a. Select a pair of parent chromosomes from the current population, the probability of
selection being an increasing function of the fitness. Selection is done with "replacement"
meaning that the same chromosome can be selected more than once to be a parent.
b. With crossover probability pcn cross over the pair at a randomly chosen cross over
point to form two offspring. If no cross over takes place form two offsprings that are
replicas of the parent. There are also "multi-point crossover" versions of the genetic
in which the cross over rate is the number of points the cross over takes place.
c. Mutate the two offsprings a each randomly chosen locus with probability pm and place
chromosomes in the new population.
4. replace the current population with the new population.
5. Goto step 2
A run is the entire set of generations, a generation being an iteration of the process.
A genetic algorithm(G.A)is typically iterated from 50 to 500 generations. At the end of
the run there are several highly fit chromosomes.
G.A's tend to be more complicated than this scheme with different types of crossovers
and mutations and also more complicated representation of the chromosomes.
There are however more details to fill like the size of the population and the probabilities
of crossover and mutation. The success of the algorithm greatly depends on these
parameters. Researchers often document the best fitness and the generation of that
The simple operator definitions.
Selection: This operator selects chromosomes in the population for reproduction. The
fitter the chromosome the more times it is likely to be selected to reproduce. A simple
method of implementing fitness proportionate selection is the "roulette-wheel sampling"
which is conceptually equivalent to giving each individual solution a slice of the circular
roulette wheel equal in area to that individuals fitness.
The roulette wheel is spun , The ball comes to rest on one wedge shaped slice, the
corresponding individual is selected.
Crossover: This operator randomly chooses a locus and exchanges the subsequences
before and after
that locus between two chromosomes to create two offsprings. For example the strings
10000100 and 11111111 could be crossed over after the third locus to give the offsprings
10011111 and 11100100.
Mutation:This operator randomly flips some of its bits in a chromosome. For example
00000100 can be mutated at the second position to give 01000100.
How do genetic algorithms work?
Although genetic algorithms are easy to code and perform very well, they are
complicated. Many open questions exist about how they work and for what problems
they are best suited. Much of the work done theoretically (Holland 1975)is on bit string
representations of the chromosomes
The traditional theory assumes that GAs work by discovering, emphasizing and
recombining good building blocks of solutions in a massively parallel way.
Holland introduced the notion of schemas or schemata to formalize the building blocks.
A schema is a bit string of ones, zeros and asterisks, the asterisks in the schemas denoting
don't care conditions or wild cards. For example the schema H=1****1 denotes all bit
strings of l=6 That start and end with a one. The strings that fit this template are called
instances, for example 100111 and 110011 are instances of H. The schema H has two
defined bits and is called an order 2 schema.
Its defining length in a hyper plane of dimension l is 5.
Note that not every possible subset of the set of length l-bit strings can be defined a s a
schema. There are 2^l possible bit strings and thus 2
possible subsets of strings, but
there are only 3^l schema Any given bit string of length l is an instance of 2^l different
schemas. Thus any given population of n strings contains instances of between 2^l and
This means that, at a given generation, while the GA is explicitly evaluating the fitness
of the n strings of the population, it is actually implicitly estimating the average fitness of
a larger population of schemas
Just as schemas are not explicitly represented or evaluated by the GA the estimates of the
average fitness of the schema average fitness are not evaluated by the GA. However the
GA's behavior in terms of increase or decrease of numbers of instances of given schemas
in the population can be described as though it actually were
actually computing and storing these averages.
Let H be a schema with at least one instance present in the population at time t, Let
m(H,t) be the number of instances of H at time t, and let u(H,t) be the observed average
fitness of H at time t.
We want to compute E(m(H,t+1)), the expected number of instances of H at time t+1,
The expected number of offspring of a string x is
f x f t
where f(x) is the fitness of
x and f(t) the average fitness of the population at time t Then assuming that x is in the
population at time t and x belongs to H , ignoring the effects of crossover and mutation
E m H,t 1 = ,xbelongsH f x f t
u H,t f t m H,t
, xbelongsHF x m H,t .
Cross over and mutation can increase or decrease the instances of H. To calculate a lower
bound on E(m(H,t+1)) we consider only the destructive effects of mutation and
Let pc be the probability of crossover of a single point. We can give a lower bound on the
that H will survive single point crossover.
where d(H) is the defining length of H and l is the length of bit strings in the search
The disruptive effect s of mutation can be quantified, let pm be the probability of any
bit being mutated. Then Sm(H) is equal to (1-pm)^o(H) where o(H) is the order of H, the
number of defined bits in H. Thus the probability of surviving mutation is higher for
lower order schemas. Amending this to equation 1.1
E m H,t 1
u H,t f t m H,t 1 pc d H l 1
This is known as the Schema theorem . It describes the growth of a schema from one
generation to the next. The schema theorem is often interpreted as implying that short
low order schemas whose fitness remains above the mean will receive exponentially
increasing number of samples over time.
The strength of a GA lies in the building block hypothesis that crossovers are the core of
a GA's power. The lower bound evaluated in 2.2 is by no means a complete statement of
a G.A's power, for a constructive crossover definition see Holland 1975, Thierens and
Golberg 1993 and Spears 1993.
Limitations of "static" schema analysis
Recent papers in genetic algorithms have criticized the schema formulation as a static
building block hypothesis (SBBH)(grefenstette 1993 and others). I will concentrate on
Grefenstette gives two possible reasons why the SBBH can fail
1. Collateral convergence: Once the population begins to converge at some loci, the
samples of some schemes are no longer uniform.
For example suppose instances of 111*...* are highly fit and the population has more or
less converged on this schema as a solution, then almost all samples of ***000*...* will
actually be samples of 111000*...*. This prevents the accurate estimate of u(***000*...*)
2.High fitness variance: If a schemas static average fitness has high variance, the GA may
not be able to make an accurate estimate of this static average fitness.
for example the variance of 1*...* is high so the GA converges on the high fitness
regions of this schema
This biases all subsequent samples of this scheme, preventing an accurate estimate of its
There is nothing to indicate that the features listed above harm the search performance of
GAs, they only demonstrate the danger of drawing conclusions about the expected
behavior of GAs from the static average fitness of schemas, Instead a more dynamic
approach is needed that takes into account the biases introduces by selection at each
One of such a scheme that pertains to a dynamical analysis is the royal road function.
one can refer to Mitchell 1996 for a detailed analysis.
Iterated hill climbing techniques
We now branch out to some other search techniques
a. Steepest ascent hill climbing(SAHC)
1. Choose a string at random, call this string current-hilltop
2.Going from left to right systematically flip each bit in the string , one at a time,
recording the fitness of the resulting one bit mutants.
3.If any of the resultant one bit mutants has a higher fitness set current-hill top to that one
bit mutant giving the highest rise to the fitness, Ties are chosen at random.
If there is no fitness increase then save current hill top and go to step one, otherwise go to
5.When a set number of function evaluations has been performed, return the highest
hilltop that was found.
b. Next-ascent hill climbing(NAHC)
1.Choose a string at random. Call this string current-hilltop.
2.For i from 1 to l , where l is the length of the string, flip bit i, if this results in an
increase in fitness keep the new string otherwise flip bit i back.
As soon as an increase in fitness is found set current hill top to that string without any
more bit flops of that string. Goto step 2 with the new current hilltop but continue
mutating the new string starting immediately after the bit position at which the previous
fitness increase was found.
3. If no increase in fitness were found save current hill top and goto step 1
4.When a set number of function evaluations has been performed return the highest hill
c. Random-mutation hill climbing(RMHC)
1. Choose a string at random, call this best-evaluated.
2.Choose a locus at random to flip, if the flip leads to equal or higher fitness, then set
best-evaluated to the resulting string.
3.goto step 2 until an optimum string has been found or until a maximum number of
evaluations have been performed.
4.Return the current value of best-evaluated.
For a detailed theoretical analysis of the above methods and the GA on simple problems,
refer to Mitchell 1996.
Genetic algorithms: Implementation issues.
There are many a successful genetic algorithm application, however there are many
problems where GAs do not fare well. Given a particular problem how does one know
whether a GA is a good method to use?
There is no rigorous answer, but if a problem is complex enough, the search space is
large, and if the search space is not perfectly smooth and unimodal. If the fitness function
is noisy or if any solution though not the globally optimized solution is needed.
Encoding the problem for a genetic algorithm.
The nature of encoding the problem along with the genetic algorithm parameters
determines the success of a GA. In this section we explore the nature of encodings either
as simple bit strings or more complicated encoding including real numbers.
This is the most common way of encoding the problems solution. Much of the existing
GA theory is based on fixed length binary encodings. Heuristics for parameters such as
the population size and the crossover and mutation probabilities have been developed for
bit string encoding.
Binary encodings are unnatural and unwieldy for a number of problems like the weights
of a neural network. Many character and real-valued encodings.
For many applications it is most natural to use an alphabet of many characters or real
valued representations. Examples include Montana and Davis's real valued
representation for neural network weights, Schultz-Kremer's real valued
representations for tortion angles in proteins. Holland's schema counting argument
seems to imply that GAs should exhibit worse performance on multiple character
encodings, however this has been refuted by many(eg see Antonisse 1989)Presently there
are no guidelines for predicting which encodings work best.
Tree encoding schemes like John Koza's scheme for representing computer programs,
have several advantages
including the fact that they allow the search space to be open ended. However this leads
to some pitfalls
The trees can grow large in uncontrollable ways, preventing the formation of more
structured hierarchical structures.(koza's 1992, 1994, "automatic definition of functions"
is one way in which a GA can be encouraged to design hieratically structured programs.
There are as yet very nascent attempts at applying
tree encodings to GAs.
How is one to decide which encoding to use for ones target problem? Lawrence Davis a
researcher with much experience in GAs suggests that one uses what is natural to ones
problem and then designing ones GA for that problem.. Most research is presently done
by guessing the encoding an d then adapting the GA to it. This is nor very different from
machine learning approaches like for example encoding a neural network is done by trail
and error. One appealing idea is however to have the encoding adapt itself to that the GA
can make a better use of it.
Adapting the encoding
The creation of the ideal encoding for a problem is paramount to solving that problem
itself. Usually genetic algorithms are used for hard problems without an easy solution.
Apart from guessing the encoding allowing it to adapt is one solution.
The ordering of bits in the chromosome is another issue. If these bits that were co adapted
were close together, then they would stay together in a crossover leading to fitter
chromosomes. But we have no idea on how to best order the bits ahead of time for the
problem. This is called the linkage problem in GA literature. A second reason for
adapting the encoding is that a fixed length chromosome limits the complexity of the
candidate solutions. It would thus be interesting to know if a chromosome were of
variable length, what strategies would evolve. Such an experiment was done by
Lindgren 1992, in which "gene doubling" and "deletion" operators allowed the
chromosome length to increase or decrease over time. More examples of such work are
described in Mitchell 1996.
Once the chromosomes are encoded. comes the next problem of selection, that is the
criteria to select some n parents from the current population
for crossovers and mutations. We encounter the classical exploitation/exploration
dilemma. In the next few sections , is described some of the selection methods. For a
detailed review see Mitchell 1996.
Fitness-Proportionate selection with "Roulette Wheel" and "Stochastic Universal"
The most common way of implementing selection is the roulette wheel where each
individual is assigned a wedge in a circle proportional to their fitness
The wheel is spun N times where there are N parents. This method can be implemented
1.Sum the total expected value of individuals in the population, Call this sum T.
2.Repeat N times: Choose a random integer between 0 and T
Loop through the individuals in the population, summing the expected values, until the
sum is greater than or equal to r. The individual whose expected value puts the sum over
the limit is the one selected. James Baker 1987, proposed a different sampling method.
Rather than spin the roulette wheel N times to select N parents, SUS spins the wheel
once, but with N equally spaced pointers, which are used to select the N parents. Baker
(1987) gives the following code fragment for SUS
ptr = Rand();/*returns random number uniformly distributed in [0 1]*/
for (sum = i=0;i<N; i++)
for(sum += ExpVal(i,t);sum>ptr;ptr++)
Where i is an index over population members and where ExpVal(i,t) gives the expected
value of individual i at time t.
SUS also suffers from premature convergence where the fitness variance of the
population decreases rapidly leading to little or no exploration.
To address the above problems, GA researchers have experimented with scaling methods,
methods to map raw fitness values to expected values. One example is sigma scaling.
Under sigma scaling an individuals expected value is a function of its fitness, the
populations mean and t he populations standard deviation.
f t 2sigma t ifsigma t
not equal to zero and
ExpVal(i,t) = 1.0 if sigma(t)=0
here ExpVal(i,t) is the expected value of individual i at time t, f)i) is the fitness of i, f_-
(t) is the average fitness of the population at time t and sigma(t) is the standard deviation
of the population fitness at time t.
For more details on sigma scaling refer to mitchell 1996.
Elitism first introduced by Kenneth De Jong 1975,many researchers have found this to
It involves retaining verbatim some of the members of the population which can be
destroyed by mutation and crossover.
It may be advantageous to have a varied program of fitness selection over time with a
liberal schedule early on so that the variance of fitness is large and in later
stages to have the selection pressure up in selecting only the very fit individuals.
Boltzman selection like simulated annealing is such a scheme. It has a variable called
temperature that can be increased over time, so the ExpVal takes on the form
ExpVal(i,t) = e^(f(i)/T)/<e^(f(i)/T)>
where T is the temperature and <> is the average over the population at time t.
Rank selection prevents premature convergence, here the population at time t is ranked 1
to N rather than use the fitness values directly. Ranking avoids giving the far largest
share of offspring to a few highly fit individuals thus reducing the selection pressure
when the variance if fitness is high.
The linear ranking method proposed by Baker is as follows :
Each individual in the population is ranked in increasing order of fitness. The user
chooses the expected value Max of the individual with rank n, and max>=0.The expected
value of each=h individual at time t, is given by
ExpVal(i,t)=Min + (Max-Min)((rank(i,t)-1)/(N-1))
For a more complete analysis of ranking see Mitchell 1996
The above mentioned selection requires two passes over the population at each
generation. One pass to compute the mean fitness and one pass to compute the
expected value for each individual
Rank selection requires sorting the population by rank a time consuming procedure,
Tournament selection is computationally more efficient and more amenable to parallel
implementation. Two individuals are chosen at random from the population. A random
number r is then chosen between 0 and 1.if r<k where k is a parameter, the fitter of the
two individuals is selected to be the parent otherwise the less fit individual is selected.
The two are returned to the original population and can be selected again.
An analysis of this method was presented by Goldberg and Deb(1991).
In steady state selection only few individuals are replaced in each generation usually a
small number of highly unfit individuals.
For more details see Mitchell 1996.
The third decision in a GA is the nature of genetic operators to use on the parent
Apart from crossover and mutation a number of other operators are also mentioned.
This includes inversion and gene doubling. De Jong 1975, experimented with a crowding
operator in which newly formed offspring replaced the existing individual most similar
to itself, this prevented crowding.
Goldberg and Richardson 1987, accomplished a similar result by an explicit fitness
sharing. In the case of fitness sharing the sharing was decreased with a factor that was
directly proportional to the similarity of the between two individuals. They showed that
in some cases this could induce speciation, allowing the population members to converge
on several peaks in the fitness landscape r rather than the population converging on one
Another way to preserve diversity is by controlling the mating, several methods have
been suggested, using mating tags, a kind of sexual selection where only individuals with
similar tags are allowed to mate, preventing incest where similar individuals cannot mate
and specism where only like individuals mate.
Finally there have been spatially restricted mating, the individuals are on a special lattice
and mating can occur only with the neighbors in the lattice.
Parameters for genetic algorithms.
The forth and last step is to determine the parameters such as the population size,
probability of crossover and mutation.
Much experimental work has been done on this issue a small part of which is described
in this section
There is no theory to compute the parameters and it still remains an experimental task.
De Jong performed much a investigation experimentally on a small test suite. His
Excerpt out of 42 pages
- Quote paper
- Anil Bheemaiah (Author), 2018, Evolutionary computing in neuronal modeling, Munich, GRIN Verlag, https://www.grin.com/document/387764