Solving Congress Timetabling with Genetic Algorithms and Adaptive Penalty Weights

摘要

When a Genetic Algorithm is used to tackle a constrained problem, it is necessary to set a penalty weight for each constraint type, so that, if the individual violates a given constraint it will be penalized accordingly. Traditionally, penalty weights remain static throughout the generations. This paper presents an approach to allow the adaptation of weights, where the penalty function takes feedback from the search process. Although, the idea is not new since other related approaches have been reported in the literature, the work presented here considers problems which contain several kinds of constraints. The method is successfully tested for the congress timetabling problem, a difficult problem and with many practical applications. Further analysis is presented to support the efficiency of the technique.