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

Re: Queens Problem and genetic algorithm

Expand Messages
  • 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 1 of 2 , Dec 26, 2004
    • 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.