I have came across my really old Genetic Algorithm code and thought I’d share it with you. The easiest way to understand GA is to think of it as a search function, a search for a way to get to a solution. Imagine you have a problem and you know the solution to it, but you don’t know how to get to that solution.
Genetic Algorithms have many applications; designing circuit boards, code breaking, finding the best route to travel etc... The traveling problem is, I guess, the easiest to define and is the most common application of GA.
Travelling Salesman Problem (TSP) is defined as follows: A salesman has to visit N number cities and the order in which he visits them is such that the total distance traveled is the minimum.
At the first glance, this is easy to solve. There are N! number of possible combinations, we can just go through them and find the best.
- 3 cities = 3! = 6 combinations
- 4 cities = 4! = 24
- 11 cities = 11! = 39 916 800
- 12 cities = 12! = 479 001 600
- 21 cities = 21! = 5.10909422 × 1019
If you have a CPU capable of analyzing one billion (1,000,000,000) combinations per second, analyzing 21! combinations would take you 21! / 86,400 (1 day = 86 400 seconds) = 5.91330349 × 1014 days. That’s a lot of days my friends. We can surely use GA to get it done :)
Download the source from http://machine.codeplex.com/ (requires XtraCharts to compile)
Let me know if you have any questions about Genetic Algorithms.
Cheers
Azret