Loading ...
Sorry, an error occurred while loading the content.

Queens Problem and genetic algorithm

Expand Messages
  • Ivan Villanueva
    Hello, I am implementing a Java library with the algorithms of the book. I was stuck with the genetic algorithm applied to the queens problem. Populations
    Message 1 of 2 , Dec 23, 2004
    View Source
    • 0 Attachment
      Hello,
      I am implementing a Java library with the algorithms of the book.
      I was stuck with the genetic algorithm applied to the queens problem.
      Populations fitness average went better and better and then worse and
      worse. I thought it was a bug in my program, but after one day of doing
      experiments I have come to the conclusion that the queens problem is a bad
      example for genetic algorithms , because when the parents have a good
      heuristic, most of the children have a bad one. Here the output of my
      experiment with 16-queens. A good heuristic is just one where 5 or less pairs
      with attacking queens. Any comments would be greatly appreciated.

      Creates 2000 random complete queens states and compares their fitness function
      with the fitness function of their children.

      Better children than parents: 649
      Worse children than parents: 351

      It seems GA is a good idea. Now we do the same with parents with a good fitness
      function
      Better children than parents: 110
      Worse children than parents: 890

      Ivan Villanueva.
    • guihergeek61
      Our class had a homework problem where doing the n-queens problem using GA was one option, though I chose to approach it as a CSP. I chose to avoid the GA
      Message 2 of 2 , Dec 26, 2004
      View Source
      • 0 Attachment
        Our class had a homework problem where doing the n-queens problem
        using GA was one option, though I chose to approach it as a CSP. I
        chose to avoid the GA approach for the very reason you stated - it
        seemed to me that there isn't a way to effectively combine the
        parents to create a child who is more fit. In researching this
        option, I considered adding various random mutations to the process,
        but in the end it seemed like you'd just end up with a very
        computationally expensive method of solving by randomly guessing the
        answer - more of a hill climbing search than a true GA approach.

        It's possible you could make the GA a little more problem specific -
        rather than creating two children by combining the
        parents "equally", you might try creating child #1 by taking Parent
        A, tossing out the queens that conflict, and replacing them with the
        equivalent queens from Parent B. Then create child #2 in similar
        fashion starting with Parent B. However, this seemed to be a pretty
        significant departure from the GA concept, and still didn't seem to
        guarantee that you'd converge on an answer. Maybe you would, I just
        didn't bother to try it.

        I also considered trying to modify the "matching" algorithm to
        improve the chances of pairing up "compatible" parents - those who
        had a better chance of producing fit offspring. The basic idea
        being that two unfit models who were unfit in ways that would offset
        might actually produce better offspring than better parents who were
        less compatible. To put it in poker terms, you're better off
        combining two hands which each contain 3 of a kind combining two
        hands which have straights or flushes.

        I hope this helps...

        --- In aima-talk@yahoogroups.com, Ivan Villanueva <ivan@a...> wrote:
        > Hello,
        > I am implementing a Java library with the algorithms of the book.
        > I was stuck with the genetic algorithm applied to the queens
        problem.
        > Populations fitness average went better and better and then worse
        and
        > worse. I thought it was a bug in my program, but after one day of
        doing
        > experiments I have come to the conclusion that the queens problem
        is a bad
        > example for genetic algorithms , because when the parents have a
        good
        > heuristic, most of the children have a bad one. Here the output of
        my
        > experiment with 16-queens. A good heuristic is just one where 5 or
        less pairs
        > with attacking queens. Any comments would be greatly appreciated.
        >
        > Creates 2000 random complete queens states and compares their
        fitness function
        > with the fitness function of their children.
        >
        > Better children than parents: 649
        > Worse children than parents: 351
        >
        > It seems GA is a good idea. Now we do the same with parents with a
        good fitness
        > function
        > Better children than parents: 110
        > Worse children than parents: 890
        >
        > Ivan Villanueva.
      Your message has been successfully submitted and would be delivered to recipients shortly.