Hi all, I finished my GA solving slide puzzles. But I''m not content with the way it performs. Can somebody take a look at it and tell me which parameters I''ve set wrong? You can find the app here: home.conceptsfa.nl/~fredo/files/GAPuzzle.zip Thanks very much ! Edo

It may not be your parameters, but rather it may be the implementation. For example, what method of selection and replacement do you use? what is your crossover operator? what type(s) of mutation do you use? what is the nature of your fitness function?

I''ve run your program a number of times and it seems there are some problems. I set the genes to 50 assuming this is the maximum number of moves. The list box (bottom right) has 50 moves listed, but when I push "perform moves" it only moves about 30 times in the actual puzzle.

Next, I ran the program a number of times sequentially. So, I started with a particular puzzle, ran the app, clicked perform moves, ran the app again, etc. I checked the fitness each time and it improved every time until it found a solution. It took 4 runs total at 10000 generations per run. Theoretically, 50,000 generations should solve the puzzle, but the app won''t let me set that many generations.

More information will help.

-Kirk

Hi, Thanks for your evaluation. I thought I did everything right, but here is some more info:

Selection: parents: Roulette Wheel using fitness
children: Roulette Wheel using inverse fitness
Mutation: loop through every bit in childs'' chromosome, and inverse bit if random() < mutationRate (default = 0.01)
Crossover: if random() < crossoverRate (default = 0.75) then swap bits at random point in childs'' chromosome.
Nature fitness function: fitness is calculated by adding the number of moves needed for each number in puzzle to slide to its original place.

The reason why its doesn''t always perform the listed moves, is that it doesn''t perform moves that bump into a wall, it just skips that move.
I thought I set the max of generations to 25000. This can be altered easily by recompiling my app.

Thanks!

I''m still a bit confused. You mention selecting parents by roulette wheel using fitness and children by roulette using inverse fitness. Since you''re trying to minimize the fitness function you specified (Manhattan distance, I believe) this seems a bit reversed. Maybe I''m just misunderstanding.

Also, I''m assuming that by "children: roulette using inverse fitness" you mean that replacement is determined by this method.

One possible problem is that you potentially have a lot of non-coding genes present. For example, when I run the program with 50 genes, only 26 (or less) moves are displayed. Effectively this results in 24 (or more) genes present which do not have any effect on your puzzle. Once you use crossover, these non-coding genes will possibly confound your results. You might want to include a constraint that the chromosome does not contain any invalid moves.

I also noticed a high frequency of repetitive cycles (Up Down Up Down) which might be coming from the non-coding genes.

I''ll ponder a bit more on it and see if I can come up with something. Please let me know if you have any more info that might help my pondering.

-kirk

Your biggest problem appears to be your crossover operator. Crossover should not be applied as the swapping of randomly selected bits between the parent chromosomes. Instead, you should select one of the L-1 (where L is the chromosome length) sites between genes and simply swap the tails (all bits to the right of the site) between the two parents. Your crossover method appears to be a form of biased mutation, which would suffer from the usual problems of mutation-only searches (they perform a nice random walk but thats about it)!

Regards,

Timkin


Edited by - Timkin on January 6, 2002 7:42:37 PM

Timkin,

What about the non-productive genes that were mentioned? I thought maybe their presence was confounding the solution.

-Kirk

Judging from what I''ve read, I think it is a combination of both of those things: excess genes and your crossover function. To explain: if you have genes in which half are no move codes, then when you do a crossover, if you have good parent and a bad or medicore parent, you have a +50% chance of switch a move from the better parent with a no-move from the worse parent. this effectively reduces the fitttness of your best set of moves. And the best set of moves will always be weakened by the other solutions.

If you keep your current methods of crossover and excss genes, I recommend two things: elitism and greedy mutation. In elitism, you keep the best for the next generation. In greedy mutation, you only keep something mutated if it is better than before.

Certainly the genes that have bad moves as their allele values will slow down your search. The term that is appropriate here is ''hitchhiking''. These weak alleles can be carried along by stronger alleles and slow down your search. However, crossover will tend to break these correlations. There are some conditions under which crossover alone does not work to get rid of hitchhikers but I don''t believe you need to worry about those at this time.

Don''t be worried about bad moves being associated with good moves. This is the whole point of the GA... it will discern that these population members are sub-optimal and they will eventually die out via poor selection rates. In the worst case scenario the timeframe for this will be based on your mutation rate, however you can generally get better performance than that.

My best suggestion is change your crossover operator to the standard one (that I suggested in my earlier post) and see what sort of improvement you get. Then you might try some other strategies to get more speed improvements out of your algorithm. Just do one thing at a time though, so you know how each one affects your algorithms performance.

Hope this helps,

Timkin

Hi,

thanks for all the replies. About the crossover: I do use the standard crossover operator ! Like this:

parent1: 10101110110111010011001
parent2: 01010000100101100100001
get random point ^
child1: 1010111011011 + 1100100001
child2: 0101000010010 + 1010011001

I''m going to implement greedy mutation and elitism now, and see how that will work out.

Thanks,

Edo

My apologies, I must have misread one of your earlier posts. I thought you were swapping random bits between parents, rather than the tails.

My mistake.

Timkin