kingsley@hpwrce.HP.COM (Kingsley Morse) (02/26/91)
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?
aighb@castle.ed.ac.uk (Geoffrey Ballinger) (02/28/91)
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.mrh@camcon.co.uk (Mark Hughes) (03/01/91)
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? Without thinking too hard I suggest that for a large proportion of problems the dominant computational load will be the evaluation of the function being solved. Generating new solutions requires relatively little work. If this is valid, Holland's offers a theoretical basis for solution times which I believe is a reasonable guide for many practical problems. This theory predicts that for a search space of size N, a genetic algorithm will on average search the space the cube root of N times faster than an exhaustive search. For a binary coded chromosome, N = 2^L - 1 where L is the number of bits in your chromosome. The rest is left as an exercise for the reader :) Mark -- ---------------- Eml: mrh@camcon.co.uk | Mark Hughes | Tel: (int +44) (0)223 420024 Cambridge Consultants Ltd. |(Compware & CCL)| Fax: (int +44) (0)223 423373 Science Park, Milton Road, ---------------- Tlx: 81481 (CCL G) Cambridge, England CB4 2JB