451Re: Queens Problem and genetic algorithm
- Dec 26, 2004Our 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 firstname.lastname@example.org, Ivan Villanueva <ivan@a...> wrote:
> I am implementing a Java library with the algorithms of the book.
> I was stuck with the genetic algorithm applied to the queens
> Populations fitness average went better and better and then worse
> worse. I thought it was a bug in my program, but after one day of
> experiments I have come to the conclusion that the queens problem
is a bad
> example for genetic algorithms , because when the parents have a
> heuristic, most of the children have a bad one. Here the output of
> experiment with 16-queens. A good heuristic is just one where 5 or
> with attacking queens. Any comments would be greatly appreciated.
> Creates 2000 random complete queens states and compares their
> 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
> Better children than parents: 110
> Worse children than parents: 890
> Ivan Villanueva.
- << Previous post in topic