Computer Science – Neural and Evolutionary Computing
Scientific paper
2011-08-23
Computer Science
Neural and Evolutionary Computing
27 pages
Scientific paper
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 on all fitness landscapes; and (5) "road through bridges" is a sufficient condition for super linear scalability.
Chen Tianshi
He Jun
No associations
LandOfFree
Population Scalability Analysis of Abstract Population-based Random Search: Spectral Radius does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Population Scalability Analysis of Abstract Population-based Random Search: Spectral Radius, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Population Scalability Analysis of Abstract Population-based Random Search: Spectral Radius will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-67039