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