Cloud Computing Viewpoint
Genetic Cloud: Cloud Computing Is For Everyone Every Day
Genetic algorithms are very simple. They have only three steps.
By: Pavel Klimov
Feb. 1, 2010 07:55 AM
Cloud Computing provides almost unlimited resources. They are always available. The payment is only for usage time. The current article continues the series about new opportunities that become available to every person.
Do you play billiard? I do. I’m not a professional player. So I enjoy pocketing a ball accidentally. The ball’s going at the rebound from cushions, coming to the pocket; it almost stops with revolving, and … falls to the pocket. Such kind of a casual luck!
But I’m not sure the luck is here today. The coming manager doesn’t look like he simplifies my current work day.
“A task for you….”
To exclude all technical details, commercial secrets, and other things, the task can be presented as a known travelling salesman problem with 50 points there. Yes, the order of variant’s number is about 50! (10^64). The distance matrix is not static additionally. Even if I find the necessary library quickly it’ll take much time to include the task features there.
“When should it be ready?” I’m asking guardedly.
Ok, at least I’m motivated now.
There are a lot of methods to solve such a problem .
It would be great if the task could be solved by my minimal efforts. Even it takes a little bit more other resources, e.g. computing time. Sure! Indeed it can be solved in this way! A genetic algorithm is the simplest method that I can implement. But I will have to just wait for the result. Wasting of time! But I can use the cloud resources. It’ll save me time, and I will be able to play billiard during waiting.
Stage 1. Genetic Algorithm.
Genetic algorithms are very simple. They have only three steps (excluding an initialization): crossover, mutation, and selection.
The chromosome is a ring path starting from the first defined point and directed to the second defined point (to not duplicate the same ways during the search).
The implementation is:
The C# code is based on the European cities with the distance though the geographical coordinates.
So the algorithm is ready. Is the search not most effective? But I’m very effective. The code is ready quickly, even if it takes some additional time to calculate, the whole task will be finished quicker.
Stage 2. Cloud.
The genetic algorithm is still randomized method. It guaranties almost optimal solution and depends on parameters. I can increase the population size to improve the probability of the best result, but it will increase the calculation time. Or I can run several instances simultaneously and pickup the best result.
As I write on .NET, I prefer any other working tools also in the Visual Studio. So my cloud is also in the Studio. I use a free tool EC2Studio. It’s the most convenient tool for me to operate with the Amazon EC2 in the Visual Studio. Amazon EC2 provides computing resources when I need them. I choose the necessary AMI configuration and start an instance. After I finish using the instance, I terminate it. The payment is only for the used time.
The deploying is:
Perfect! I shut down a laptop soon and go to play billiard.
The picture shows 4 cloud instances and 1 locally run version (on Vista).
The best solution is 181.85 here (it’s on the slowest machine, but the genetic algorithm is random).
There are different configurations by software and hardware are available on EC2. My tests use small and large images (small images are on 32bit, large images are on 64bit). The competitive test result - the average time per one cycle (selection, mutation, and crossing over according to defined shares):
Taking into account 4th times prices difference between a small and large instance in EC2, a small instance is twice cheaper for this program (when the execution time is not critical).
The same day later.
Now I think almost all optimization tasks can be solved with two components: a cloud and a genetic algorithm.
Every problem leads to a good solution. Every cloud has a silver lining.
Reader Feedback: Page 1 of 1
Latest Cloud Developer Stories
Subscribe to the World's Most Powerful Newsletters
Subscribe to Our Rss Feeds & Get Your SYS-CON News Live!
SYS-CON Featured Whitepapers
Most Read This Week