http://cs.felk.cvut.cz/~xobitko/ga/
Genetic algorithms are inspired by Darwin's theory
of evolution. Solution to a problem solved by genetic
algorithms is evolved.
What you need about a problem: a candidate solution can be evaluated
efficiently; gradient descent is likely to be bad.
Algorithm is started with a set of solutions
(represented by chromosomes) called population.
Solutions from one population are taken and used to
form a new population. This is motivated by a hope, that
the new population will be better than the old one.
Solutions which are selected to form new solutions
(offspring) are selected according to their fitness - the
more suitable they are the more chances they have to
reproduce.
This is repeated until some condition (for example
number of populations or improvement of the best
solution) is satisfied.
Example
As you already know from the chapter about
search space, problem solving can be often
expressed as looking for extreme of a function.
This is exactly what the problem shown here is.
Some function is given and GA tries to find
minimum of the function.
Outline of the Basic Genetic Algorithm
1.[Start] Generate random population of n
chromosomes (suitable solutions for the problem)
2.[Fitness] Evaluate the fitness f(x) of each
chromosome x in the population
3.[New population] Create a new population by
repeating following steps until the new population is
complete
1.[Selection] Select two parent chromosomes from
a population according to their fitness (the better
fitness, the bigger chance to be selected)
Take the best solutions (elitism to new population)
without crossover or mutation.
Then weight the rest based proportional to fitness.
2.[Crossover] With a crossover probability cross
over the parents to form a new offspring
(children). If no crossover was performed,
offspring is an exact copy of parents.
3.[Mutation] With a mutation probability mutate
new offspring at each locus (position in
chromosome).
4.[Accepting] Place new offspring in a new
population
4.[Replace] Use new generated population for a
further run of algorithm
5.[Test] If the end condition is satisfied, stop, and
return the best solution in current population
6.[Loop] Go to step 2
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:
Chromosome 1
1101100100110110
Chromosome 2
1101111000011110
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.
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.
You can have a crossover probability.
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:
Original offspring 1
1101111000011110
Original offspring 2
1101100100110110
Mutated offspring 1
1100111000011110
Mutated offspring 2
1101101100110110
You can have a mutation probability.
Example of Problem: Knapsack problem
The problem: There are things with given value
and size. The knapsack has given capacity. Select
to maximize the value of things in
knapsack, but do not extend knapsack capacity.
Encoding: Each bit says, if the corresponding
thing is in knapsack.
Example of Problem: Travelling salesman
problem (TSP)
The problem: There are cities and given
distances between them.Travelling salesman has
to visit all of them, but he does not want to travel very
much. Find a sequence of cities to minimize
travelled distance.
Encoding: Chromosome says order of cities, in
which salesman will visit them.
Mutation: reorders cities.
Example of problem: determine signals in a financial securities setting.
Jake Loveless and Amrut Bharambe (Cantor Fitzgerald).
All data-mining applications involve the same strategy, whether on Wall Street
or elsewhere: Take historical data and divide it into two parts: the training
set and the testing set. Then find rules in the training set and see whether
the rules hold in the testing set. The data is divided in this way to avoid
formulating a rule that arose just by chance. Even random pieces of data appear
to have patterns. The test data is there to determine whether the rule is
likely to be real.
A typical rule might be this: "If the price of a 10-year treasury rises by a
certain amount over 2 minutes while the 5-year treasury doesn't move, then the
5-year treasury is likely to rise in the next 2 minutes."
Rules that survive
the test data are said to be backtested. Statistics can also help evaluate when
rules hold by pure chance (bad) or are likely to be repeatable (good).
Rules might be made up of attributes such as
the slopes of the market price line over 1- or 5-minute intervals. Or rules
could be constructed out of moving averages over various time periods. Each
attribute has multiple values. A trading rule is a collection of these values.
Ended up with 28,000 possible rule components.
The brute force approach to finding rules consists of discovering all
combinations of attributes and values for a desired outcome, such as maximum
historical return. A good rule would find conditions that lead to a price rise
in the training set but not to a price decline in the testing data. A rule that
contained thousands of attributes would be useless, however, because it might
never or rarely recur and would not survive the statistical tests. The
computational solution is to find rules that use relatively few attributes and
maximize the desired outcome. The trouble is that even a small set of 10
attributes, in which each attribute has 10 distinct values, yields over 10
billion combinations.
Evolutionary approach: The
system would start by randomly selecting attributes and values, build a trading
rule from them, backtest them against the training set, and record the profit
or loss.
If the 1-minute slope of the traded price is >5%, and the 5-minute slope of the
traded size is >10%, then buy.
and profitable rule 2 stated,
If the 2-minute slope of the traded price is >5% and the 10-minute slope of the
traded size is <20%, then buy.
What would a new rule built from the two look like? And how would you combine
them? You could randomly interchange components of each of the two and end up
with rule 3:
If the 2-minute slope of the traded price is >5%, and the 5-minute slope of the
traded size is >10%, then buy.
Or you could modify a profitable rule by shifting one of its values.for
example, changing the value of the 2-minute slope attribute in rule 2 from 5%
to 10%, resulting in rule 4:
If the 2-minute slope of the traded price is >10% and the 10-minute slope of
the traded size is <20%, then buy.
Loveless used a collection of rule-searching strategies with technical names
like classical elite selection, local shifting, tabu-constrained crossover,
random selection, and a few he invented along the way. He combined these with
different fitness criteria. Each method attempts to build a collection of
solutions. At the end of each generation, or iteration, all solutions from all
methods are evaluated and recombined.
Bringing Modern Biology to Genetic Algorithms
Transcription factors -- certain genes can influence many other
genes in combination with other transcription factors.
MicroRNAs -- a single gene can repress a large number of other genes.
Honeypots -- a single honeypot could absorb many microarrays.
Can these be used? Should they?