Balancing heuristics (for timetable problem)

Question

I'm writing a genetic algorithm for generating timetables.

At the moment I'm using these two heuristics:

1. Number of holes between lectures in one day (related) (less holes -> bigger score)
2. Each hour has some value, so for each timetable I sum values for hours when lectures are on. (lectures at more appropriate hours -> bigger score)

I want to balance these two heuristics, so the algorithm wouldn't favor neither one. What would be the best way to achieve this?

Answer 1

A very simple approach would simply be to add the scores together. At the end of the day, you want a blended score that goes up when either independent score goes up. You could use multiplication as well (being wary of number overflows depending on the size of your scores). With either approach you could weight the individual scores, e.g.

total_score = 0.4 * hours_score + 0.7 * holes_score

You could even make the weights user-configurable.

Answer 2

1. Develop a scoring function to evaluate the quality of generated timetables. You have the idea for that in your two heuristics.

2. Generate some random timetable problems.

3. Choose some values to balance the two heuristics, generate solutions, and evaluate which ones look best (if you can't come up with a scoring function, then eyeball it).

4. choose a new set of balance weightings (i.e. around a neighborhood of the best choice from last time) and repeat