# OT: Genetic Algorithm Recipe Bug Fix

Discussion in 'Python' started by Sean Ross, Jul 3, 2003.

1. ### Sean RossGuest

Hi. For anyone who has chosen to use my Genetic Algorithm recipe
(http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/199121), I'd like
to make you aware of a fairly serious oversite on my part - I left out the
division part of the standard deviation routine! That's been fixed on the
recipe page, but not on my personal web site - which will be done when I
post the new version I'm building for a study I'll be working on this fall.
I'd like to apologize for any difficulties and/or confusion this error may
have caused you. Thanks for your time.
Sean

Sean Ross, Jul 3, 2003

2. ### Anton VredegoorGuest

"Sean Ross" <> wrote:

>Hi. For anyone who has chosen to use my Genetic Algorithm recipe
>(http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/199121), I'd like
>to make you aware of a fairly serious oversite on my part - I left out the
>division part of the standard deviation routine! That's been fixed on the
>recipe page, but not on my personal web site - which will be done when I
>post the new version I'm building for a study I'll be working on this fall.

Importing the math module should also make a big difference for the
standard deviation routine Also stddev was only used by the
sigmascaling code, which was unreachable ... However, this is a very
nice module and I especially like the graphical TSP-solver that is in
the other package on your website.

I had been looking at it before but I failed to comprehend what you
were doing. However recently I developed a taste for Genetic
Algorithms as a side result of a thread on c.l.py here ("getting a
submatrix of all true").

In the process of finding a heuristic solution to the problem I came
to understand your module a bit better and I've also tinkered a bit
with it (minor changes) and I have produced a heuristic solution for
the submatrix problem. (it counts 59928 zero's, for insiders

If someone is interested it's here:

http://home.hccnet.nl/a.vredegoor/twomax

Anyway, maybe seeing your code used and *changed* will give enough of
a jolt to start working on it some more (which I would welcome

Anton

Anton Vredegoor, Jul 9, 2003

3. ### Sean RossGuest

"Anton Vredegoor" <> wrote in message
> Importing the math module should also make a big difference for the
> standard deviation routine Also stddev was only used by the
> sigmascaling code, which was unreachable ...

Thank you! I tacked on the fitness proportional stuff (roulette selection,
sigma scaling, expected values) on at the end to try to make the offering
more well-rounded, but I only did a couple of quick runs on one problem to
test. It looked fine, so I went ahead. I won't do that again - heh.

I had *no* idea that the sigma scaling was unreachable. I'm stunned and
embarassed. Thank you for making me aware the problem. I've done the
imported math module fix but, as for the sigma scaling, that will be
resolved in the newer version I'm working on: refactoring, renaming,
redesigning, reworking, that sort of thing. That version should be available
on my site sometime in early August. I already prefer it over the old
version, and I'm not quite finished

> However, this is a very
> nice module and I especially like the graphical TSP-solver that is in
> the other package on your website.
>

I'm glad you like it. I enjoyed watching it try to solve problems too.
Seeing where it would get stalled, trying to fiddle with the parameters to
make it work faster, better. Unfortunately, I did that display for a course,
so it was a matter of "just meet the deadline" code production. So, for
instance, the builtin scaling mechanisms are poorly designed - you can't
easily introduce a TSP problem that is different from the one provided and
have it display well. I don't know if I'll get around to fixing that soon -
I have other things to work on at the moment.

> I had been looking at it before but I failed to comprehend what you
> were doing.

There's a lot there. I'm a bit torn. I wanted to give people some examples
of operators that you may not find in other Genetic Algorithm code, but I
also think there's just a bit too much code there. When I post the next
version, I'm thinking I will just post a kernel of the system with a few
interesting tidbits, and then make the entire module available on my site.
That way it will be easier to read on the recipe page, and you can still get
more if you like.
We'll see.

> Anyway, maybe seeing your code used and *changed* will give enough of
> a jolt to start working on it some more (which I would welcome

Wait til you read the next version It has 3 whole classes! (heh). Thanks
again for making me aware of the bugs in this code. I was hoping people
might get some benefit from this code, and I'm glad that someone has. I'm
just sorry it's not better.

Sean Ross, Jul 9, 2003
4. ### Sean RossGuest

If you find further issues with the code please email me directly, I'd
prefer not to clutter this forum any more than I have already. I can be
reached at sross at connectmail.carleton.ca until January 2004.

Sean Ross, Jul 9, 2003
5. ### Anton VredegoorGuest

John Hunter <> wrote:

> Anton> http://home.hccnet.nl/a.vredegoor/twomax
>
>Hmm, now if I can only figure out what it all means

Me too. A friend of mine showed me that it's really a bipartite graph
optimization problem and that it's in NP because it's harder than the
maximum clique problem. Go figure

Anyway it seems to be possible to solve a maximum clique problem like
this:

- copy the graph and color the original nodes white and the nodes of
the copy black
- connect the two graphs by drawing lines between black and white
nodes that originate from the same node, and between black and white
nodes where the original graph had a line between the original nodes.
- make a matrix where the rows represent black nodes and the columns
represent white nodes and where a "1" is in the matrix if there's a
line between two nodes

You now should have a matrix with ones on the diagonal and which is
symmetric along the diagonal.

Solve the matrix using the code above (I did some back porting to
Python22)

Look at the columns that are kept, it should be the nodes of a maximum
clique.

Is anybody still with me? I'd like to know if anyone can reproduce
this result or understand my explanation (I'm just repeating what I
saw on the blackboard)

Anton

Anton Vredegoor, Jul 17, 2003
6. ### Anton VredegoorGuest

"Andrew Dalke" <> wrote:

>I haven't followed the thread, just pinged on 'maximum clique problem.'
>
>Does this help?
> http://starship.python.net/crew/dalke/clique/
>
>It's code I wrote years ago. Don't ask me any more questions about
>it .... unless you want to pay me for it.

It helps a little. Whether I want to pay you depends on what you eat.

Anton

Anton Vredegoor, Jul 18, 2003
7. ### Andrew DalkeGuest

Anton Vredegoor:
> It helps a little. Whether I want to pay you depends on what you eat.

Pizza, burgers, black beans&rice, BBQ, chili rellenos, breakfast burritos.
Huh. A lot of 'b'-based foods.

And for midsummer the last couple years - herring. But that's a special
occasion.

Andrew

Andrew Dalke, Jul 18, 2003