Self-adapting genetic algorithms with an application to project scheduling

This paper introduces a new general framework for genetic algorithms to solve a broad range of optimization problems. When designing a genetic algorithm, there may be several alternatives for a component such as crossover, mutation or decoding procedure, and it may be difficult to determine the best alternative (e.g., the best crossover strategy) a priori. For such cases, we suggest to include alternative components into the genetic algorithm. Indicating the component to be actually used in the genotype, this allows the genetic algorithm to adapt itself. That is, the genetic algorithm learns which of the alternative components is the most successful by means of genetic optimization. In order to demonstrate the potential of the self-adapting genetic algorithm concept, we apply it to the classical resource-constrained project scheduling problem (RCPSP). Motivated by previous computational studies as well as theoretical insight, we employ two different decoding procedures and leave the decision which of them to select to the evolution. The approach is further enhanced by a problem-specific local search extension. An in-depth computational experimental analysis shows that the self-adapting genetic algorithm approach is currently the most promising heuristic for the RCPSP.