Research And Application Of Ant Colony Optimization In Timetabling Problem

Timetabling problem is a typical combinatorial optimization and an uncertain scheduling problem. With the development of artificial intelligence technologies, people have had a strong need in automation solution for timetabling problem.Ant colony optimization derived from the field of swarm intelligence. It has a good global search capability, a wide range of applications in optimization problem.This thesis first extends ACO (Ant colony optimization) to solve the timetabling problem. Based on ACO and the theories of probability, statistics, timetabling algorithm based on ACO is given. Ant colony optimization and correlative key problems, such as individual enlighten information strategy, adaptive selection strategy, the max and the minimum information strategy and information-smoothing mechanism for handling, are studied and analyzed systematically in this thesis.First, after describing the biological theory and algorithm models of ACO theoretically, we conclude some improvement strategies, such as, information-update mechanism, group strategy and so on.Second, take the curriculum problem as an example, the mathematical description of the timetabling problem is proposed, and the bipartite graph model is given.Third, the method of how to solve the timetabling problem using ACO is discussed theoretically. Then the timetabling algorithm based on ACO is presented.At last, the timetabling algorithm based on ACO is applied to the curriculum problem. We analyze the algorithm and then get a good curriculum result.The results of research and application show us that the timetabling algorithm based on ACO is feasible. It broadens the methods of solving the timetabling problem. And it is efficient to research some key problems in information strategy and choice mechanism using the theories of probability, statistics and ACO. It popularizes the application of ACO.