difficulty of linkage learning in estimation of distribution algorithms
This paper investigates the difficulty of linkage learning, an essential core, in EDAs. Specifically, it examines allelicpairwise independent functions including the parity, paritywith-trap, and Walsh-code functions. While the parity function was believed to be difficult for EDAs in previous work, our experiments indicate that it can be solved by CGA within a polynomial number of function evaluations to the problem size. Consequently, the apparently difficult paritywith-trap function can be easily solved by ECGA, even though the linkage model is incorrect. A convergence model for CGA on the parity function is also derived to verify and support the empirical findings. Finally, this paper proposes a socalled Walsh-code function, which is more difficult than the parity function. Although the proposed function does deceive the linkage-learning mechanism in most EDAs, EDAs are still able to solve it to some extent.
linkage learning estimation of distribution algorithms parity function genetic algorithms