Genetic Algorithms

Genetic algorithms are a meta-heuristic, a strategy, to deal with complex optimisation problems that are infeasible to tackle otherwise. Together with ant systems they are the best known approaches to NP-hard problems like the project scheduling problem.

To use genetic algorithms you need a model or representation structure (called genome) in which you can express every possible solution of any problem instance, and a decoding function that transforms a solution in this form (called genotype) into an actual solution (called a phenotype), e.g. start times for each task in a project. You also need a scoring function that creates comparable fitness scores for a solution. The basic algorithm then creates a population of many more or less random solutions, and continues to create new solutions from the existing ones, removing bad solutions from the population in favor of solutions with better scores. To create new solutions, existing solutions are combined and then mutated with genome-specific operators.

The whole process mimics evolution in nature and is capable of optimizing independent features in the genome concurrently, while also being able to optimize linked features. The algorithm is also non-deterministic which might look weird to some, but is not a problem in reality.

While the basic approach is quite simple, there are many interesting problems when applying genetic algorithms: first of all you need to find a good representation that makes it simple (=fast) to derive a phenotype, but at the same type creates a compact and smooth hyperplane in the solution space. Then you need good crossover and mutation operators that combine correct mutation distance with simplicity. The whole algorithm has quite some parameters (e.g. mutation rates) that need to be optimized, which is a quite difficult problem in itself that needs a lot of computing power to tackle. Finally there are many improvements, e.g. improved start populations and different decoding functions that are selected by the genotype) that can be used to improve the stability and performance of the algorithm.

Overall, genetic algorithms are probably the best strategy to deal with the project scheduling problem, but implementing them in an efficient manner means tackling a number of engineering problems. We are confident that LibRCPS does quite well here.