Genetic Algorithms and time series
The first approach to the time series problem using GA was made by Meyer and Packad [May90]. In this work, the main idea is to find prediction rules in the time series data. These rules are conditions over a set of variables. In he case of time series, these variables are the instants previous to the prediction x(k),...,x(k-d), or maybe a subset of them. The rules are asserts such as "if variable 1 is smaller than 0.9 and bigger than 0.13, variable 2 is smaller than 0.81 and bigger than 0.2, variable 4 is smaller than 0.94 and bigger than 0.01, and variable 7 is smaller than 9.9 and bigger than 0.45, then the prediction (for the output variable) will be 0.73. It could be expressed as
IF (0.13 < v1 < 0.9) AND (0.2 < v2 < 0.81) AND (0.01 < v4 < 0.94) AND (0.45 < v7 < 0.99) THEN prediction = 0.73
In order to use Genetic Algorithms, we need to encode this assert in an individual. This information is encoded as follows:
(0.13, 0.9, 0.2, 0.81, dc, dc, 0.01, 0.94, dc, dc, dc, dc, 0.45, 0.99, 0.73)
where dc means "don't care" (so there is no condition for the variable).
Let C be an individual and i a training pattern. If the value of the variables for pattern i meet the requirements of C, we will say C(i)=true, otherwise C(i)=false. The prediction assigned to the rule will be derived by averaging the target variable of the patterns from the training sample that fulfill the requirements specified by C.
In order to attain better results, [Luq04] applies some advanced GA and prediction techniques.
The most important step in this work is the use of a Michigan Approach.
We cannot use an standard Genetic Algorithm, because of the fact that the average values of the series have more data points than the extreme points or unusual set of data (for example an unusual high tide in the Venice Lagoon) deletes the individuals which makes predictions for that values of data, and the population becomes dominated by individuals which predicts medium values of the series. [Luq04] justify the use of a Michigan's approach [Boo89] using a Steady-State strategy. In the Michigan's approach, the solution to the problem is the total population instead of only one individual. In the Pittsburgh approach [Smi80] [Jan93] [Dej93], the solution to the problem is the best individual of the population, whose chromosome encodes a set of rules. [Luq04] uses a Michigan's approach because in a complex time series we can find a lot of rules, and for the Pittsburgh approach this produces very big individuals that consume a lot of memory and make his fitness evaluation too slow. [Luq04] applies the Michigan's approach selecting each generation only two parents by three rounds trial to generate only one offspring. Then it replaces the nearest individual to the offspring in phenotypic space. That is, it finds the individual whose prediction is nearest to the offspring's prediction, and replaces it by the offspring if and only if the offspring fitness is better than the individual's fitness. If this doesn't happen, there isn't any change this generation. That strategy generates a diverse population, in which each individual makes a prediction different to the others individuals, instead of genetic clones of the best individual, produced by the standard genetic algorithm method. Finally, after each execution of the model (75.000 generations), the individuals which predicts more than 5 points in the training set (and not only one as the standard genetic algorithm model does) are stored in a file, and the process is executed again. After some executions a file with a set of individuals is generated. Some individuals predicts the same points of the test set, so the final prediction is the mean of all predictions (we must remember that, possibly, not all the individuals could predict a point of the series).
[Luq04] also use a linear regression instead of an average of values in order to attain a higher accuracy in the predictions.