BioInformatics Pakistan

Practical Applications 2

Ansari — Wed, 24 Aug 2011 18:07:01 GMT

"…PRACTICAL APPLICATIONS/RESEARCH AREAS…”

Structural Bioinformatic Approaches

12. Prediction Of Protein Structure:

Protein structure prediction is another important application of bioinformatics. The amino acid sequence of a protein, the so-called primary structure, can be easily determined from the sequence on the gene that codes for it. In the vast majority of cases, this primary structure uniquely determines a structure in its native environment. (Of course, there are exceptions, such as the bovine spongiform encephalopathy – a.k.a. Mad Cow Disease – prion.) Knowledge of this structure is vital in understanding the function of the protein. For lack of better terms, structural information is usually classified as one of secondary, tertiary and quaternary structure. A viable general solution to such predictions remains an open problem. As of now, most efforts have been directed towards heuristics that work most of the time.

One of the key ideas in bioinformatics is the notion of homology. In the genomic branch of bioinformatics, homology is used to predict the function of a gene: if the sequence of gene A, whose function is known, is homologous to the sequence of gene B, whose function is unknown, one could infer that B may share A's function. In the structural branch of bioinformatics, homology is used to determine which parts of a protein are important in structure formation and interaction with other proteins. In a technique called homology modeling, this information is used to predict the structure of a protein once the structure of a homologous protein is known. This currently remains the only way to predict protein structures reliably.

One example of this is the similar protein homology between hemoglobin in humans and the hemoglobin in legumes (leghemoglobin). Both serve the same purpose of transporting oxygen in the organism. Though both of these proteins have completely different amino acid sequences, their protein structures are virtually identical, which reflects their near identical purposes.

Other techniques for predicting protein structure include protein threading and de novo (from scratch) physics-based modeling.

13. Molecular Interaction:

Efficient software is available today for studying interactions among proteins, ligands and peptides. Types of interactions most often encountered in the field include – Protein–ligand (including drug), protein–protein and protein–peptide.

Molecular dynamic simulation of movement of atoms about rotatable bonds is the fundamental principle behind computational algorithms, termed docking algorithms for studying molecular interactions.

14. Docking Algorithms:

In the last two decades, tens of thousands of protein three-dimensional structures have been determined by X-ray crystallography and Protein nuclear magnetic resonance spectroscopy (protein NMR). One central question for the biological scientist is whether it is practical to predict possible protein–protein interactions only based on these 3D shapes, without doing protein–protein interaction experiments. A variety of methods have been developed to tackle the Protein–protein docking problem, though it seems that there is still much work to be done in this field.

Software And Tools

Software tools for bioinformatics range from simple command-line tools, to more complex graphical programs and standalone web-services available from various bioinformatics companies or public institutions.

15. Open Source Bioinformatics Software:
  Many free and open source software tools have existed and continued to grow since the 1980s. The combination of a continued need for new algorithms for the analysis of emerging types of biological readouts, the potential for innovative in silico experiments, and freely available open code bases have helped to create opportunities for all research groups to contribute to both bioinformatics and the range of open source software available, regardless of their funding arrangements. The open source tools often act as incubators of ideas, or community-supported plug-ins in commercial applications. They may also provide de facto standards and shared object models for assisting with the challenge of bioinformation integration.
The range of open source software packages includes titles such as Bioconductor, BioPerl, BioJava, Bioclipse, EMBOSS, Taverna workbench, and UGENE. In order to maintain this tradition and create further opportunities, the non-profit Open Bioinformatics Foundation have supported the annual Bioinformatics Open Source Conference (BOSC) since 2000.

16. Web Services In Bioinformatics:
  SOAP and REST-based interfaces have been developed for a wide variety of bioinformatics applications allowing an application running on one computer in one part of the world to use algorithms, data and computing resources on servers in other parts of the world. The main advantages derive from the fact that end users do not have to deal with software and database maintenance overheads.
  Basic bioinformatics services are classified by the EBI into three categories: SSS (Sequence Search Services), MSA (Multiple Sequence Alignment) and BSA (Biological Sequence Analysis). The availability of these service-oriented bioinformatics resources demonstrate the applicability of web based bioinformatics solutions, and range from a collection of standalone tools with a common data format under a single, standalone or web-based interface, to integrative, distributed and extensible bioinformatics workflow management systems.

Neighbor Joining

Ansari — Tue, 23 Aug 2011 12:57:59 GMT

Neighbor Joining

1. Description:

