Compact Genetic Algorithms using belief vectors

Abstract

Instead of the genetic operators such as crossover and mutation, compact Genetic Algorithms (cGAs) use a probability vector (PV) for the current population to reproduce offsprings of the next generation. Therefore, the original cGA can be easily implemented with no parameter tuning of the genetic operators and with reducing memory requirements. Many researchers have suggested their own schemes to improve the performance of the cGA, such as quality of solutions and convergence speed. However, these researches mainly have given fast convergence to the original cGA. They still have the premature convergence problem resulting in the low quality of solutions. Besides, the additional control parameters such as eta of ne-cGA are even required for several cGAs. We propose two new schemes, called cGABV (an acronym for cGA using belief vectors) and cGABVE (an acronym for cGABV with elitism), in order to improve the performance of conventional cGAs by maintaining the diversity of individuals. For this purpose, the proposed algorithms use a belief vector (BV) instead of a PV. Each element of the BV has a probability distribution with a mean and a variance, whereas each element of a PV has a singular probability value. Accordingly, the proposed BV enables to affect the performances by controlling the genetic diversity of each generation. In addition, we propose two variants of the proposed cGABV and cGABVE, Var1 and Var2, employing the entropy-driven parameter control scheme in order to avoid the difficulty of designing the control parameter (lambda). Experimental results show that the proposed variants of cGAs outperform the conventional cGAs. For investigating the diversity of each cGA, the entropy is employed and calculated at each generation. Finally, we discuss the effect of lambda related to the variances of the BV through the additional experiment. (C) 2010 Elsevier B.V. All rights reserved.