Excerpt

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**

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

has.(fertility)

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

exact

replicas of the parent. There are also "multi-point crossover" versions of the genetic

algorithms

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

the resulting

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

solution.

**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

2

*l*

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

n*2^l schemas.

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

we have.

*E m H,t*1

*= ,xbelongsH f x f t*

*u H,t f t m H,t*

(1.1)

since

*u 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

crossover.

Let pc be the probability of crossover of a single point. We can give a lower bound on the

probability Sc(H)

that H will survive single point crossover.

Sc(H)>=1-pc(d(H)/(l-1))

where d(H) is the defining length of H and l is the length of bit strings in the search

space.

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

gives:

*E m H,t*1

*u H,t f t m H,t*1

*pc d H l*1

1

*pm**o H*

(1.2)

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

grefentette's critique.

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

static fitness.

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

generation.

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

step 2

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

top found.

**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.

**Binary encodings**

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 encodings**

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.

**Selection methods**

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"**

**sampling.**

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

as follows

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++)

Select (i);

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.

**Sigma scaling:**

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.

*ExpVal i,t*

1

*f i*

*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**

Elitism first introduced by Kenneth De Jong 1975,many researchers have found this to

improve performance.

It involves retaining verbatim some of the members of the population which can be

destroyed by mutation and crossover.

**Boltzman selection.**

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**

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

**Tournament Selection**

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).

**Steady-State selection**

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.

**Genetic Operators**

The third decision in a GA is the nature of genetic operators to use on the parent

population.

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

peak.

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

Publish now - it's free

Comments