In bioinformatics, neighbor joining is a bottom-up clustering method for the creation of phenetic trees (phenograms), created by Naruya Saitou and Masatoshi Nei. Usually used for trees based on DNA or protein sequence data, the algorithm requires knowledge of the distance between each pair of taxa (e.g., species or sequences) to form the tree.

2. Key Points:

Most widely-used distance based method for phylogenetic reconstruction
UPGMA illustrated that it is not enough tojust pick closest neighbors
Idea here: take into account averageddistances to other leaves as well
Produces an unrooted tree

Start off with star tree; pull out pairs at a time

3. NJ Algorithm:

Step 1: Let

(Almost) "average” distance to other nodes

Step 2: Choose i and j for which Mij – ui –uj is smallest

Look for nodes that are close to each other,and far from everything else
Turns out minimizing this is minimizing sum of branch lengths

Step 3: Define a new cluster (i, j), with a corresponding node in the tree

Distance from i and j to node (i,j):
di, (i,j) = 0.5(Mij + ui-uj)
dj, (i,j) = 0.5(Mij +uj-ui)
Default: split distance but if on average one is further away, make it longer

Step 4: Compute distance between new cluster and all other clusters:

Step 5: Delete i and j from matrix and replace by (i, j)
Step 6: Continue until only 2 leaves remain

4. Example:

Let us assume that we have four taxa (A, B, C, D) and the following distance matrix:

	A	B	C	D
A	0	7	11	14
B	7	0	6	9
C	11	6	0	7
D	14	9	7	0

We obtain the following values for the Q matrix:

	A	B	C	D
A	0	−40	−34	−34
B	−40	0	−34	−34
C	−34	−34	0	−40
D	−34	−34	−40	0

In the example above, two pairs of taxa have the lowest value, namely −40. We can select either of them for the second step of the algorithm. We follow the example assuming that we joined taxa A and B together. If $u$ denotes the new node, then the branch lengths of edges ${A, u}$ and ${B, u}$ are respectively 6 and 1, by the above formula.

We then proceed to updating the distance matrix, by computing $d (u, k)$ according to the above formula for every node $k$ . In this case, we obtain $d (u, C) = 5$ and $d (u, D) = 8$ . The resulting distance matrix is:

	AB	C	D
AB	0	5	8
C	5	0	7
D	8	7	0

We can start the procedure anew taking this matrix as the original distance matrix. In our example, it suffices to do one more step of the recursion to obtain the complete tree.

5. Advantages And Disadvantages:

Neighbor joining is based on the minimum-evolution criterion, i.e. the topology that gives the least total branch length is preferred at each step of the algorithm. However, neighbor joining may not find the true tree topology with least total branch length because it is a greedy algorithm that constructs the tree in a step-wise fashion. Even though it is sub-optimal in this sense, it has been extensively tested and usually finds a tree that is quite close to the optimal tree. Nevertheless, it has been largely superseded by phylogenetic methods that do not rely on distance measures and offer superior accuracy under most conditions.

The main virtue of neighbor joining relative to these other methods is its computational efficiency. That is, neighbor joining is a polynomial-time algorithm. It can be used on very large data sets for which other means of analysis (e.g. minimum evolution, maximum parsimony, maximum likelihood) are computationally prohibitive. Unlike the UPGMA algorithm for tree reconstruction, neighbor joining does not assume that all lineages evolve at the same rate (molecular clock hypothesis) and produces an unrooted tree. Rooted trees can be created by using an outgroup and the root can then effectively be placed on the point in the tree where the edge from the outgroup connects.

Furthermore, neighbor joining is statistically consistent under many models of evolution. Hence, given data of sufficient length, neighbor joining will reconstruct the true tree with high probability.

Atteson proved that if each entry in the distance matrix differs from the true distance by less than half of the shortest branch length in the tree, then neighbor joining will construct the correct tree.

RapidNJ and NINJA are fast implementations of the neighbor joining algorithm.

Although neighbor joining relies on a matrix whose entries are natural, some branch lengths in the resulting topology may be real numbers

6. NJ Performance:

Works well in practice
If there is a tree that fits the matrix, it will find it
Can sometimes get trees with negative length edges (!)

UPGMA

Ansari — Tue, 23 Aug 2011 11:56:35 GMT

UPGMA (Unweighted group method with arithmetic mean)

1. Description:

UPGMA (Unweighted Pair Group Method with Arithmetic Mean) is a simple agglomerative or hierarchical clustering method used in bioinformatics for the creation of phenetic trees (phenograms). UPGMA assumes a constant rate of evolution (molecular clock hypothesis), and is not a well-regarded method for inferring relationships unless this assumption has been tested and justified for the data set being used. UPGMA was initially designed for use in protein electrophoresis studies, but is currently most often used to produce guide trees for more sophisticated phylogenetic reconstruction algorithms.

