Title: Genetic algorithm with integrated computing budget allocation for stochastic problems

Authors: Mengmei Liu; Aaron M. Cramer

Addresses: Department of Electrical and Computer Engineering, University of Kentucky, Lexington, KY 40506, USA ' Department of Electrical and Computer Engineering, University of Kentucky, Lexington, KY 40506, USA

Abstract: Stochastic problems are of great interest in many applications, and genetic algorithms (GAs) have been widely used to solve these kinds of problems. Normally, a large number of samples are needed to evaluate the stochastic function such that the sample mean closely approximates the actual mean in order to rank and select accurately in the GA; however, this method is computationally expensive. Some researchers have integrated different computing budget allocation schemes into the evaluation procedure of the GA to reduce the total computing cost. Herein, a GA is proposed in which computing budget allocation techniques are integrated directly into the selection operator rather than being used during fitness evaluation. This allows fitness evaluations to be allocated towards specific individuals for whom the algorithm requires more information, and this selection-integrated method is shown to be more accurate for the same computing budget than the existing evaluation-integrated methods on several test problems. Different computing budget allocation methods are studied on both traditional test functions and benchmark functions from a recent conference competition, and it is shown that the existing evaluation-integrated algorithm may require up to 225% of the samples required by the proposed selection-integrated GA to achieve results with the same accuracy.

Keywords: genetic algorithms; optimisation; statistical distributions; stochastic problems; budget allocation; computing budget.

DOI: 10.1504/IJMHEUR.2016.080257

International Journal of Metaheuristics, 2016 Vol.5 No.2, pp.115 - 135

Available online: 06 Nov 2016 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article