Constructing Timetabling Heuristics through Evolved Learning
Producing a conflict-free schedule is an example of a graph colouring problem. A substantial number of timetabling algorithms therefore employ graph colouring techniques to solve the underlying problem. The most popular technique is to order events by some heuristic. By tending to schedule the more difficult events first better quality timetables are usually constructed. This approach is known as heuristic sequencing.
We intend to introduce the concept of a difficulty function, which we define as a function mapping from a number of event characteristics to an integer providing a relative indication of how difficult that event will be to schedule effectively. As with heuristic sequencing this function will directly affect the order in which we schedule the events. The characteristics we can use as the basis of this function are based on the same heuristics used in sequencing methods.
The advantage of this approach over other methods is that we are not limited to simply choosing a single heuristic. Instead complex combinations of heuristics could be expressed. The internal operation of the function could weigh each of the characteristics according to its applicability to a given problem space. The difficulty function may need to be applied to a number of scheduling problem areas, thus creating the problem of suitability. Although suitable for one problem area, a given function may not be efficient or applicable to another. A different function may be required for each problem area encountered. One of the main problems associated with this is the amount of functions which may be required. Too few functions may result in a small set of generalised functions which do not completely apply to any of the problem areas. To specify exactly a complete set of specialised functions for each predicted problem area may be time-consuming and require specific user-knowledge of each. In addition, a mechanism would be required to choose the correct function for the current problem area, and it is not guaranteed that all potential problem areas are covered. A more practical solution would be implement a method that can create this function for a given problem space.
It would be interesting to employ the application of Neural Network technology to allow the characteristics of the problem area to be fed as input, with the difficulty value as output. The third method uses Genetic Programming to dynamically build the difficulty function itself:
- The Neural Network will be used initially as the difficulty function for a general construction algorithm, and then trained using carefully controlled test data and a specified set of problem characteristics as input.
- A second Neural Network will be built that will evolve to identify the best strategy for placing an event based on difficulty input function.
- This method will involve the application of Genetic Programming techniques to build the difficulty function. Again, this will involve some intelligent techniques for identifying relevant characteristics. For example, the difficulty function may be influenced by the resources available to a particular problem.
There are a number of potential benefits to these approaches:
- General difficulty functions for specific problem areas (such as examination timetabling or course timetabling) could be evolved using large ranges of training data.
- Specialised difficulty functions could be evolved for a particular organisation’s recurrent scheduling problem. Often a problem that occurs recurrently will have many of the same characteristics present in each occurrence. By evolving a difficulty function trained on previous occurrences of the problem we can then apply this to new future occurrences.
- Through the use of dithering on the evolved neural networks we can establish which characteristics are having the most effect on a problem space.