- View SourceHello,

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. - View SourceOur 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.