Increase the search capabilities of genetic algorithms using time series prediction

On writing the article, pushed the publication of forecasting time series .

Here I will show how time series prediction can be applied to increase search capabilities (PS) of genetic algorithms (GA).


')
By the search abilities of a genetic algorithm we mean its ability to create a chromosome corresponding to an arbitrary point in the search space.
The characteristic of the GA, which describes the PS, is not expressed numerically. Various factors, such as population size, selected crossbreeding and mutation operators, as well as other factors, influence PS GAs. It is legitimate to assume that the higher the search capabilities of the GA, the smaller the population is required, and the reduction of the population implies a decrease in the number of calculations of the fitness function.

When building a GA, few people pay enough attention to how the chromosomes will be created for the new generation, although with a good choice of the algorithm for creating new chromosomes, the PS can be significantly increased.

To increase the PS GA apply the so-called adaptive algorithms. Their idea is to dynamically change the various parameters of GA. The adaptive GA can also include the so-called statistical algorithms. The idea of ​​these algorithms is to study the statistics of some parameters of the GA. One of the first statistical algorithms is SANUX, which was proposed by Young in 2002. This is a binary GA based on the assumption of convergence of allele values.
The essence of this assumption is simple and intuitively obvious : the chromosomes converge to the optimal solution at the level of alleles, that is, each value in the chromosome converges to some optimal variant.
I said that the assumption is intuitively obvious, because it is not proven, but it works.
By the way, practically applicable theorems proven for GA can be counted on the fingers of one hand, so if someone feels strong in himself, then there is always a chance to write himself into the story.

Now apply this hypothesis to the construction of new chromosomes.
For each allele in the chromosome we will maintain a time series. Further, the next value of this series is somehow predicted, and it is selected as the chromosome allele. In addition to the algorithms proposed in the article , the following algorithm recommended itself well:

If the row for the allele is statistically controlled, then on this basis it is easy to guess about the meaning of the allele in the next population. If the series is uncontrollable, then there are several choices for the value of the allele, which practically do not improve the PS, so it is permissible to use the values ​​of the alleles from the templates with a sufficiently high fitness.
At the same time, for binary GA, about 15-20 generations are sufficient for collecting statistics. In the case of integer GA, the more generations passed, the better.

It should be noted that it makes sense to use this method of constructing chromosomes on problems of large dimensions.

Also, by analyzing the time series of alleles, one can dynamically control the crossover and mutation operators, as well as change the population size. When this is achieved a significant increase in PS GA.