Optimal sampling of genetic algorithms on polynomial regression.
Journal
GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation 2008
Pages
1089-1096
Date Issued
2008
Author(s)
Lin, Wei-Kai
Abstract
This paper investigates the utility of sampling as an evaluation-relaxation technique in genetic algorithms (GAs). In many real-world applications, sampling can be used to generate a less accurate, but computationally inexpensive fitness evaluator to speed GAs up. This paper focuses on the problem of polynomial regression as an example of problems with positive dependency among genes. Via statistical analysis of the noise introduced by sampling, this paper develops facet-wise models for the optimal sampling size, and these models are empirically verified. The results show that when the population is sized properly, small sampling sizes are preferred for most applications. When a fixed population size is adopted, which is usually the case in real-world applications, an optimal sampling size exists. If the sampling size is too small, the sampling noise increases, and GAs would perform poorly because of an insufficiently large population. If the sampling size is too large, the GA would spend too much time in fitness calculation and cannot perform well either within limited run duration. Copyright 2008 ACM.
Subjects
Fitness relaxation; Function mapping; Genetic algorithms; Optimal sampling; Polynomial regression; Speedup technique
Other Subjects
Genetic algorithms; Health; Polynomials; Population statistics; Regression analysis; Fitness relaxation; Function mapping; Optimal sampling; Polynomial regression; Speed-up techniques; Sampling
Type
conference paper