Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!uunet!mcsun!ukc!acorn!camcon!mrh
From: mrh@camcon.co.uk (Mark Hughes)
Newsgroups: comp.ai.neural-nets
Subject: Re: Genetic algorithm computational complexity
Message-ID: <11462@titan.camcon.co.uk>
Date: 1 Mar 91 09:48:15 GMT
References: <3430025@hpwrce.HP.COM>
Organization: Cambridge Consultants Ltd., Cambridge, UK
Lines: 25

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