Evaluation relaxation using substructural information and linear estimation
11 July 2006Sastry, K., Lima, C. F., Goldberg, D. E. (2006). Proceedings of the 2006 Genetic and Evolutionary Computation Conference, 419—426. [Full paper - PDF] [Full paper - PS] [Presentation slides].
Abstract:
The paper presents an evaluation-relaxation scheme where a fitness surrogate automatically adapts to the problem structure and the partial contributions of subsolutions to the fitness of an individual are estimated efficiently and accurately. In particular, the probabilistic model built by extended compact genetic algorithm is used to infer the structural form of the surrogate and a least squares method is used to estimate the coefficients of the surrogate. Using the surrogate avoids the need for expensive fitness evaluation for some of the solutions, and thereby yields significant efficiency enhancement. Results show that a surrogate, which automatically adapts to problem knowledge mined from probabilistic models, yields substantial speedup (1.75–3.1) on a class of boundedly-difficult additively-decomposable problems with and without additive Gaussian noise. The speedup provided by the surrogate increases with the number of substructures, substructure complexity, and noise-to-signal ratio.
Related Posts:
- Evaluation-relaxation schemes for genetic and evolutionary algorithms
- Genetic algorithms, efficiency enhancement, and deciding well with fitness functions with differing variances
- Sub-structural niching in estimation of distribution algorithms
- Substructural neighborhoods for local search in the Bayesian optimization algorithm
- Towards billion bit optimization via parallel estimation of distribution algorithm
No comments yet