The algorithm examines the structure present in a pairwise distance matrix (or a similarity matrix) to then construct a rooted tree (dendrogram).

At each step, the nearest two clusters are combined into a higher-level cluster. The distance between any two clusters A and B is taken to be the average of all distances between pairs of objects "x" in A and "y" in B, that is, the mean distance between elements of each cluster:

The method is generally attributed to Sokal and Michener. Fionn Murtagh found a time optimal O(n²) time algorithm to construct the UPGMA tree.

2. Key Points:

Sequential clustering algorithm
Start with things most similar

Build a composite OTU(Operational Taxonomic Units)

Distances to this OTU are computed asarithmetic means–
From new group of OTUs, pick pair withhighest similarity etc.
Average-linkage clustering

3. UPGMA Visually:

4. UPGMA Example:

5. UPGMA Weaknesses:

In fact, exact fitting tree exists !

UPGMA assumes that the rates of evolutionare the same among different lineages
In general, should not use this method forphylogenetic tree reconstruction (unlessbelieve assumption)
Produces a rooted tree
As a general clustering method (as wediscussed in an earlier lecture), it is better…

Markov Chains

Ansari — Tue, 23 Aug 2011 11:23:37 GMT

Markov Chains

1. Description:

A Markov chain, named for Andrey Markov, is a mathematical system that undergoes transitions from one state to another (from a finite or countable number of possible states) in a chainlike manner. It is a random process characterized as memoryless: the next state depends only on the current state and not on the entire past. This specific kind of "memorylessness" is called the Markov property. Markov chains have many applications as statistical models of real-world processes.

2. Key Points:

If we can predict all of the properties of a sequence knowing only the conditional dinucleotide probabilities, then that sequence is an example of a Markov chain
A Markov chain is defined as a sequence of states in which each state depends only on the previous state

3. Formalism For Markov Chains:

M=(Q,.,P) is a Markov chain, where
Q = vector (1,..,n) is the list of states

Q(1)=A, Q(2)=C, Q(3)=G, Q(4)=T for DNA

p = vector (p1,..,pn) is the initial probability of each state

p(i)=pQ(i) (e,g., p(1)=pA for DNA)

P= n x n matrix where the entry in row i and column j is the probability of observing state j if the previous state is i and the sum of entries in each row is 1 ( dinucleotide probabilities)

P(i,j)=p*Q(i)Q(i) (e.g., P(1,2)=p*AC for DNA)

4. Generating Markov Chains:

Given Q,.,P (and a random number generator), we can generate sequences that are members of the Markov chain M
If .,P are derived from a single sequence, the family of sequences generated by M will include that sequence as well as many others
If .,P are derived from a sampled set of sequences, the family of sequences generated by M will be the population from which that set has been sampled

5. Matlab Code For Generating Markov Chains:

chars = ['a' 'c' 'g' 't'];

% the dinucs array shows the frequency of observing the character in the
% row followed by the character in the column
% these values show strong preference for c-c
dinucs = [2, 1, 2, 0; 0, 8, 0, 1; 2, 0, 2, 0; 1, 0, 0, 1];
% these values restrict transitions more
%dinucs = [2, 0, 2, 0; 0, 8, 0, 0; 2, 0, 2, 0; 1, 1, 0, 1];

% calculate mononucleotide frequencies only as the probability of
% starting with each nucleotide
monocounts = sum(dinucs,2);
monofreqs = monocounts/sum(monocounts);
cmonofreqs = cumsum(monofreqs);
% calculate dinucleotide frequencies and cumulative dinuc freqs
freqs = dinucs./repmat(monocounts,1,4);
cfreqs = cumsum(freqs,2);
disp('Dinucleotide frequencies (transition probabilities)');
fprintf(' %c %c %c %c\n',chars)
for i=1:4
fprintf('%c %f %f %f %f\n',chars(i),freqs(i,:))
end
nseq = 10;
for ntries=1:20
rnums = rand(nseq,1);
% start sequence using mononucleotide frequencies
seq(1) = min(find(cmonofreqs>=rnums(1)));
for i=2:nseq
% extend it using the appropriate row from the dinuc freqs
seq(i) = min(find(cfreqs(seq(i-1),:)>=rnums(i)));
end

output=chars(seq);
disp(strvcat(output));
end

6. Discriminating Between Two States With Markov Chains:

To determine which of two states a sequence is more likely to have resulted from, we calculate

7. State probablities for + and - models

