Learnability analysis of real-coded evolutionary algorithms

Evolutionary Algorithms is a school of algorithms inspired by biological evolutionary progress. Darwin's Principle of Evolution, Over many generations, random variation and nature selection shape the behaviors of individuals and species to fit the demands of their surroundings, is the intrinsic concept of Evolutionary Algorithms design. Despite of their practical success, more theoretical questions for better understanding on their mechanism are needed to be answered. For example, the convergence rate of EAs, the population sizing and genetic operator selection, are questions remaining open.;Population size is usually an empirical parameter when adjusting Evolutionary Algorithms. In this investigation, we study the population sizing problem from two new aspects: fitness landscapes' ruggedness and the Probably Approximately Correct (PAC) learning. The population size is therefore also referred to as sample complexity using the language of statistical learning. We characterize the population sizing as a learning process of the search space so that the Evolutionary Algorithms has high probability to globally optimize the fitness function. We define granularity, a ruggedness measure for fitness functions. We also derive a sampling theorem based on the epsilon-cover and the PAC learning theory, which theoretically determines a population size towards effective convergence for global optimization and multimodal optimization tasks.