The Study And Implementation Of Optimizing University Course Timetabling Problem By Ant Colonies

Ant colony algorithms have been well studied all over the world. There are a lotof successful applications which prove that ACO algorithms are good solutions to mostof the Combinational Optimization Problems. This thesis studies how to apply ACOalgotrithm to the University Timetabling Problem(UCTP).On the basis of analyzing the properties of UCTP and the object of the prob-lem,a new computing model which combines with the max-min ant system(MMAS)algorithm is constructed. Compared with the original MMAS-UCTP, the new modeltakes more advantage of metaheuristic searching strategy and is enhanced with a newheuristic information which relies on the soft constraint violation(scv). The algorithmis implemented and tested on several problems with di?erent scales and the resultsshow that the new MMAS-UCTP can conveniently merge the new techniques, whichmay improves the solution's quality.It is well known that any metaheuristic algorithms should analyze the propertiesand the logic of the given problem before solving it. Here the thesis try to improve theMMAS-UCTP algorithm, i.e. to make the solutions constructed by the general ACOalgorithm feasible. Specifically speaking, the technique includes three parts named im-prove, shu?e and survive, the experiments show that the results are highly improved.Finally, the thesis parallelize the new MMAS-UCTP algorithm by parallelizingant's solution construction with sharing a common pheromone matrix. The experi-ments show that the final solution achieves good performance on both solution qualityand running time.