Given examples sequences that are from either + model (CpG island) or - model (not CpG island), can calculate the probability that each nucleotide will occur for each model (the a values for each model)

+ A C G T - A C G T

A 0.180 0.274 0.426 0.120 A 0.300 0.205 0.285 0.210

C 0.171 0.368 0.274 0.188 C 0.322 0.298 0.078 0.302

G 0.161 0.339 0.375 0.125 G 0.248 0.246 0.298 0.208

T 0.079 0.355 0.384 0.182 T 0.177 0.239 0.292 0.292

8. Transition Probabilities Converted To Log Likelihood Ratios:

ß A    C G   T

A   -0.740 0.419 0.580 -0.803

C    -0.913 0.302   1.812 -0.685

G   -0.624 0.461 0.331 -0.730

T -1.169 0.573 0.393 -0.679

9. Example:

What is relative probability of C+G+C+ compared with C-G-C-?

First calculate log-odds ratio: S(CGC)= ß(CG) +ß(GC)=1.812+0.461=2.273

Convert to relative probability: 22.273=4.833

Relative probability is ratio of (+)to(-) P(+)=4.833 P(-)

Convert to percentage

P(+) + P(-) = 1 4.833
P(-) + P(-) = 1
P(-) = 1/5.833 = 17%

Conclusion

P(+)=83% P(-)=17%

Simulated Annealing

Ansari — Tue, 23 Aug 2011 10:43:53 GMT

Simulated Annealing

1. Description:

Simulated annealing is a generalization of a Monte Carlo method for examining the equations of state and frozen states of n-body systems [Metropolis et al. 1953]. The concept is based on the manner in which liquids freeze or metals recrystallize in the process of annealing. In an annealing process a melt, initially at high temperature and disordered, is slowly cooled so that the system at any time is approximately in thermodynamic equilibrium. As cooling proceeds, the system becomes more ordered and approaches a "frozen" ground state at T=0. Hence the process can be thought of as an adiabatic approach to the lowest energy state. If the initial temperature of the system is too low or cooling is done insufficiently slowly the system may become quenched forming defects or freezing out in meta-stable states (ie. trapped in a local minimum energy state).

The original Metropolis scheme was that an initial state of a thermodynamic system was chosen at energy E and temperature T, holding T constant the initial configuration is perturbed and the change in energy dE is computed. If the change in energy is negative the new configuration is accepted. If the change in energy is positive it is accepted with a probability given by the Boltzmann factor exp -(dE/T). This processes is then repeated sufficient times to give good sampling statistics for the current temperature, and then the temperature is decremented and the entire process repeated until a frozen state is achieved at T=0.

By analogy the generalization of this Monte Carlo approach to combinatorial problems is straight forward [Kirkpatrick et al. 1983, Cerny 1985]. The current state of the thermodynamic system is analogous to the current solution to the combinatorial problem, the energy equation for the thermodynamic system is analogous to at the objective function, and ground state is analogous to the global minimum. The major difficulty (art) in implementation of the algorithm is that there is no obvious analogy for the temperature T with respect to a free parameter in the combinatorial problem. Furthermore, avoidance of entrainment in local minima (quenching) is dependent on the "annealing schedule", the choice of initial temperature, how many iterations are performed at each temperature, and how much the temperature is decremented at each step as cooling proceeds.

2. Key Points:

What exploits an analogy between the annealing process and the search for the optimum in a more general system.
Annealing Process:

Raising the temperature up to a very high level (melting temperature, for example), the atoms have a higher energy state and a high possibility to re-arrange the crystalline structure.
Cooling down slowly, the atoms have a lower and lower energy state and a smaller and smaller possibility to re-arrange the crystalline structure.

Analogy:

Metal ßà Problem
Energy State ßà Cost Function
Temperature ßà Control Parameter
A completely ordered crystalline structure ßà the optimal solution for the problem
Global optimal solution can be achieved as long as the cooling process is slow enough.

Metropolis Loop:

The essential characteristic of simulated annealing.
Determining how to randomly explore new solution, reject or accept the new solutionat a constant temperature T.
Finished until equilibrium is achieved.

Metropolis Criterion:

X be the current solution and X’ be the new solution
C(x) (C(x’))be the energy state (cost) of x (x’)

Probability Paccept = exp [(C(x)-C(x’))/ T]
Let N=Random(0,1)
Unconditional accepted if

C(x’) < C(x), the new solution is better

Probably accepted

if C(x’) >= C(x), the new solution is worse . Accepted only when N < Paccept

3. Algorithm Structure:

4. Algorithm:

