Optimization of noisy fitness functions by means of genetic algorithms using history of search with test of estimation

The authors discuss optimization of functions with uncertainty by means of genetic algorithms (GAs). In practical application of such GAs, the possible number of fitness evaluations is quite limited. The authors have proposed a GA utilizing history of search (Memory-based Fitness Evaluation GA: MFEGA) so as to reduce the number of fitness evaluations for such applications of GAs. However, it is also found that the MFEGA faces difficulty when the optimum resides outside of the region where population covers because the MFEGA uses the history of search for estimation of fitness values. The authors propose the tested-MFEGA, an extension of the MFEGA that tests validity of the estimated fitness value so as to overcome the aforesaid problem. Numerical experiments show that the proposed method outperforms a conventional GA of sampling fitness values several times even when the original MFEGA fails.