New Sampling Distributions for Evolutionary Algorithms


Abstract

Evolution algorithms are stochastic optimization methods based on evolutionary principles. They have long been used in optimization, and are gaining in popularity. They are particularly useful in high dimensional problems, or in problems where gradient methods fails. Evolution strategies, a class of evolutionary algorithms, are stochastic searches which evolve by "mutation". This work proposes a new mutation distribution for use in single objective optimization. Up to now, cost function information obtained by mutations that do not improve fitness has been discarded. In many problems, particularly when cost function calls are expensive, it is desirable to use all available information to guide the search. The new method in this work patches Gaussians of different variances together to create a sampling distribution which delivers mutations designed to direct the search away from regions where low values of fitness have been observed. Analytic results for this new method are derived on idealized problems. The method is compared with existing methods on a range of test problems, and its overall performance attributes are assessed. A new method for multiobjective optimization is also developed. Genetic Algorithms introduce innovation into their populations by a process of bit mutation. This small scale mutation is often insufficient to successfully direct the search, unless the initial population is of sufficient quality. The new method proposed here, termed "Rank Biased Sampling", uses the population to create new members, which are resampled across the entire search space from a distribution designed to favor regions which are inadequately represented by the current population. Again, this method is compared to existing methods on some standard test problems. These new optimization methods are then applied to some real-world problems of engineering interest. The optimization routines developed in this work performed well on these applications, and provide good improvements on existing methods, as well as opening up avenues for further research.