Initialize initial solution x , highest temperature Th, and coolest temperature Tl
T= Th
When the temperature is higher than Tl
While not in equilibrium
Search for the new solution X’
Accept or reject X’ according to Metropolis Criterion
End
Decrease the temperature T
End

Definition of solution
Search mechanism, i.e. the definition of a neighborhood
Cost-function

5. Control Parameters:

Definition of equilibrium

Cannot yield any significant improvement after certain number of loops
A constant number of loops

Annealing schedule (i.e. How to reduce the temperature)

A constant value, T’ = T - Td
A constant scale factor, T’= T * Rd

A scale factor usually can achieve better performance

Temperature determination

Artificial, without physical significant
Initial temperature

80-90% acceptance rate

Final temperature

A constant value, i.e., based on the total number of solutions searched
No improvement during the entire Metropolis loop
Acceptance rate falling below a given (small) value

Problem specific and may need to be tuned

6. Example:

Traveling Salesman Problem (TSP)

Given 6 cities and the traveling cost between any two cities
A salesman need to start from city 1 and travel all other cities then back to city 1
Minimize the total traveling cost

Solution Representation

An integer list, i.e., (1,4,2,3,6,5)

Search Mechanism

Swap any two integers (except for the first one)
(1,4,2,3,6,5) ßà (1,4,3,2,6,5)

Cost Function
Temperature

Initial temperature determination

Around 80% acceptation rate for "bad move”
Determine acceptable (Cnew – Cold)

Final temperature determination

Stop criteria
Solution space coverage rate

Annealing schedule

Constant number (90% for example)
Depending on solution space coverage rate

7. Others:

Global optimal is possible, but near optimal is practical
Parameter Tuning

Aarts, E. and Korst, J. (1989). Simulated Annealing and Boltzmann Machines. John Wiley & Sons.

Not easy for parallel implementation
Randomly generator

Genetic Algorithms

Ansari — Tue, 23 Aug 2011 10:17:14 GMT

Genetic Algorithms

Page: 1 2

13. Other Parameters Of GA:

Initialization:

Population size
Random
Dedicated greedy algorithm

Reproduction:

Generational: as described before (insects)
Generational with elitism: fixed number of most fit individuals are copied unmodified into new generation
Steady state: two parents are selected to reproduce and two parents are selected to die; two offspring are immediately inserted in the pool (mammals)

Stop criterion:

Number of new chromosomes
Number of new and unique chromosomes
Number of generations

Measure:
Best of population

Average of population

Duplicates

Accept all duplicates
Avoid too many duplicates, because that degenerates the population (inteelt)
No duplicates at all

14. Example Run:

Maxima and Averages of steady state and generational replacement

Page: 1 2

Genetic Algorithms 2

Ansari — Mon, 22 Aug 2011 19:22:22 GMT

Genetic Algorithms

Page: 1 3

6. Parent/Survivor Selection:

Strategies

Survivor selection

Always keep the best one
Elitist: deletion of the K worst
Probability selection : inverse to their fitness
Etc.

Too strong fitness selection bias can lead to sub-optimal solution
Too little fitness bias selection results in unfocused and meandering search
Parent selection

Chance to be selected as parent proportional to fitness

Roulette wheel

To avoid problems with fitness function

Tournament

Not a very important parameter
Uniform randomly selection
Probability selection : proportional to their fitness
Tournament selection (Multiple Objectives)

Build a small comparison set Randomly select a pair with the higher rank one beats the lower one Non-dominated one beat the dominated one Niche count: the number of points in the population within certain distance, higher the niche count, lower the rank.

Etc.

Others

Global Optimal
Parameter Tuning
Parallelism
Random number generators

7. Example Of Coding For TSP:

Binary

Cities are binary coded; chromosome is string of bits

Most chromosomes code for illegal tour
Several chromosomes code for the same tour

Path

Cities are numbered; chromosome is string of integers

Most chromosomes code for illegal tour
Several chromosomes code for the same tour

Ordinal

Cities are numbered, but code is complex
All possible chromosomes are legal and only one chromosome for each tour

Several others

8. Roulette wheel:

Sum the fitness of all chromosomes, call it T
Generate a random number N between 1 and T
Return chromosome whose fitness added to the running total is equal to or larger than N
Chance to be selected is exactly proportional to fitness

Chromosome : 1   2   3 4   5   6
Fitness : 8   2   17   7   4   11
Running total : 8 10   27 34 38   49
N (1 £ N £ 49): 23
Selected : 3

9. Tournament:

Binary tournament

Two individuals are randomly chosen; the fitter of the two is selected as a parent

