Brief theoretical background on fitness functions

Tablix uses a simple weighted sum to compute a fitness value of a timetable. This is implemented with a for loop in function table_fitness() in modsup.c. It looks like this in pseudo code:


FOR each partial fitness function defined by loaded modules DO
        CALL partial fitness function
        MULTIPLY the result with the weight of this module
        ADD the result to the total fitness of this timetable
DONE

Lower fitness value for a timetable means a better timetable. A perfect timetable that has no errors would have the fitness value equal to zero.

Each module usually defines one partial fitness function. This function in most cases returns the number of errors of a certain type in the timetable. There are some cases where this is not possible (for example when a module is calculating a dispersion of events). In that case the function should return lower values for better timetables. It is not mandatory that a timetable with fitness zero exists although it is desirable (a module can not be declared mandatory if its fitness function can never reach zero).

It is important that the return value of the partial fitness function depends only on one type of errors in the timetable. Because user can define which modules will be used by the kernel this enables her to customize the search for solution. By assigning different weight values to different modules she can assign more computational effort to solving a specific type of errors. This would not be possible if a fitness value depended on more than one type of errors. Experience also shows that partial fitness functions that are not orthogonal (if a value of one fitness function strongly affects the value of another) sometimes cause instability in the genetic algorithm.

Genetic algorithm gives best results if the fitness functions are continuous. This means that the fitness value should gradually decrease as the timetable gets better (has less errors). An example of the worst kind of a fitness function would be a function that returns zero for a perfect timetable and some fixed value for non-perfect ones