“Computer programs that evolve in ways that resemble natural selection can solve complex problems even their creators do not fully understand." - John Henry Holland
A few months ago, one of our users took on the fascinating task of implementing a genetic algorithm for optimization of job scheduling on CrowdProcess.
In a rather crude nutshell, genetic algorithms act the same way as nature: they take a group of candidate solutions and allow them to mutate, reproduce, and crossover. They then keep the best results (as defined by a fitness function) from one generation to the next. For more on genetic algorithms, we recommend this book by David E. Goldberg
Genetic algorithms are, by their nature, prone to parallelism. Going back to the parallel (no pun intended) with nature, the more candidates and generations you have, the more likely one of them with reach a better optimum. In nature, that optimum is simply the ability to survive.
So how does this overlap with a distributed computing platform made of thousands of web browsers? Extremely well, it turns out. The solution is to make each web browser an independent population, run each simulation in isolation from all others, and return the best result from each one. These can then be compared locally, and the “best of the best” chosen as the optimum.
In the case of the current problem, the objective was to find the order of jobs that gave the fastest completion time of the whole production cycle. The problem is essential for production management, as proper planning of jobs can lead to significant savings in production costs.
Applications such as telecommunications routing, financial forecasting or fleet logistics use Genetic algorithms, and we hope that the CrowdProcess platform can bring them into more common use.
The source code is on this link, and we encourage developers to try it out, and to run Genetic algorithms on thousands of web browsers in parallel.
Our heartfelt Thank You to Jerzy Duda from AGH University of Science and Technology in Krakow, Poland for providing us an initial code of GA and the test problems.
We are very interested in supporting developers who would like to run GA algorithms on CrowdProcess for their own use cases, and potentially add functionality such as editable fitness functions, and control over parameters such as population size, crossover type, mutation type, etc.
If you are working with GA algorithms feel free to get in touch.