Enhancement of Ant System Algorithm for Course Timetabling Problem
As a member of the NP Problem, an exact algorithm to solve the course scheduling problem is not available to date. It is believe that this kind of problem can not be solved by any deterministic algorithm except with the one that performs checking for all possible solution exhaustedly to find solutio...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | eng eng |
| Published: |
2009
|
| Subjects: | |
| Online Access: | https://etd.uum.edu.my/1525/1/Djasli_Djamarus.pdf https://etd.uum.edu.my/1525/2/1.Djasli_Djamarus.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | As a member of the NP Problem, an exact algorithm to solve the course scheduling problem is not available to date. It is believe that this kind of problem can not be solved by any deterministic algorithm except with the one that performs checking for all possible solution exhaustedly to find solutions that comply with all mandatory constraints. The running time of this algorithm is usually expressed as a
mathematical function that grows very fast with the increment of the input data size. For this kind of problem, researchers believe that it will be better to find an
approximate solution that can be delivered by a stochastic algorithm than waiting for an exact solution from the deterministic algorithm. In order to develop a new algorithm for the course scheduling problem, this research
follows the experimental research methodology that consist of problem analysis, designing algorithm, implementing algorithm as a computer program in order to examine the results, analyzing the results, and if necessary improving the algorithm by doing all those activities over and over again. This research starts with developing an algorithm based on original concept of Ant System Algorithm. As the requirement of the Ant System Algorithm, the problem is
modeled as a graph that can be used by the ant to deliver its pheromone. This graph consists of four types of vertices that construct the course schedule element. To
direct the ant in the journey, heuristic factors are developed by analyzing the characteristic of the course scheduling problem model. The ant uses this heuristic
factor to build its pheromone trail, where the number of pheromone laid on the edge indicates the preference level of the edge to be chosen. A Two-pass Ant System Algorithm that able to come up with the course schedule without violating any hard constraints has been proposed to cater for the course scheduling problem. The proposed algorithm incorporates a new pheromone update method that includes the negative value for the pheromone update, failure
anticipation, cluster computation and best fit event placement features. These features were tested in conjunction with the proposed Ant System Algorithm either
individually or in combination among the features. Results of the experiments that were conducted using various data sets showed that the proposed algorithm produced better course schedule solution than the Greedy Algorithm, Genetic Algorithm, and other variants of Ant System Algorithm. |
|---|