Skip to main content
gamedev.net
🔒 Locked

Genetic Algorithms Problems

Started by firefly2442 10 replies 900+ views
Original Post
firefly2442
firefly2442
Can people give me examples of types of problems that can be solved with Genetic Algorithms? So far I have: -The Traveling Salesman Problem. -Knapsack problem (have a bunch of objects and trying to fit the best ones in the knapsack) -Anything with Value Encoding. Are there any others that would be good? I''m doing a presentation for my discrete math class and I''m looking for some simple easy problems that I could demo. Thanks in advance. www.abyssgames.gotdns.com
http://www.rivetcode.com
RPGeezus
RPGeezus
You can use genetic algorithms to write a program for you. The program doesn''t have to be complicated (use state tables if you want).

Heres an example of something I used a GA for. It was used in a commercial product (for a while anyway) so it''s not totally theory.

The product would monitor a stream of video images and try to pick out people. The first indicator of this was motion. A function would return the ''changing'' parts between a series of frames (this wasn''t just a simple compare), and would run a series of checks on this data.

By analyzing the ''shape'' of the changes we hoped to programmatically decide if it was caused by a human or not. The inital problems of large lighting changes were easily overcome, and other types of motion (such as moving cars, buses, etc..) were filtered out without too much problem. Car headlights, however, became an issue.

This is where I decided to use a gentic algorithm. There was a lot of preprocessing going on, and the input data for the GA was made as simple as possible, In case your wondering, the input was a binary image with a constant width and height.

In the end, the Genetic Algorithm was able to block out over 80% of the false alarms. It took quite a long time to get a ''good'' solution, and required hundreds of data samples. 80% is not that great though, so I can''t say it was a total success. Still, thats 30% better than what we had (50% = random chance).


Cheers,
Will
Timkin
Timkin
Genetic Algorithms are appropriate on any blind search problem. How they perform though depends on the particular problem, the encoding scheme, the operators chosen and the parameters of the algorithm.

Cheers,

Timkin
firefly2442
firefly2442
Ok thanks. The link doesn''t seem to work Fup.

www.abyssgames.gotdns.com
http://www.rivetcode.com
firefly2442
firefly2442
Cool, now they both work. Thanks for the replies. I can see an "A" coming up for the project. hehe.

www.abyssgames.gotdns.com
http://www.rivetcode.com
Timkin
Timkin
quote:
Original post by fup
I just knew yuo would come along and say that Timkin


Well, it needed to be said! I''m surprised you didn''t get in before me!
Kylotan
Kylotan
quote:
Original post by firefly2442
Can people give me examples of types of problems that can be solved with Genetic Algorithms?

On a vague level, I''d think that GAs are especially suited to a problem space that has an output which is somewhat continuous, so that it is able to converge effectively. They''d also be best when used on an input space that is very large or not discrete (eg. if the input was a floating point number from 0.0 to 10.0 as opposed to an integer from 0 to 10), as discrete ranges might be more likely to suit some sort of exhaustive search better.

One example application I saw, although fairly abstract, was using GAs to find parameters for a polynomial to use when trying to approximate an existing function. Due to the curved nature of the output, the GA is able to converge upon a solution pretty effectively, and the input range of floating point numbers is too large to use a brute-force search on.



[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]
Timkin
Timkin
quote:
Original post by Kylotan
On a vague level, I''d think that GAs are especially suited to a problem space that has an output which is somewhat continuous, so that it is able to converge effectively.


Actually GAs perform equally well (if not better) on discrete data as they do on continuous data. As I said above, GAs are suited to Blind Search problems, which are problems where only function evaluations (no derivative information) are available to the search algorithm. This is certainly true of discrete domains.

The predominant issue with working in discrete domains is finding an appropriate mapping from the state space to the encoding space, which depends on the encoding scheme chosen.

Cheers,

Timkin
Kylotan
Kylotan
quote:
Original post by Timkin
Actually GAs perform equally well (if not better) on discrete data as they do on continuous data.

I didn''t explain myself very well, and was perhaps plain misleading now that I re-read what I posted. What I should have said is that trivial searches (eg. linear, or binary) are usually less suited to continuous data, and therefore GAs might be a common choice in such fields.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.