Statistical analysis of genetic algorithms and inference about optimal factors
Andrei Petrovski, Alexander E. Wilson, John McCall · 1998
Abstract In this paper, statistical analysis, in the form of regression models and fractionalfactorial experiments, has been applied to genetic algorithms (GA) – a search methodfor non-linear constrained function optimisation. The distribution of the experimentalresults and a way to make this distribution normal have been established. Then, GAfactors whose significance is invariant to the environmental noise have beendetermined. Finally, regression models describing two characteristics of searchefficiency in terms of significant GA factors have been obtained. These modelsenabled calculation of optimal values for the significant GA factors. After substitutionof these values, algorithm performance is substantially improved.Keywords: regression models, Taguchi method, fractional factorial design, Weibullmodel, genetic algorithms, non-linear optimisation and control. 1. Introduction Genetic algorithms (GA) are an optimisation tool that computationally emulates the process ofevolution. They have been applied to a number of engineering and biomedical problems whichrequire the search for an optimum through a large space of candidate solutions (Mitchell,1996).Genetic algorithms combine elements of stochastic and directed search strategies (Michalewicz,1992). Stochastic features of GA present themselves in the process of information gatheringand exchange implemented by the mutation and crossover operators. These operators play anextremely important role with respect to the speed of the search and the robustness of themethod.Unfortunately, there is no simple analytical expression or a theoretical model that describes theperformance of the GA in terms of the method’s factors. One way to estimate the effects ofsignificant GA factors is to use statistical methods of analysis and inference. This is the majortask of the report.1.1. Exploration vs. exploitationOne of the areas where genetic algorithms have shown their effectiveness is a wide class ofproblems that require the implementation of an efficient search. Genetic algorithms are able toperform a multi-directional search using a population of candidate solutions that explores thesearch space (Michalewicz, 1992).