Domain knowledge and representation in Genetic Algorithms for real world scheduling problems
Ioannis T. Christou, Armand Zakarian · 2000
This paper discusses the issues that arise in the design and implementation of an industrial-strength evolutionary-based system for the opti-mization of the monthly work schedules for the pilots of Delta Air Lines. We detail the system’s multiple and often conflicting goals and rules, providing the background for understanding the problem. Then, we describe the algorithm that we use to solve it. One important difference of our approach from other commonly used GA im-plementations is our use of the GA as a feasibil-ity procedure: the first phase of our approach is responsible for building a very high quality par-tial solution based on the domain knowledge of the problem. The GA is responsible for com-pleting this solution, finding a feasible solution to the remaining problem. We illustrate the im-pact that the representation can have on over-all performance by comparing two implementa-tions of the same algorithm based on two “or-thogonal ” encodings of the problem at hand. The computational results show how with the help of hill climbing techniques in the evaluation func-tion (either as repair procedures or as part of a decoder function) we were able to successfully put the system into production. We also make computational comparisons with exact methods which show a clear, though unexpected, superi-ority of the GA against them. 1