very simple Genetic Algorithm completed

[Matthew_WARREN at bnpparibas.com]

On Jan 31, 10:43 am, Matthew_WAR... at bnpparibas.com wrote:
> > Hi,
> >
> > I got some help with this from here, and there's been a little bit of
> > discussion around GA's recently, so thought I'd post up my likey slow
and
> > clunky version of a GA that in essence just 'evolves' a solution to
'make a

>
> Some improvement tips:
>
> 0. Tack this bit onto the end of quickga.py, and you wont have to
> write a separate routine to import quickga and invoke evolve():
>
>     if __name__ == "__main__":
>         evolve()

I hear you, but something I dont tend to do as I use pythons interactive
prompt a lot, and I like things not autorunning when I import them. I
normally add it in at the end of writing something.

> 1. Remove all calls to floatify, and instead start your program with:
>         from __future__ import division
> On my system this gained about 16% improvement.
>

I was sure there must be a nicer way of achieving that, thanks :)


>
> 2. Bugfix: In 2 places, change:
>         newgene=genes[randint(0,14)-1]
>  to
>         newgene=genes[randint(0,14-1)]
>
> randint(a,b) returns values from a to b inclusive, and genes is a list
> containing 14 elements (so you want subscripts from 0 to 13).  (Usingd
> subscripts from -1 to 13 will bias the selection of genes to use twice
> as many of the last item in the list, since both -1 and 13 will give
> that value.)
>
> Similarly, change:
>
>     s=rationalise_signs(''.join([ genes[randint(0,len(genes))-1] ...
> to:
>     s=rationalise_signs(''.join([ genes[randint(0,len(genes)-1)] ...
>

Doh! - I was assuming I would get 1-14, not 0-14 with randint. Brain slip.

>
> 3. Change mutate to build a list instead of a string.  Then use
> ''.join() at the end to convert the list into a single string return
> value.
>

Interesting. I knew string operations arent necesarilly the quickest but I
didnt think of lists as being any quicker because I'm sure I've read
somewhere pythons strings are treated like lists, and I assumed the
''.join() would undo any savings. I'll go read up on it :)

>
>
> (This was less of a speed improvement than I thought it would be, but
> IIRC, the optimization of successive string concatentions is only
> available when running Python on Windows. If you are running on Linux,
> this should have more benefit.)

It is windows.

>
>
> 4. Include psyco to cut execution time in half.  Put this at the top

I was doing this as your mail arrived :)

>
>
> 5. On a hunch that many of your individuals are the same string, I
> lifted the call to eval out of express() into a separate routine
> called evaluate(), and added a memoizing cache to skip the call to
> eval if the string had been eval'ed before - if so, the value is
> reported from the cache.  This chopped another 40% off the runtime.
>
> evalcache = {}
> def evaluate(s):
>     if s in evalcache:
>         ret = evalcache[s]
>     else:
>         ret = eval(s)
>         evalcache[s] = ret
>     return ret
>
> (A note on timing this code: since there are many calls to
> randomization methods, consistent timing requires an explicit call to
> random.seed() to ensure that a consistent set of random numbers is
> used.  Otherwise, the timing gets thrown off by the randomization,
> which sends the program down different paths.)

Thats great! not something I would have thought of, caching the eval
results. Simple and effective :)


>
>
> 6. This is another change that had little effect, but I'll at least
> put it out there (a leftover from an algorithmic optimization course I
> took ages ago).  Instead of:
>
>     fitness=abs(fitvalue-expression)
>
> try using:
>
>     fitness=(fitvalue-expression)*(fitvalue-expression)
>
I originally had this. I was seeing absoloutley huuge int's appear and
wondered if dealing with those in memory might slow things down. I'll try
it either way.


..timing the code. I was just puzzling over that, and yep a call to seed()
will fix it.


Thanks for the suggestions and hints, esp the cache idea.

Matt.





This message and any attachments (the "message") is
intended solely for the addressees and is confidential. 
If you receive this message in error, please delete it and 
immediately notify the sender. Any use not in accord with 
its purpose, any dissemination or disclosure, either whole 
or partial, is prohibited except formal approval. The internet
can not guarantee the integrity of this message. 
BNP PARIBAS (and its subsidiaries) shall (will) not 
therefore be liable for the message if modified. 
Do not print this message unless it is necessary,
consider the environment.

                ---------------------------------------------

Ce message et toutes les pieces jointes (ci-apres le 
"message") sont etablis a l'intention exclusive de ses 
destinataires et sont confidentiels. Si vous recevez ce 
message par erreur, merci de le detruire et d'en avertir 
immediatement l'expediteur. Toute utilisation de ce 
message non conforme a sa destination, toute diffusion 
ou toute publication, totale ou partielle, est interdite, sauf 
autorisation expresse. L'internet ne permettant pas 
d'assurer l'integrite de ce message, BNP PARIBAS (et ses
filiales) decline(nt) toute responsabilite au titre de ce 
message, dans l'hypothese ou il aurait ete modifie.
N'imprimez ce message que si necessaire,
pensez a l'environnement.