Simulated Annealing with Dynamic Initial Temperatures for University Course Timetable Problem

摘要

This research proposes a dynamic initial temperature for Simulated Annealing (SA) to solve a problem of curriculum-based course timetabling. Initial temperature setting is an important factor that affects the performance of the SA where very high initial temperature will lead SA to accept any solution whilst the lower value leads SA to quickly trap in local optima which behaves as a descent heuristic. Unfortunately, different initial temperature is required for each instance to ensure that SA can perform well. Therefore, researchers propose a dynamic mechanism to initialize the initial temperatures according to some solutions for each instance. Given the feasible initial solution, the SA starts several iterations and calculates the deviations average where the deviation equals the difference between the current objective value and the new one. Using this average, the mechanism will decide the initial moderate temperature according to the SA acceptance criterion ratio that we examine in the extermination. A computational result shows the effectiveness of the proposed mechanism to dynamically initialize the initial temperature compared with the fixed initial temperatures.