A Simple Real-Coded Extended Compact Genetic Algorithm
L. Fossati, Pier Luca Lanzi, Kumara Sastry, David E. Goldberg, Osvaldo Gomez · 2007
This paper presents a simple real-coded estimation of distribution algorithm (EDA) design using χ-ary extended compact genetic algorithm (χECGA) and discretization methods. Specifically, the real-valued decision variables are mapped to discrete symbols of user-specified cardinality using discretization methods. The χECGA 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 additivelyseparable 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 realcoded 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