Fitness approximation

This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. Please improve this article by introducing more precise citations where appropriate. (April 2009)

Artificial intelligence portal

In many real-world optimization problems including engineering problems, the number of fitness function evaluations needed to obtain a good solution dominates the optimization cost. In order to obtain efficient optimization algorithms, it is crucial to use information gained during optimization process. This leads to build model of the fitness function to choose smart search steps. A variety of techniques for constructions of such a model – often also referred to as surrogates, metamodels or approximation models – for computationally expensive optimization problems are investigated.

Common approaches based on learning and interpolation from known fitness values of a small population, (e.g. low-degree polynomials and the Least square estimations, artificial neural networks (ANN), including multilayer perceptrons and radial basis function networks, support vector machine (SVM), regression model, etc.) are being employed. Because of the limited number of training samples and high dimensionality encountered in engineering design optimization, constructing a globally valid approximate model remains to be difficult. As a result, evolutionary algorithms using such approximate fitness functions may converge to local optimums. Therefore, it can be beneficial to selectively use the original fitness function together with the approximate model.

Look up fitness in Wiktionary, the free dictionary.

Adaptive fuzzy fitness granulation (AFFG), a granulation-based fitness approximation scheme, is one of the recent solutions. It is proposed in order to approximate the fitness function for substituting the time consuming large-scale problem analysis like (L-SPA) by FEA. In this approach, an adaptive pool of solutions (fuzzy granules) with an exactly computed fitness function is maintained. If a new individual is sufficiently similar to a known fuzzy granule, then that granule’s fitness is used instead as a crude estimate. Otherwise, that individual is added to the pool as a new fuzzy granule. In this fashion, regardless of the competition’s outcome, fitness of the new individual is always a physically realizable one, even if it is a “crude” estimate and not an exact measurement. The pool size as well as each granule’s radius of influence is adaptive and will grow/shrink depending on the utility of each granule and the overall population fitness. To encourage fewer function evaluations, each granule’s radius of influence is initially large and is gradually shrunk in latter stages of evolution. This encourages more exact fitness evaluations when competition is fierce among more similar and converging solutions. Furthermore, to prevent the pool from growing too large, granules that are not used are gradually eliminated.

Actually AFFG mirrors two fundamental facts of human cognition: (a) granularity (b) similarity analysis. This granulation-based fitness approximation scheme is applied to solve various engineering optimization problems including detecting hidden information from watermarked signal in addition to several structural optimization problems.

Computer Science portal

References

• The cyber shack of Adaptive Fuzzy Fitness Granulation (AFFG) That is designed to accelerate the convergence rate of EAs.
• A complete list of references on Fitness Approximation in Evolutionary Computation, by Yaochu Jin.
• M. Davarynejad, "Fuzzy Fitness Granulation in Evolutionary Algorithms for complex optimization", (PDF) M.Sc. Thesis. Ferdowsi University of Mashhad, Department of Electrical Engineering, 2007.