Probabilistic binary tournament

Two individuals are randomly chosen; with a chance p, 0.5

Larger tournaments

n individuals are randomly chosen; the fittest one is selected as a parent

By changing n and/or p, the GA can be adjusted dynamically

10. Problems With Fitness Range:

Premature Convergence

DFitness too large
Relatively superfit individuals dominate population
Population converges to a local maximum
Too much exploitation; too few exploration

Slow Finishing

DFitness too small
No selection pressure
After many generations, average fitness has converged, but no global maximum is found; not sufficient difference between best and average fitness
Too few exploitation; too much exploration

11. Solutions For These Problems:

Use tournament selection

Implicit fitness remapping

Adjust fitness function for roulette wheel

Explicit fitness remapping

Fitness scaling
Fitness windowing
Fitness ranking

12. Fitness Function:

Purpose

Parent selection
Measure for convergence
For Steady state: Selection of individuals to die
Should reflect the value of the chromosome in some "real” way
Next to coding the most critical part of a GA

Fitness scaling

Fitness values are scaled by subtraction and division so that worst value is close to 0 and the best value is close to a certain value, typically 2

Chance for the most fit individual is 2 times the average
Chance for the least fit individual is close to 0

Problems when the original maximum is very extreme (super-fit) or when the original minimum is very extreme (super-unfit)

Can be solved by defining a minimum and/or a maximum value for the fitness

Example of Fitness Scaling

Fitness windowing

Same as window scaling, except the amount subtracted is the minimum observed in the n previous generations, with n e.g. 10
Same problems as with scaling

Fitness Ranking

Individuals are numbered in order of increasing fitness
The rank in this order is the adjusted fitness
Starting number and increment can be chosen in several ways and influence the results
No problems with super-fit or super-unfit
Often superior to scaling and windowing

Fitness Evaluation

A key component in GA
Time/quality trade off
Multi-criterion fitness

Multi-Criterion Fitness

Dominance and Indifference

For an optimization problem with more than one objective function (fi, i=1,2,…n)
given any two solution X1 and X2, then

X1 dominates X2 ( X1 X2), if fi(X1) >= fi(X2), for all i = 1,…,n
X1 is indifferent with X2 ( X1 ~ X2), if X1 does not dominate X2, and X2 does not dominate X1

Pareto Optimal Set

If there exists no solution in the search space which dominates any member in the set P, then the solutions belonging the the set P constitute a global Pareto-optimal set.
Pareto optimal front

Dominance Check
Weighted sum

F(x) = w1f1(x1) + w2f2(x2) +…+wnfn(xn)
Problems?

Convex and convex Pareto optimal frontSensitive to the shape of the Pareto-optimal front
Selection of weights?

Need some pre-knowledge
Not reliable for problem involving uncertainties

Optimizing single objective

Maximize: fk(X) Subject to: fj(X) <= Ki ,i <> k , X in F where F is the solution space.

Preference based weighted sum

(ISMAUT Imprecisely Specific Multiple Attribute Utility Theory)
F(x) = w1f1(x1) + w2f2(x2) +…+wnfn(xn)
Preference

Given two know individuals X and Y, if we prefer X than Y, then F(X) > F(Y), that is w1(f1(x1)-f1(y1)) +…+wn(fn(xn)-fn(yn)) > 0

All the preferences constitute a linear space Wn={w1,w2,…,wn}

w1(f1(x1)-f1(y1)) +…+wn(fn(xn)-fn(yn)) > 0
w1(f1(z1)-f1(p1)) +…+wn(fn(zn)-fn(pn)) > 0, etc

For any two new individuals Y’ and Y’’, how to determine which one is more preferable?

Construct the dominant relationship among some indifferent ones according to the preferences.

Page: 1 3

Genetic Algorithms

Ansari — Mon, 22 Aug 2011 18:25:27 GMT

Genetic Algorithms

Page: 2 3

1. Description:

A genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of evolutionary algorithms (EA), which generate solutions to optimization problems using techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover.

2. Steps:

Encoding
Fitness Evaluation
Reproduction
Survivor Selection

3. Encoding:

Design alternative à individual (chromosome)
Single design choice à gene
Design objectives à fitness
Example: Problem

Schedule n jobs on m processors such that the maximum span is minimized.

Design Alternative: job i ( i=1,2,…n) is assigned to processor j (j=1,2,…,m)
Individual: A n-vector x such that xi = 1, …,or m
Design objective: minimize the maximal span
Fitness: the maximal span for each processor

4. Reproduction:

Reproduction operators

