Population Scalability Analysis of Abstract Population-based Random Search: I. Spectral Radius

H...............H

Show simple item record

dc.contributor.author Chen, Tianshi
dc.contributor.author He, Jun
dc.date.accessioned 2012-06-20T10:27:56Z
dc.date.available 2012-06-20T10:27:56Z
dc.date.issued 2012-06-20
dc.identifier.citation Chen , T & He , J 2012 , Population Scalability Analysis of Abstract Population-based Random Search: I. Spectral Radius . Unknown Publisher . en
dc.identifier.other PURE: 178928
dc.identifier.other dspace: 2160/7849
dc.identifier.uri http://hdl.handle.net/2160/7849
dc.description.abstract 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. en
dc.language.iso eng
dc.publisher Unknown Publisher
dc.title Population Scalability Analysis of Abstract Population-based Random Search: I. Spectral Radius en
dc.type Text en
dc.type.publicationtype Report (commissioned) en
dc.contributor.institution Department of Computer Science en


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search Cadair


Advanced Search

Browse

My Account