## Queens Problem and genetic algorithm

Expand Messages
• 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
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.
• 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
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
> 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.