Population Scalability Analysis of Abstract Population-based Random Search: I. Spectral Radius
Tianshi Chen, Jun He · arXiv (Cornell University) · 2012
Population-based Random Search (RS) algorithms, such as Evolutionary Algorithms (EAs), Ant Colony Optimization (ACO), Artificial Immune Systems (AIS) and Particle Swarm Optimization (PSO), have been widely applied to solving discrete optimization problems. A common belief in this area is that the performance of a population-based RS algorithm may improve if increasing its population size. The term of population scalability is used to describe the relationship between the performance of RS algorithms and their population size. Although understanding population scalability is important to design efficient RS algorithms, there exist few theoretical results about population scalability so far. Among those limited results, most of them belong to case studies, e.g. simple RS algorithms for simple problems. Different from them, the paper aims at providing a general study. A large family of RS algorithms, called ARS, has been investigated in the paper. The main contribution of this paper is to introduce a novel approach based on the fundamental matrix for analyzing population scalability. The performance of ARS is measured by a new index: spectral radius of the fundamental matrix. Through analyzing fundamental matrix associated with ARS, several general results have been proven: (1) increasing population size may increase population scalability; (2) no super linear scalability is available on any regular monotonic fitness landscape; (3) potential super linear scalability may exist on deceptive fitness landscapes; (4) “bridgeable point” and “diversity preservation” are two necessary conditions for super linear scalability