Path: utzoo!censor!geac!torsqnt!lethe!yunexus!ists!helios.physics.utoronto.ca!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!decwrl!uunet!mcsun!ukc!edcastle!aighb
From: aighb@castle.ed.ac.uk (Geoffrey Ballinger)
Newsgroups: comp.ai.neural-nets
Subject: Re: Genetic algorithm computational complexity
Message-ID: <8772@castle.ed.ac.uk>
Date: 28 Feb 91 09:53:53 GMT
References: <3430025@hpwrce.HP.COM>
Organization: Edinburgh University
Lines: 20

In article <3430025@hpwrce.HP.COM> kingsley@hpwrce.HP.COM (Kingsley Morse) writes:
-Has anyone measured the computation complexity of genetic algorithms?
-For example, how rapidly does cpu time increase as the number of genes
-increases? Polynomially? Exponentially?

	I assume you mean the time complexity for one application of
reproduction - there is no sensible bound on the number of applications
by definition. This would be a function of both the size of the
chromosomes and the population size. The actual function is completely
dependent on the genetic operators being used but should certainly be
polynomial and if the GA is to be usefull a relatively small polynomial.
For Holland's original GA it would be something like
O(popsize*chromosize) assuming an oracle for producing random numbers,

				Geoff.
-- 
 Geoff Ballinger,                           EMAIL: Geoff@Ed.Ac.Uk
 Department of Artificial Intelligence,
 University of Edinburgh, 80 South Bridge,
 Edinburgh, Scotland.