Crossover
Mutation

Crossover

Two parents produce two offspring
There is a chance that the chromosomes of the two parents are copied unmodified as offspring
There is a chance that the chromosomes of the two parents are randomly recombined (crossover) to form offspring
Generally the chance of crossover is between 0.6 and 1.0

Mutation

There is a chance that a gene of a child is changed randomly
Generally the chance of mutation is low (e.g. 0.001)

5. Reproduction Operators:

Crossover

Generating offspring from two selected parents

Single point crossover
Two point crossover (Multi point crossover)
Uniform crossover

Randomly one position in the chromosomes is chosen
Child 1 is head of chromosome of parent 1 with tail of chromosome of parent 2
Child 2 is head of 2 with tail of 1
Single point crossover
Two point crossover (Multi point crossover)
One-point crossover - Nature
Two-point crossover
Uniform crossover

A random mask is generated
The mask determines which bits are copied from one parent and which from the other parent
Bit density in mask determines how much material is taken from the other parent (takeover parameter)

Is uniform crossover better than single crossover point?

Trade off between

Exploration: introduction of new combination of features
Exploitation: keep the good features in the existing solution

Depending on coding, simple crossovers can have high chance to produce illegal offspring

E.g. in TSP with simple binary or path coding, most offspring will be illegal because not all cities will be in the offspring and some cities will be there more than once

Uniform crossover can often be modified to avoid this problem

E.g. in TSP with simple path coding:

Where mask is 1, copy cities from one parent
Where mask is 0, choose the remaining cities in the order of the other parent

Mutation

Generating new offspring from single parent
Maintaining the diversity of the individuals

Crossover can only explore the combinations of the current gene pool
Mutation can "generate” new genes

Control Parameters: population size, crossover/mutation probability

Problem specific
Increase population size

Increase diversity and computation time for each generation

Increase crossover probability

Increase the opportunity for recombination but also disruption of good combination

Increase mutation probability

Closer to randomly search
Help to introduce new gene or reintroduce the lost gene

Varies The Population:

Usually using crossover operators to recombine the genes to generate the new population, then using mutation operators on the new population

Page: 2 3

Evolution Strategies

Ansari — Mon, 22 Aug 2011 07:29:29 GMT

Evolution Strategies

1. Description:

In computer science, evolution strategy (ES) is an optimization technique based on ideas of adaptation and evolution. It belongs to the general class of evolutionary computation or artificial evolution methodologies.

The evolution strategy optimization technique was created in the early 1960s and developed further in the 1970s and later by Ingo Rechenberg, Hans-Paul Schwefel and his co-workers.

2. Key Points:

Typically applied to:

numerical optimisation

Attributed features:

fast
good optimizer for real-valued optimisation
relatively much theory

Special:

self-adaptation of (mutation) parameters standard

Representation	Real-valued vectors
Recombination	Discrete or intermediary
Mutation	Gaussian perturbation
Parent selection	Uniform random
Survivor selection	(m,l) or (m+l)
Specialty	Self-adaptation of mutation step sizes

3. Introductory Example:

Task: minimimise f : Rnà R
Algorithm: "two-membered ES” using

Vectors from Rn directly as chromosomes
Population size 1
Only mutation creating one child
Greedy selection

Pseudocode:

Set t = 0
Create initial point xt = á x1t,…,xntñ
REPEAT UNTIL (TERMIN.COND satisfied) DO
Draw zi from a normal distr. for all i = 1,…,n
yit = xit + zi
IF f(xt) < f(yt) THEN xt+1 = xt

ELSE xt+1 = yt
FI
Set t = t+1

Mutation Mechanism:

z values drawn from normal distribution N(x,s)

mean x is set to 0
variation s is called mutation step size

s is varied on the fly by the "1/5 success rule”:
This rule resets s after every k iterations by

s = s / c if ps > 1/5
s = s • c if ps < 1/5
s = s if ps = 1/5

where ps is the % of successful mutations, 0.8 £ c £ 1

Illustration Of Normal Distribution:

4. Representation:

Chromosomes consist of three parts:

Object variables: x1,…,xn
Strategy parameters:

Mutation step sizes: s1,…,sns
Rotation angles: a1,…, ana

Not every component is always present
Full size: á x1,…,xn, s1,…,sn ,a1,…, ak ñ
where k = n(n-1)/2 (no. of i,j pairs)

5. Mutation:

Main Mechanism: changing value by adding random noise drawn from normal distribution
x’i = xi + N(0,s)
Key Idea:

s is part of the chromosome áx1,…,xn,sñ
s is also mutated into s’

