How to use GA to slove the 8 - puzzle?
A GA is probably not the best choice for the 8-puzzle. In fact, it may be a poor choice. You could compose your chromosome as a series of moves (left, right, up, down), but this will very likely get stuck in cycles (left, right, left, right, left, ...) and will need measures to prevent such cycles.
Why have you chosen GAs? Some insight on your decision would be helpful.
-Kirk
Why have you chosen GAs? Some insight on your decision would be helpful.
-Kirk
I have an application with solves an 8-puzzle with Genetic Algorithms. Must be said, this is definately not the most effective or efficient way, but I just did it for fun.
If you want to solve the 8-puzzle (efficiently), you might want to look into A* (or even standard Backtracking will do). The way I coded it with a GA:
- You have a pool of chromosomes (30-50)
- Each chomosome has a number of genes (maximum number of moves you want to search).
- Each gene is a 2-bit value (1 0 for left, 0 1 for right etc...).
You either penalize chromosomes which contains illegal moves, or just ignore them. If you implement it the right way, it could be fast and would not get stuck in endless loops.
But then again, GA is not the optimal tool for this problem.
Edo
If you are looking for efficient solutions to the n-queens problem, you may want to look into constraint satisfaction problems (CSP).
Author
Thanks all for answer my question, if you all said that GA is not the optimal tool to slove the 8-puzzle, I agree with it. But I only want to make some thing interesting to show the GA. Do you have some wanderful advice?
The bin packing problem is usually a good start, or also known as the knapsack problem.
Given: You have a bag of a fixed volume or size and n items each with a specific volume/size and a value.
Problem: Which items would you put in the bag from the n items available tus to optimize the total value.
Solution: Binary coded GA
Given: You have a bag of a fixed volume or size and n items each with a specific volume/size and a value.
Problem: Which items would you put in the bag from the n items available tus to optimize the total value.
Solution: Binary coded GA
If it is just for learning purposes and for an interesting demo, edtorpedo's advice is likely your best option. IMHO
-Kirk
-Kirk
Quote:
Are there any interesting question like TSP sloved by AG will very efficiency?
Ehmmm... what?
The thing with GA is: you can not guarantee that a solution given by a GA is the optimal solution or even the most efficient. I think you should look into the workings of Genetic Algorithms a bit further and just start experimenting with a few simple problems.
Found a nice example once:
You have a rectangular area filled with random circles, all with different diameters.
Question: what is the largest circle (ie a circle having the largest radius) you can fit in to that area without overlapping other circles?
Start your Algorithms!
Edo
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
