Application Research Of Ant Algorithm In Combination Optimization Problems

Combination optimization problems are the key branch of the optimization problems. Combination optimizatin problems have a strong background of engineering, for example: Assignment Problem and Job-Shop Problem. Ant algorithm is a new appearing heuristic algorithm whose main characteristics are positive feedback, distributed computation and the use of a constructive greedy heuristic. Ant algorithm has already applied to solving Traveling Salesman Problem(TSP), which has attracted much attention recently. But because application research of ant algorithm still stands in the preliminary phase now, so in many fields of combination optimization, it's application research is blank. In this thesis, ant algorithm is applied to solving Assignment Problem and Job-Shop Problem, and pointing to the problems which are generated in the process of solving the problems, two improved ant algorithms are put forward, which are validated by many simulations and have good results. In the chapter 1, the thesis introduces the background of the research, and the design methods of heuristic approach. Then, the findings in the thesis are pointed out. In the chapter 2, the thesis introduces the outline of combination optimizatin problems and general solving approaches. In the chapter 3, the thesis introduces ant algorithm, including: bionic model of ant algorithm, ant system, and domestic and foreign status of research. In the chapter 4, ant algorithm is used to slove Assignment Problem. Because of local search ability of traditional ant algorithm the solution is easy to drop into local trap, so we added a chaos function disturb to the probability of choice, which can help the solution dap out local trap. The effectiveness of the algorithm is demonstrated by simulations. In the chapter 5, ant algorithm is used to slove Job-Shop Problem. Because of bad solutions got by using traditional heuristic information, we applied a new heuristic information named Earliest Allowed Porocessing Time(EAPT) to the algorithm and added a random information to the algorithm to avoid droping into local trap. The validity of the algorithm is demonstrated by many simulations. At last of the chapter, the relation between the simulation results and the two main parameters of the algorithm is further studied. In the chapter 6, we summarize this thesis and pointed out the problems, which are worthy of further research in the furure.