Exploiting Constraints as Background Knowledge for Genetic Algorithms: A Case-Study for Scheduling.
Jan Paredis · 1992
In this paper, we propose a general methodology for handling constraints in genetic algorithms (GAs). Our algorithm finds promising states in the search space of constrained optimization problems. Once these states are found, a more thorough process can explore the regions around them. We show how constraint programming techniques can be used to augment a genetic algorithm with domain specific knowledge. The constraints allow the GA to take into account the epistatic linkages in the problem. The constraints are exploited during the generation of the initial population, during the application of the genetic operators and during the calculation of the fitness value. We illustrate our approach within the context of job shop scheduling. Keywords: constraint satisfaction, epistatic problems, genetic algorithms, optimization, problem solving, (re)scheduling, state-space search. 1. INTRODUCTION This paper describes an algorithm which finds promising states in a search space for constrained o...