Genetic algorithm with integrated computing budget allocation for stochastic problems. (2016)

• Record Type: Journal Article
• Authors: Liu, Mengmei; Cramer, Aaron M.
• Is Part Of: International journal of metaheuristics. Volume 5:Number 2(2016)
• Page Start: 115
• Page End: 135
• Publication Date: 2016
• Subjects: genetic algorithms -- optimisation -- statistical distributions -- stochastic problems -- budget allocation -- computing budget; Heuristic algorithms -- Periodicals; 006.3105
• Languages: English
• ISSNs: 1755-2176

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.