Thus: mutation step size s is co-evolving with the solution x

6. Recombination:

Creates one child

Acts per variable / position by either

Averaging parental values, or
Selecting one of the parental values

From two or more parents by either:

Using two selected parents to make a child
Selecting two parents for each position a new

Names Of Recombinations:

	Two fixed parents	Two parents selected for each i
zi=(xi + yi)/2	Local intermediary	Global intermediary
zi is xi or yi chosen randomly	Local discrete	Global discrete

7. Parent Selection:

Parents are selected by uniform random distribution whenever an operator needs one/some
Thus: ES parent selection is unbiased - every individual has the same probability to be selected
Note that in ES "parent” means a population member (in GA’s: a population member selected to undergo variation)

8. Survivor Selection:

Applied after creating p children from the m parents by mutation and recombination
Deterministically chops off the "bad stuff”
Basis of selection is either:

The set of children only: (m,p)-selection
The set of parents and children: (m+p)-selection

(m+p)-selection is an elitist strategy
(m,p)-selection can "forget”
Often (m,p)-selection is preferred for:
Better in leaving local optima
Better in following moving optima
Using the + strategy bad m values can survive in áx,mñ too long if their host x is very fit
Selective pressure in ES is very high (p » 7 • m is the common setting)

9. Self-Adaptation Illustrated:

Given a dynamically changing fitness landscape (optimum location shifted every 200 generations)

Self-adaptive ES is able to

follow the optimum and
adjust the mutation step size after every shift !

Prerequisites For Self-Adaptation:

m 1 to carry different strategies
p > m to generate offspring surplus
Not "too” strong selection, e.g., p » 7•m
(m,p)-selection to get rid of misadapted s‘s
Mixing strategy parameters by (intermediary) recombination on them

Evolutionary Computation

Ansari — Sun, 21 Aug 2011 19:50:55 GMT

Evolutionary computation

1. Description:

In computer science, evolutionary computation is a subfield of artificial intelligence (more particularly computational intelligence) that involves combinatorial optimization problems.

Evolutionary computation uses iterative progress, such as growth or development in a population. This population is then selected in a guided random search using parallel processing to achieve the desired end. Such processes are often inspired by biological mechanisms of evolution.

As evolution can produce highly optimised processes and networks, it has many applications in computer science. Here, simulations of evolution using evolutionary algorithms and artificial life started with the work of Nils Aall Barricelli in the 1960s, and was extended by Alex Fraser, who published a series of papers on simulation of artificial selection. Artificial evolution became a widely recognised optimisation method as a result of the work of Ingo Rechenberg in the 1960s and early 1970s, who used evolution strategies to solve complex engineering problems. Genetic algorithms in particular became popular through the writing of John Holland. As academic interest grew, dramatic increases in the power of computers allowed practical applications, including the automatic evolution of computer programs. Evolutionary algorithms are now used to solve multi-dimensional problems more efficiently than software produced by human designers, and also to optimise the design of systems.

2. History:

The use of Darwinian principles for automated problem solving originated in the fifties. It was not until the sixties that three distinct interpretations of this idea started to be developed in three different places.

Evolutionary programming was introduced by Lawrence J. Fogel in the USA, while John Henry Holland called his method a genetic algorithm. In Germany Ingo Rechenberg and Hans-Paul Schwefel introduced evolution strategies. These areas developed separately for about 15 years. From the early nineties on they are unified as different representatives ("dialects”) of one technology, called evolutionary computing. Also in the early nineties, a fourth stream following the general ideas had emerged – genetic programming.

These terminologies denote the field of evolutionary computing and consider evolutionary programming, evolution strategies, genetic algorithms, and genetic programming as sub-areas.

3. Evolutionary Algorithms:

Evolutionary algorithms form a subset of evolutionary computation in that they generally only involve techniques implementing mechanisms inspired by biological evolution such as reproduction, mutation, recombination, natural selection and survival of the fittest. Candidate solutions to the optimization problem play the role of individuals in a population, and the cost function determines the environment within which the solutions "live". Evolution of the population then takes place after the repeated application of the above operators.

In this process, there are two main forces that form the basis of evolutionary systems: Recombination and mutation create the necessary diversity and thereby facilitate novelty, while selection acts as a force increasing quality.

Many aspects of such an evolutionary process are stochastic. Changed pieces of information due to recombination and mutation are randomly chosen. On the other hand, selection operators can be either deterministic, or stochastic. In the latter case, individuals with a higher fitness have a higher chance to be selected than individuals with a lower fitness, but typically even the weak individuals have a chance to become a parent or to survive.