Sample Complexity of Real-Coded Evolutionary Algorithms

Jian Zhang, Xiaohui Yuan, and Bill P. Buckles

Researchers studying Evolutionary Algorithms and their applications have always been confronted with the sample complexity problem. The relationship between population size and global convergence is not clearly understood. Population size is usually chosen depending on researcher’s experience. In this paper, we study the population size using Probably Approximately Correct (PAC) learning theory. A ruggedness measure for fitness functions is defined. A sampling theorem that theoretically determines an appropriate population size towards effective convergence is proposed. Preliminary experiments show that the initial population of the proposed size provides good starting point(s) for searching the solution space and thus leads to finding global optima.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.