OT: Genetic Algorithm Recipe Bug Fix

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

  1. Sean Ross

    Sean Ross Guest

    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
    #1
    1. Advertising

  2. "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
    #2
    1. Advertising

  3. Sean Ross

    Sean Ross Guest

    "Anton Vredegoor" <> wrote in message
    news:beh8ad$dm0$...
    > 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
    #3
  4. Sean Ross

    Sean Ross Guest

    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
    #4
  5. 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:

    - start with a graph containing your clique problem
    - 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
    #5
  6. "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
    #6
  7. Sean Ross

    Andrew Dalke Guest

    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
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Xah Lee
    Replies:
    22
    Views:
    1,121
    Tim Roberts
    Mar 21, 2006
  2. SNAKE

    genetic algorithm

    SNAKE, Nov 4, 2003, in forum: C++
    Replies:
    2
    Views:
    338
    Allan Bruce
    Nov 4, 2003
  3. Xah Lee
    Replies:
    23
    Views:
    1,062
    Tim Roberts
    Mar 21, 2006
  4. Max

    Python Genetic Algorithm

    Max, Jan 27, 2008, in forum: Python
    Replies:
    14
    Views:
    1,083
    Wildemar Wildenburger
    Jan 28, 2008
  5. Xah Lee
    Replies:
    21
    Views:
    783
    Tim Roberts
    Mar 21, 2006
Loading...

Share This Page