A Simple Real-Coded Extended Compact Genetic Algorithm

This paper presents a simple real-coded estimation of distribution algorithm (EDA) design using x-ary extended compact genetic algorithm (_XECGA) and discretization methods. Specifically, the real-valued decision variables are mapped to discrete symbols of user-specified cardinality using discretization methods. The XECGA is then used to build the probabilistic model and to sample a new population based on the probabilistic model. The effect of alphabet cardinality and the selection pressure on the scalability of the real-coded ECGA (rECGA) method is investigated. The results show that the population size required by rECGA-to successfully solve a class of additively- separable problems-scales sub-quadratically with problem size and the number of function evaluations scales sub-cubically with problem size. The proposed rECGA is simple, making it amenable for further empirical and theoretical analysis. Moreover, the probabilistic models built in the proposed real- coded ECGA are readily interpretable and can be easily visualized. The proposed algorithm and the results presented in this paper are first step towards conducting a systematic analysis of real-coded EDAs and towards developing a design theory for development of scalable and robust real-coded EDAs.