Scalability of Estimation of Distribution Algorithms On Allelic Pairwise Independent Functions
Date Issued
2009
Date
2009
Author(s)
Chen, Si-Cheng
Abstract
This thesis investigates the difficulty of linkage learning, an essential core, in EDAs. Specifically, it examines allelic-pairwise independent functions including the parity, parity-with-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 parity-with-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. Then the root cause of the different performances between different EDAs is also discussed. Finally, this thesis proposes a so-called 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.
Subjects
Genetic Algorithms
Linkage Learning
Estimation of Distribution Algorithms
Parity Function
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R96921065-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):79f974828ffa0e3017f522286dcfe7a3